Language Shootout

[David C. Ullrich]

On Fri, 13 Jul 2001 15:11:52 -0400, "Tim Peters" <tim.one at home.com>
wrote:

>[Tim]
>> 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>.
>
>[David C. Ullrich]
>> 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.
>>
>> But when I think about it I don't see why that would give any
>> improvement - it _seems_ to me that vanilla long multiplication
>> should be quadratic (a*b takes time "len"(a) * "len"(b), where
>> "len" is the number of "digits".) If that's correct then using
>> [*] wouldn't improve things at all as far as I can see.
>
>Right, it's not "clever" enough:  that reduces an NxN mult to four
>(N/2)x(N/2) mults.  NxN takes N**2 "elementary" (1x1->2) mults, and
>(N/2)x(N/2) N**2/4, so four of the latter is no savings over the former.
>
>The trick is to reduce it to three (N/2)x(N/2) multiplications 

That would do it all right...

>(and
>recursively too for those in turn).  Then the overall complexity drops from
>O(N**2) to O(N**log2(3)) ~= O(N**1.58).
>
>> Can't decide:
>>
>> You're hinting at [*] and I'm analyzing it wrong? (Like
>> if vanilla multiplication is actually worse than quadratic
>> in the sense above then [*] will speed things up...)
>
>You'll figure it out <wink>. 

Thanks. (Too late, Emmanuel already gave it away.)

> "An answer" is spelled out in Knuth vol 2, or
>search for "Karatsuba multiplication" on the web.
>
>> You're hinting at something kinda like [*] but with clever
>> rearrangents that does give improvement, like that
>> Strassen(?) thing for matrix multiplcation?
>
>Yes, but not nearly *that* clever.
>
>> You're talking about using an FFT-based multiplication?
>> (One can certainly write a recursive FFT. But surely if
>> _this_ is what you meant then the hint would be "FFT"
>> instead of "recursion"...)
>
>I'm not sure you can write one of those *in Python* that's actually faster
>than the builtin long *, unless the longs are so large nobody would care.

Doesn't seem likely to me either, wasn't sure what you were getting
at. (Just for giggles I made a few Python FFT's yesterday; one of
them is only about 100 times slower than the same algorithm in
Object Pascal...)

>See
>
>    http://groups.yahoo.com/group/python-list/message/63188
>
>and followups for Christian Tismer's last known stab at implementing
>Karatsuba in Python.  It pays for ints short enough that somebody *might*
>care.  OTOH, anyone who cares a lot should be using one of the GMP wrappers
>(GMP also uses this trick, but in excruciatingly long-winded and
>platform-optimized C).

Right - wasn't meaning to suggest that this was the right solution
for serious work, just wanted to know what the algorithm in
question was. Lemme write this down: Karatsuba.



David C. Ullrich