"balanced" unbalanced toom22

[Niels Möller]

David Harvey <dmharvey at nyu.edu> writes:

> Similarly, if you start with 200x196 (to get rid of the odd/even
> issue) then after two levels of karatsuba it's
>
> 8*(50x50) + 1*(50x46)     vs     5*(50x50) + 4*(50x49).
>
> As in your example, these should be the same cost once you reach
> subquadratic territory. I think it's clear from these examples that
> if you start with something relatively balanced, it shouldn't really
> matter which approach you take (except for added overhead).

My intuition is that if you can gain in general by the balanced
unbalanced method, then you ought to win at least one multiplication
in these border cases. Let me say that again in a little more detail.

Let 0 <= r < 1 be the degree of unbalancedness, representing
multiplication n x (1-r) n. Consider the gain from the balanced
unbalanced method as a function g(r) (for some fixed n above the
Karatsuba threshold). If there is a gain, then I'd expect that

  g(r) > 0 for all 0 < r < 1/2.    (*)

But these examples show that g(e) = 0 for a small e > 0, if we measure
the gain in terms of the number of needed limb multiplications. This
kind of contradicts the statement (*) above.

Regards,
/Niels