有效地将大的 BigInteger 转换为字符串，ToString() 耗时太长

debugcn 发表于 Dev

奥默·埃内斯

我正在研究一个阶乘函数，大整数的阶乘会变得非常长。

比如20万！= 973350 位长，如果我只使用 ToString()，事情需要很长时间。

20万！转换为字符串需要更长的时间然后实际计算它！

我尝试将阶乘函数设置为进程，然后使用ProcessorAffinity将线程固定到特定核心，以便该核心仅转换为字符串，但这只是花费了完全相同的时间。

另外，我想将其转换为字符串的原因是因为我想将输出 (FactFile) 写入文本文件。

字符串转换代码：

using (Process proc = Process.GetCurrentProcess())
{
     proc.ProcessorAffinity = (IntPtr)0x0003;
     FactFile = Res.ToString(); //FactFile is Going to be the final string, Res is the Factorial.
}

这是我的因子代码：

for (BigInteger i = 1; i < k; i++)
{
    Res *= i; // Res is the number to Calculate the factorial of
}

20万！计算需要 15 秒，然后再用 18 秒将其转换为字符串（这可能因 cpu 到 cpu 不同，我有一个 i7）。

提醒：转换为字符串的最有效方法是什么？

输出：

Total Computation Time: 00:00:16.2007276
String Conversion Time: 00:00:19.4049292

西奥多·祖利亚斯

这是一个快 40% 的字符串化器。它将大整数与数字 10^10000 反复相除，对余数进行字符串化，最后将所有字符串连接在一起。它也可以处理负数。

public static string ToDecimalString(this BigInteger value)
{
    if (value == 0) return "0";
    var digits = 10000;
    var divider = BigInteger.Pow(10, digits);
    var parts = new Stack<string>();
    while (true)
    {
        BigInteger remainder;
        value = BigInteger.DivRem(value, divider, out remainder);
        if (value != 0)
        {
            parts.Push(BigInteger.Abs(remainder).ToString().PadLeft(digits, '0'));
        }
        else
        {
            parts.Push(remainder.ToString());
            break;
        }
    }
    return String.Join("", parts);
}

通过将剩余部分的字符串化卸载到后台线程，它可以变得稍微快一些。不幸的是，算法中最慢的部分（对的调用BigInteger.DivRem）是不可并行化的。

public static string ToDecimalStringParallel(this BigInteger value)
{
    if (value == 0) return "0";
    var digits = 10000;
    var divider = BigInteger.Pow(10, digits);
    var remainders = new BlockingCollection<BigInteger>();
    var parts = new ConcurrentStack<string>();
    var task = Task.Run(() =>
    {
        foreach (var remainder in remainders.GetConsumingEnumerable())
        {
            parts.Push(BigInteger.Abs(remainder).ToString().PadLeft(digits, '0'));
        }
    });
    while (true)
    {
        BigInteger remainder;
        value = BigInteger.DivRem(value, divider, out remainder);
        if (value != 0)
        {
            remainders.Add(remainder);
        }
        else
        {
            remainders.CompleteAdding();
            task.Wait();
            parts.Push(remainder.ToString());
            break;
        }
    }
    return String.Join("", parts);
}

本文收集自互联网，转载请注明来源。

如有侵权，请联系[email protected] 删除。