一尘不染

牛顿法求浮点数除法的倒数

algorithm

我正在尝试将分子N除以除数D。我正在使用牛顿–拉夫森方法,该方法使用牛顿方法来求D(1 / D)的倒数。然后,可以通过将分子N乘以倒数1 / D得出N /
D来找到除法结果。

牛顿-
拉夫森算法可以在这里找到

因此,算法的第一步是从对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值,并且我始终可以确保在D>
Dmin处有一个存储的1 / D值,那么我应该可以。但是,这是标准做法吗?


阅读 771

收藏
2020-07-28

共1个答案

一尘不染

  1. 要正确设置符号位,请对原始除数和除数的符号执行XOR。

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

  3. 首先将股息指数设置为等于aspx_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 = ceil(log_2((P + 1)/ log_2(17)))。其中P是二进制位数

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

更新:此算法正常工作。

2020-07-28