[plt-scheme] Integer-length

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

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

-jacob

Joe Marshall wrote:

>On 3/22/06, Jens Axel Søgaard <jensaxel at soegaard.net> wrote:
>  
>
>>Is there a faster way of doing this?
>>    
>>
>
>Yes.
>
>  
>
>>  ; integer-length : non-negative-integer -> natural-number
>>  ;   return the number of bits needed to represent n
>>  (define (integer-length n)
>>    (unless (and (integer? n) (not (negative? n)))
>>      (error "a non-negative integer was expected, got: " n))
>>    (if (<= n 1)
>>        1
>>        (+ 1 (integer-length (arithmetic-shift n -1)))))
>>
>>
>>  > (map integer-length
>>         (list 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16))
>>  (1 2 2 3 3 3 3 4 4 4 4 4 4 4 4 5)
>>    
>>
>
>(define (integer-length n)
>  (define (iter i next length nextlength)
>    (if (> next n)
>        (if (= i 1)
>            1
>            (+ length (integer-length (floor->exact (/ n i)))))
>        (iter next (* next next) nextlength (+ nextlength nextlength))))
>  (iter 1 2 1 1))
>
>As an example, (integer-length (expt 2 50000)) requires only 62
>multiplications and 6 divisions.
>
>If you are only interested in numbers with a few bits, however, a
>nested conditional will most likely be the fastest.
>
>--
>~jrm
>_________________________________________________
>  For list-related administrative tasks:
>  http://list.cs.brown.edu/mailman/listinfo/plt-scheme
>
>  
>