Knuth长除法

Question

我正在实现D. E. Knuth的“计算机编程艺术”第2卷4.3.2节的算法D。

在步骤D3中，我应该计算q = floor(u[j+n]*BASE+u[j+n-1] / v[n-1])和r = u[j+n]*BASE+u[j+n-1] mod v[n-1]。这里，u (派息)和v (除数)分别是长度m+n和n的单精度数组。BASE是表示基，对于32位或64位的二进制计算机分别等于2^32或2^64。

我的问题是q和r表示的精度。正如我所理解的算法的其余部分，它们应该是单精度*，但是很容易发现很多情况，它们必须是双精度*才能符合结果。

如何计算这些值？精确到什么程度？

*表达式单/双精度指的是整数算法，而不是浮点算法.

Answer 1

当除数被规范化(最重要的位集)时，商总是适合于一个单词。使用两个基表示的幂次，通过廉价的左移位操作来实现规范化。

链接到一个更详细、更正式的答案。