Loading ...
Sorry, an error occurred while loading the content.
 

Re: Help with recursion on a Karasuba algorithm

Expand Messages
  • gpicciotta
    ... 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);
      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
      > 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
    • Not Important
      ... 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,
        Madrid,
        > Spain, June 21-22, 2007.
        >
        > --
        > Alan Eliasen | "Furious activity is no substitute
        > eliasen@... | for understanding."
        > http://futureboy.us/ | --H.H. Williams
        >

        My thanks to Alan, through his pointers I was able to figure out what
        logic I was missing and am now working through writing my own code.
      Your message has been successfully submitted and would be delivered to recipients shortly.