Language Shootout

[David C. Ullrich]

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.

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.

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're hinting at something kinda like [*] but with clever
rearrangents that does give improvement, like that
Strassen(?) thing for matrix multiplcation?

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

Something else entirely?

???)



David C. Ullrich