# [plt-scheme] Integer-length

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