multiplication of unequal sizes
Sat, 1 Feb 2003 12:35:20 +0000
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=
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.