## Re: Help with recursion on a Karasuba algorithm

Expand Messages
• ... The correct way is to compute A=(12*56), B=(12+56)*(34+78), C=(34*78). The result is then A*10000+(B-A-C)*100+C. ... To be honest, the evaluation proposed
Message 1 of 5 , Sep 26, 2008
--- In primenumbers@yahoogroups.com, Alan Eliasen <eliasen@...> wrote:
> > understand how to compute 1234 * 5678 and that works well. What I
> > don't understand is how the recursion works if I try to break down
> > the problem into (12 * 34) * (56 * 78). The math just does not seem
> > to work.

The correct way is to compute A=(12*56), B=(12+56)*(34+78), C=(34*78).
The result is then A*10000+(B-A-C)*100+C.

> The Toom-Cook implementation uses the efficient choices found by
> Marco Bodrato. See references below.

To be honest, the evaluation proposed by Bodrato was slightly
different (using a few operation less).

Here is a small patch to your code.

---------------------8<---------------8<-----------------
--- BigInteger.java 2008-09-26 10:39:25.000000000 +0200
+++ BigIntegerMine.java 2008-09-26 10:43:06.000000000 +0200
@@ -1380,13 +1380,15 @@

BigInteger v0, v1, v2, vm1, vinf, t1, t2, tm1, da1, db1;

- v0 = a0.multiply(b0);
vm1 = da1.subtract(a1).multiply(db1.subtract(b1));
+ v1 = da1.multiply(db1);
+ v0 = a0.multiply(b0);
vinf = a2.multiply(b2);

/* The algorithm requires two divisions by 2 and one by 3.
@@ -1656,11 +1658,12 @@
a0 = getToomSlice(k, r, 2, len);
BigInteger v0, v1, v2, vm1, vinf, t1, t2, tm1, da1;

- v0 = a0.square();
vm1 = da1.subtract(a1).square();
+ v1 = da1.square();
+ v0 = a0.square();
vinf = a2.square();

/* The algorithm requires two divisions by 2 and one by 3.

---------------------8<---------------8<-----------------

> implementation details. These patches are intended to be written in a
> relatively readable style built on existing operations without a lot of

Yes, your code is really clean!

> See: http://bodrato.it/papers/#WAIFI2007 "Towards Optimal Toom-Cook

...and his page http://bodrato.it/toom.cook/ for further formulas.

Regards,
Giu
• ... faster, ... in a ... lot of ... intended ... easily ... algorithms ... (That is, ... Cook ... Madrid, ... My thanks to Alan, through his pointers I
Message 2 of 5 , Sep 26, 2008
--- In primenumbers@yahoogroups.com, Alan Eliasen <eliasen@...> wrote:
>
> Not Important wrote:
> > I've decided to use the Karasuba algorithm for multiplying large
> > numbers in the program I'm writing. I've understand FFT is
faster,

<snip>

>
> Perhaps it will give some concrete hints if you're stuck in
> implementation details. These patches are intended to be written
in a
> relatively readable style built on existing operations without a
lot of
> low-level bit-fiddling or optimization for special cases. It's
intended
> to be readily understood and checked so that the changes could be
easily
> reviewed and Java could get trustable asymptotically-faster
algorithms
> much sooner. Based on the delays at Sun, that didn't happen.
(That is,
> it's been over 6 months since I submitted the first patch, and they
> haven't reviewed it yet. Augh.)
>
> See: http://bodrato.it/papers/#WAIFI2007 "Towards Optimal Toom-
Cook
> Multiplication for Univariate and Multivariate Polynomials in
> Characteristic 2 and 0." by Marco BODRATO; In C.Carlet and B.Sunar,
> Eds., "WAIFI'07 proceedings", p. 116-133, LNCS #4547. Springer,