"balanced" unbalanced toom22
Paul.Zimmermann at loria.fr
Thu Aug 7 15:23:26 CEST 2008
> 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.
More information about the gmp-devel