牛顿法求浮点数除法的倒数 [英] Newton's Method for finding the reciprocal of a floating point number for division

问题描述

我正在尝试将分子N除以除数D。
我正在使用Newton–Raphson方法，该方法使用Newton方法求D（1 / D）的倒数。然后，通过将分子N乘以倒数1 / D得到N / D，可以得出除法结果。

I am trying to divide two numbers, a numerator N by a divisor D. I am using the Newton–Raphson method which uses Newton's method to find the reciprocal of D (1/D). Then the result of the division can be found by multiplying the numerator N by the reciprocal 1/D to get N/D.

可以找到Newton-Raphson算法< a href = http://en.wikipedia.org/wiki/Division_%28digital%29#Newton.E2.80.93Raphson_division rel = nofollow>此处

The Newton-Raphson algorithm can be found here

所以算法的第一步是从对1 / D的初始猜测开始，我们将其称为X_0。

So the first step of the algorithm is to start with an initial guess for 1/D which we call X_0.

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

X_0 is defined as X_0 = 48/17-39/17*D

但是，我们必须首先对除数D进行位移位以对其进行缩放，以使0.5≤D≤1。相同位移应应用于分子N，以使商不变。

However, we must first apply a bit-shift to the divisor D to scale it so that 0.5 ≤ D ≤ 1. The same bit-shift should be applied to the numerator N so that the quotient does not change.

然后我们使用公式X_（i + 1）= X_i *（2-D * X_i）来找到X_（i + 1）

We then find X_(i+1) using the formula X_(i+1) = X_i*(2-D*X_i)

由于分子N，除数D和结果均为浮点IEEE-754 32位格式，我想知道如何正确应用此缩放比例，因为我的1 / D值不会收敛取一个值，它只是接近-Inf或+ Inf（取决于D）。

Since both the numerator N, divisor D, and result are all floating point IEEE-754 32-bit format, I am wondering how to properly apply this scaling since my value for 1/D does not converge to a value, it just approaches -Inf or +Inf (depending on D).

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

What I have found works though is that if I make X_0 less than 1/D, the algorithm seems to always converge. So if I just use a lookup table where I always store a bunch of values of 1/D and I can always ensure I have a stored 1/D value where D > Dmin, then I should be okay. But is that standard practice?

推荐答案

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

1. To set the sign bit correctly, perform the XOR on the sign of the original dividend and divisor.

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

Make the sign of the divisor and dividend positive now.

首先将等于x的指数设置为aspx_exponent-1-divisor_exponent-1 +127。
+127用于偏差，因为我们只是将其减去了。

First set the dividend exponent equal to dividend_exponent- 1 - divisor_exponent - 1 + 127. The +127 is for the bias since we just subtracted it out. This scales the dividend by the same amount we will scale the divisor by.

将除数的倍数更改为126（有偏）或-1（无偏）。这会将除数缩放到0.5到1之间。

Change the divisor exponent to 126 (biased) or -1 (unbiased). This scales the divisor to between 0.5 and 1.

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

Proceed to find Xo with the new scaled D value from step one. Xo = 48/17-32/17 * D.

使用新的D继续查找Xn，直到我们迭代了足够的时间以使我们具有精度我们需要。 X（i + 1）= X（i）*（2-D * X（i））。同样，我们需要的步骤数为S = ceil（log_2（（P + 1）/ log_2（17）））。其中P是二进制位数

Proceed to find Xn using the new D until we have iterated enough times so that we have the precision we need. X(i+1) = X(i) * (2-D*X(i)). Also, the number of steps S we need is S = ceil(log_2((P + 1)/log_2(17))). Where P is the number of binary places

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

Multiply Xn * N = 1/D * N = N/D and your result should be correct.

更新：此算法正确运行。

Update: This algorithm works correctly.

这篇关于牛顿法求浮点数除法的倒数的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！