# [plt-scheme] calculation time for 11.5.3

 From: Stephen Bloch (sbloch at adelphi.edu) Date: Thu Nov 6 17:19:02 EST 2008 Previous message: [plt-scheme] calculation time for 11.5.3 Next message: [plt-scheme] calculation time for 11.5.3 Messages sorted by: [date] [thread] [subject] [author]

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