21

log a bを計算しようとしています（整数ではなく浮動小数点を取得します）。私はこれをとして行うことを計画していましたlog(b)/log(a)。数学的に言えば、cmathこの計算を行うために任意の対数関数（基数2、e、または10）を使用できます。ただし、プログラム中にこの計算を頻繁に実行するので、そのうちの1つが他の計算よりも大幅に高速であるかどうか（または、より高速でありながら単純な方法がある場合はさらに良い）と考えていました。重要な場合は、aとbの両方が整数です。

4

5 に答える 5

15

まず、それぞれを事前に計算して、代わりにその式を1.0/log(a)掛けます。log(b)

編集：私は当初、自然対数（基数e）が最速であると述べましたが、基数2はプロセッサによって直接サポートされ、最速であると述べている人もいます。私はそれを疑う理由はありません。

編集2：私はもともとそれaが一定であると思っていましたが、決して述べられていない質問を読み直しました。もしそうなら、事前計算するメリットはありません。ただし、そうである場合は、変数名を適切に選択することで読みやすさを維持できます。

const double base_a = 1.0 / log(a);
for (int b = 0; b < bazillions; ++b)
    double result = log(b) * base_a;

不思議なことに、Microsoftはベース2のログ関数を提供していません。これが、私がそれに慣れていない理由を説明しています。また、ログを計算するためのx86命令には自動的に乗算が含まれ、異なるベースに必要な定数は最適化された命令を介して利用できるため、3つの異なるログ関数のタイミングは同じであると予想されます（ベース2でも乗算する必要があります） 1）。

于 2011-07-11T20:09:10.110 に答える
11

bとaは整数であるため、ビットをいじるすべての栄光を使用して、基数2へのログを見つけることができます。

  • O（N）演算でMSB Nが設定されている整数の対数基数2を見つけます（明白な方法）
  • 64ビットIEEE浮動小数点数を使用して整数の2を底とする整数の対数を求めます
  • ルックアップテーブルを使用して整数の対数基数2を検索します
  • O（lg（N））演算でNビット整数の対数基数2を求めます
  • 乗算とルックアップを使用して、O（lg（N））演算でNビット整数の対数基数2を見つけます

ニーズに最適な「高速ログ」機能の選択はあなたにお任せします。

于 2011-07-11T20:18:19.980 に答える
4

私がデータを持っているプラ​​ットフォームでlog2は、私の期待に沿って、他のプラットフォームよりもわずかに高速です。ただし、違いはごくわずかであることに注意してください（わずか数パーセント）。これは本当に心配する価値はありません。

明確な実装を記述します。次に、パフォーマンスを測定します。

于 2011-07-11T20:13:23.297 に答える
1

8087命令セットには、2を底とする対数の命令しかないので、これが最速だと思います。

もちろん、この種の質問はプロセッサ/アーキテクチャに大きく依存するため、簡単なテストを行って時間を計ることをお勧めします。

于 2011-07-11T20:14:21.313 に答える
0

答えは次のとおりです。

  • 場合によります
  • プロファイルする

CPUタイプ、変数タイプ、コンパイラフラグ、データレイアウトについても言及していません。これらの多くを並行して実行する必要がある場合は、SIMDオプションがあると確信しています。コンパイラーは、アライメントを使用し、単純なループ（または古風なアプローチが好きな場合はvalarray）をクリアする限り、それを最適化します。

おそらく、インテル®コンパイラーには、この分野のインテル®プロセッサー向けの特定のトリックがあります。

本当に必要な場合は、CUDAを使用してGPUを活用できます。

残念ながら、これらの命令セットが不足している場合は、ビットをいじくり回して、適切な近似を行うアルゴリズムを作成できると思います。この場合、2ログが他のどのベースログよりも高速になることを複数のアップルパイに賭けることができます

于 2011-07-11T20:11:46.477 に答える