帮助调试这个乘法算法

Question

我正在实施simple multiplication algorithm来比较它的表现和分而治之的方法。

我放弃了我最初的想法，用字节算法做这件事，并选择通过字符数组转换数字。

好了，一切工作正常简单的情况下，像33×33，在调试方法打印，正确：

0 9 9 
0 9 9 

但在34 X 33，我得到

1 0 3 
1 0 2 

，它应该be

1 0 2 
1 0 2 

3从哪里来？

public static BigInteger simpleMultiply(BigInteger x, BigInteger y){ 

    char [] longerNum; 
    char [] shorterNum; 

    if(x.compareTo(y)>=0){ // x is a longer/equal num 

     longerNum = x.toString().toCharArray(); 
     shorterNum = y.toString().toCharArray(); 

    } 

    else { //y is a longer num 

     longerNum = y.toString().toCharArray(); 
     shorterNum = x.toString().toCharArray(); 

    } 


    //shorter num equals the number of rows in partial result 
    // longer num + 1 equals the number of columns in partial result 


    int [][] partialResult = new int [shorterNum.length][longerNum.length+1]; 

    int pastCarry=0; 
    int result=0; 
    int carry=0; 

    for (int sIndex=(shorterNum.length-1); sIndex>=0; sIndex--) 
     for (int lIndex = (longerNum.length-1); lIndex>=0; lIndex--) 
     { 
      int sInt = Integer.parseInt(""+shorterNum[sIndex]+""); 
      int lInt = Integer.parseInt(""+longerNum[lIndex]+""); 

      int product = sInt*lInt; 

      if (lIndex==0){ 

      result = (pastCarry+product)% 10; 
      carry = (pastCarry+product)/10; 

      pastCarry = carry; 

      partialResult [sIndex][lIndex+1] = result; //one more column element in partialResult 

      partialResult[sIndex][lIndex] = carry; 


      } 

      else { 

      result = (pastCarry+product)% 10; 
      carry = (pastCarry+product)/10; 

      pastCarry = carry; 

      partialResult [sIndex][lIndex+1] = result;//one more column element in partialResult 


      } 

     } 

     for (int i=0; i<partialResult.length;i++) 
      for (int j=0; j<partialResult[0].length;j++) 
      { 

        System.out.print(partialResult[i][j] + " "); 
        if (j==partialResult[0].length-1){System.out.println();} 
      } 





    return null; 
} 

Answer 1

这是因为你没有外部循环的迭代之间归零pastCarry。

变化

for (int sIndex=(shorterNum.length-1); sIndex>=0; sIndex--) 
    for (int lIndex = (longerNum.length-1); lIndex>=0; lIndex--) 
    { 
     [snip] 
    } 

到

for (int sIndex=(shorterNum.length-1); sIndex>=0; sIndex--) 
{ 
    pastCarry = 0; 
    for (int lIndex = (longerNum.length-1); lIndex>=0; lIndex--) 
    { 
     [snip] 
    } 
} 

顺便说一下，在int sInt = ....线也应在内部循环，因为它不依赖于内环内之外的任何移动。