問題タブ [natural-logarithm]

切り捨てられたテイラー級数のパデ近似に基づく近似自然対数関数を実装しました。精度は許容範囲内 (±0.000025) ですが、数回の最適化にもかかわらず、実行時間は標準ライブラリln関数の約 2.5 倍です! 速くなく、正確でなければ意味がありません。それにもかかわらず、Rust コードを最適化する方法を学ぶ方法としてこれを使用しています。criterion(私のタイミングはクレートの使用から来ています。私はブラックボックスを使用し、ループ内の値を合計し、結果から文字列を作成してオプティマイザーを無効にしました。)

Rust Playground では、私のコードは次のとおりです。

https://play.rust-lang.org/?version=stable&mode=debug&edition=2018&gist=94246553cd7cc0c7a540dcbeff3667b9

アルゴリズム

符号なし整数の比率で機能する私のアルゴリズムの概要:

1. 値を超えない最大の 2 の累乗で除算することにより、区間 [1, 2] に範囲を縮小します。
   • 分子の表記を変更 →2ⁿ·N where 1 ≤ N ≤ 2
   • 分母の表記変更→2ᵈ·D where 1 ≤ D ≤ 2
2. これにより結果が得られますlog(numerator/denominator) = log(2ⁿ·N / 2ᵈ·D) = (n-d)·log(2) + log(N) - log(D)
3. log(N) を実行するために、テイラー級数は 0 付近では収束しませんが、1 付近では収束します...
4. ... N は 1 に近いので、x = N - 1 に置き換えて、log(1 + x) を評価する必要があります。
5. の置換を実行しますy = x/(2+x)
6. 関連する機能を検討するf(y) = Log((1+y)/(1-y))
   • = Log((1 + x/(2+x)) / (1 - x/(2+x)))
   • = Log( (2+2x) / 2)
   • = Log(1 + x)
7. f(y) には、Log(1+x) の展開よりも速く収束する必要があるテイラー展開があります ...
   • Log(1+x) の場合 →x - x²/2 + x³/3 - y⁴/4 + ...
   • Log((1+y)/(1-y)) の場合 →y + y³/3 + y⁵/5 + ...
8. 切り捨てられた系列にパデ近似を使用するy + y³/3 + y⁵/5 ...
9. ...どちらが2y·(15 - 4y²)/(15 - 9y²)
10. 分母について繰り返し、結果を結合します。

パデ近似

コードのパデ近似部分は次のとおりです。

明らかに、そこまで高速化する必要はありません。

上位ビット

これまでで最も大きな影響を与えた変更は、最上位ビットの位置を取得する計算を最適化したことです。範囲を縮小するにはそれが必要です。

これが私のmsb機能です：

さびた u64::next_power_of_two、安全でないコードと組み込み関数

これで、Rust には数値以上の最小の 2 乗を見つけるための高速な方法があることがわかりました。これが必要ですが、ビット位置も必要です。これは、数値の基数 2 の対数に相当するからです。(例: next_power_of_two(255) は 256 を生成しますが、8 番目のビットが設定されているため、8 が必要です。) のソース コードを見ると、next_power_of_twoというプライベート ヘルパー メソッド内に次の行がありますfn one_less_than_next_power_of_two。

同じ方法でビット位置を取得するために使用できる組み込み関数はありますか? 私がアクセスできるパブリックメソッドで使用されていますか? または、私が知らない組み込み関数を呼び出すための安全でないコードを作成する方法はありますか (これがほとんどです)。

私が呼び出すことができるそのようなメソッドまたは組み込み関数があれば、それが私のプログラムを大幅に高速化すると思いますが、おそらく他にも役立つことがあります。

アップデート：

頭叩き！63 - x.leading_zeros()最上位ビットの位置を見つけるために使用できます! 反対側から来るとは思いもしませんでした。これを試して、速度が上がるかどうかを確認します...

ベースラインを作成しています。このベースラインは、いくつかの変数で構成されています。これらの変数の一部は正の値ですが、他の変数は正と負の値を示します。ここに問題があります: 別のモデルに対してこれらの変数の対数変換を行う必要があります。どうすれば対処できますか？

すべての正/負ベクトルに絶対値 +1 の最小値を追加する必要がありますか? この場合、ベースラインが変更されます。使用する定数 (絶対値の最小値 +1) に再び比例させることはできますか?

よろしくお願いします。