从头开始实现 BigInteger 乘法（并确保其时间复杂度为 O(n^2)）

Question

作为家庭作业，我正在实现 Karatsuba 的算法，并将其与小学风格的大整数 O(n^2) 乘法算法进行基准测试。

我想我在这里唯一的选择是将数字带到它们的字节数组表示中，然后从那里开始工作。

好吧，我被困在这里......当使用 * 运算符时，我不知道如何检测/纠正数字是否溢出字节乘法或添加进位。有什么想法吗？

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

        //BigInteger result = x.multiply(y);

        byte [] xByteArray = x.toByteArray();
        byte [] yByteArray = y.toByteArray();

        int resultSize = xByteArray.length*yByteArray.length;

        byte [][] rowsAndColumns = new byte[resultSize][resultSize];

        for (int i =0; i<xByteArray.length;i++)
           for (int j=0; j<yByteArray.length;j++){


               rowsAndColumns[i][j] = (byte )(xByteArray[i] * yByteArray[j]); 
               // how would I detect/handle carry or overflow here?               
           }

        return null;
    }

Answer 1

字节乘法的结果是 2 个字节。您必须使用低位字节作为结果，使用高位字节作为进位（溢出）。

我还建议您注意字节的符号。由于 Java 中的字节是有符号的，因此您必须仅使用它们的低 7 位，或者将它们转换为整数并在相乘之前更正符号。

你会想要一个像这样的循环：

        for (int i =0; i<xByteArray.length;i++)
           for (int j=0; j<yByteArray.length;j++){
               // convert bytes to ints
               int xDigit = xByteArray[i], yDigit = yByteArray[j];
               // convert signed to unsigned
               if (xDigit < 0)
                   xDigit += 256;
               if (yDigit < 0)
                   yDigit += 256;
               // compute result of multiplication
               int result = xDigit * yDigit;
               // capture low order byte
               rowsAndColumns[i][j] = (byte)(result & 0xFF);
               // get overflow (high order byte)
               int overflow = result >> 8;
               // handle overflow here
               // ...
           }

Answer 2

避免溢出的最好方法就是从一开始就不要让它发生。使用更高宽度的数字进行所有计算以避免出现问题。

例如，假设我们有 256 基数，每个数字都存储为单个无符号字节。

d1 = (int) digits[i] //convert to a higher-width number
d2 = (int) digits[j]
product = d1*d2  //ints can handle up to around 2^32. Shouldn't overflow w/ 256*256
result = product % 256
carry  = product / 256

您可能会想将二的幂除法转换为位运算，但这并不是真正必要的。