# [plt-scheme] Integer-length

 From: Jens Axel Søgaard (jensaxel at soegaard.net) Date: Wed Mar 22 16:58:33 EST 2006 Previous message: [plt-scheme] Integer-length Next message: [plt-scheme] Integer-length Messages sorted by: [date] [thread] [subject] [author]

```Robby Findler wrote:
> At Wed, 22 Mar 2006 22:10:14 +0100, Jens Axel Søgaard wrote:
>>Philippe Meunier wrote:
>>>Joe Marshall wrote:

>>>>If you are only interested in numbers with a few bits, however, a
>>>>nested conditional will most likely be the fastest.
>>>
>>>For big numbers I'd go with Jacob's log-based solution.
>>>For small numbers I'd just precompute the answers, keep them in a
>>>vector, and use the input number as the vector's index.
>>
>>I think I have too many small numbers :-)
>
> Did you consider building a conditional of size log(10000) (presumably
> building it with a macro)?

Nope. But it turned out it was a good idea.

Below the "Big" test runs through all numbers from 1 to 1000000.
Here Jacob and Robby's are the fastest.

In the small tests the numbers from 1 to N is computed multiple
times. Here Robby's is the fastest, but my original suggestion
isn't too bad either.

The timings were done on a stock 301 with the dynamic
properties set to "No Debugging or profiling".

It would be interesting to hear the timings on the JIT version.

/Jens Axel

(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)))]))
(define jacob integer-length)

(define (integer-length n)
(define (iter i next length nextlength)
(if (> next n)
(if (= i 1)
1
(+ length (integer-length (quotient n i))))
(iter next (* next next) nextlength (+ nextlength nextlength))))
(iter 1 2 1 1))
(define joe integer-length)

(define (integer-length n)
(if (<= n 1)
1
(+ 1 (integer-length (arithmetic-shift n -1)))))
(define jens-axel integer-length)

;(map (lambda (n)
;         (sub1 (expt 2 n)))
;       (list 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16))
;(1 3 7 15
; 31 63 127 255
;
; 511 1023 2047 4095
; 8191 16383 32767 65535)

(define (integer-length n)
(if (<= n 65535)
(if (<= n 255)
(if (<= n 15)
(if (<= n 3)
(if (<= n 1)
1
2)
(if (<= n 7)
3
4))
(if (<= n 63)
(if (<= n 31)
5
6)
(if (<= n 127)
7
8)))
(if (<= n 4095)
(if (<= n 1023)
(if (<= n 511)
9
10)
(if (<= n 2047)
11
12))
(if (<= n 16383)
(if (<= n 8191)
13
14)
(if (<= n 32767)
15
16))))
(jacob n)))
(define robby integer-length)

;;;
;;; TEST
;;;

(define (test f n)
(if (zero? n)
#t
(begin
(f n)
(test f (sub1 n)))))

(define (timed-test f n)
(collect-garbage)
(time (test f n)))

'BIG-TEST

(define N 1000000)
'joe
(timed-test joe N)
'jens-axel
(timed-test jens-axel N)
'jacob
(timed-test jacob N)
'robby
(timed-test robby N)

(define (small-test f m n)
(if (= m 0)
#t
(begin
(test f n)
(small-test f (sub1 m) n))))

(define (timed-small-test f n)
(collect-garbage)
(time (small-test f (quotient 1000000 n) n)))

'SMALL-TEST-100
(define N 100)
'joe
(timed-small-test joe N)
'jens-axel
(timed-small-test jens-axel N)
'jacob
(timed-small-test jacob N)
'robby
(timed-small-test robby N)

'SMALL-TEST-500
(define N 500)
'joe
(timed-small-test joe N)
'jens-axel
(timed-small-test jens-axel N)
'jacob
(timed-small-test jacob N)
'robby
(timed-small-test robby N)

'SMALL-TEST-1000
(define N 1000)
'joe
(timed-small-test joe N)
'jens-axel
(timed-small-test jens-axel N)
'jacob
(timed-small-test jacob N)
'robby
(timed-small-test robby N)

'SMALL-TEST-10000
(define N 10000)
'joe
(timed-small-test joe N)
'jens-axel
(timed-small-test jens-axel N)
'jacob
(timed-small-test jacob N)
'robby
(timed-small-test robby N)

'SMALL-TEST-100000
(define N 100000)
'joe
(timed-small-test joe N)
'jens-axel
(timed-small-test jens-axel N)
'jacob
(timed-small-test jacob N)
'robby
(timed-small-test robby N)

(define (sanity-check n)
(if (= n N)
#t
(if (= (jens-axel n) (joe n) (jacob n) (robby n))
(sanity-check (+ n 1))
(list n (jens-axel n) (joe n) (jacob n) (robby n)))))
(sanity-check 1)

Welcome to DrScheme, version 301.
Language: Pretty Big (includes MrEd and Advanced Student) custom.
BIG-TEST
joe
cpu time: 2110 real time: 2110 gc time: 0
#t
jens-axel
cpu time: 1453 real time: 1453 gc time: 407
#t
jacob
cpu time: 1000 real time: 1015 gc time: 203
#t
robby
cpu time: 1094 real time: 1094 gc time: 203
#t
SMALL-TEST-100
joe
cpu time: 1422 real time: 1422 gc time: 0
#t
jens-axel
cpu time: 562 real time: 563 gc time: 0
#t
jacob
cpu time: 1000 real time: 1000 gc time: 203
#t
robby
cpu time: 390 real time: 391 gc time: 0
#t
SMALL-TEST-500
joe
cpu time: 1532 real time: 1531 gc time: 0
#t
jens-axel
cpu time: 562 real time: 563 gc time: 0
#t
jacob
cpu time: 1000 real time: 1000 gc time: 203
#t
robby
cpu time: 391 real time: 390 gc time: 0
#t
SMALL-TEST-1000
joe
cpu time: 1593 real time: 1594 gc time: 0
#t
jens-axel
cpu time: 563 real time: 562 gc time: 0
#t
jacob
cpu time: 1016 real time: 1015 gc time: 203
#t
robby
cpu time: 391 real time: 390 gc time: 0
#t
SMALL-TEST-10000
joe
cpu time: 1641 real time: 1641 gc time: 0
#t
jens-axel
cpu time: 563 real time: 562 gc time: 0
#t
jacob
cpu time: 1000 real time: 1000 gc time: 203
#t
robby
cpu time: 406 real time: 407 gc time: 0
#t
SMALL-TEST-100000
joe
cpu time: 1781 real time: 1781 gc time: 0
#t
jens-axel
cpu time: 563 real time: 562 gc time: 0
#t
jacob
cpu time: 1016 real time: 1015 gc time: 203
#t
robby
cpu time: 578 real time: 578 gc time: 0
#t
#t
>

```

 Posted on the users mailing list. Previous message: [plt-scheme] Integer-length Next message: [plt-scheme] Integer-length Messages sorted by: [date] [thread] [subject] [author]