相关疑难解决方法(0)

因此,我正在尝试改进.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 = …