7

我正在寻找 Python Nth 根函数/算法，但在您发布之前：NO INTEGER ROOT，HELL！
我在哪里可以获得至少一个指南，如何对产生精确float/Decimal的第 N 个根函数进行编程？
这样的函数不返回1也不0为root(125, 1756482845)（第一个参数是数字，第二个是根深度（或其他东西））。

编辑：所以，你给了我这个解决方案：n ** (1.0 / exp)当我问这个问题时我就知道了，但它只是不适用于例如exp = 3. 你不能1/3用有理数来表达，所以125 ** (1/3)给出了不正确的结果4.999999...。我在要求一些“智能”算法，它可以为如此好的数字提供正确的结果，并且至少为 4-decimal-points-accurate 的理性结果exp。如果没有这样的函数或算法，我会使用这个（n ** (1/exp)）。

4

5 回答 5

11

我会尝试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.

于 2016-09-30T15:38:34.200 回答
3

您可以对答案进行二进制搜索。如果你想找到等于 N 的第 k 个根的 X，你可以对 X 进行二分搜索，测试二分搜索的每一步 X^k 是否等于 N + - 一些小常数以避免精度问题。

这是代码：

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 中存在与浮点变量精度限制相关的精度限制

于 2016-10-01T02:10:39.367 回答
1

你的意思是这样的：

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

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

于 2016-09-30T14:56:01.577 回答
1

这pow是math模块的功能。

import math
math.pow(4, 0.5)

将返回 4 的平方根，即2.0.

因为root(125, 1756482845)，你需要做的是

math.pow(125, 1.0 / 1756482845)
于 2016-09-30T14:56:05.927 回答
1

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

相关代码（MIT 许可）转载在这里。基本算法是用一些 Newton-Raphson 搜索截断的整数的第 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

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

它适用于大整数，例如：

  • (10 raisedTo: 600) nthRoot: 300-> 100“准确”
  • (10 raisedTo: 600) + 1 nthRoot: 300-> 100.0“不准确”

如果您没有这样的期望，最初的猜测可能会使用 inexact naive n**(1/exp)。

代码应该很容易在 Python 中移植，并留有很多优化空间。

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

于 2016-10-02T23:48:59.837 回答