Помогите отладке этого алгоритма умножения

Question

Я реализую простой алгоритм умножения , чтобы сравнить его производительность с подходом "разделяй и властвуй".

Я отказался от своей первоначальной идеи сделать это с помощью байтовой арифметики и решил преобразовать числа с помощью массивов символов.

Ну, все отлично работает в простых случаях, таких как 33 x 33, где метод отладки печатает правильно:

0 9 9
0 9 9

пока на 34 х 33, получаю

1 0 3
1 0 2

где это должно быть

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 = .... также должна быть перемещена за пределы внутреннего цикла, поскольку она не зависит ни от чего внутри внутреннего цикла.