22

C# での計算速度の向上に関する SO の質問に対するこの回答で以前に説明した高速な Exp(x) 関数を試しています。

public static double Exp(double x)
{
  var tmp = (long)(1512775 * x + 1072632447);
  return BitConverter.Int64BitsToDouble(tmp << 32);
}

この式は、いくつかの IEEE 浮動小数点「トリック」を使用しており、主にニューラル セットでの使用を目的としています。この機能は、通常の機能よりも約 5 倍高速ですMath.Exp(x)

残念ながら、数値の精度は通常の関数に比べて -4% ~ +2%Math.Exp(x)です。理想的には、少なくともサブパーセントの範囲内の精度が必要です。

近似関数と通常の Exp 関数の商をプロットしました。グラフからわかるように、相対的な差は実質的に一定の頻度で繰り返されているように見えます。

高速と通常の exp 関数の商

この規則性を利用して、計算速度を大幅に低下させることなく「高速exp」関数の精度をさらに向上させることは可能ですか?それとも、精度向上の計算オーバーヘッドが元の式の計算ゲインを上回るでしょうか?

(補足として、同じ SO の質問で提案されている代替アプローチの 1 つも試しましたが、このアプローチは、少なくとも一般的なケースでは、C# では計算効率が悪いようです。)

5月14日更新

@Adriano からのリクエストに応じて、非常に単純なベンチマークを実行しました。[-100, 100] の範囲の浮動小数点値に対して代替の各exp関数を使用して、1,000 万回の計算を実行しました。関心のある値の範囲は -20 から 0 までであるため、x = -5 の関数値も明示的にリストしました。結果は次のとおりです。

      Math.Exp: 62.525 ms, exp(-5) = 0.00673794699908547
Empty function: 13.769 ms
     ExpNeural: 14.867 ms, exp(-5) = 0.00675211846828461
    ExpSeries8: 15.121 ms, exp(-5) = 0.00641270968867667
   ExpSeries16: 32.046 ms, exp(-5) = 0.00673666189488182
          exp1: 15.062 ms, exp(-5) = -12.3333325982094
          exp2: 15.090 ms, exp(-5) = 13.708332516253
          exp3: 16.251 ms, exp(-5) = -12.3333325982094
          exp4: 17.924 ms, exp(-5) = 728.368055056781
          exp5: 20.972 ms, exp(-5) = -6.13293614238501
          exp6: 24.212 ms, exp(-5) = 3.55518353166184
          exp7: 29.092 ms, exp(-5) = -1.8271053775984
      exp7 +/-: 38.482 ms, exp(-5) = 0.00695945286970704

ExpNeuralは、このテキストの冒頭で指定したExp関数に相当します。ExpSeries8は、.NET ではあまり効率的ではないと私が最初に主張した定式化です。Neil とまったく同じように実装すると、実際には非常に高速でした。ExpSeries16は類似の式ですが、乗算は 8 回ではなく 16回です。exp1からexp7は、以下の Adriano の回答とは異なる関数です。exp7の最後のバリアントは、 xの符号がチェックされるバリアントです。負の場合、関数は1/exp(-x)代わりに戻ります。

残念ながら、AdrianoによってリストされたexpN関数はいずれも、私が検討しているより広い負の値の範囲では十分ではありません。Neil Coffeyによる級数展開アプローチは、「私の」値の範囲により適しているようですが、特に「8 つの」乗算のみを使用する場合、負のxが大きくなるとあまりにも急速に発散します。

4

5 に答える 5

14

テイラー級数の近似 (アドリアーノの回答expX()の関数など) は、ゼロ付近で最も正確であり、-20 または -5 でさえも大きなエラーが発生する可能性があります。入力が既知の範囲 (元の質問のように -20 から 0 など) の場合、小さなルックアップ テーブルと 1 つの追加の乗算を使用して、精度を大幅に向上させることができます。

秘訣は、exp() が整数部分と小数部分に分離できることを認識することです。例えば:

exp(-2.345) = exp(-2.0) * exp(-0.345)

小数部分は常に -1 から 1 の間になるため、テイラー級数の近似はかなり正確になります。整数部分には、exp(-20) から exp(0) までの 21 の可能な値しかないため、これらは小さなルックアップ テーブルに格納できます。

于 2013-01-03T16:40:28.393 に答える
13

次の代替案を試してください (exp1より高速で、exp7より正確です)。

コード

public static double exp1(double x) { 
    return (6+x*(6+x*(3+x)))*0.16666666f; 
}

public static double exp2(double x) {
    return (24+x*(24+x*(12+x*(4+x))))*0.041666666f;
}

public static double exp3(double x) {
    return (120+x*(120+x*(60+x*(20+x*(5+x)))))*0.0083333333f;
}

public static double exp4(double x) {
    return 720+x*(720+x*(360+x*(120+x*(30+x*(6+x))))))*0.0013888888f;
}

