Language Shootout
David C. Ullrich
ullrich at math.okstate.edu
Fri Jul 13 14:56:42 CEST 2001
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
More information about the Python-list
mailing list