Codelets for ToomN1 (for N=2, 3, 4, 6, 8) should be added and here's why. (Also: a significant non-triviality on where cut-off points should be).

[Rock Brentwood]

It may be possible to eliminate the need for a "basecase" (except for 1x1
limb multiplication, of course) by including codelets for Toom21, Toom31,
Toom41, Toom61, Toom81, etc. In many cases, the recursive decompositions
done through these codelets will end up falling *back* into the other
codelets! A method based on thresholding completely misses both of these
features.

I included an ASCII picture showing the cut-off points for multiplication
that uses Toom11 (O) Toom21 (.) and Toom22 (o). Hopefully the mailer will
not cut off the diagram.

In some places (:), a balance point between Toom21 and Toom22 is reached.
This optimum is taken over *all* splitting points for Toom21 and Toom22,
not just midpoints. This diagram is relatively invariant with respect to
changes in the cost ratio for addition versus multiplication. Generally it
only affects what the cutoff for Toom22 is, not where the thresold between
Toom21 and Toom22 lies.

You should run a dynamic programming algorithm to compile a table over all
of your codelets, just to see where the optimal splits occur.

For the cases examined here: all cases of Toom21 optimally cut off at the
largest power of 2 smaller than the digit size of the larger numeral. Many
cases of Toom22 optimally cut off at a power of 2 or places other than
expected; although I didn't indicate in the diagram below where it is.
There is some dependency on how the dataflow is carried out with the
recursion (particularly the moving back and forth between the numerals and
the temporary workspace) but it should not affect the results below
significantly. This is something I will try to check against your
implementations.

The pattern is fractal. The "seeds" of the islands in the diagram below all
grow to larger sizes, for each power of 2 size you scale the diagram up by.
This picture will get far more complex when the other Toom codelets are
added in

This should come out as a 128 x 128 table. You may need to run a script to
lay it out as such, if the e-mailer messes it up.

-- Rock Brentwood