public static double exp5(double x) {
    return (5040+x*(5040+x*(2520+x*(840+x*(210+x*(42+x*(7+x)))))))*0.00019841269f;
}

public static double exp6(double x) {
    return (40320+x*(40320+x*(20160+x*(6720+x*(1680+x*(336+x*(56+x*(8+x))))))))*2.4801587301e-5;
}

public static double exp7(double x) {
  return (362880+x*(362880+x*(181440+x*(60480+x*(15120+x*(3024+x*(504+x*(72+x*(9+x)))))))))*2.75573192e-6;
}

精度

[-1...1] の関数エラー [3.14...3.14] のエラー

exp1 0.05 1.8% 8.8742 38.40%
exp2 0.01 0.36% 4.8237 20.80%
exp3 0.0016152 0.59% 2.28 9.80%
exp4 0.0002263 0.0083% 0.9488 4.10%
exp5 0.0000279 0.001% 0.3516 1.50%
exp6 0.0000031 0.00011% 0.1172 0.50%
exp7 0.0000003 0.000011% 0.0355 0.15%

クレジット
のこれらの実装はexp()、"fuzzpilz" の実装からテイラー級数を使用して "scoofy" によって計算されましたtanh()(それらが誰であれ、コードにこれらの参照がありました)。

于 2012-05-11T13:43:10.050 に答える
11

質問に示されている相対誤差関数を複製したい場合は、Matlab を使用する方法を次に示します (Matlab では「高速」指数はそれほど高速ではありませんが、正確です)。

t = 1072632447+[0:ceil(1512775*pi)];
x = (t - 1072632447)/1512775;
ex = exp(x);
t = uint64(t);
import java.lang.Double;
et = arrayfun( @(n) java.lang.Double.longBitsToDouble(bitshift(n,32)), t );
plot(x, et./ex);

tmpここで、エラーの期間は、 のバイナリ値が仮数部から指数部にオーバーフローする時期と正確に一致します。指数となるビットを破棄して (周期的に)、残りの上位 8 ビットのみを保持して (ルックアップ テーブルを妥当なサイズにする)、データをビンに分割してみましょう。

index = bitshift(bitand(t,uint64(2^20-2^12)),-12) + 1;

ここで、必要な調整の平均を計算します。

relerrfix = ex./et;
adjust = NaN(1,256);
for i=1:256; adjust(i) = mean(relerrfix(index == i)); end;
et2 = et .* adjust(index);

相対誤差は +/- .0006 に減少します。もちろん、他のテーブル サイズも可能であり (たとえば、64 エントリの 6 ビット テーブルは +/- .0025 になります)、エラーはテーブル サイズにほぼ比例します。テーブル エントリ間の線形補間により、エラーはさらに改善されますが、パフォーマンスが犠牲になります。精度の目標はすでに達成しているので、これ以上のパフォーマンスの低下は避けましょう。

この時点で、MatLab によって計算された値を取得し、C# でルックアップ テーブルを作成するのは、編集者の簡単なスキルです。計算ごとに、ビットマスク、テーブル ルックアップ、および倍精度乗算を追加します。

static double FastExp(double x)
{
    var tmp = (long)(1512775 * x + 1072632447);
    int index = (int)(tmp >> 12) & 0xFF;
    return BitConverter.Int64BitsToDouble(tmp << 32) * ExpAdjustment[index];
}

スピードアップは元のコードと非常に似ています。私のコンピューターでは、x86 としてコンパイルすると約 30% 速くなり、x64 では約 3 倍速くなります。ideone の mono では、実質的な純損失です (ただし、元の も同様です)。

完全なソース コードとテストケース: http://ideone.com/UwNgx

using System;
using System.Diagnostics;

