# [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