Knuth 长除法算法
Knuth long division algorithm
我正在实现 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 的表示精度。据我了解算法的其余部分，它们应该是单精度*，但很容易发现它们必须是双精度*才能拟合结果的许多情况。
应该如何计算这些值？精度是多少？
*表达式single/double-precision指的是整数运算，不是浮点运算。
当除数被归一化（设置最高有效位）时，商总是适合单个字。使用两个基本表示的幂，归一化是通过廉价的左移操作完成的。
我正在实现 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 的表示精度。据我了解算法的其余部分，它们应该是单精度*，但很容易发现它们必须是双精度*才能拟合结果的许多情况。
应该如何计算这些值？精度是多少？
*表达式single/double-precision指的是整数运算，不是浮点运算。
当除数被归一化（设置最高有效位）时，商总是适合单个字。使用两个基本表示的幂，归一化是通过廉价的左移操作完成的。