namespace fastexponent
{
    class Program
    {
        static double[] ExpAdjustment = new double[256] {
            1.040389835,
            1.039159306,
            1.037945888,
            1.036749401,
            1.035569671,
            1.034406528,
            1.033259801,
            1.032129324,
            1.031014933,
            1.029916467,
            1.028833767,
            1.027766676,
            1.02671504,
            1.025678708,
            1.02465753,
            1.023651359,
            1.022660049,
            1.021683458,
            1.020721446,
            1.019773873,
            1.018840604,
            1.017921503,
            1.017016438,
            1.016125279,
            1.015247897,
            1.014384165,
            1.013533958,
            1.012697153,
            1.011873629,
            1.011063266,
            1.010265947,
            1.009481555,
            1.008709975,
            1.007951096,
            1.007204805,
            1.006470993,
            1.005749552,
            1.005040376,
            1.004343358,
            1.003658397,
            1.002985389,
            1.002324233,
            1.001674831,
            1.001037085,
            1.000410897,
            0.999796173,
            0.999192819,
            0.998600742,
            0.998019851,
            0.997450055,
            0.996891266,
            0.996343396,
            0.995806358,
            0.995280068,
            0.99476444,
            0.994259393,
            0.993764844,
            0.993280711,
            0.992806917,
            0.992343381,
            0.991890026,
            0.991446776,
            0.991013555,
            0.990590289,
            0.990176903,
            0.989773325,
            0.989379484,
            0.988995309,
            0.988620729,
            0.988255677,
            0.987900083,
            0.987553882,
            0.987217006,
            0.98688939,
            0.98657097,
            0.986261682,
            0.985961463,
            0.985670251,
            0.985387985,
            0.985114604,
            0.984850048,
            0.984594259,
            0.984347178,
            0.984108748,
            0.983878911,
            0.983657613,
            0.983444797,
            0.983240409,
            0.983044394,
            0.982856701,
            0.982677276,
            0.982506066,
            0.982343022,
            0.982188091,
            0.982041225,
            0.981902373,
            0.981771487,
            0.981648519,
            0.981533421,
            0.981426146,
            0.981326648,
            0.98123488,
            0.981150798,
            0.981074356,
            0.981005511,
            0.980944219,
            0.980890437,
            0.980844122,
            0.980805232,
            0.980773726,
            0.980749562,
            0.9807327,
            0.9807231,
            0.980720722,
            0.980725528,
            0.980737478,
            0.980756534,
            0.98078266,
            0.980815817,
            0.980855968,
            0.980903079,
            0.980955475,
            0.981017942,
            0.981085714,
            0.981160303,
            0.981241675,
            0.981329796,
            0.981424634,
            0.981526154,
            0.981634325,
            0.981749114,
            0.981870489,
            0.981998419,
            0.982132873,
            0.98227382,
            0.982421229,
            0.982575072,
            0.982735318,
            0.982901937,
            0.983074902,
            0.983254183,
            0.983439752,
            0.983631582,
            0.983829644,
            0.984033912,
            0.984244358,
            0.984460956,
            0.984683681,
            0.984912505,
            0.985147403,
            0.985388349,
            0.98563532,
            0.98588829,
            0.986147234,
            0.986412128,
            0.986682949,
            0.986959673,
            0.987242277,
            0.987530737,
            0.987825031,
            0.988125136,
            0.98843103,
            0.988742691,
            0.989060098,
            0.989383229,
            0.989712063,
            0.990046579,
            0.990386756,
            0.990732574,
            0.991084012,
            0.991441052,
            0.991803672,
            0.992171854,
            0.992545578,
            0.992924825,
            0.993309578,
            0.993699816,
            0.994095522,
            0.994496677,
            0.994903265,
            0.995315266,
            0.995732665,
            0.996155442,
            0.996583582,
            0.997017068,
            0.997455883,
            0.99790001,
            0.998349434,
            0.998804138,
            0.999264107,
            0.999729325,
            1.000199776,
            1.000675446,
            1.001156319,
            1.001642381,
            1.002133617,
            1.002630011,
            1.003131551,
            1.003638222,
            1.00415001,
            1.004666901,
            1.005188881,
            1.005715938,
            1.006248058,
            1.006785227,
            1.007327434,
            1.007874665,
            1.008426907,
            1.008984149,
            1.009546377,
            1.010113581,
            1.010685747,
            1.011262865,
            1.011844922,
            1.012431907,
            1.013023808,
            1.013620615,
            1.014222317,
            1.014828902,
            1.01544036,
            1.016056681,
            1.016677853,
            1.017303866,
            1.017934711,
            1.018570378,
            1.019210855,
            1.019856135,
            1.020506206,
            1.02116106,
            1.021820687,
            1.022485078,
            1.023154224,
            1.023828116,
            1.024506745,
            1.025190103,
            1.02587818,
            1.026570969,
            1.027268461,
            1.027970647,
            1.02867752,
            1.029389072,
            1.030114973,
            1.030826088,
            1.03155163,
            1.032281819,
            1.03301665,
            1.033756114,
            1.034500204,
            1.035248913,
            1.036002235,
            1.036760162,
            1.037522688,
            1.038289806,
            1.039061509,
            1.039837792,
            1.040618648
        };

