[plt-scheme] Integer-length

From: Jens Axel Søgaard (jensaxel at soegaard.net)
Date: Wed Mar 22 16:09:40 EST 2006

Jacob Matthews wrote:
> This seems to beat both Jens' or Joe's implementation handily, at least 
> in drscheme 301.11  --
> (define (log2 n) (/ (log n) (log 2)))
> (define (integer-length n)
>    (cond
>      [(< n 0) (error 'integer-length 
 >                       "a non-negative integer was
 >                        expected, got: " n)]
>      [(= n 0) 1]
>      [else (add1 (floor (log2 n)))]))

This works fine in the range I am working with. I checked that
it returns the same results for all numbers up 1000000.

I dug up this snippet from math-repl:

   (define integer-log2
     (let ([log2 (log 2)])
       (lambda (n)
         (/ (log n) log2))))

   (define (big-log2 n)
     (define (loop n l)
       (if (<= n 1)
           (loop (quotient n 2) (add1 l))))
     (loop n 0))

So there might be a problem with very large numbers.

> The speedup is probably because mzscheme's log is implemented in C.


Jens Axel Søgaard

Posted on the users mailing list.