## Integer Roots

### April 19, 2013

One solution first brackets the answer between lo and hi by repeatedly multiplying hi by 2 until n is between lo and hi, then uses binary search to compute the exact answer:

`(define (iroot k n)`

(let loop ((hi 1))

(if (< (expt hi k) n)

(loop (* hi 2))

(let loop ((lo (/ hi 2)) (hi hi))

(let* ((mid (quotient (+ lo hi) 2))

(mid^k (expt mid k)))

(cond ((<= (- hi lo) 1)

(if (= (expt hi k) n) hi lo))

((< mid^k n) (loop mid hi))

((< n mid^k) (loop lo mid))

(else mid)))))))

A different solution uses Newton’s method, which works perfectly well on integers:

`(define (iroot k n)`

(let ((k-1 (- k 1)))

(let loop ((u n) (s (+ n 1)))

(if (<= s u) s

(loop (quotient (+ (* k-1 u) (quotient n (expt u k-1))) k) u)))))

You can run the program at http://programmingpraxis.codepad.org/iyHozRKJ. This function will be added to the Standard Prelude the next time it is updated.

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).