Зачем считать все биты?
В 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
В С# это будет:
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);
Что касается доступа к внутреннему массиву UInt32 структуры BigInteger, вот хак для этого.
импортировать пространство имен отражения
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 можно использовать для прямого доступа к базовому полю _bits UInteger() структуры BigInteger. Это быстрее, чем вызов метода ToUInt32Array(). Однако, когда BigInteger B ‹= UInteger.MaxValue _bits ничего не значит. Я подозреваю, что в качестве оптимизации, когда BigInteger соответствует размеру 32-битного (размер машины) слова, MS возвращает обычную арифметику машинного слова, используя собственный тип данных.
Я также не смог использовать _bits.SetValue(B, Data()), как вы обычно могли бы использовать отражение. Чтобы обойти это, я использую конструктор BigInteger(bytes() b), у которого есть накладные расходы. В С# вы можете использовать небезопасные операции с указателями для приведения UInteger() к Byte(). Поскольку в VB нет операций с указателями, я использую Buffer.BlockCopy. При доступе к данным таким образом важно отметить, что если MSB массива bytes() установлен, MS интерпретирует его как отрицательное число. Я бы предпочел, чтобы они сделали конструктор с отдельным полем знака. Массив слов должен добавить дополнительный 0 байт, чтобы снять отметку с MSB
Кроме того, при возведении в квадрат вы можете улучшить еще больше
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 вычитания из каждой рекурсии вашего алгоритма умножения.
person
Alexander Higgins
schedule
20.02.2011
<<
имеет более низкий приоритет, чем+
/-
- person BlueRaja - Danny Pflughoeft   schedule 20.02.2011