Language Shootout

[Emmanuel Jeandel]

In article <3b4eed03.298292 at nntp.sprynet.com>, David C. Ullrich wrote:
> On Wed, 11 Jul 2001 23:52:59 -0400, "Tim Peters" <tim.one at home.com>
> wrote:
> 
> [...]
>>
>>Here's another fun one:  you can also write a long-int multiplication
>>routine in Python that runs significantly faster than the builtin long *!
>>Hint:  recursion <wink>.
> 
> I give up, howdaya do that?
> 
> (When I read this I said aha, you're getting at something like 
> using
> 
> [*] (a*2**k+b)*(c*2**k+d) = a*c*2**(2*k) + (a*d+b*c)*2**k + b*d.
> 
Perhaps you mean : 
(a*2**k+b)*(c*2**k+d) = a*c*2**(2*k) + ((a+d)*(b+c) - a*c - b*d)*2**k + b*d.

You only have to compute 3 multiplications
  a*c
  b*d
  (a+d)*(b+c)

Then you can have an algorithm for multiplying a and b, if a and b 
are of the same size (len(a) = len(b)) of complexity
len(a)**(1.6)  
significantly better than len(a)**2
(len(a)*len(b) is *not* linear, rather quadratic)

Emmanuel