## Integer Roots

### April 19, 2013

We filled in a missing piece of the Standard Prelude in the previous exercise. In today’s exercise we fill in another missing piece, the integer root function: `iroot(k, n)`

returns the largest integer *x* such that *x ^{k}* does not exceed

*n*, assuming

*k*and

*n*are both positive integers. For example,

`iroot(3, 125)`

equals 5, because 5^{3}equals 125; likewise,

`iroot(3, 126)`

equals 5, but `iroot(3, 124)`

is 4, because 5^{3}is greater than 124.

Your task is to write the integer root function. When you are finished, you are welcome to read or run a suggested solution, or to post your own solution or discuss the exercise in the comments below.

A quick solution using power of 1/k in Haskell:

iroot :: (Floating b, Integral c, RealFrac b) => b -> b -> c

iroot k n = floor . exp $ 1/k * log n

def iroot(k,n):

capturelasti=0

for i in range(0,1000):

if pow(i,k) == n:

return(i);

if pow(i,k) n:

return(capturelasti)

#Tests

print(iroot(3,125))

print(iroot(3,126))

print(iroot(3,124))

print(iroot(6,124))

from itertools import count

def iroot(k, n):

….return next(x for x in count() if x**kn)

Ahem. The blog had edited my code?

from itertools import count

def iroot(k, n):

..return next(x for x in count() if x**kn)

Another try. The software doesn’t like less-than or greater-than signs?

from itertools import count

from operator import le, gt

def iroot(k, n):

..return next(x for x in count() if le(x**k, n) and gt((x+1)**k, n))

There’s a link to instructions on how to post source code in the red bar above.

The source code is embedded in HTML where < and > have to be written < and > (assuming I get this right :) or otherwise escaped.

Go Newton’s method! This is a Common Lisp one, not using any floating arithmetic.

It may have a bug – I don’t know if it always converges.

def iroot(k, n):

x = float(n)**(1/float(k))

return int(x)

#include

#include

#define e 2.718281828

main()

{

int x,y;

printf(“x,y\n”);

scanf(“%d %d”, &x,&y);

iroot(x,y);

}

void iroot(int m,int n)

{

float z;

z=(log(n))/m;

int root;

root=pow(e,z);

printf(“%d”,root);

}

Did in SmallTalk; the initial guess for Newton’s method is taken by calculating 2 ^ (floor(log2(n)) / k).