[plt-scheme] calculation time for 11.5.3

On Nov 6, 2008, at 10:05 AM, I wrote:

> As long as you're using Peano numbers (whose only constructor is  
> add1), this is unavoidable.  You can do much better, of course, if  
> you use binary representation:
>
> ; A nat-num is either
> ; 0,
> ; 2n where n is a nat-num, or
> ; 2n+1 where n is a nat-num
>
> Note that this uses "multiplication", but only the restricted case  
> of multiplication by 2.  With this representation,
>
> add(n1, n2) takes O(max(log(n1), log(n2)) time
> mult(n1, n2) takes O(log(n1) * log(n2)) time (assuming you don't  
> start doing fast Fourier transforms!)
> raise(x, n) takes O(n*log(x)) time by the obvious algorithm, or
> O(log(n)*log(x)) time by a less-obvious but fairly straightforward  
> algorithm.
>
> Homework problem: define a data structure to represent natural  
> numbers in binary form (not using the built-in number type), and  
> define these functions on that data type.

I just tried this as an exercise, in ISL+lambda.  A binary-number is  
a list of 0's and 1's, with the least significant digit first.

 > fifty
(list 0 1 0 0 1 1)
 > (time (raise fifty four))
cpu time: 2 real time: 1 gc time: 0
(list 0 0 0 0 1 0 0 0 0 1 1 1 1 0 1 0 1 1 1 1 1 0 1)
 > (time (raise four fifty))
cpu time: 2 real time: 1 gc time: 0
(list [long list of digits] )
 > (time (raise fifty fifty))
cpu time: 240 real time: 243 gc time: 0
(list [even longer list of digits])

Not bad....


Stephen Bloch
sbloch at adelphi.edu