4

2 の 10,000,000 乗のオーダーの数値を持つ BigInteger クラスを扱っています。

BigInteger Log 関数は現在、私のアルゴリズムで最もコストのかかる関数であり、代替手段を必死に探しています。

ログの不可欠な部分だけが必要なので、速度の点では素晴らしいと思われるこの回答に出くわしましたが、何らかの理由で正確な値が得られません。小数部分は気にしませんが、値が下限か上限かを知っている限り、正確な整数部分を取得する必要があります。

実装した関数は次のとおりです。

public static double LogBase2 (System.Numerics.BigInteger number)
{
    return (LogBase2(number.ToByteArray()));
}

public static double LogBase2 (byte [] bytes)
{
    // Corrected based on [ronalchn's] answer.
    return (System.Math.Log(bytes [bytes.Length - 1], 2) + ((bytes.Length - 1) * 8));
}

まれなケースを除いて、値は非常に正確になりました。7 ～ 7.99999、15 ～ 15.9999、23 ～ 23.9999、31 ～ 31.9999 などの値は -Infinity を返します。数値はバイト境界を中心に展開しているようです。ここで何が起こっているのか分かりますか？

例：

LogBase2(                    1081210289) = 30.009999999993600 != 30.000000000000000
LogBase2(                    1088730701) = 30.019999999613300 != 30.000000000000000
LogBase2(                    2132649894) = 30.989999999389400 != 30.988684686772200
LogBase2(                    2147483648) = 31.000000000000000 != -Infinity
LogBase2(                    2162420578) = 31.009999999993600 != -Infinity
LogBase2(                    4235837212) = 31.979999999984800 != -Infinity
LogBase2(                    4265299789) = 31.989999999727700 != -Infinity
LogBase2(                    4294967296) = 32.000000000000000 != 32.000000000000000
LogBase2(                    4324841156) = 32.009999999993600 != 32.000000000000000
LogBase2(                  545958373094) = 38.989999999997200 != 38.988684686772200
LogBase2(                  549755813887) = 38.999999999997400 != 38.988684686772200
LogBase2(                  553579667970) = 39.009999999998800 != -Infinity
LogBase2(                  557430119061) = 39.019999999998900 != -Infinity
LogBase2(                  561307352157) = 39.029999999998300 != -Infinity
LogBase2(                  565211553542) = 39.039999999997900 != -Infinity
LogBase2(                  569142910795) = 39.049999999997200 != -Infinity
LogBase2(                 1084374326282) = 39.979999999998100 != -Infinity
LogBase2(                 1091916746189) = 39.989999999998500 != -Infinity
LogBase2(                 1099511627775) = 39.999999999998700 != -Infinity
4

2 に答える 2

10

これを試して：

public static int LogBase2(byte[] bytes)
{
    if (bytes[bytes.Length - 1] >= 128) return -1; // -ve bigint (invalid - cannot take log of -ve number)
    int log = 0;
    while ((bytes[bytes.Length - 1]>>log)>0) log++;
    return log + bytes.Length*8-9;
}

最上位バイトが 0 である理由は、BigInteger が符号付き整数であるためです。上位バイトの最上位ビットが 1 の場合、正の整数の符号ビット 0 を表すために追加のバイトが追加されます。

また、丸められた値のみが必要な場合は、ビット操作を使用する方がはるかに高速であるため、System.Math.Log 関数の使用から変更されました。

Microsoft Solver Foundation ( http://msdn.microsoft.com/en-us/devlabs/hh145003.aspxからダウンロード) がある場合は、BitCount() 関数を使用できます。

public static double LogBase2(Microsoft.SolverFoundation.Common.BigInteger number)
{
    return number.BitCount;
}

または、Java ライブラリを使用できます。vjslib ライブラリへの参照を追加します ([.NET] タブにあります - これは Java ライブラリの J# 実装です)。

コードに「using java.math」を追加できるようになりました。

java.math.BigInteger には bitLength() 関数があります

于 2012-08-17T10:09:33.527 に答える
4 
BigInteger bi = new BigInteger(128);   
int log =  bi.Log2();

public static class BigIntegerExtensions
{
    static int[] PreCalc = new int[] { 8, 7, 6, 6, 5, 5, 5, 5, 4, 4, 4, 4, 4, 4, 4, 4, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1};
    public static int Log2(this BigInteger bi)
    {
        byte[] buf = bi.ToByteArray();
        int len = buf.Length;
        return len * 8 - PreCalc[buf[len - 1]] - 1;
    }
}
于 2012-08-17T11:04:01.417 に答える