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 xk does not exceed n, assuming k and n are both positive integers. For example, iroot(3, 125) equals 5, because 53 equals 125; likewise, iroot(3, 126) equals 5, but iroot(3, 124) is 4, because 53 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.
Programming Praxis 
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.
(defun ipow (n k) "Takes n to the kth power" (unless (and (integerp k) (not (minusp k))) (error "Power must be a non-negative integer")) (unless (and (integerp n) (not (minusp n))) (error "N must be a non-negative integer")) (case k (0 1) (1 n) (2 (* n n)) (t (if (evenp k) (ipow (* n n) (/ k 2)) (* n (ipow n (1- k))))))) (defun iroot (n &optional (k 2)) (unless (and (integerp n) (plusp n)) (error "N must be a positive integer")) (unless (and (integerp k) (plusp k)) (error "Power must be a positive integer")) (loop with 1-1/k = #M 1-1/k and k-1 = #M k-1 and 1/k = #M 1/k repeat 1000 for p = 0 then x and x = (floor n (* k k-1)) then (floor (+ (* 1-1/k x) (/ (* n 1/k) (ipow x k-1)))) ;do (format t "~A -> ~A~%" p x) until (or (= x p) (and (<= (ipow x k) n) (<= n (ipow (1+ x) k)))) finally (return x))) ; (iroot 10000 10); => 3 ; (iroot 10 2); => 3 ; (iroot 124 3) ; (iroot 125 3) ; (iroot 126 3)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).
Integer extend [ floorRoot: n [ |a x0 x y| a := self abs. x0 := 1 bitShift: a highBit // n. x := a // (x0 raisedTo: n-1) - x0 // n + x0. [ y := a // (x raisedTo: n-1) - x // n + x. x > y] whileTrue: [ x := y ]. ^ self > 0 ifTrue: [x] ifFalse: [n odd ifTrue: [x negated] ifFalse: [x i]]. ] ] GNU Smalltalk ready st> 1000 floorRoot: 2 31 st> 1000 floorRoot: 3 10 st> 1000 floorRoot: 4 5 st> -125 floorRoot: 3 -5 st> -25 floorRoot: 2 (0+5i)