multiplication of unequal sizes
14 Jan 2003 15:00:45 +0100
Paul.Zimmermann@loria.fr (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.