How fast can we multiply?

Christian Tismer tismer at appliedbiometrics.com
Mon Jul 19 14:13:56 EDT 1999


Tim Peters wrote:
> 
> [Christian Tismer, hiding from continuations <wink>]

Oh, just a break.

> > Version 0.2 is now 4 times faster at 100000 bits.
> 
> Factor of 5.7 on my machine.

And the cutoff should better be set to 5000, again better.

> > It is a well known fact that by some factorization, integer
> > multiplication's complexity can be brought from O(n**2) down to
> > O(n**1.5).
> 
> The exponent is actually log2(3) ~= 1.58.

I dumbhead thought of 4 mults -> 3 and just said 1.5 - but yes,
sure, sorry.

[Karatsuba, GMP,...]

> Right, GMP does do this.  There's a much faster method (O(n)) based on
> Fourier transforms, but it's much harder to code and I've only seen it used
> in David Bailey's MPFUN package (a highly optimized Fortran pkg for
> arbitrary-but-fixed precision float arithmetic + the std elementary
> functions).

Can you give me a pointer? What I know is O(n log n loglog n),
based on convolutions, but I may be 20 years behind state of the art.

[we agree that coding in Python leads to etter solutions]

> > ...
> > A function to obtain the bit length of a long would
> > be most helpful.
> 
> The lack of this has gotten unbearable, eh?

This is my old fault. If there is a good algorithm with a better Oh,
that's one thing. But then it hurts so much to see an unnecessary
constant factor left over. The counter (number of words) is even
part of the long number and cries to be used.

> > Some kind of split function as well.
> 
> That one is much weaker; unlike bit length, the obvious ways to split and
> join already have the right O() behavior.

Sure. I should stop thinking about it. Just so tempting
to have a functon to break a long into two peaces, at
a word boundary, no shifts... sigh. No, I resist [now].

> 
> > ...
> > (1) Aho/Hopcroft/Ullmann:
> >     "The Design and Analysis of Computer Algorithms"
> 
> Knuth Vol 2 is a better reference for fast integer mult, although it goes
> off the deep end on theoretical refinements of no practical value ("what if
> the number of bits is bigger than the number of electrons in the
> universe?").

I know, also the subject "how..." is from there. But they re-arranged
my office. I found the Knuth corner again five minutes ago.
Yes, there is also the O(n) thing, and I'm not so behind.

> >         if not val1 and val2:

> The test only succeeds when val1 == 0 and val2 != 0 -- not what you
> intended.  OTOH, it's debatable whether programs multiply by 0 often enough
> to pay back the cost of testing for it!

How could I forget the braces. Well, the "why" was in fact to save
time when my "max" is a bad guess.

...
> Need a fancier strategy when nbits(val1) and nbits(val2) are far apart.
> This strategy takes strong advantage of the special-case-for-0 test above
> <wink>, but can easily run 100s of times slower than the builtin mult; e.g.,
> change your test case to lambda x:x*5.

I was undecided what's best. Obviously you are right. The asymmetric
case has a small and a large side, it already doesn't suffer from
the quadratic "flesh". I see it.

Also I was tempted to use "&" on the numbers, in order to save
one nbits call. It was just unclear what happens with negative
numbers and dropped it. Was happy that negatives went correct without
special treatment.

> This is all the more reason to write in Python, though!  Much clumsier to
> handle imbalance in C.  In the meantime, using "min" instead of "max" to
> compute bitcount greatly speeds the worst cases, and doesn't hurt the best
> ones.

> > def nbits(x):
> >     """not clean, rather fast, inaccurate"""
> >     s=marshal.dumps(x)
> >     return abs(struct.unpack("i", s[1:5])[0])*15 -7

Yes it is ugly. I just needed to lower the break-even point,
since I was impatient for the result. :-)

[nbits with hex...]

brrr. I can't help it. This should really be a quick log2()
call, this seems quite natural to me.

> >       time=time.time
> 
> Not time.clock?

One of my very first scripts. Don't ask me, perhaps an old
Python/Win32 problem.

> > # the end ----------------------------------------------------
> 
> looks-more-like-the-beginning-to-me<wink>-ly y'rs  - tim

It was impressive for me to see that with an hour of
coding, I can outperform C in Python. (Actually is was some
more hours, since I didn't remember how, and undusted some books).
My intent was to encourage people to play with stuff like
this, and to see how it can continue. The last word btw. keeps
me busy enough :)

At the same time, the reacton of the list was a little
disappointing to me. There seems to be near to zero interest.
Is this the hot summer? Holidays? Bad title of my post?

Then I also had a look into NumPy and its matrix multiplication.
I stunned. Again no attempt to optimize big O. It could be done
with Python, the algorithms are known, the fruit is waiting
to be picked.

Challenge: I claim Python could be a competitor to Mathematica,
if only some people were interested.

*** Hey Python, where are your ambitioned Math students? ***

(did they wake up, finally?)

waiting-for-the-beginning-to-show-up-ly y'rs  - chris

-- 
Christian Tismer             :^)   <mailto:tismer at appliedbiometrics.com>
Applied Biometrics GmbH      :     Have a break! Take a ride on Python's
Kaiserin-Augusta-Allee 101   :    *Starship* http://starship.python.net
10553 Berlin                 :     PGP key -> http://wwwkeys.pgp.net
PGP Fingerprint       E182 71C7 1A9D 66E9 9D15  D3CC D4D7 93E2 1FAE F6DF
     we're tired of banana software - shipped green, ripens at home




More information about the Python-list mailing list