使用 BCD 格式进行数字除法
我有两个包含（解压的）BCD 数字的 std::deque 对象。每个字节是一个 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) 以便稍后重新缩放。
计算第三个数值对象的商的最快方法是什么？
我已经实现了加法、减法和乘法，但是我找不到如何实现（快速）除法（具有无限位数）的良好解释。
I've two std::deque objects containing (unpacked) BCD numbers. Each byte is one BCD digit. The size is not limited, but there is a MAX_SCALE = 10, so 1 / 3 should result in 0.3333333333. For both objects, the scale and sign is saved:
class Numeric
{
std::deque<uint8_t> m_digits;
size_t m_scale; // indicates how many digits after "."
bool sign; // true = positive, false = negative
};
Each Numeric object is scaled to 0 before calculation, 10.34 / 2.1 is scaled to 1034 / 210 and the highest scale (2) is recorded for rescale back later.
What is the fastest method to calculate the quotient into a third Numeric object?
I've already implemented addition, substraction und multiplication, but I can't find a good explanation how to implement (fast) divison (with an unlimited number of digits).
如果你对这篇内容有疑问，欢迎到本站社区发帖提问 参与讨论，获取更多帮助，或者扫码二维码加入 Web 技术交流群。
绑定邮箱获取回复消息
由于您还没有绑定你的真实邮箱，如果其他用户或者作者回复了您的评论，将不能在第一时间通知您！
发布评论
评论（2）
您可以使用牛顿法求 1 / a。
令 f(x) = 1 / x - a，您想要找到 f^{-1}(0)。
然后
收敛到f^{-1}(0)。 我们
因此
收敛到 1/a。您使用以下标准测试收敛性：
您大致需要 log n 乘法才能收敛。如果乘法为 O(n^2)，则对于大数来说，这比长除法慢（O(n^2) 与 O(n^2 log n)）。尽管如此，它实施起来很快，而且在实践中也不错。事实上，一些处理器使用该方案的变体来求逆并执行除法。请注意，如果您有更好的乘法算法，那么牛顿方法将渐近优于长除法。
作为对 x_0 的第一个猜测，您可以将除最高有效数字之外的所有数字设置为零，并直接找到其倒数。
示例：a = 3425,23。第一个猜测：1 / a ~ 1 / 3000 ~ 0.0033333333
顺便说一句，迭代
将收敛到 1 / sqrt(a) （采用两个前导数字和一个小查找表作为初始猜测）。
You can use Newton's method to find 1 / a.
Let f(x) = 1 / x - a, you want to find f^{-1}(0).
Then
converges to f^{-1}(0). This gives us
therefore
converges to 1 / a. You test convergence with the criterion
You roughly need log n multiplications to converge. If multiplications are O(n^2), this is slower than long division for large numbers (O(n^2), vs O(n^2 log n)). Nevertheless, it is quick to implement and not so bad in practice. In fact, some processors use a variant of this scheme to find inverses and perform divisions. Note that if you have a better multiplication algorithm, then Newton's method outperforms long division asymptotically.
As a first guess for x_0, you can set all but the most significant digit to zero, and find its inverse directly.
Example: a = 3425,23. First guess : 1 / a ~ 1 / 3000 ~ 0.0033333333
As an aside, the iteration
will converge to 1 / sqrt(a) (take two leading digits and a small lookup table for the initial guess).
执行整数算术中的所有操作：要计算
10.34 / 2.1，您需要计算10340000000000 / 2100，然后除以10^10。要计算10340000000000 / 2100，您只需购买 Knuth vol 2，正如 Alexandre C 已经提到的那样。 （这不是你会后悔的事情！）我认为牛顿方法在这里不适用，除非你的数字非常大。Do everything in integer arithmetic: to calculate
10.34 / 2.1, you want to calculate10340000000000 / 2100and then divide by10^10. And to calculate10340000000000 / 2100, you only need to purchase Knuth vol 2, as Alexandre C already mentioned. (This is not something that you will ever regret!) I don't think Newton's method is applicable here, unless your numbers are very large.