Language Shootout

[David C. Ullrich]

On 13 Jul 2001 17:09:55 GMT, ejeandel at ens-lyon.fr (Emmanuel Jeandel)
wrote:

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

Aha. No, that's not what I "meant", but it's exactly what I wondered
Tim meant (too early in the morning to try to make an English sentence
out of this). Thanks.

>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


David C. Ullrich