c++ - 对于需要精度的定点，最好的乘法算法是什么

Question

我知道，我知道，人们可能会说“只切换到浮点”，但由于我正在从事的项目的性质，目前这不是一个选项。我正在帮助用 C++ 编写一种编程语言，目前我很难尝试获得一个非常准确的乘法算法，我有一个 VM，主要是 mod/smod、div/sdiv 的操作(即带符号的数字在这里不是问题), mul，一个完全小数的减半数和一个插入的移位数，我乘以和除以创建我的移位。为简单起见，假设我正在使用 32 字节空间。我的算法几乎适用于任何涉及整数的东西，只是当我的小数部分超过 16 个字节时，我会遇到精度问题，如果我对它进行四舍五入，这个数字会相当准确，但我希望它是尽可能准确，甚至愿意为它牺牲一点性能，只要它保持固定点并且不进入浮点领域。我所关心的算法将以一种伪代码的形式映射出来。会喜欢任何关于如何使它变得更好的见解，或者任何关于为什么根据计算科学定律的推理，我所要求的是徒劳的努力。

对于完全小数(所有字节都是小数):

 A = num1 / halfShift //truncates the number down to 16 so that when multiplied, we get a full 32 byte num
 B = num2 / halfShift
 finalNum = A * B

对于其余大于 16 字节的数字，我使用此算法:

 this algorithm can essentially be broken down into the int.frac form
 essentially A.B * C.D taking the mathematic form of
 D*B/shift + C*A*shift + D*A + C*B
 if the fractional numbers are larger than the integer, I halve them, then multiply them together in my D*B/shift
 just like in the fully fractional example above

是否有某种我应该注意的“神奇”舍入方法？请告诉我。

Answer 1

如果先进行乘法然后进行缩放，您将获得最准确的结果。当然，这意味着您需要将乘法结果存储在 64 位 int 类型中。如果那不是一种选择，那么您提前换档的方法是有道理的。但是你肯定会失去精度。

无论哪种方式，如果舍入而不是截断，都可以稍微提高准确性。

我支持阿空加瓜关于四舍五入到最接近的建议。为此，您需要在应用除法之前添加将被截断的最高位。

在你的情况下看起来像这样:

A = (num1 + 1<<(halfshift-1)) >> halfshift 
B = (num2 + 1<<(halfshift-1)) >> halfshift
finalNum = A * B

编辑:

有关如何根据因子值动态缩放因子和结果的示例(这会提高分辨率，从而提高结果的准确性):

shiftA 和 shiftB 需要设置为 A 和 B 都是 16 字节的小数，因此 32 字节的结果不会溢出。如果事先不知道shiftA和shiftB，可以通过计算num1和num2的前导零来确定。

A = (num1 + 1<<(shiftA-1)) >> shiftA
B = (num2 + 1<<(shiftB-1)) >> shiftB
finalNum = (A * B) >> (fullshift - (shiftA + shiftB))