计算正实数的乘法逆 [英] Calculate multiplicative inverse of positive real number

问题描述

我想在不使用除法的情况下计算正实数的乘法逆.在阅读完有关Newton Raphson方法的各个页面之后，我实现了以下代码来计算逆:

I wanted to calculate the multiplicative inverse of a positive real number without using division. After reading through various pages on Newton Raphson method, i implemented the following code for calculating the inverse:

#define PRECISION 0.1e-5
double inverse(double num) {
    double ans = num;
    while (ans * num > 1 + PRECISION || ans * num < 1 - PRECISION) {
        ans = ans * (2 - num * ans);
    }
    return ans;
}

现在，问题是，我实际上没有得到逆值.循环无限进行.

Now, the problem is, I actually do not get the inverse value. The loop goes on infinitely.

所以，我注意到的第一是: ans的值变为负数，我添加了一条语句
if (ans < 0) ans *= -1;
，以便ans始终保持正数.

So, 1st thing I noticed was: The value of ans become negative, I added a statement
if (ans < 0) ans *= -1;
so that ans remains positive always.

第二个要注意的地方: 如果对ans = 0.5进行了初始化，那么对于num = (1, 2, 3, 5)的几个值，我会得到正确的答案.

2nd point to be noticed: If my initialization for ans = 0.5 then I get the correct answer for a few values of num = (1, 2, 3, 5).

因此，我的假设是，由于变量ans的初始化不正确，因此该实现无法正常工作.

So, my assumption is, that the implementation isn't working because of inappropriate initialization of the variable ans.

所以，最后我的问题是:
1 .此方法可以实际用于计算所有正实数的逆吗?
2 .如果是，那么使用Newton Raphson方法假设初始值是否有任何条件?
3 .是否还有其他更好的方法可以在不使用除法的情况下计算倒数?

So, finally my questions:
1.Can this method actually be used to calculate inverse of all positive real numbers?
2.If yes, then are there any conditions required for the initial value assumed when using Newton Raphson method?
3.Is there any other better method to calculate reciprocal without using division?

感谢您的回答.因此，如答案中所述，我将ans的初始值更改为PRECISION，它可以正常工作！而且，由于初始值适合num的特定最大限制，因此ans永远不会变为负数，因此不需要我最初添加的负数检查条件.

Thanks for the answer. So, as mentioned in the answer, I changed my initial value of ans to PRECISION and it works! Also, now as the initial value is good for particular max limit on num, ans never becomes negative, so no need for the negative checking condition that I had added initially.

所以，这是工作代码(对于我给出的输入，至少是可以工作的.)

So, this is the working code (atleast works for the input I have given.)

double inverse(double num) {
    // Added to make it valid for all inputs.
    // For a too large number under the precision constraint, the answer is 0.
    if (num > 999999)
        return 0;
    double ans = PRECISION;
    while (ans * num > 1 + PRECISION || ans * num < 1 - PRECISION) {
        ans = ans * (2 - num * ans);
    }
    return ans;
}

推荐答案

您应该从(0，2/num)中选择初始近似值.如果从2/num的另一侧选择它，则该方法可能不会收敛:近似值将超过0，并且序列将趋于-∞.

You should pick the initial approximation from (0, 2/num). If you pick it from the other side of 2/num, the method may not converge: the approximation will overshoot 0 and the sequence will tend to -∞.

要得出该间隔，让我们看看ans*(2-num*ans)在哪里改变符号:当2 num * ans<变为负数时. 0，或者当ans> 2/num时.因此，最初ans应该小于2/num.

To arrive at the interval, let's see where ans*(2-num*ans) changes sign: it becomes negative when 2-num*ans < 0, or when ans > 2/num. So initially ans should be less than 2/num.

要能够选择一个好的初始近似值，您必须对浮点数的表示方式有所了解.通常，计算机使用x = s * m * 2 ^e ，其中s是符号，m(尾数")在(0.5，1)中，e(指数")是整数.现在1/x = s * 1/m * 2 ^-e ，因此问题就减少了，计算范围为(0.5，1)的数字的倒数，在该范围内，您可以使用示例1作为初始猜测.显然，该范围内的最佳初始猜测是 48/17-32/17 * m .

To be able to pick a good initial approximation you have to know a little about how floating point numbers are expressed. Typically computers use x = s*m*2^e, where s is the sign, m ("mantissa") is in (0.5, 1) and e ("exponent") is an integer. Now 1/x = s*1/m * 2^-e, so the problem is reduced to calculating the inverse of a number in range (0.5, 1), and in that range you can use for example 1 as the initial guess. Apparently the optimal initial guess in that range is 48/17 - 32/17*m.

一个对所有数字s * m * 2 ^e 都适用的初始猜测是s * 2 ^-e .在C语言中，可以这样计算:

One initial guess that should work for all numbers s*m*2^e is s*2^-e. In C this can be calculated as:

double ans = num;
// Initial guess: ans = 2**(-floor(log num))
long int *t = (long int*)(&ans);
*t = (*t & (0x1l<<63)) | (~*t & (0x3FFl << 52)) - (0x1l << 52);
      /* sign */              /* negative exponent */

(请注意:我还没有检查边缘条件.)

(Beware: I haven't checked the edge conditions.)

这篇关于计算正实数的乘法逆的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！