        static double FastExp(double x)
        {
            var tmp = (long)(1512775 * x + 1072632447);
            int index = (int)(tmp >> 12) & 0xFF;
            return BitConverter.Int64BitsToDouble(tmp << 32) * ExpAdjustment[index];
        }

        static void Main(string[] args)
        {
            double[] x = new double[1000000];
            double[] ex = new double[x.Length];
            double[] fx = new double[x.Length];
            Random r = new Random();
            for (int i = 0; i < x.Length; ++i)
                x[i] = r.NextDouble() * 40;

            Stopwatch sw = new Stopwatch();
            sw.Start();
            for (int j = 0; j < x.Length; ++j)
                ex[j] = Math.Exp(x[j]);
            sw.Stop();
            double builtin = sw.Elapsed.TotalMilliseconds;
            sw.Reset();
            sw.Start();
            for (int k = 0; k < x.Length; ++k)
                fx[k] = FastExp(x[k]);
            sw.Stop();
            double custom = sw.Elapsed.TotalMilliseconds;

            double min = 1, max = 1;
            for (int m = 0; m < x.Length; ++m) {
                double ratio = fx[m] / ex[m];
                if (min > ratio) min = ratio;
                if (max < ratio) max = ratio;
            }

            Console.WriteLine("minimum ratio = " + min.ToString() + ", maximum ratio = " + max.ToString() + ", speedup = " + (builtin / custom).ToString());
         }
    }
}
于 2012-05-29T02:44:55.490 に答える
7

次のコードは、[-87,88] の入力の場合、結果の相対誤差 <= 1.73e-3 であるため、精度要件に対処する必要があります。私は C# を知らないので、これは C コードですが、変換はかなり簡単だと思います。

精度要件は低いので、単精度計算の使用は問題ないと思います。exp() の計算が exp2() の計算にマップされる古典的なアルゴリズムが使用されています。log2(e) に​​よる乗算による引数変換の後、小数部分によるべき乗は次数 2 のミニマックス多項式を使用して処理されますが、引数の整数部分によるべき乗は IEEE-754 シングルの指数部分の直接操作によって実行されます。 -正確な数。

揮発性共用体は、指数操作に必要な整数または単精度浮動小数点数としてのビット パターンの再解釈を容易にします。C# は、これに対して決定された再解釈関数を提供しているように見えますが、これははるかにクリーンです。

2 つの潜在的なパフォーマンスの問題は、floor() 関数と float->int 変換です。従来、動的なプロセッサ状態を処理する必要があるため、x86 ではどちらも低速でした。しかし、SSE (特に SSE 4.1) は、これらの操作を高速にするための命令を提供します。C# がこれらの命令を利用できるかどうかはわかりません。

 /* max. rel. error <= 1.73e-3 on [-87,88] */
 float fast_exp (float x)
 {
   volatile union {
     float f;
     unsigned int i;
   } cvt;

   /* exp(x) = 2^i * 2^f; i = floor (log2(e) * x), 0 <= f <= 1 */
   float t = x * 1.442695041f;
   float fi = floorf (t);
   float f = t - fi;
   int i = (int)fi;
   cvt.f = (0.3371894346f * f + 0.657636276f) * f + 1.00172476f; /* compute 2^f */
   cvt.i += (i << 23);                                          /* scale by 2^i */
   return cvt.f;
 }
于 2012-05-29T02:06:57.733 に答える
3

上記の関数の元の C 実装がより詳細に定義されている Nicol Schraudolphの論文を調べました。パフォーマンスに深刻な影響を与えずにexp計算の精度を実質的に承認することはおそらく不可能であるように思われます。一方、近似は最大 +/- 700 までの大きなxに対しても有効であり、もちろん有利です。

上記の関数の実装は、二乗平均平方根誤差が最小になるように調整されています。Schraudolph は、tmp式の加法的項を変更して、別の近似特性を実現する方法を説明しています。

"exp" >= exp for all x                      1072693248 -  (-1) = 1072693249
"exp" <= exp for all x                                 - 90253 = 1072602995
"exp" symmetric around exp                             - 45799 = 1072647449
Mimimum possible mean deviation                        - 68243 = 1072625005
Minimum possible root-mean-square deviation            - 60801 = 1072632447

彼はまた、 longからdoubleへの変換で 32 ビットが破棄されるため、「微視的な」レベルでは近似の「exp」関数が階段状の動作を示すことも指摘しています。これは、関数が非常に小さいスケールでは区分的に一定であることを意味しますが、少なくともxの増加に伴って関数が減少することはありません。

于 2012-05-17T13:08:50.600 に答える