将BigInteger转换为十进制（Base 10）字符串的最快方法？
答案到目前为止
所以这是代码细分。
//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);
在100,000！ 在我的机器上需要大约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(); 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 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); }
以二进制或hex格式保存BigInteger数据。 它对计算机和足够专用的人类都是可读的。 ;>
花费额外的努力使输出“人类可读”是浪费时间。 无论人类是基数10，基数16，基数2还是其他任何数据，任何人都无法理解450,000个数字。
UPDATE
再仔细研究Base 10转换，可以使用多核系统上的多个线程将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 powersOfTen; // Must be called before ToStringMt() public static void InitPowersOfTen(BigInteger n) { powersOfTen = new List (); 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(() => { BigInteger r1r2; BigInteger r1q2 = BigInteger.DivRem(r1, BigIntExtensions.powersOfTen[m - 1], out r1r2); var t2 = Task.Factory.StartNew (() => 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 (() => 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函数手动构造工作程序任务，以将剩余的工作分散到多核CPU中可用执行核心上的4个线程中。 你可以改为让原始的ToQuickString（）函数在每次递归时将其一半的工作分解为另一个线程，但是这会很快创建太多任务并且在任务调度开销中陷入困境。 递归一直向下钻取到单个十进制数字。 我修改了BuildString（）函数以提前纾困（m <= 8而不是m == 0），因为对于小数字，BigInteger.ToString（）比DivRem更快。
第一个DivRem调用占用ToStringMt（）90％的执行时间。 之后它很快收敛，但第一个真的很痛苦。
首先，我计算小于n 10^(2^m)forms的所有数字。 然后我会使用其中最大的DivRem将问题分成两个子问题。 递归重复，直到你找到个别数字。
var powersOfTen=new List(); powersOfTen.Add(1); for(BigInteger i=10;i
您还可以通过直接写入字符数组来完全优化字符串连接。
或者，您可以考虑在所有计算过程中使用1000'000'000。 这样你根本不需要基本转换。 对于因子计算，这可能要快得多。
List multiply(List f1, int f2) { int carry=0; for(int i=0;i
现在转换为基数10字符串是微不足道的和便宜的。