优化Karatsuba实施 [英] Optimizing Karatsuba Implementation
问题描述
因此，我正在尝试改进.net 4的BigInteger类提供的某些操作，因为这些操作似乎是二次的.我对Karatsuba进行了粗略的实现，但它仍然比我预期的要慢.
So, I'm trying to improve some of the operations that .net 4's BigInteger class provide since the operations appear to be quadratic. I've made a rough Karatsuba implementation but it's still slower than I'd expect.
主要问题似乎是BigInteger没有提供简单的方法来计算位数，因此，我必须使用BigInteger.Log(...，2).根据Visual Studio的说法，约有80-90％的时间用于计算对数.
The main problem seems to be that BigInteger provides no simple way to count the number of bits and, so, I have to use BigInteger.Log(..., 2). According to Visual Studio, about 80-90% of the time is spent calculating logarithms.
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();
}
}
}
那么，我该怎么做才能加快速度?
So, what can I do to speed it up?
推荐答案
为什么要计算所有位数?
Why count all of the bits?
在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));
}
调用扩展方法可能会减慢速度，因此可能会更快:
Calling the extension method may slow things down so perhaps this would be faster:
int n = (int)Math.Max(BitLength(x), BitLength(y));
FYI:使用位长方法，您还可以比BigInteger方法更快地计算出对数的近似值.
FYI: with the bit length method you can also calculate a good approximation of the log much faster than the BigInteger Method.
bits = BitLength(a) - 1;
log_a = (double)i * log(2.0);
就访问BigInteger结构的内部UInt32数组而言，这是一个技巧.
As far as accessing the internal UInt32 Array of the BigInteger structure, here is a hack for that.
导入反射名称空间
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()作为
Then you can get the underlying UInteger() of the big integer as
Dim Data() As UInteger = ToUInt32Array(Value)
Length = Data.Length
或替代
Dim Data() As UInteger = Value.ToUInt32Array()
请注意，_bits字段信息可用于直接访问BigInteger结构的基础UInteger()_bits字段.这比调用ToUInt32Array()方法要快.但是，当BigInteger B< = UInteger.MaxValue _bits时为空.我怀疑作为优化，当BigInteger适合32位(机器大小)字的大小时，MS返回使用本机数据类型执行正常的机器字算术.
Note that _bits fieldinfo can be used to directly access the underlying UInteger() _bits field of the BigInteger structure. This is faster than invoking the ToUInt32Array() method. However, when BigInteger B <= UInteger.MaxValue _bits is nothing. I suspect that as an optimization when a BigInteger fits the size of a 32 bit (machine size) word MS returns performs normal machine word arithmetic using the native data type.
我也无法使用_bits.SetValue(B，Data())，因为您通常可以使用反射.要解决此问题，我使用BigInteger(bytes()b)构造函数，该构造函数具有开销.在c#中，您可以使用不安全的指针操作将UInteger()强制转换为Byte().由于VB中没有指针操作，因此我使用Buffer.BlockCopy.当以这种方式访问数据时，必须注意，如果设置了bytes()数组的MSB，则MS会将其解释为负数.我希望他们将其构造为带有单独的符号字段的构造函数.字数组是要添加一个额外的0字节以取消选中MSB
I have also not been able to use the _bits.SetValue(B, Data()) as you normally would be able to using reflection. To work around this I use the BigInteger(bytes() b) constructor which has overhead. In c# you can use unsafe pointer operations to cast a UInteger() to Byte(). Since there are no pointer ops in VB, I use Buffer.BlockCopy. When access the data this way it is important to note that if the MSB of the bytes() array is set, MS interprets it as a Negative number. I would prefer they made a constructor with a separate sign field. The word array is to add an addition 0 byte to make uncheck the MSB
此外，在平方时，您甚至可以进一步改善
Also, when squaring you can improve even further
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个减法.
This eliminates 2 shifts, 2 additions and 3 subtractions from each recursion of your multiplication algorithm.
这篇关于优化Karatsuba实施的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！
