How fast can we multiply?

[Christian Tismer]

Tim Peters wrote:
> 
> [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.

Waaah, did I say "&"? I used "|" or course.

> 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

But your "min" suggestion makes still a lot more sense to me.

> > Was happy that negatives went correct without special treatment.
> 
> Yup!  It's a delight.

My first attempt had special "-" treatment, until I recognized
that the shift and mask operations already do all we need. :-)

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

I see. The gmp makes very much sense. Until now.

On the other hand, if the hard coded "C" basic elements are
made fine and tiny, they give us nuts and bolts to build
the real algorithms on top.

We can therefore do what gmp does, not so much slower, but
readable, in Python. No porting, no nothing, just using.

And again I see a win for Python. It is able to show how
algorithms work, in a very clear way using its clean
syntax, and you can use the implementation of math directly
as highschool text. *And* it just works, and is fast.
Fells very very promising to me.

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

[lemon tree - sung]

It is just so easy. Factoring matrix multiplication
into its submatrices and then save (I think it was one)
multiplications - it would be a dlight to write in
Python. Not doing so appears to me as to know
quicksort, but using bubble sort all the time,
not just at break-even (10-20).
But I'm telling nothing new to you.

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

I'm bored enough, just the few weeks are missing. Sigh...

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

Reading the last posts, I think we aren't as alone as I thought.

As another little challenge:

Tim already mentioned Jurjen N.E. Bos' high precision math
library. It is in Python's contrib site.
I have the strong impression that it was not used by anybody
since a year now. python.org fails also to advertize it.

It could need a little rework, to make use of 1.5.2's features.
And if someone marries it with a fast multiplication, that
could make a neat tool.

If I were a student, I would propose my advisor to let me do such
things as my semester homework. What a delight :-)

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