[ create a new paste ] login | about

Link: http://codepad.org/M5U3EZEv    [ raw code | fork ]

programmingpraxis - Scheme, pasted on May 4:
; integer logarithms

(define (ilog b n)
  (if (zero? n) -1
    (+ (ilog b (quotient n b)) 1)))

(define (ilog-new b n)
  (let loop1 ((lo 0) (b^lo 1) (hi 1) (b^hi b))
    (if (< b^hi n) (loop1 hi b^hi (* hi 2) (* b^hi b^hi))
      (let loop2 ((lo lo) (b^lo b^lo) (hi hi) (b^hi b^hi))
        (if (<= (- hi lo) 1) (if (= b^hi n) hi lo)
          (let* ((mid (quotient (+ lo hi) 2))
                 (b^mid (* b^lo (expt b (- mid lo)))))
            (cond ((< n b^mid) (loop2 lo b^lo mid b^mid))
                  ((< b^mid n) (loop2 mid b^mid hi b^hi))
                  (else mid))))))))

(define-syntax assert
  (syntax-rules ()
    ((assert expr result)
      (if (not (equal? expr result))
          (for-each display `(
            #\newline "failed assertion:" #\newline
            expr #\newline "expected: " ,result
            #\newline "returned: " ,expr #\newline))))))

(do ((bs '(2 3 5 7) (cdr bs))) ((null? bs))
  (do ((n 1 (+ n 1))) ((= n 100000))
    (assert (ilog (car bs) n) (ilog-new (car bs) n))))


Output:
No errors or program output.


Create a new paste based on this one


Comments: