GMP 4.3 multiplication performance

[Paul Zimmermann]

       Torbjörn,

> 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[10000][100000];
>   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.
> 
> Where?

he did send it to me. I will ask him whether he wants to share with the list.

Paul