"balanced" unbalanced toom22
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