multiplication of unequal sizes

[Jason Moxham]

On Monday 20 Jan 2003 11:33 pm, Kevin Ryde wrote:
> Jason Moxham <J.L.Moxham@maths.soton.ac.uk> 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=
ve=20
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=
=20
poor decisions made when doing the recursive split on unequal sizes and a=
=20
larger than half-part is wanted.

http://217.35.81.229/gmp/gmp_plus.html