How fast can we multiply?

[Tim Peters]

[Christian Tismer]
> ...
> 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.

It's clear enough what happens with positive numbers, though <wink>:

m = 1L << 10000
n = m - 1
print m & n  # prints 0

Use "|" instead and you're golden.  But that takes time proportional to the
number of bits in the larger input, so-- again --we need to fix nbits.  Then

nx = nbits(x)
ny = nbits(y)
if nx == 0 or ny == 0:
    return 0

would be constant-time.

> Was happy that negatives went correct without special treatment.

Yup!  It's a delight.

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

It should be constant-time.

> ...
> 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?

Na, I think "little interest" is it.  Outside of crypto, prime-number fans,
and people studying Calendars from Hell <wink>, nobody cares about really
big ints.  The first two groups-- who care a lot --care *so* much they're
using hyper-optimized bigint pkgs anyway.  Andrew Kuchling's wrapping gmp
for Python is the most useful thing that's ever been done in this area.

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

Large dense matmult isn't very common.  Sing along:

Lemon tree, very pretty,
And de lemon flower is sweet.
But de fruit of de poor lemon,
Is impossible to eat.

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

Give me one bored programmer with a few weeks to spare, and you can keep a
whole web full of people who are interested <wink>.

> *** Hey Python, where are your ambitioned Math students? ***
>
> (did they wake up, finally?)
>
> waiting-for-the-beginning-to-show-up-ly y'rs  - chris

i'll-join-you-in-the-bar-ly y'rs  - tim