将BigInteger转换为十进制（Base 10）字符串的最快方法是什么？

Question

将BigInteger转换为十进制（Base 10）字符串的最快方法是什么？

3

目前的答案

以下是代码解析。

//Time: ~7s (linear loop algorithm)
//100,000! (456,574 decimal digits)
BigInteger bigIntVar = computeFactorial(100000);

//The first three here are just for comparison and are not actually Base 10.
bigIntVar.ToBase64String() //Time: 00.001s | Base 64 | Tetrasexagesimal
bigIntVar.ToString("x")    //Time: 00.016s | Base 16 | Hexadecimal
bigIntVar.ToBinaryString() //Time: 00.026s | Base 02 | Binary
bigIntVar.ToQuickString()  //Time: 11.200s | Base 10 | String Version
bigIntVar.ToQuickString()  //Time: 12.500s | Base 10 | StringBuilder Version
bigIntVar.ToString()       //Time: 13.300s | Base 10 | Original

原始问题内容

我已经花了太多时间在这个问题上，所以我需要你的帮助。

这是一个用于计算巨大阶乘（例如100,000！）的个人项目。

以下是我的代码：

using (var stream = new StreamWriter(fileName + ".txt", false))
{
    stream.WriteLine(header);

    var timer = new Stopwatch();    
    timer.Restart();
    //This is the huge BigInteger holding the answer to 100,000!
    stream.WriteLine(saveFactorial.Output.ToString());         
    //Let me be clear: ToString() is directly causing the the 13sec time delay.
    //Not the stream.
    timer.Stop();                   
}

time = (timer.ElapsedMilliseconds / 1000.0).ToString() + "s"; 

MessageBox.Show(time);

在我的机器上，使用线性循环算法计算10万条数据只需要约7秒钟。

然而，使用标准IO代码保存这些数据却需要13秒钟。

换句话说，保存这些数据所需的时间比进行中等规模的计算所需的时间更长。

因此，我想也许可以尝试使用：

BigInteger.ToByteArray();

虽然这个运行速度非常快，但我无法找出如何将其保存为可读取的文本。

您可以使用上述方法使用此自制扩展名将二进制字符串写入文本文件：

ToBinaryString

//Usage: string bigIntBinary = bigIntVar.ToBinaryString();
public static string ToBinaryString(this BigInteger source)
{
    //If you lookup the ToByteArray() method...
    //It actually stores the bytes in reverse order.
    var bigIntBytes = source.ToByteArray().Reverse();

    StringBuilder bigIntBinary = new StringBuilder();

    foreach (var bigIntByte in bigIntBytes)
    {
       bigIntBinary.Append(Convert.ToString(bigIntByte, 2).PadLeft(8, '0'));
    }

    return bigIntBinary.ToString();
}

ToBase64String

    ////Usage: string bigIntBase64 = bigIntVar.ToBase64String();
    public static string ToBase64String(this BigInteger source)
    {
        var bigIntBytes = source.ToByteArray().Reverse().ToArray();

        return Convert.ToBase64String(bigIntBytes);
    }

我也尝试过使用数学方法（mod 10等）来获取每个数字，但这比使用ToString()要花费更多的时间。

我在这里做错了什么？

根据下面的答案，我想出了这段代码。这比ToString()更快，但只快了几秒钟。

ToQuickString

//Usage: string bigIntString = bigIntVar.ToQuickString()
public static String ToQuickString(this BigInteger source)
{
    powersOfTen = new List<BigInteger>();

    powersOfTen.Add(1);

    for (BigInteger i = 10; i < source; i *= i)
    {
        powersOfTen.Add(i);
    }

    return BuildString(source, powersOfTen.Count - 1).ToString().TrimStart('0');
}

private static List<BigInteger> powersOfTen;

private static string BuildString(BigInteger n, int m)
{
    if (m == 0)
        return n.ToString();

    BigInteger remainder;
    BigInteger quotient = BigInteger.DivRem(n, powersOfTen[m], out remainder);

    return BuildString(quotient, m - 1) + BuildString(remainder, m - 1);
}

- user1787963

似乎是调用 ToString 花费了很长时间，但如果您希望文件可读性强，那么您无法做太多改变。 - Rawling

是的，我进行了编辑以使其更清晰。我调试了相当长的时间，并发现 ToString() 是导致时间延迟的唯一原因。难道没有更快的方法将 BigInteger 转换为字符串吗？ - user1787963

3

我怀疑这个。你真的需要这些内容可读吗？谁会花时间去阅读一个有450k字符的数字呢？ - Rawling

我有一个1GB的文本文件，其中包含十亿位的圆周率数字...这更多是个人爱好。我只是喜欢知道我在电脑上拥有一个有意义的45万位数。 - user1787963

在你的ToBinaryString中，删除Reverse()后面的.ToList()。ToList()会创建数据的副本。你不需要数据的副本，ForEach可以直接作用于Reverse()返回的IEnumerable<>。 - dthorpe

显示剩余2条评论

2个回答

1

将BigInteger数据以二进制或十六进制格式保存。这对于计算机和足够专注的人来说都是可读的。

花费额外的精力使输出“人类可读”是浪费时间。无论是十进制、十六进制、二进制还是其他任何进制，没有人能够理解450,000个数字。

更新

更仔细地研究了十进制转换，可以在多核系统上使用多个线程将ToString的基准性能减少近一半。主要障碍是整个十进制过程中耗时最长的是原始450k位数的第一个除法运算。

Stats on my quad core P7: 
Generating a 500k digit random number using power and multiply: 5 seconds
Dividing that big number by anything just once: 11 seconds
ToString(): 22 seconds
ToQuickString: 18 seconds
ToStringMT: 12.9 seconds

