"balanced" unbalanced toom22

David Harvey dmharvey at nyu.edu
Thu Aug 7 18:31:41 CEST 2008

On Aug 7, 2008, at 9:23 AM, Paul Zimmermann wrote:

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

Ha ha ha... that's very cute but kind of ridiculous. I guess the  
reason for this result is that if you recursed into karatsuba s  
times, the proportion of subproducts which are full n/2^s * n/2^s  
products approaches 1. (I think the proportion is exactly 1 - (2/3)^s.)

But this doesn't help much in reality, since we don't recurse s times  
for arbitrarily large s; we only recurse maybe once or twice.


More information about the gmp-devel mailing list