如果整数有整数根,如何解决?

How to solve if an integer has an integer root?

提问人:Anthony Massie 提问时间:1/1/2016 更新时间:1/1/2016 访问量:141

问:

我需要求解任何具有整数根的度数 n 的根。我最初的想法是用牛顿的方法找到近似根,但是,幂函数不会给我们提供机器浮子可以表达的最大精度吗?

function hasIntegerRoot( $integer, $degree ) {
    if( $degree == 0 || $degree == 1 ) return true;

    $r = pow( $integer, 1/$degree );

    //get nearest integer
    $n = round($r);

    //solve n^x
    $answer = pow( $n, $degree );

    return $answer == $integer;
}

我有两个问题:

幂函数是否足够接近整数根,以便对浮点数进行舍入永远不会返回错误的整数根?这将要求它偏离 0.5,直觉上我无法想象会发生什么,但我没有艰巨的证据。

其次,return 语句需要十进制数学吗?问题是对于足够大的$integer和$n,PHP 将使用 float。这是可取的,因为它不会溢出大整数;但是,它保留了浮点数学的使用,浮点数学本身就具有不准确性。不过,这些不准确会影响我的算法吗?

同样,凭直觉,我觉得$integer是整数的约束,根$n必须是整数,避免了任何浮点数学问题。数学永远不会涉及小数。但是,我没有办法绝对证明直觉。

php 算法 浮动精度

评论

0赞 Ignacio Vazquez-Abrams 1/1/2016
你使用和倒数的事实意味着你涉及浮点数。pow()
0赞 Rodney Salcedo 1/5/2016
您可以使用 BC Math 功能,它支持任何大小和精度的数字,表示为字符串

答:

0赞 Matt Timmermans 1/1/2016 #1

我不能依赖 pow() 足够准确,但你当然可以从 pow(...,1/degree) 开始,然后向上或向下走$n直到 $n**$degree 匹配或交叉$integer。(但是自己实现**度,因为它内部使用pow())

pow() 是一个近似值,它并不总是返回与确切结果最接近的可能值