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