python n次精确根

sg24os4d  于 2023-01-01  发布在  Python
关注(0)|答案(6)|浏览(141)

我正在寻找Python第N根函数/算法,但在你发布之前:没有整数根,地狱!
我在哪里至少可以获得一个指导,如何编程N根函数,产生精确的float/Decimal
对于root(125, 1756482845)**,**不返回10(第一个参数是数字,第二个参数是根深度(或其他))。

**编辑:**您给我的解决方案是:当我问这个问题的时候我就知道了,但是它不起作用,例如,exp = 3。你不能用有理数来表达1/3,所以125 ** (1/3)给出了错误的结果4.999999...。我问的是一些“聪明”的算法,该算法对这样的好数给出正确的结果,对有理数exp给出至少4个小数点的精确结果,如果没有这样的函数或算法,我将使用这个(n ** (1/exp))。

vfh0ocws

vfh0ocws1#

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

ekqde3dh

ekqde3dh2#

你可以对答案进行二分查找,如果你想找到X等于N的k次根,你可以对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中有一个与浮点变量精度限制相关的精度限制

qvk1mo1f

qvk1mo1f3#

math模块的函数pow

import math
math.pow(4, 0.5)

将返回4的平方根,即2.0
对于root(125, 1756482845),您需要做的是

math.pow(125, 1.0 / 1756482845)
sauutmhj

sauutmhj4#

你的意思是这样的:

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

你可能会感兴趣的是bigfloat模块(没有亲自使用过,只是知道它的存在:)-实际上在过去安装它时遇到了问题-可能是OS X的错误)

fhity93d

fhity93d5#

在Squeak Smalltalk中,如果整数接收方是某个整数的n次幂,则存在nthRoot:消息,该消息回答精确的Integer结果,然而,如果解是代数根,则实现不后退到简单的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

这也可以应用于Fraction,但是最近的浮点数有点复杂,而且Squeak的实现目前还很幼稚。
它适用于大整数,如:

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

如果你没有这样的期望,初始猜测可以使用不精确的朴素n**(1/exp)
代码应该很容易移植到Python中,并留有很多优化的地方。
我没有检查Python中有什么可用的,但是也许你需要正确地舍入LargeInteger -〉Float和Fraction -〉Float,就像这里解释的那样(Smalltalk也是,抱歉,但是语言并不重要)。

z8dt9xmd

z8dt9xmd6#

带有num7包的root_i()方法可以计算python3中的精确n次根,如以下3个对大十进制数的计算:

#ROOT ITH
from num7 import Num

def main():
    E = 8; n = '123.456'
    n = Num(n)**E; n = Num(n); ITH = E
    print(n, 'n_len =>', n.len())
    r = n.root_i(ITH)
    print(f'root {E}th =>', r, 'r_len =>', r.len(), 'TEST =>', Num(r)**E==n)
    print('-'*20)
    
    E = 11; n = '-2.51'
    n = Num(n)**E; n = Num(n); ITH = E
    print(n, 'n_len =>', n.len())
    r = n.root_i(ITH)
    print(f'root {E}th =>', r, 'r_len =>', r.len(), 'TEST =>', Num(r)**E==n)
    print('-'*20)
    
    E = 17; ni = 99999377777
    n = ni**E; n = Num(n); ITH = E
    print(n, 'n_len =>', n.len())
    r = n.root_i(ITH)
    print(f'root {E}th =>', r, 'r_len =>', r.len(), 'TEST =>', ni**E==int(n))

if __name__ == '__main__':
    main()
    print('ROOTS ITH OVER')

答案:

  • 53963189778652575.835351234834193203593216 n_长度=〉(17,24)第八次根=〉123.456 r_长度=〉(3,3)测试=〉真实
  • -24912.1342886682932269065251 n_长度=〉(5,22)第11次的根=〉-2.51 r_长度=〉(1,2)测试=〉真
  • 999894227355232070560802471633758119122136452997047714883085983788069966555993362562111298820203740269923571875460828131363700652652875999885262315083 4378239672382087798737606758743312497.0 n_长度=〉(187,0)第17次的根=〉9999937777.0 r_长度=〉(11,0)测试=〉实际根

相关问题