"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.
david
More information about the gmp-devel
mailing list