Java中的Karatsuba乘法，无限递归

Question

我正在尽我最大的努力在Java中做一个Karatsuba实现，但我失败得很惨。some1 可以看看我的代码并告诉我我到底做错了什么吗？我一直在疯狂地敲打这个和谷歌，没有找到任何东西可以让我出去。我只是不明白冷冰冰的问题是什么！

来了：

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

我知道有一些实现可以用来激励我，我可以重新开始;但我真的很想知道我哪里出错了。提前感谢大家，很抱歉打扰：|。

编辑：我用调试器运行了它（虽然我现在在工作，但无法发布它）。它递归向下，直到长度为 70008 70009 或类似的东西，然后在这一点上无限循环。

Answer 1

有了这个语句和你的初始条件，看起来会有问题，除非你打算截断它：

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

您正在尝试将 10^100000 的结果强制转换为只能保存最大值 2,147,483,647 的(int)，该值介于 10^9 和 10^10 之间。

我看不出有任何方法可以使用传递两个double值并返回double的 Math.Pow 函数来计算适当的alpha分量作为int，即使数字比 10^100000 更合理。

例如，Math.Pow(10,10) 返回double值 10,000,000,000 。

当你把它投到(int)时会发生什么？

在 C# 中，您可以获得(int)(Math.Pow(10,10))的值1410065408

Answer 2

如果你总是得到无限递归，这意味着这里的这个条件

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

总是得到满足。在该 if 语句中，您有多个对包含函数的调用，这会导致无限递归。

Answer 3

实际上发现了问题。好像是这段代码：

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

我将"alpha"更改为BigInteger，并尝试使用上面的代码。由于没有明显的原因，代码不起作用。例：如果 alpha = alpha.pow（len/2）;alpha 的初始值为 "10"，len/2 的值为 "100000"，表达式的计算结果为 "332193" ：|。

可悲的是，没有人再关注这个问题了。