作业:如何编写自己的大数字乘法？

Question

在我的项目中,我必须处理在我自己的BigNumber类中盯着的大数字(大于java.long)的乘法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.

制作数字的二维数组.使用单个数字的乘法填充数组.

写一些逻辑来刮掉对角线,如上所述.

这适用于任意大数(只要你还有内存).