[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