Language Shootout

[Tim Peters]

[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 (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>.  "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.
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).