multiplication of unequal sizes

Jason Moxham
Sat, 1 Feb 2003 12:35:20 +0000

On Monday 20 Jan 2003 11:33 pm, Kevin Ryde wrote:
> Jason Moxham <> writes:
> > so what splitting is optimal ?
> Some investigation would be good.  Make a basic Karatsuba that just
> calls the basecase for its recursions, then measure how it goes for
> combinations of x and y sizes, and with the split point selected at
> different places (between xsize/2 and ysize I guess).  Hopefully
> there's a pattern to where it's faster than the basecase, and what
> split is best.
> > and are there any referances to papers on this ?

I was surprised that such a basic problem remains largely unexplored ,=20
although in practice it may not affect running times for typical algorith=
ms .=20
Paul Z and co 's theoretically optimal kara case is good , although it=20
remains to be seen how it works in practice.

Anyway heres the latest version of my gmp-hack , which includes a recursi=
method for calculating low and high part multiplication , and a hack to=20
mpf_mul to use it. The mpf_mul hack is slower though , mostly due to very=
poor decisions made when doing the recursive split on unequal sizes and a=
larger than half-part is wanted.