multiplication of unequal sizes

Torbjorn Granlund
14 Jan 2003 15:00:45 +0100 (Paul Zimmermann) writes:
  I think only the smallest size should be compared to the threshold,
  at least up to the Toom-Cook range.
Indeed.  But perhaps not exactly...

Both Karatsuba and Toom use have this structure:

add/subtract U pieces
add/subtract V pieces
recursively multiply U pieces and V pieces forming W pieces
add/subtract/combine W pieces

When multiplying numbers with U being twice as many digits
as V, we could avoid doing "add/subtract V pieces" twice.
That would theoretically make the threshold for this lower
than when multiplying numbers of the same size.