作业：如何写自己的大数乘法？

Question

在我的项目中，我必须处理大数字的乘法（大于java.long），该乘法一直盯着我自己的BigNumber类int[]。基本上我需要实现这样的事情：

    157 x
    121 y
   ----
    157 result1
   314  + result2
  157   + result3
 ------
 18997  finalResult

但是我该如何实施呢？

我考虑过用零（3140、15700）扩展result2,3并将其添加。但是首先我需要以某种方式在y的每个数字之间导航，然后乘以x的每个数字。

Answer 1

使用对角线方法。创建一个数组，然后将每个数字彼此相乘，然后在每个单元格中填写数字。

36 x 92

       3     6
    +-----+-----+
    | 2 / | 5 / |
9   |  /  |  /  |
    | / 7 | / 4 |
    +-----+-----+
    | 0 / | 1 / |
2   |  /  |  /  |
    | / 6 | / 2 |
    +-----+-----+

在每个对角线上加上数字。从最低有效数字（在右下方）移动到最高数字（在左上方）。

2                                                                    2 (least-significant)
(6 + 1 + 4) = 11 (make this 1, and carry the 1 to the next digit)    1
(5 + 7 + 0 + 1(carried)) = 13 (make this 3, and carry the 1)         3
2 + 1(carried) = 3                                                   3 (most-significant)

答案是3312。

对您的数字进行二维排列。用个位数的乘法一起填充数组。

像上面一样，编写一些逻辑以刮除对角线。

这应该适用于任意大的数字（只要您还有剩余的内存）。