c++ - 使用 BCD 格式的数字除法

Question

我有两个 std::deque 对象，其中包含(未打包的)BCD 数字。每个字节是一个 BCD 码。大小没有限制，但是有一个 MAX_SCALE = 10，所以 1/3 应该得到 0.3333333333。对于这两个对象，比例和符号都被保存:

class Numeric
{
   std::deque<uint8_t> m_digits;
   size_t m_scale; // indicates how many digits after "."
   bool sign; // true = positive, false = negative
};

每个数值对象在计算前缩放为 0，10.34/2.1 缩放为 1034/210 并记录最高缩放比例 (2) 以供稍后重新缩放。

将商计算为第三个数值对象的最快方法是什么？

我已经实现了加法、减法和乘法，但我找不到很好的解释如何实现(快速)除法(位数不限)。

Answer 1

您可以使用牛顿法求出 1/a。

设f(x) = 1/x - a，你想求f^{-1}(0)。

然后

x_{n + 1} = x_n - f(x_n) / f'(x_n)

收敛于 f^{-1}(0)。这给了我们

x_{n + 1} = x_n - (1 / x_n - a) / (-1 / x^2)

因此

x_{n + 1} = x_n * (2 - a * x_n)

收敛于 1/a。你用标准测试收敛性

if (|x_{n + 1} - x_n| < tolerance) then stop

您大致需要 log n 次乘法才能收敛。如果乘法是 O(n^2)，这比大数的长除法慢(O(n^2)，对比 O(n^2 log n))。尽管如此，它实现起来很快，而且在实践中还不错。事实上，一些处理器使用这种方案的变体来求逆和执行除法。请注意，如果您有更好的乘法算法，那么牛顿法渐近地优于长除法。

作为 x_0 的第一个猜测，您可以将除最高有效数字以外的所有数字都设置为零，并直接求出它的倒数。

示例:a = 3425,23。第一次猜测:1/a ~ 1/3000 ~ 0.0033333333

顺便说一句，迭代

x_{n + 1} = x_n * (3 - a * x_n^2)

将收敛到 1/sqrt(a)(取两个前导数字和一个小的查找表作为初始猜测)。