浮動小数点演算またはlongを使用しないfloor（log2（5^x））の整数値の計算方法は問題です。整数計算？私は、シンプルで効率的で数学的にエレガントな方法を探しています。浮動小数点演算または長整数計算を使用しないfloor（log2（5 ** x））の計算方法
観察： 式はわずか5のビット数** X（プラス1）
試みである： 私はそれを簡素化しようとした： 床（図示X *のLOG2（5））
私の場合、xは非常に大きくなく、たぶんわずか1〜100です。小さな値を扱うエレガントな式で十分ですが、xの任意の値に対して有効な数式/アルゴリズムに興味があります
私は普遍番号（タイプIII）の参照ソフトウェア実装を行っています。純粋にビットごとの基本操作を使用して、すべてを簡単にマイクロコードに変換できるようにしたいと考えています。これは私が簡略化する必要がある式の一つです。
...
floor(x*log2(5))
xが整数の100に1値があるので、様々なテストは、整数乗算を使用する「最良の」見つけるために作られたためにすることができますpower_of_2で割ります。
f(x) = x*a integer_divide power_of_2
f(x) = floor(x*log2(5)) = floor(x*some_float_c)についてsome_float_cの値は100、最小及び以下の最大値によって制限されます。
x f(x) mn mx
f(x)/x (f(x) + 1)/x
1 2 2.00000 3.00000
2 4 2.00000 2.50000
3 6 2.00000 2.33333
...
59 136 2.30508 2.32203
...
87 202 2.32184 2.33333
...
98 227 2.31633 2.32653
99 229 2.31313 2.32323
100 232 2.32000 2.33000
、最大minは2.32184、最小最大の2.32203です：
2.32184... <= some_float_c < 2.32203...
我々はfloatを使用することはできませんので、some_integer/some_power_of_2
2.32184... <= some_integer/some_power_of_2 < 2.32203...
ceil(some_power_of_2 * 2.32184...) <= some_integer < floor(some_power_of_2 * 2.32203...)
min max
2.32184 2.32203
2 5 4
4 10 9
8 19 18
...
1024 2378 2377
2048 4756 4755
4096 9511 9511 < first one where min <= max
8192 19021 19022
見つけるので9511/4096は "最も簡単" で、 「最良の」候補者である。
f(x) = (x*9511) integer_divide_by_power_of_2 4096
// In C
unsigned y = (x*9511u) >> 12;
正確には、log2(5**x) == x * log2(5)に注意してください。 log2(5)は定数であり、これは2.3219281に近似することができます。
ただし、質問ごとに浮動小数点数は許可されません。問題ない！整数除算ではなく、フロートなりscaleで割ること、result % scaleによってresultを減少させることによって
log2_5 = 23219281;
scale = 10000000; // note log2_5/scale is the actual value
result = x * log2_5;
output = (result - (result % scale))/scale;
。ここで
は非常に粗い近似であるが、あなたはn個の電源を高めるためだから、精神的に
5^3 = 125
2^7 = 128
それを取得する場合、それは助けることができます。
5^n ~~ 2^(7n/3)
だから、5^12れます2^28の近くには29ビットまでが必要です。
2^7> 5^3なので、少し大きめです.28ビットで十分ですので、端数を上に丸めるのが良い方法です。
私はSmalltalkの中で評価された場合：
(1 to: 50) reject: [:i | (5 raisedTo: i) highBit = (i*7/3) ceiling].
私が手：
#(31 34 37 40 43 46 49)
あなたは非常に単純な製剤はそれほど悪くされていない5^30までに動作していることがわかります。 、シンプル、効率的かつ数学的にエレガントな方法について
5 ** xのビット数は、フロアではなく、天井（x * log2（5））です。 5 ** 1を格納するには3ビットが必要です。 –
私はそれが床（x * log2（5））+ 1だと思います。 編集：うん、私の右のように思える。 f（2）= f（3）は、floorを使用して1を加算すると動作しますが、ceilでは動作しません。 – Mercado
あなたは正しいと思います。 4はそれを格納するために3ビットを必要とする。 –