2

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

#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;
}

现在,问题是,我实际上没有得到反值。循环无限进行。

所以,我注意到的第一ans件事是:变得负数的值,我添加了一个声明
if (ans < 0) ans *= -1;
,以便ans始终保持正数。

需要注意的第二点:如果我的初始化,ans = 0.5那么我得到了几个num=值的正确答案(1, 2, 3, 5)

所以,我的假设是,由于变量初始化不当,实现无法正常工作ans

所以,最后我的问题是:
1。这种方法实际上可以用来计算所有正实数的倒数吗?
2 .如果是,那么在使用牛顿拉夫森法时,假设的初始值有什么条件吗?
3 .有没有其他更好的方法来计算倒数而不使用除法?

编辑:

感谢你的回答。因此,如答案中所述,我将初始值更改为anstoPRECISION并且它有效!此外,现在由于初始值适用于特定的最大限制numans因此永远不会变为负数,因此不需要我最初添加的否定检查条件。

所以,这是工作代码(至少适用于我给出的输入。)

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;
}
4

2 回答 2

4

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

为了得出区间,让我们看看ans*(2-num*ans)符号变化的地方:当 2-num*ans < 0 或 ans > 2/num 时,它变为负数。所以最初ans应该小于 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

一个应该适用于所有数字 s*m*2 e的初始猜测是 s*2 -e。在 C 中,这可以计算为:

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 */

(注意:我没有检查边缘条件。)

于 2013-03-13T10:39:19.817 回答
0

要近似 x 的倒数,只使用乘法和减法,可以猜出一个数字 y,然后用 2y - xy^2 重复替换 y。一旦 y 的变化变得(并保持)足够小,y 就是 x 的倒数的近似值。

ans = (2*ans)- (num*ans*ans);

请添加括号并尝试

在建设性数学中,要使实数 x 有倒数,x ≠ 0 是不够的。必须给定一个有理数 r,使得 0 < r < |x|。就上一段的逼近算法而言,这需要证明y的变化最终会变得任意小。 => 此方法不能扣除所有实数的乘法逆

每个非零元素都具有乘法逆元的环是除法环;同样地,它成立的代数是除法代数。

你想使用模数吗?在模算术中,还定义了 a 的模乘逆:它是满足 ax ≡ 1 (mod n) 的数 x。当且仅当 a 和 n 互质时,这种乘法逆存在。

_编辑_ _ ____

刚刚注意到最初 ans = num; ans = 2*ans-num*ans*ans; => ans = 2 * ans - 3 * ans = -1 * ans

所以它总是会是一个负值。相信初始化为num并不是一个好主意。尝试将ans设置为1

于 2013-03-13T09:11:43.867 回答