algorithm - 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有代表。据我了解算法的其余部分，它们应该是单精度*，但很容易发现它们必须是 double *才能拟合结果的许多情况。

这些值应该如何计算？精度如何？

*单精度/ double 指的是整数运算，不是 float 运算。

Answer 1

当除数被归一化(设置最高有效位)时，商总是适合单个字。使用两个基本表示的幂，归一化是通过廉价的左移操作完成的。

Link to a more detailed and formal answer.