O...............................................................................................................................
.o..............................................................................................................................
..oo..:.........................................................................................................................
..oo:...........................................................................................................................
...:oooo....:...................................................................................................................
....oooo:.......................................................................................................................
..:.ooooo.......................................................................................................................
....ooooo:......................................................................................................................
.....:ooooooooooo.......:.......................................................................................................
.......:ooooooooo.......:.......................................................................................................
........ooooooooo...............................................................................................................
........ooooooooo:..............................................................................................................
....:...oooooooooo..............................................................................................................
........oooooooooo:.............................................................................................................
........ooooooooooo.............................................................................................................
........ooooooooooo:............................................................................................................
........oooooooooooooooooooooooooo..............::...:....:.....................................................................
...........:oooooooooooooooooooooo..............::..............................................................................
.............:oooooooooooooooooooo..............:...............................................................................
...............:oooooooooooooooooo:.............................................................................................
................ooooooooooooooooooo.............................................................................................
................ooooooooooooooooooo.............:...............................................................................
................ooooooooooooooooooo.............................................................................................
................ooooooooooooooooooo:............................................................................................
........::......oooooooooooooooooooo............................................................................................
................oooooooooooooooooooo:...........:...............................................................................
................ooooooooooooooooooooo...........:...............................................................................
................ooooooooooooooooooooo:..........:...............................................................................
................oooooooooooooooooooooo..........................................................................................
................oooooooooooooooooooooo:.........................................................................................
................ooooooooooooooooooooooo.........................................................................................
................ooooooooooooooooooooooo:........................................................................................
................oooooooooooooooooooooooooooooooooooooooooooooooooooo............................::::.:...:::.....:::::::........
................oooooooooooooooooooooooooooooooooooooooooooooooooooo............................::..................:...........
...................:oooooooooooooooooooooooooooooooooooooooooooooooo............................:...............................
.......................:oooooooooooooooooooooooooooooooooooooooooooo:...........................:...............................
.........................:ooooooooooooooooooooooooooooooooooooooooooo...........................:...............................
...........................:ooooooooooooooooooooooooooooooooooooooooo...........................:...............................
.............................:ooooooooooooooooooooooooooooooooooooooo...........................:...............................
...............................:ooooooooooooooooooooooooooooooooooooo:..........................................................
................................oooooooooooooooooooooooooooooooooooooo..........................................................
................................oooooooooooooooooooooooooooooooooooooo..........................:...............................
................................oooooooooooooooooooooooooooooooooooooo..........................:...............................
................................oooooooooooooooooooooooooooooooooooooo:.........................:...............................
................................ooooooooooooooooooooooooooooooooooooooo.........................:...............................
................................ooooooooooooooooooooooooooooooooooooooo.........................................................
................................ooooooooooooooooooooooooooooooooooooooo.........................................................
................................ooooooooooooooooooooooooooooooooooooooo:........................................................
................:::..:...:::....oooooooooooooooooooooooooooooooooooooooo........................................................
................::..............oooooooooooooooooooooooooooooooooooooooo:.......................:...............................
................................ooooooooooooooooooooooooooooooooooooooooo.......................:...............................
................................ooooooooooooooooooooooooooooooooooooooooo:......................:...............................
................................oooooooooooooooooooooooooooooooooooooooooo......................::..............................
................:...............oooooooooooooooooooooooooooooooooooooooooo:.....o...............:...............................
................................ooooooooooooooooooooooooooooooooooooooooooo.....................:...............................
................................ooooooooooooooooooooooooooooooooooooooooooo:....................:...............................
................................oooooooooooooooooooooooooooooooooooooooooooo....................:...............................
................................oooooooooooooooooooooooooooooooooooooooooooo:...o...............................................
................:...............ooooooooooooooooooooooooooooooooooooooooooooo...o...............................................
................................ooooooooooooooooooooooooooooooooooooooooooooo:..o...............................................
................................oooooooooooooooooooooooooooooooooooooooooooooo..................................................
................................oooooooooooooooooooooooooooooooooooooooooooooo:.................................................
................................ooooooooooooooooooooooooooooooooooooooooooooooo.................................................
................................ooooooooooooooooooooooooooooooooooooooooooooooo:................................................
................................oooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooo
................................oooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooo
................................oooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooo
................................oooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooo
...................................:oooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooo
.......................................:oooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooo
...........................................:oooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooo
...............................................:oooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooo
.................................................:oooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooo
...................................................:oooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooo
.....................................................:oooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooo
.......................................................:oooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooo
.........................................................:oooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooo
...........................................................:oooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooo
.............................................................:oooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooo
...............................................................:oooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooo
.....................................................o...ooo....oooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooo
................................................................oooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooo
................................................................oooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooo
................................................................oooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooo
................................................................oooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooo
................................................................oooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooo
................................................................oooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooo
................................................................oooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooo
................................................................oooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooo
................................................................oooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooo
................................................................oooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooo
................................................................oooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooo
................................................................oooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooo
................................................................oooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooo
................................................................oooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooo
................................................................oooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooo
................................:::::::..::::....::::::::.......oooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooo
................................::..................:...........oooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooo
................................:...............................oooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooo
................................:...............................oooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooo
................................................................oooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooo
................................:...............................oooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooo
................................................................oooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooo
................................................................oooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooo
................................................................oooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooo
................................:...............................oooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooo
................................:...............................oooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooo
................................:...............................oooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooo
................................................................oooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooo
................................................................oooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooo
................................................................oooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooo
................................................................oooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooo
................................................................oooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooo
................................:...............................oooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooo
................................:...............................oooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooo
................................:...............................oooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooo
................................::..............................oooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooo
................................:...............................oooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooo
................................:...............................oooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooo
................................:...............................oooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooo
................................................................oooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooo
................................................................oooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooo
................................................................oooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooo
................................................................oooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooo
................................................................oooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooo
................................................................oooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooo
................................................................oooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooo
................................................................oooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooo