3

非常に多くのログを見つけなければなりません。

私はこれをC++で行います

すでに掛け算、足し算、引き算、割り算の関数を作ったのですが、対数に問題がありました。コードは必要ありません。これらの関数を使用してコードを実行する方法について簡単なアイデアが必要です。

ありがとう。

PS申し訳ありませんが、私はあなたに言うのを忘れました：私はその数の2進対数だけを見つけなければなりません

PS-2ウィキペディアで見つけました：

int floorLog2(unsigned int n) {

if (n == 0)

  return -1;

int pos = 0;

if (n >= (1 <<16)) { n >>= 16; pos += 16; }

if (n >= (1 << 8)) { n >>=  8; pos +=  8; }

if (n >= (1 << 4)) { n >>=  4; pos +=  4; }

if (n >= (1 << 2)) { n >>=  2; pos +=  2; }

if (n >= (1 << 1)) {           pos +=  1; }

return pos;

}

大きな数字で作り直した場合、正しく動作しますか？

4

2 に答える 2

7

私はあなたがあなた自身のbignumクラスを書いていると思います。log2の積分結果のみを気にする場合、それは非常に簡単です。ゼロではない最上位桁のログを取得し、その1バイトの後に各バイトに8を追加します。これは、各バイトが0〜255の値を保持していることを前提としています。これらは±.5以内の精度ですが、非常に高速です。

[0][42][53] (10805 in bytes)
    log2(42) = 5
    + 8*1    = 8    (because of the one byte lower than MSB)
             = 13  (Actual: 13.39941145)

値が基数10桁を保持している場合、それはになりlog2(MSB)+3.32192809*num_digits_less_than_MSBます。

[0][5][7][6][2] (5762)
 log2(5)        =  2.321928095
 + 3.32192809*3 =  9.96578427  (because 3 digits lower than MSB)
                =  12.28771  (Actual: 12.49235395)
(only accurate for numbers with less than ~10 million digits)

ウィキペディアで見つけたアルゴリズムを使用した場合、それは非常に遅くなります。（ただし、小数が必要な場合は正確です）

MSBが小さい場合（まだ±.5以内ですが、それ以上ではありません）、私の方法は不正確であると指摘されていますが、これは、上位2バイトを1つの数値にシフトし、そのログを取得するだけで簡単に修正できます。その数より少ないバイトの乗算を実行します。これは0.5％以内の精度であり、通常の対数よりも大幅に高速であると思います。

[1][42][53] (76341 in bytes)
    log2(1*256+42) = ?
    log2(298) = 8.21916852046
    + 8*1     = 8    (because of the one byte lower than MSB)
              = 16.21916852046  (Actual: 16.2201704643)

基数10桁の場合、それはlog2( [mostSignificantDigit]*10+[secondMostSignifcantDigit] ) + 3.32192809*[remainingDigitCount]です。

それでもパフォーマンスが問題になる場合は、完全な対数関数を使用する代わりに、log2のルックアップテーブルを使用できます。

于 2011-11-22T20:09:10.123 に答える
3

「手作業」で対数を計算する方法を知りたいと思います。だから私はこれについて私が見つけたものをあなたに話します。

手作業で対数化する方法が説明されているここをご覧ください。これをアルゴリズムとして実装できます。これが「オイラーのやり方」による記事です。この記事も有望だと思います。

これを行うにはもっと洗練された方法があると思いますが、それらは非常に複雑なので、おそらくそれらを実装したくないでしょう。

于 2011-11-22T20:05:33.610 に答える