This is the mail archive of the
libc-alpha@sourceware.org
mailing list for the glibc project.
Re: [PATCH] Another tweak to the multiplication algorithm
On Wed, Feb 13, 2013 at 05:57:54PM +0000, Joseph S. Myers wrote:
> The point of Karatsuba is not achieving a factor-2 reduction, but using
> recursion to reduce the time required for multiplying numbers of 2^n
> digits (n large enough for this to be worthwhile) from 4^n to 3^n. I
> don't see obvious recursion here....
Right, it's not really Karatsuba, just that it shares the basic step,
which is to reduce the equation:
x[i]*y[j] + x[j]*y[i]
to
(x[i] + x[j]) * (y[i] + y[j]) - (x[i]*y[i] + x[j]*y[i])
TBH, I didn't _try_ to implement Karatsuba at all. I figured out the
above by myself and tried to implement it as optimally as possible,
which is evident from the performance numbers. I read the wiki
article on Karatsuba later (since I remembered your suggestion) to see
if there was a quicker way and found the similarity, which is why I
decided to 'give credit' as it were.
I haven't thought about this deeply enough, but implementing recursion
could be non-trivial and might not be quicker than this.
So keeping Karatsuba aside, what do you think of the
algorithm/implementation in general? Do you think it is sound enough
to commit into master?
Siddhesh