How fast can we multiply?

[Tim Peters]

[Ivan Van Laningham]
> Oh, bad title, most certainly!  ;-)  *I'm* interested!  I don't
> understand most of what you guys are talking about, but I can see that
> if I could afford to spend the time studying it I would be rewarded.

Here's the heart of it.  Suppose you want to multiply 10*A+B by 10*C+D,
where A, B, C, D are all in range(10).  The answer is

    100*A*C + 10*(A*D + B*C) + B*D

Multiplying by 100 or 10 is just tacking zeroes on the end, so that's cheap.
Adding is cheap too.  Multiplying is expensive (well, imagine you already
understood what follows so that A, B, C, D each had hundreds of digits
instead of one <wink>).

Now time for a trick:  consider (A+B)*(C+D).  That's A*C+A*D+B*C+B*D.  So
the answer above is the same as

    100*A*C + 10*((A+B)*(C+D)-A*C-B*D) + B*D

and there are only *three* unique products there instead of 4:  A*C,
(A+B)*(C+D), and B*D.  That means we can compute the product of two B-bit
numbers via 3 multiplications of B/2-bit numbers, plus some cheap stuff.
The same trick applies to the B/2-bit numbers, down & down.  In the end that
implies we can do multiplication in time proportional to B**log2(3) instead
of B**2.

The method Chris actually used computes (A-B)*(D-C) instead for obscure
technical reasons (history, plus that subtracting instead of adding reduces
the size of the multiplicands a little on average).

> On topic, though, doesn't Knuth include in his "How Fast can We
> Multiply?" section a discussion of using modular arithmetic to speed up
> multiplies by a pretty large factor?  Now, maybe I've misunderstood the
> discussion so far so badly that I missed your use of it, but I don't
> recall seeing anything about it.

We didn't mention it.  Python doesn't store numbers in modular form, so it's
not that interesting -- it's expensive to convert in to and out of modular
form.  If it kept them in modular form, then multiplication would be
essentially linear-time.  If you want that-- and can live with numbers in
modular form over long stretches of calculations --it's easy enough to write
a class to do that.

> I would be interested--just not competent!  But a Python version of
> Mathematica could indeed be a killer app.  (Or is that a killer rabbit?)

I thought Mayan calendar analysis was Python's killer app!

or-is-that-an-app-killer<wink>?-ly y'rs  - tim