因此,我正在尝试改进 .net 4 的
BigInteger
类提供的一些操作,因为这些操作似乎是二次的。我已经做了一个粗略的 Karatsuba 实现,但它仍然比我预期的慢。
主要问题似乎是 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();
}
}
}
那么,我能做些什么来加快速度呢?
为什么要计算所有位?
在 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 数组而言,这里有一个 hack。
导入反射命名空间
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 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
此外,当平方时你可以进一步提高
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 次减法。
评论
@Alexander Higgins
的回复:
ac + ((abcd - ac - bd) << n) + (bd << (2 * n))
当可以使用嵌套层时,这仍然在做重复的工作:
ac + ((abcd - ac - bd + (bd << n)) << n)
导致减少 1 对
( )
和 1 次乘法。
但就我个人而言,我并不认为 Karatsuba 节省了那么多,因为在 bigint 级别,减法比加法的成本稍高(并且您在每个递归级别执行其中 2 个),与只是
(using AH`s same letters for consistency) :
BigInteger b = x >> n;
BigInteger a = x - (b << n);
BigInteger d = y >> n;
BigInteger c = y - (d << n);
然后是
的幼稚方法return ac + ((ad + bc + (bd << n)) << n)
与
相比,看起来并没有那么糟糕return ac + ((abcd - ac - bd) << n) + (bd << (2 * n))
额外的好处是不需要存储减法部分的任何部分积。
我通常在任何递归开始之前预先确定符号,在无符号领域中执行所有操作,并在必要时简单地执行 1 个最终否定。