7

私はbcmath拡張機能のラッパーを書いていますが、バグ #10116bcpow()特に厄介です - $right_operand( $exp) を (ネイティブ PHP、任意の長さではない) 整数にキャストするため、平方根 (またはその他の任意の長さ) を計算しようとすると正しい結果ではなく、1常に最終的に得られる数の )より大きい根。1

数値の n 乗根を計算できるアルゴリズムを探し始めたところ、この答えはかなりしっかりしているように見えました。実際にWolframAlpha を使用して数式を拡張したところ、精度を維持しながら速度を約 5% 向上させることができました結果の。

これは、私の BCMath 実装とその制限を模倣した純粋な PHP 実装です。

function _pow($n, $exp)
{
    $result = pow($n, intval($exp)); // bcmath casts $exp to (int)

    if (fmod($exp, 1) > 0) // does $exp have a fracional part higher than 0?
    {
        $exp = 1 / fmod($exp, 1); // convert the modulo into a root (2.5 -> 1 / 0.5 = 2)

        $x = 1;
        $y = (($n * _pow($x, 1 - $exp)) / $exp) - ($x / $exp) + $x;

        do
        {
            $x = $y;
            $y = (($n * _pow($x, 1 - $exp)) / $exp) - ($x / $exp) + $x;
        } while ($x > $y);

        return $result * $x; // 4^2.5 = 4^2 * 4^0.5 = 16 * 2 = 32
    }

    return $result;
}

上記 、整数が得られない場合を除い1 / fmod($exp, 1)てうまく機能するようです。たとえば、$expisの場合0.123456、その逆は となり、と8.10005の結果は少し異なります ( demo ):pow()_pow()

  • pow(2, 0.123456)=1.0893412745953
  • _pow(2, 0.123456)=1.0905077326653
  • _pow(2, 1 / 8)= _pow(2, 0.125)=1.0905077326653

「手動」の指数計算を使用して同じレベルの精度を達成するにはどうすればよいですか?

4

1 に答える 1

5

(正の) 数の n乗根aを見つけるために使用されるアルゴリズムは、次のゼロを見つけるためのニュートン アルゴリズムです。

f(x) = x^n - a.

これには指数として自然数を持つ累乗のみが含まれるため、実装は簡単です。

が整数の形式0 < y < 1ではない指数を使用してべき乗を計算するのは、より複雑です。アナログをやって、解決するy1/nn

x^(1/y) - a == 0

再び非整数指数を使用して累乗を計算する必要があります。これはまさに私たちが解決しようとしている問題です。

y = n/dが分母が小さい有理数の場合d、問題は次の計算で簡単に解決されます。

x^(n/d) = (x^n)^(1/d),

しかし、ほとんどの有理数0 < y < 1では、分子と分母はかなり大きく、中間x^nは巨大になるため、計算には大量のメモリが使用され、(比較的) 長い時間がかかります。( の指数の例では0.123456 = 1929/15625、それほど悪くはありませんが、0.1234567かなり負担になります。)

一般有理数の累乗を計算する 1 つの方法0 < y < 1は、

y = 1/a ± 1/b ± 1/c ± ... ± 1/q

整数a < b < c < ... < qを使用して、個体を乗算/除算しますx^(1/k)。(すべての有理数0 < y < 1にはそのような表現があり、最短のそのような表現は一般に多くの用語を含みません。

1929/15625 = 1/8 - 1/648 - 1/1265625;

分解で足し算のみを使用すると、分母が大きくなり、表現が長くなります。

1929/15625 = 1/9 + 1/82 + 1/6678 + 1/46501020 + 1/2210396922562500,

そのため、より多くの作業が必要になります。)

アプローチを混合することにより、いくつかの改善が可能です。最初に、指数の例の場合、-yの継続的な分数展開を介して小さな分母を持つの近い有理近似を見つけ、最初の 4 つの部分商を使用すると、近似が得られます[注意してください、最短の部分和純粋な分数への分解は収束します] - 次に、残りを純粋な分数に分解します。y1929/15625 = [0;8,9,1,192]10/81 = 0.123456790123...10/81 = 1/8 - 1/648

ただし、一般に、このアプローチでは、大きなの n乗根nを計算することになり、最終結果の精度が高い場合は、これも遅くなり、メモリを大量に消費します。

exp全体として、実装しlogて使用する方がおそらく簡単で高速です

x^y = exp(y*log(x))
于 2012-05-10T01:03:38.497 に答える