Re: big number arithmetic

Thus spake Paul Zimmermann ([email protected]):
> > Don't.  Karatsuba starts to be useful (depending on the architecture) at
> > 1024 bit numbers and up.  Do the school method for smaller numbers, as
> > someone else already suggested.
> I do not agree. On a Pentium M, "make tune" in gmp-4.2.1 gives:

The point was: it's not useful at 128 bits. :-)

> #define MUL_KARATSUBA_THRESHOLD          22

> which means that Karatsuba is faster than the schoolbook method up from
> 22 words, i.e., 704 bits.

My hunch is that that's because gmp's schoolbook multiplication is not
very fast.  I haven't polished mine yet, but it's significantly faster
than even tomfastmath's one, which in turn beats gmp.

> PS: it's funny that after several years without any message, this list
> suddenly wakes up. I also recommend the gmp-discuss list.

:-)

Felix