精确的 n 次根

Question

我正在寻找 Python N 次根 function/algorithm 但在你之前 post：没有整数根，见鬼！
我在哪里可以获得至少一个指南，如何编写生成精确 float/Decimal?
的 Nth root 函数 不return1也不0为root(125, 1756482845)的函数（第一个参数是数字，第二个是根深度（或其他））。

编辑： 所以，你给了我这个解决方案：n ** (1.0 / exp) 当我问这个问题时我就知道了，但它不起作用，因为例如，exp = 3。您不能用有理数表示 1/3，因此 125 ** (1/3) 给出了不正确的结果 4.999999...。我要求一些 "smart" 算法，它为如此好的数字提供正确的结果，并且为有理数 exp 提供至少 4 个小数点的准确结果。如果没有这样的函数或算法，我就用这个(n ** (1/exp)).

Answer 1

你的意思是这样的：

>>> 125**(1/9.0)
1.7099759466766968

您可能感兴趣的其他东西是 bigfloat 模块（没有亲自使用过，只是知道它存在 :) - 实际上在过去安装它时遇到问题 - 可能是 OS X 错误）

Answer 2

是math模块的函数pow。

import math
math.pow(4, 0.5)

将return4的平方根，即2.0。

对于root(125, 1756482845)，你需要做的是

math.pow(125, 1.0 / 1756482845)

Answer 3

我会尝试 gmpy2 库。

>>> import gmpy2
>>> gmpy2.root(125,3)
mpfr('5.0')
>>>

gmpy2 使用 MPFR 库来执行正确的舍入浮点运算。默认精度为 53 位，但可以增加。

>>> gmpy2.root(1234567890123456789**11, 11)
mpfr('1.2345678901234568e+18')  # Last digits are incorrect.
>>> gmpy2.get_context().precision=200
>>> gmpy2.root(1234567890123456789**11, 11)
mpfr('1234567890123456789.0',200)
>>>

免责声明：我维护gmpy2。

Answer 4

您可以对答案进行二分查找。

代码如下：

import math

N,K = map(float,raw_input().split()) # We want Kth root of N
lo = 0.0
hi = N
while 1:
    mid = (lo+hi)/2
    if math.fabs(mid**K-N) < 1e-9: # mid^K is really close to N, consider mid^K == N
        print mid
        break
    elif mid**K < N: lo = mid
    else: hi = mid

对于 (N,K) = (125,3) 它打印 5.0，正确答案。您可以通过更改 1e-9 常量使其更精确，但是在 Python

中存在与浮点变量精度限制相关的精度限制

Answer 5

在 Squeak Smalltalk 中，有一个 nthRoot: 消息可以回答精确的 Integer 结果，如果整数接收器是某个整数的精确 n 次方。但是，如果解决方案是代数根，则实现不会退回到朴素 n**(1/exp)；该方法通过适当处理残差舍入到最近的浮点数。

相关代码（MIT许可）转载于此。基本算法正在使用一些牛顿-拉夫森搜索整数的截断 n 次根：

Integer>>nthRootTruncated: aPositiveInteger
    "Answer the integer part of the nth root of the receiver."
    | guess guessToTheNthMinusOne nextGuess |
    self = 0 ifTrue: [^0].
    self negative
        ifTrue:
            [aPositiveInteger even ifTrue: [ ArithmeticError signal: 'Negative numbers don''t have even roots.' ].
            ^(self negated nthRootTruncated: aPositiveInteger) negated].
    guess := 1 bitShift: self highBitOfMagnitude + aPositiveInteger - 1 // aPositiveInteger.
    [
        guessToTheNthMinusOne := guess raisedTo: aPositiveInteger - 1.
        nextGuess := (aPositiveInteger - 1 * guess * guessToTheNthMinusOne + self) // (guessToTheNthMinusOne * aPositiveInteger).
        nextGuess >= guess ] whileFalse:
            [ guess := nextGuess ].
    ( guess raisedTo: aPositiveInteger) > self  ifTrue:
            [ guess := guess - 1 ].
    ^guess

这不是特别聪明，因为在指数很大的情况下收敛速度可能会很慢，但它确实有效。然后，相同的根从零四舍五入：

Integer>>nthRootRounded: aPositiveInteger
    "Answer the integer nearest the nth root of the receiver."
    | guess |
    self = 0 ifTrue: [^0].
    self negative
        ifTrue:
            [aPositiveInteger even ifTrue: [ ArithmeticError signal: 'Negative numbers don''t have even roots.' ].
            ^(self negated nthRootRounded: aPositiveInteger) negated].
    guess := self nthRootTruncated: aPositiveInteger.
    ^self * 2 > ((guess + 1 raisedTo: aPositiveInteger) + (guess raisedTo: aPositiveInteger))
        ifTrue: [guess + 1]
        ifFalse: [guess]

然后在nthRoot中测试正确性：

Integer>>nthRoot: aPositiveInteger
    "Answer the nth root of the receiver.
    Answer an Integer if root is exactly this Integer, else answer the Float nearest the exact root."

    | guess excess scaled nBits |
    guess := self nthRootRounded: aPositiveInteger.
    excess := (guess raisedTo: aPositiveInteger) - self.
    excess = 0 ifTrue: [ ^ guess ].

    nBits := Float precision - guess highBitOfMagnitude.
    nBits <= 0 ifTrue: [ ^(Fraction numerator: guess * 4 - excess sign denominator: 4) asFloat].

    scaled := self << (nBits * aPositiveInteger).
    guess := scaled nthRootRounded: aPositiveInteger.
    excess := (guess raisedTo: aPositiveInteger) - scaled.
    ^(Fraction numerator: guess * 4 - excess sign denominator: 1 << (nBits + 2)) asFloat

这也可以应用于分数，但最近的浮点数有点复杂，Squeak 实现目前还很幼稚。

它适用于像这样的大整数：

(10 raisedTo: 600) nthRoot: 300 -> 100 "exact"
(10 raisedTo: 600) + 1 nthRoot: 300 -> 100.0 "inexact"

如果你没有这样的期望，最初的猜测可以使用不精确的天真n**(1/exp)。

代码应该很容易移植Python并且留有很多优化的地方。

我没有检查 Python 中可用的内容，但也许您需要正确舍入的 LargeInteger -> Float 和 Fraction -> Float，就像这里解释的那样（Smalltalk 也是，抱歉，但语言并不重要）。

精确的 n 次根

Precise nth root

python

algorithm

floating-point

precision

nth-root