"balanced" unbalanced toom22

[David Harvey]

On Aug 7, 2008, at 1:43 PM, Niels Möller wrote:

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

Hmmmm. Suppose n is fixed. It's conceivable to me that g(r) = 0 for  
all r in some interval 0 < r < s (where s is somewhat smaller than  
1/2), but that when you pass the threshold s, a different algorithm  
choice is made at a lower recursion level (because of different  
unbalancedness at that lower level), which then causes g(r) > 0 (or  
maybe g(r) < 0!) for r > s.

david