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.

About these ads

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)
    

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s

Follow

Get every new post delivered to your Inbox.

Join 600 other followers

%d bloggers like this: