[ create a new paste ] login | about

Project: programmingpraxis
Link: http://programmingpraxis.codepad.org/iyHozRKJ    [ raw code | output | fork ]

programmingpraxis - Scheme, pasted on Apr 18:
; integer roots

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

(display (iroot 3 124)) (newline)
(display (iroot 3 125)) (newline)
(display (iroot 3 215)) (newline)
(display (iroot 3 216)) (newline)

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

(display (iroot 3 124)) (newline)
(display (iroot 3 125)) (newline)
(display (iroot 3 215)) (newline)
(display (iroot 3 216)) (newline)


Output:
1
2
3
4
5
6
7
8
4
5
5
6
4
5
5
6


Create a new paste based on this one


Comments: