CODEWITHSUNDEEP
javarecursionmultiplicationinfinite
tudor balus
tudor balus

Reputation: 149

Karatsuba multiplication in Java, infinite recursion

I'm doing my best to do a Karatsuba implementation in Java and I'm failing miserably. Can some1 please take a look at my code and tell me what the hell I'm doing wrong? I've been banging my head against this and Google-ing like crazy and found nothing to get me out. I just don't see what the friggin' problem is!

Here ya go:

   Random rand = new Random();
   int lenght = 200000;
   int lenght1 = 200000;
   BigInteger value = new BigInteger(lenght, rand);
   BigInteger value1 = new BigInteger(lenght1, rand);

   doTheMath(lenght, lenght1, value, value1);

   private BigInteger doTheMath(int len, int len1, BigInteger var, BigInteger var1)
   {
    // A = A1*alpha + A0; where alpha is a suitable power of the radix
    int alpha = 0;
    BigInteger Z0 = null, Z1 = null, Z2 = null, result = null, A1 = null, A0 = null, B1 = null, B0 = null;
    int nTemp = 0, nTemp1 = 0, nLenght = 0, nLenght1 = 0;


    // we chose base 10 as our base
    if(len > len1)
       {alpha = (int) Math.pow(10, len1/2);}
    else if(len <= len)
       {alpha = (int) Math.pow(10, len/2);}
    String converter = "" + alpha;

    // we calculate A1 and B1 respectively
    A1 = var.divide(new BigInteger(converter));
    B1 =  var1.divide(new BigInteger(converter));

    // we calculate A0 and B0 respectively
    // the formula used: A0 = A - (A1 * alpha)
    A0 = var.subtract(A1.multiply(new BigInteger(converter)));
    // the formula used: B0 = B - (B1 * alpha)
    B0 = var1.subtract(B1.multiply(new BigInteger(converter)));

    // Formulas:
    // A*B = (A1*alpha+A0)*(B1*alpha+B0) = Z2*alpha^2+Z1*alpha+Z0
    // Z2 = A1*B1
    // Z1 = (A1+A0)*(B1+B0)-Z2-Z0
    // Z0 = A0*B0

    // recursively calculate the values of Z2, Z1 and Z0
    if((A1.bitLength() >= 70000) || (A0.bitLength() >= 70000) || (B1.bitLength() >= 70000) || (B0.bitLength() >= 70000))
        {
         Z2 = doTheMath(A1.bitLength(), B1.bitLength(), A1, B1);             
         Z0 = doTheMath(A0.bitLength(), B0.bitLength(), A0, B0);
         Z1 = doTheMath(A1.bitLength(), B1.bitLength(), A1.add(A0), B1.add(B0)).subtract(Z2).subtract(Z0);
        }
    else    // if the length of the recursive operands that need multiplying is smaller than 100000 then do it normally, not recursively
        {
         Z2 = A1.multiply(B1);
         Z0 = A0.multiply(B0);
         Z1 = A1.add(A0).multiply(B1.add(B0)).subtract(Z2).subtract(Z0);
        }

    //result = Z2 * Math.pow(alpha, 2)+ Z1 * alpha + Z0;
    result = Z2.multiply(new BigInteger(""+(int) Math.pow(alpha, 2))).add(Z1.multiply(new BigInteger(converter))).add(Z0);

    return result;
  }

I know there are implementations out there which I can use to inspire me and I can start this all over; but I really wanna know where I went wrong. Thanks in advance everyone and sorry for the bother :|.

EDIT: I ran with the debugger over it (can't post it though cuz I'm at work now). It goes recursively down until the length is 70008 70009 or something like that and then it cycles infinitely at this point.

Upvotes: 1

Views: 723

Answers (3)

tudor balus
tudor balus

Reputation: 149

Found the problem actually. It seems that it was this piece of code:

if(len > len1)
       {alpha = alpha.pow(len1/2);}
    else if(len <= len1)
       {alpha = alpha.pow(len/2);}

I changed "alpha" as to be a BigInteger and I tried using the above code. For no apparent reason, the code doesn't work. Example: if alpha = alpha.pow(len/2); and alpha has the initial value "10" and len/2 has the value "100000", the expression evaluates to "332193" :|.

Sadly nobody is looking at this question anymore.

Upvotes: 0

nvuono
nvuono

Reputation: 3363

With this statement and your initial conditions it looks like there's going to be a problem unless you're intending to truncate this:

alpha = (int) Math.pow(10, len1/2);}

You're trying to cast the result of 10^100000 to an (int) which can only hold a max value of 2,147,483,647 which is between 10^9 and 10^10.

I don't see any way that using a Math.Pow function passing in two double values and returning a double can be used to calculate a proper alpha component as an int even with a more reasonable number than 10^100000.

For example, Math.Pow(10,10) returns a double value of 10,000,000,000.

What happens when you cast that to an (int)?

In C# you get a value for (int)(Math.Pow(10,10)) of 1410065408

Upvotes: 2

Omar Himada
Omar Himada

Reputation: 2588

If you are always getting infinite recursion, that means this condition here

 if((A1.bitLength() >= 70000) || (A0.bitLength() >= 70000) || (B1.bitLength() >= 70000) ||     (B0.bitLength() >= 70000))

is always getting satisfied. Inside that if statement you have multiple calls to the containing function, which is causing the infinite recursion.

Upvotes: 1

Related Questions