April 19, 2013 9:00 AM
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.
Posted by programmingpraxis
Categories: Exercises
Tags:
Mobile Site | Full Site
Get a free blog at WordPress.com Theme: WordPress Mobile Edition by Alex King.
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
By izidor on April 19, 2013 at 6:13 PM
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))
By OptimusPrime on April 20, 2013 at 3:46 PM
from itertools import count
def iroot(k, n):
….return next(x for x in count() if x**kn)
By eupraxia on April 22, 2013 at 1:25 PM
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)
By eupraxia on April 22, 2013 at 1:30 PM
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))
By eupraxia on April 22, 2013 at 1:41 PM
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.
By Jussi Piitulainen on April 22, 2013 at 3:06 PM
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.
By Jonathan on April 23, 2013 at 3:13 AM
def iroot(k, n):
x = float(n)**(1/float(k))
return int(x)
By Jeff on April 23, 2013 at 5:20 PM
#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);
}
By Shail Shah on May 4, 2013 at 10:37 AM
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)By David on September 26, 2013 at 9:00 PM