# [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
*>*
*>*
*>*
*