[plt-scheme] Integer-length

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
 >