algorithm - 求除法 float 倒数的牛顿法

Question

我正在尝试将两个数字相除，分子 N 除以除数 D。 我正在使用 Newton–Raphson 方法，该方法使用牛顿法求 D (1/D) 的倒数。然后除法的结果可以用分子N乘以倒数1/D得到N/D。

可以找到Newton-Raphson 算法here

因此算法的第一步是从 1/D 的初始猜测开始，我们称之为 X_0。

X_0 定义为 X_0 = 48/17-39/17*D

但是，我们必须首先对除数 D 进行位移以缩放它，以便 0.5 ≤ D ≤ 1。同样的位移应该应用于分子 N，这样商就不会改变。

然后我们使用公式 X_(i+1) = X_i*(2-D*X_i) 求 X_(i+1)

由于分子 N、除数 D 和结果都是浮点 IEEE-754 32 位格式，我想知道如何正确应用这种缩放，因为我的 1/D 值没有收敛到一个值，它只是接近 -Inf 或 +Inf(取决于 D)。

不过我发现有效的是，如果我使 X_0 小于 1/D，算法似乎总是收敛。因此，如果我只使用一个查找表，我总是在其中存储一堆 1/D 值，并且我始终可以确保我有一个存储的 1/D 值，其中 D > Dmin，那么我应该没问题。但这是标准做法吗？

Answer 1

1. 要正确设置符号位，请对原始被除数和除数的符号执行异或操作。

2. 现在使除数和被除数的符号为正。

3. 首先将被除数指数设置为 dividend_exponent- 1 - divisor_exponent - 1 + 127。 +127 是偏差，因为我们刚刚将其减去。这会按我们将按除数缩放的相同数量缩放股息。

4. 将除数指数更改为 126(有偏)或 -1(无偏)。这会将除数缩放到 0.5 到 1 之间。

5. 使用第一步中的新缩放 D 值继续查找 Xo。 Xo = 48/17-32/17 * D。

6. 继续使用新的 D 找到 Xn，直到我们迭代了足够多的次数以获得所需的精度。 X(i+1) = X(i) * (2-D*X(i))。此外，我们需要的步数 S 是 S = ceil(log_2((P + 1)/log_2(17)))。其中P为二进制位数

7. 乘以 Xn * N = 1/D * N = N/D，您的结果应该是正确的。

更新:该算法工作正常。