GMP 4.3 multiplication performance
Paul.Zimmermann at loria.fr
Tue Jun 2 16:55:26 CEST 2009
> The way we do that in GMP is typically to look at the smaller size (here
> called vn). It works reasonably well.
> But I am working on various refinements, without resorting to
> two-dimensional algorithm selection tables.
> The first thing is to separate THRESHOLD values for balanced and
> unbalanced multiplication; it turns out that the unbalanced cases
> typically should stay with an algorithm longer (i.e., for larger
> operands) than balanced cases.
this might indicate that the comparison might perhaps involve un+vn, not only
the smaller size vn.
> Yes, but that might be quite difficult to implement in practice:
> enum mul_algorithm choose;
> switch (choose[un][vn])
> case SCHOOLBOOK:
> case KARATSUBA:
> case TOOM32:
> Or do you have something less memory-hungry in mind? :-)
we might imagine that the tuning program might decompose the search space
in say 1000 regions at most, each one delimited with straight lines, and
then a few well-chosen comparison should be enough to find the right region.
Or you might decompose vn/un in say 10 slices, and have a unidimensional
threshold mechanism for each slice.
> Marco Bodrato did produce a corresponding graph some time ago.
he did send it to me. I will ask him whether he wants to share with the list.
More information about the gmp-devel