# [plt-scheme] calculation time for 11.5.3

 From: Prabhakar Ragde (plragde at uwaterloo.ca) Date: Thu Nov 6 19:17:28 EST 2008 Previous message: [plt-scheme] calculation time for 11.5.3 Next message: [plt-edu] Re: [plt-scheme] calculation time for 11.5.3 Messages sorted by: [date] [thread] [subject] [author]

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

```

 Posted on the users mailing list. Previous message: [plt-scheme] calculation time for 11.5.3 Next message: [plt-edu] Re: [plt-scheme] calculation time for 11.5.3 Messages sorted by: [date] [thread] [subject] [author]