9

そのため、操作は2次式であるように見えるため、 .net4のBigIntegerクラスが提供する操作の一部を改善しようとしています。大まかなカラツバの実装を行いましたが、それでも予想よりも遅いです。

主な問題は、BigIntegerがビット数をカウントする簡単な方法を提供していないことであると思われるため、BigInteger.Log（...、2）を使用する必要があります。Visual Studioによると、時間の約80〜90％が対数の計算に費やされています。

using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using System.Numerics;

namespace Test
{
    class Program
    {
        static BigInteger Karatsuba(BigInteger x, BigInteger y)
        {
            int n = (int)Math.Max(BigInteger.Log(x, 2), BigInteger.Log(y, 2));
            if (n <= 10000) return x * y;

            n = ((n+1) / 2);

            BigInteger b = x >> n;
            BigInteger a = x - (b << n);
            BigInteger d = y >> n;
            BigInteger c = y - (d << n);

            BigInteger ac = Karatsuba(a, c);
            BigInteger bd = Karatsuba(b, d);
            BigInteger abcd = Karatsuba(a+b, c+d);

            return ac + ((abcd - ac - bd) << n) + (bd << (2 * n));
        }

        static void Main(string[] args)
        {
            BigInteger x = BigInteger.One << 500000 - 1;
            BigInteger y = BigInteger.One << 600000 + 1;
            BigInteger z = 0, q;

            Console.WriteLine("Working...");
            DateTime t;

            // Test standard multiplication
            t = DateTime.Now;
            z = x * y;
            Console.WriteLine(DateTime.Now - t);

            // Test Karatsuba multiplication
            t = DateTime.Now;
            q = Karatsuba(x, y);
            Console.WriteLine(DateTime.Now - t);

            // Check they're equal
            Console.WriteLine(z == q);

            Console.Read();
        }
    }
}

それで、私はそれをスピードアップするために何ができますか？

4

1 に答える 1

13

なぜすべてのビットを数えるのですか?

vbで私はこれを行います:

<Runtime.CompilerServices.Extension()> _
Function BitLength(ByVal n As BigInteger) As Integer
    Dim Data() As Byte = n.ToByteArray
    Dim result As Integer = (Data.Length - 1) * 8
    Dim Msb As Byte = Data(Data.Length - 1)
    While Msb
        result += 1
        Msb >>= 1
    End While
    Return result
End Function

C# では次のようになります。

public static int BitLength(this BigInteger n)
{
    byte[] Data = n.ToByteArray();
    int result = (Data.Length - 1) * 8;
    byte Msb = Data[Data.Length - 1];
    while (Msb != 0) {
        result += 1;
        Msb >>= 1;
    }
    return result;
}

ついに...

    static BigInteger Karatsuba(BigInteger x, BigInteger y)
    {
        int n = (int)Math.Max(x.BitLength(), y.BitLength());
        if (n <= 10000) return x * y;

        n = ((n+1) / 2);

        BigInteger b = x >> n;
        BigInteger a = x - (b << n);
        BigInteger d = y >> n;
        BigInteger c = y - (d << n);

        BigInteger ac = Karatsuba(a, c);
        BigInteger bd = Karatsuba(b, d);
        BigInteger abcd = Karatsuba(a+b, c+d);

        return ac + ((abcd - ac - bd) << n) + (bd << (2 * n));
    }

拡張メソッドを呼び出すと処理が遅くなる可能性があるため、おそらくこれはより高速です。

int n = (int)Math.Max(BitLength(x), BitLength(y));

参考までに: ビット長法を使用すると、BigInteger メソッドよりもはるかに高速に対数の適切な近似値を計算することもできます。

bits = BitLength(a) - 1;
log_a = (double)i * log(2.0);

BigInteger 構造体の内部 UInt32 配列にアクセスする限り、これはそのためのハックです。

リフレクション名前空間をインポートする

Private Shared ArrM As MethodInfo
Private Shard Bits As FieldInfo
Shared Sub New()
    ArrM = GetType(System.Numerics.BigInteger).GetMethod("ToUInt32Array", BindingFlags.NonPublic Or BindingFlags.Instance)
    Bits = GetType(System.Numerics.BigInteger).GetMember("_bits", BindingFlags.NonPublic Or BindingFlags.Instance)(0)

End Sub
<Extension()> _
Public Function ToUInt32Array(ByVal Value As System.Numerics.BigInteger) As UInteger()
    Dim Result() As UInteger = ArrM.Invoke(Value, Nothing)
    If Result(Result.Length - 1) = 0 Then
        ReDim Preserve Result(Result.Length - 2)
    End If
    Return Result
End Function

次に、大きな整数の基になる UInteger() を次のように取得できます。

 Dim Data() As UInteger = ToUInt32Array(Value)
 Length = Data.Length

または交互に

Dim Data() As UInteger = Value.ToUInt32Array()

_bits fieldinfo を使用して、基になる BigInteger 構造体の UInteger() _bits フィールドに直接アクセスできることに注意してください。これは、ToUInt32Array() メソッドを呼び出すよりも高速です。ただし、BigInteger B <= UInteger.MaxValue _bits の場合は何もありません。BigInteger が 32 ビット (マシン サイズ) ワードのサイズに収まるときの最適化として、MS が返すネイティブ データ型を使用して通常のマシン ワード演算を実行すると思われます。

通常はリフレクションを使用できるため、_bits.SetValue(B, Data()) も使用できませんでした。これを回避するには、オーバーヘッドのある BigInteger(bytes() b) コンストラクターを使用します。C# では、安全でないポインター操作を使用して、UInteger() を Byte() にキャストできます。VB にはポインター操作がないため、Buffer.BlockCopy を使用します。この方法でデータにアクセスする場合、bytes() 配列の MSB が設定されている場合、MS はそれを負の数として解釈することに注意することが重要です。別の符号フィールドを持つコンストラクターを作成することをお勧めします。ワード配列は、MSBのチェックを外すために0バイトを追加することです

また、二乗するとさらに改善できます

 Function KaratsubaSquare(ByVal x As BigInteger)
    Dim n As Integer = BitLength(x) 'Math.Max(BitLength(x), BitLength(y))

    If (n <= KaraCutoff) Then Return x * x
    n = ((n + 1) >> 1)

    Dim b As BigInteger = x >> n
    Dim a As BigInteger = x - (b << n)
    Dim ac As BigInteger = KaratsubaSquare(a)
    Dim bd As BigInteger = KaratsubaSquare(b)
    Dim c As BigInteger = Karatsuba(a, b)
    Return ac + (c << (n + 1)) + (bd << (2 * n))

End Function

これにより、乗算アルゴリズムの各再帰から 2 回のシフト、2 回の加算、および 3 回の減算が不要になります。

于 2011-02-20T04:50:14.217 に答える