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

Advertisement

Pages: 1 2

### 10 Responses to “Integer Roots”

1. izidor said

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 ```

2. OptimusPrime said

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

3. eupraxia said

from itertools import count

def iroot(k, n):
….return next(x for x in count() if x**kn)

4. eupraxia said

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)

5. eupraxia said

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

6. Jussi Piitulainen said

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 &lt; and &gt; (assuming I get this right :) or otherwise escaped.

7. Jonathan said

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.

8. Jeff said

def iroot(k, n):
x = float(n)**(1/float(k))
return int(x)

9. Shail Shah said

#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);
}

10. David said

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