- --- In primenumbers@yahoogroups.com, Alan Eliasen <eliasen@...> wrote:
> > understand how to compute 1234 * 5678 and that works well. What I

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

> > 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 result is then A*10000+(B-A-C)*100+C.

> The Toom-Cook implementation uses the efficient choices found by

To be honest, the evaluation proposed by Bodrato was slightly

> Marco Bodrato. See references below.

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);

da1 = a2.add(a0);

db1 = b2.add(b0);

- v1 = da1.add(a1).multiply(db1.add(b1));

- v2 = a2.shiftLeft(2).add(a1.shiftLeft(1)).add(a0).multiply(

- b2.shiftLeft(2).add(b1.shiftLeft(1)).add(b0));

vm1 = da1.subtract(a1).multiply(db1.subtract(b1));

+ da1 = da1.add(a1);

+ db1 = db1.add(b1);

+ v1 = da1.multiply(db1);

+ v2 = da1.add(a2).shiftLeft(1).subtract(a0).multiply(

+ db1.add(b2).shiftLeft(1).subtract(b0));

+ 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();

da1 = a2.add(a0);

- v1 = da1.add(a1).square();

- v2 = a2.shiftLeft(2).add(a1.shiftLeft(1)).add(a0).square();

vm1 = da1.subtract(a1).square();

+ da1 = da1.add(a1);

+ v1 = da1.square();

+ v2 = da1.add(a2).shiftLeft(1).subtract(a0).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

Yes, your code is really clean!

> relatively readable style built on existing operations without a lot of

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

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

Regards,

Giu - --- In primenumbers@yahoogroups.com, Alan Eliasen <eliasen@...> wrote:
>

faster,

> 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

<snip>

>

in a

> Perhaps it will give some concrete hints if you're stuck in

> implementation details. These patches are intended to be written

> 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

Cook

> haven't reviewed it yet. Augh.)

>

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

> Multiplication for Univariate and Multivariate Polynomials in

Madrid,

> Characteristic 2 and 0." by Marco BODRATO; In C.Carlet and B.Sunar,

> Eds., "WAIFI'07 proceedings", p. 116-133, LNCS #4547. Springer,

> Spain, June 21-22, 2007.

My thanks to Alan, through his pointers I was able to figure out what

>

> --

> Alan Eliasen | "Furious activity is no substitute

> eliasen@... | for understanding."

> http://futureboy.us/ | --H.H. Williams

>

logic I was missing and am now working through writing my own code.