.

public static class BigIntExtensions
{
    private static List<BigInteger> powersOfTen;

    // Must be called before ToStringMt()
    public static void InitPowersOfTen(BigInteger n)
    {
        powersOfTen = new List<BigInteger>();

        powersOfTen.Add(1);

        for (BigInteger i = 10; i < n; i *= i)
            powersOfTen.Add(i);
    }

    public static string ToStringMT(this BigInteger n)
    {
        // compute the index into the powersOfTen table for the given parameter. This is very fast.
        var m = (int)Math.Ceiling(Math.Log(BigInteger.Log10(n), 2));

        BigInteger r1;
        // the largest amount of execution time happens right here:
        BigInteger q1 = BigInteger.DivRem(n, BigIntExtensions.powersOfTen[m], out r1);

        // split the remaining work across 4 threads - 3 new threads plus the current thread
        var t1 = Task.Factory.StartNew<string>(() =>
        {
            BigInteger r1r2;
            BigInteger r1q2 = BigInteger.DivRem(r1, BigIntExtensions.powersOfTen[m - 1], out r1r2);
            var t2 = Task.Factory.StartNew<string>(() => BuildString(r1r2, m - 2));
            return BuildString(r1q2, m - 2) + t2.Result;
        });
        BigInteger q1r2;
        BigInteger q1q2 = BigInteger.DivRem(q1, BigIntExtensions.powersOfTen[m - 1], out q1r2);
        var t3 = Task.Factory.StartNew<string>(() => BuildString(q1r2, m - 2));
        var sb = new StringBuilder();
        sb.Append(BuildString(q1q2, m - 2));
        sb.Append(t3.Result);
        sb.Append(t1.Result);
        return sb.ToString();
    }

    // same as ToQuickString, but bails out before m == 0 to reduce call overhead.
    // BigInteger.ToString() is faster than DivRem for smallish numbers.
    private static string BuildString(BigInteger n, int m)
    {
        if (m <= 8)
            return n.ToString();

        BigInteger remainder;
        BigInteger quotient = BigInteger.DivRem(n, powersOfTen[m], out remainder);
        return BuildString(quotient, m - 1) + BuildString(remainder, m - 1);
    }
}

对于ToQuickString()和ToStringMT()函数，需要在使用这些函数之前初始化10的幂数组。初始化此数组不应包含在函数执行时间测量中，因为该数组可以在后续调用中重复使用，因此其初始化成本分摊在程序的生命周期内，而不是单个函数调用。

对于生产系统，我会设置更自动化的初始化，例如在类静态构造函数中初始化合理数量的条目，然后在ToQuickString()或ToStringMT()中检查表中是否有足够的条目来处理给定的BigInteger。如果没有，则添加足够的条目到表中以处理当前的BigInteger，然后继续操作。

这个ToStringMT函数手动构建工作任务，将剩余的工作分散到可用执行核心上的4个线程中。您也可以将原始的ToQuickString()函数的一半工作分配到每个递归的另一个线程中，但这很快会创建太多的任务，并陷入任务调度开销中。递归一直深入到单个十进制数字。我修改了BuildString()函数，以更早地退出（m <= 8而不是m == 0），因为BigInteger.ToString()对于较小的数字比DivRem更快。

ToStringMt()的执行时间中有90%被第一个DivRem调用占用。在此之后，它会非常快速地收敛，但第一个调用确实很痛苦。

- dthorpe

我同意在保存BigInteger时最好使用Hex和Binary。然而，我正在寻找一种更快的方法将其保存为Base10。我意识到一个450k位数不会被完全读取，但是无论如何，我希望将文件保存为Base10（仅仅是为了这样做）。 - user1787963

转换为Base10需要大量的工作。从概念上讲，每个数字需要进行一次长除法（mod）。450k个长除法需要一段时间，特别是在BigInteger数据上，因为除法可能没有在硬件中实现。如果10^n的除法性能小于n*(除以10)，您可以将BigInteger分解并将十进制化工作分配到多个线程中，以利用多个执行核心。在4核CPU上，可能会将ToString()时间减半。在具有数百个核心的CUDA GPU硬件上可能效果非常好。 - dthorpe

另外，由于您只对BigInteger的快速十进制转换感兴趣，因此您可能需要更改问题的标题，或者新开一个问题，专门讨论BigInteger和Base10转换为字符串。 - dthorpe

网页内容由stack overflow 提供, 点击上面的

可以查看英文原文，
原文链接

- CodesInChaos · Accepted Answer

首先，我会计算所有形如10^(2^m)的数字，使其小于n。然后，我会使用最大的这些数字来使用DivRem函数将问题分成两个子问题。重复此过程，直到你只剩下单个数字。

var powersOfTen=new List<BigInteger>();
powersOfTen.Add(1);
for(BigInteger i=10;i<n;i=i*i)
  powersOfTen.Add(i);

string ToString(BigInteger n, int m)
{
  if(m==0)
    return n.ToString();
  quotient = DivRem(n,powersOfTen[m], remainder)
  return ToString(quotient, m-1)+ToString(remainder, m-1)
}

你可以通过直接写入字符数组来完全优化字符串连接。

另外，你可以考虑在所有计算过程中使用基数1000'000'000。这样，在最后就不需要进行基数转换了。这对于阶乘计算可能会更快。

List<int> multiply(List<int> f1, int f2)
{
  int carry=0;
  for(int i=0;i<f1.Count;i++)
  {
    var product=(Int64)f1[i]*(Int64)f2;
    carry=product/1000000000;
    result.Add(product%1000000000);
  }
  if(carry!=0)
    result.Add(carry);
}

现在将其转换为十进制字符串是非常简单和便宜的。