[plt-scheme] calculation time for 11.5.3

Stephen Bloch 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

I have used this definition, which I call "the binary definition of a 
natural number" (the definition given in HtDP I call "the unary 
definition") in my HtDP-based course for several years now. It comes in 
handy when doing modular exponentiation, which is an important component 
of the RSA encryption/decryption algorithms.

> 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.

Only if you count manipulation of large numbers in Scheme as taking 
constant time. I think technically we need to toss in another O(log n) 
factor for raise (not for modular exponentiation).

> 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.

Given as an exercise in my first-term CS course this term (an "advanced" 
course for the best students) and handled very nicely. This is a really 
good exercise for CS majors, as it foreshadows the algorithms they 
should see as part of their computer organization and design course.

And all of this is structurally recursive! --PR