# "balanced" unbalanced toom22

Niels Möller nisse at lysator.liu.se
Thu Aug 7 19:43:40 CEST 2008

```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

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
```