"balanced" unbalanced toom22

David Harvey dmharvey at nyu.edu
Thu Aug 7 19:54:57 CEST 2008

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.


More information about the gmp-devel mailing list