"balanced" unbalanced toom22

[Paul Zimmermann]

       David,

> Do you have any theoretical reason to think that it should win, or  
> should not win, for certain sizes (assuming mpn_mul handled the  
> unbalanced subproducts better)?

good question. Yes, I have a theoretical reason why it should not win in the
Karatsuba range. Let K2(n,m) be the cost of multiplying two numbers of n and m
limbs with the "centered" variant, with n/2 < m < n, and K(n) the cost of
Karatsuba for a product n x n. Then we have:

K2(n,m) = K(n/2) + 2 K2(n/2, m/2)

thus assuming K2(n,r*n) = c(r) K(n) for 1/2 < r < 1, this yields:

c(r) = 1/3 + 2/3 c(r)

which gives c(r) = 1. What is astonishing is that c(r) does not depend on r!
Thus whatever the value of r, this scheme has (theoretically) the same
complexity of a full n x n product using Karatsuba's algorithm.

Paul