David C. Ullrich
ullrich at math.okstate.edu
Sat Jul 14 09:13:57 EDT 2001
On Fri, 13 Jul 2001 15:11:52 -0400, "Tim Peters" <tim.one at home.com>
>> 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
>> [*] (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...
>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
>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
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
More information about the Python-list