"balanced" unbalanced toom22

[David Harvey]

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.

david