我想在不包含浮点数的系统中执行两个128位无符号整数的乘法和除法

Question

目前我面临一个问题，当我把两个数字相乘时

5e20 * 5e20 = 2.5E41

它从128 bit最大值范围溢出，该范围只能包含39 digits的最大数目。所以我不能把两个非常大的数字相乘，因为它降低了我的精度。我想要精度达到16小数位。如果我也做数字除法

10 / 3 = 3.3333333

我只得到3，因为我的系统不包含浮点，所以浮点部分被忽略。为了达到这个精度，我通过将1e16乘以16小数点的精度来增加我的分值。我还试着用科学的符号来解决我的精度，这样我就可以乘法和除法了。

2.5/4 or 2.5x4

通过写作

25x10^-1和4x10^0，但由于这一点，我的乘法仍然是scale-down格式，而我的除法仍然是scaled-up格式。

2.5/4 = 6.25E16 * 10^-1 (scaled up)

2.5*4 = 100 * 10^-1 (scaled down)

我该如何解决这个问题？我应该用什么方法？

Answer 1

没有简单的答案，您将不得不为256位整数实现操作(仍然不能帮助您的除法，您应该使用缩放因子来表示您的数字)、为不动点表示实现操作，或者为浮点表示(mantissa +指数)实现操作，这些操作都不是简单的工作。

对于256位算法，有人创建了一个概念证明(但没有经过战斗测试)：https://github.com/KStasi/clarity-uint256-lib。她使用了4 uint64，以便能够在不溢出的情况下使用uint128算法。

下面是一个使用8位乘法器的16位乘法器：https://www.techiedelight.com/multiply-16-bit-integers-using-8-bit-multiplier/。你需要用128位数做类似的事情。

类似地，下面是一些使用低精度算术进行除法的指针：http://www.mattmillman.com/mcs-48-the-quest-for-16-bit-division-on-the-8-bit-cpu-which-cant-divide-anything/

另一种方法是使用不动点表示，而不是使用缩放因子。有关理论，请参阅https://en.wikipedia.org/wiki/Fixed-point_arithmetic，更实际的注意事项请参见https://schaumont.dyn.wpi.edu/ece4703b20/lecture6.html (一些DSP有相同的问题，它们只有整数运算)。

Answer 2

这里的问题是，这两种操作的科学符号是不一样的。例如,

2.5/4 = 6.25E16 * 10^-1 (scaled up)

2.5*4 = 100 * 10^-1 (scaled down)

在这里，你可以简单地把-16加到指数部分，如果你在尾数中乘以1e16。所以你的答案变成了2.5/4 = 6.25E16 * 10^-1 (scaled up)

2.5/4 = 6.25E16 * 10^-1 * 10^-16

2.5/4 = 6.25E16 * 10^-17

2.5/4 = 0.625

有了这个，你的乘法和除法都是在科学的符号中，得到的是实际的数字。