7

Python の N 番目のルート関数/アルゴリズムを探していますが、投稿する前に: NO INTEGER ROOT, HELL! 正確な/を生成する N 番目のルート関数
をプログラムする方法のガイドを少なくともどこで入手できますか? 戻り値もforも返さない 関数(1 番目の引数は数値、2 番目はルートの深さ (または何か))。floatDecimal
10root(125, 1756482845)

編集:だから、あなたは私にこの解決策を与えていました:n ** (1.0 / exp)私はこの質問をしたときに知っていましたが、たとえばexp = 3. 1/3有理数で表現できないため125 ** (1/3)、間違った結果が得られ4.999999...ます。私はいくつかの「スマートな」アルゴリズムを求めていました。これは、そのような素敵な数値に対して正しい結果を出し、有理数に対して少なくとも4桁の正確な結果をもたらしexpます。そのような関数やアルゴリズムがない場合は、これを使用します ( n ** (1/exp))。

4

5 に答える 5

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 には、Integer 受信者が整数の正確な n 乗である場合nthRoot:に正確な結果を返すメッセージがあります。Integerただし、解が代数根の場合、実装はナイーブにフォールバックしませんn**(1/exp)。このメソッドは、残差を適切に処理して、最も近い float に丸めます。

関連するコード (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 にも適用できますが、最も近い float はもう少し複雑で、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 に答える