6

およそ対数目盛にマッピングしたい32〜8191の範囲の整数値があります。2進数を使用している場合は、先行ゼロビットをカウントして8スロットにマップすることもできますが、これはあまりにもきめ細かいものです。32個のスロットが必要です（さらに多くのスロットが必要ですが、32ビット値のビットにマップする必要があります）。これは、対数で約1.18〜1.20のベースになります。誰かがこの値、または合理的な近似を非常に速く計算するためのいくつかのトリックを持っていますか？

私の直感は、範囲を条件付きの2つまたは3つのサブ範囲に分割し、それぞれに小さなルックアップテーブルを使用することですが、特に結果が正確である必要はありませんが、大まかに対数である必要があります。

4

3 に答える 3

4

先頭ビット以外の次の2ビットを使用してみませんか。最初に数値を8つのビンに分割し、次の2ビットで各ビンをさらに4つに分割できます。この場合、非常に高速な単純なシフト操作を使用できます。

編集：対数を使用することが実行可能な解決策であると考える場合。一般的なアルゴリズムは次のとおりです。

対数aの底とし、範囲は(b_min, b_max) = (32,8191)です。次の式を使用してベースを見つけることができます。

log(b_max/b_min) / log(a) = 32 bin

あなたに与えるa~1.1892026。これを対数の底として使用する場合、範囲(b_min, b_max)をにマップできます(log_a(b_min), log_a(b_max)) = (20.0004,52.0004)。

20.0004これで、範囲を取得するには、すべての要素をaで引くだけで済みます(0,32)。すべての要素が対数的に均一であることを保証します。終わり

注：数値エラーのため、いずれかの要素が範囲外になる可能性があります。正確な値については、自分で計算する必要があります。

注2： log_a（b）= log（b）/ log（a）

于 2010-12-11T04:52:39.610 に答える
2

テーブルルックアップは1つのオプションであり、そのテーブルはそれほど大きくありません。8Kテーブルが大きすぎて、先行ゼロのカウント命令がある場合は、上位数ビットでテーブルルックアップを使用できます。

nbits = 32 - count_leading_zeros(v)  # number of bits in number
highbits = v >> (nbits - 4)          # top 4 bits.  Top bit is always a 1.
log_base_2 = nbits + table[highbits & 0x7]

log_2の近似値を入力するテーブル

table[i] = approx(log_2(1 + i/8.0))

整数演算を続けたい場合は、最後の行に便利な係数を掛けます。

于 2010-12-11T04:53:29.863 に答える
2

回答IEEE754浮動小数点に基づいて思いついたのは次のとおりです。

((union { float v; uint32_t r; }){ x }.r >> 21 & 127) - 16

32-8192を0-31にほぼ対数的にマッピングします（hwlauの回答と同じ）。

改善されたバージョン（役に立たないビット単位の切り取りと）：

((union { float v; uint32_t r; }){ x }.r >> 21) - 528
于 2010-12-11T05:13:46.300 に答える