【300分】如何算99999的阶乘？
刚刚测试了一下System.Numerics.BigInteger类，最简单的阶乘...结果吓了我一跳...
先来月经的递归算法...
- C# code
static System.Numerics.BigInteger Factorial(System.Numerics.BigInteger i){ if (i.IsZero || i.Sign == -1) return System.Numerics.BigInteger.Zero; if (i.IsOne) return System.Numerics.BigInteger.One; else return i * Factorial(i - 1);} static void Main(string[] args){ if (args.Length < 1) return; int i; if (int.TryParse(args[0], out i)) { System.Numerics.BigInteger bi = i; System.Diagnostics.Stopwatch sw = System.Diagnostics.Stopwatch.StartNew(); bi = Factorial(bi); sw.Stop(); //计算结果太长，只输出结果长度 Console.Write("结果长度：{0} 用时：{1}", bi.ToString().Length, sw.Elapsed); }}Release运行...
9999! 结果长度：35656 用时：00:00:02.6131329
15000! 结果长度：56130 用时：00:00:08.6232216
15102! 结果长度：56556 用时：00:00:08.8157251
不幸由于递归堆栈溢出的问题，我测试的运行环境(x86)最大只能算到15102，15103即堆栈溢出...
于是优化一下，改为循环算法...
- C# code
static System.Numerics.BigInteger Factorial(System.Numerics.BigInteger i){ System.Numerics.BigInteger result = 1; while (true) { if (i < 2) return result; result *= i; i--; }}9999! 结果长度：35656 用时：00:00:00.2164311
15000! 结果长度：56130 用时：00:00:00.5164868
15102! 结果长度：56556 用时：00:00:00.5154113
效率很惊人，但还没完...
99999! 结果长度：456569 用时：00:00:36.1188483
36秒多！看来微软在匆匆推出System.Numerics又匆匆撤回后做了大量的优化...
那么999999能算吗？答案是能！结果是多少？抱歉，我这儿还没算完，跑了10多分钟了...
值得一提的是这段代码运行时内存占有并不大，很稳定...工作设置内存在11MB左右，专用工作集内存在5MB左右...即使是现在正在计算999999!，也不过12MB左右和6MB左右...
还要注意一点...System.Numerics并没有包含在C#项目的默认引用中，需要添加引用程序集...这是为什么呢？因为F#！但是...明天上午我有事要早睡，以后有空再介绍吧...
[解决办法]
接分啊啊啊啊啊
[解决办法]
。。。 就多看了两眼
[解决办法]
MARK
[解决办法]
你这个沙发板凳不留的作风不太好
[解决办法]
比我写的那个快多了：http://topic.csdn.net/u/20100318/14/9d47ec28-6b69-4c3f-98ea-c8e53157c779.html
[解决办法]
。。。
[解决办法]
可以安装一个 VS2010 试试.
[解决办法]
那样就可以啊 是不
[解决办法]
沙发地板都被人占了！我就来占过位置！
[解决办法]
你这个沙发板凳不留的作风不太好批评的同时进行膜拜
[解决办法]
说实话对于System.Numerics.BigInteger的效率挺失望的，其乘法运算肯定没有使用FFT，否则绝对不会这么慢，我试了一下算999999，大概得10分钟左右（还不包括输出），而用开源项目IntX，计算部分只需要30多秒，差距太大了，4.0的System.Numerics.BigInteger大数乘法的效率其实还不如3.5下用反射弄出来的那个快。
附IntX的网址
http://intx.codeplex.com/releases/view/41807
- C# code
using System;using System.Collections.Generic;using System.Linq;using Oyster.Math;namespace csdnTest{ class Program { static void Main(string[] args) { DateTime beginTime = DateTime.Now; IntX result = Factorial(1000000); DateTime endTime = DateTime.Now; Console.WriteLine(endTime - beginTime); Console.WriteLine(result); Console.ReadKey(); } static IntX Factorial(int n) { int[] counter = GetPowCounter(n); SortedDictionary<IntX, bool> sDict = new SortedDictionary<IntX, bool>(); //计算幂乘并将结果压入优先队列(使用优化过的大数乘法,在计算相等规模的大数乘法时，效率最高) for (int i = 2; i <= n; i++) { if (counter[i] > 0) sDict.Add(IntX.Pow(i, (uint)counter[i]), false); } IntX valueA = 1, valueB; //用SortedDictionary模拟优先队列进行最后的计算 while (sDict.Count > 1) { valueA = sDict.ElementAt(0).Key; valueB = sDict.ElementAt(1).Key; sDict.Remove(valueA); sDict.Remove(valueB); sDict.Add(valueA * valueB, false); } return sDict.ElementAt(0).Key; } //做质因数分解,以便使用幂乘进行计算 static int[] GetPowCounter(int n) { int[] pList = GetPrime(n); int[] pCounter = new int[n + 1]; for (int i = 0; i < pList.Length; i++) { int k = n; while ((k /= pList[i]) > 0) pCounter[pList[i]] += k; } return pCounter; } //生成质数列表 static int[] GetPrime(int n) { List<int> prime = new List<int>(); bool[] flags = new bool[n + 1]; for (int i = 2; i <= n; i++) { if (!flags[i]) prime.Add(i); for (int j = 0; j < prime.Count; j++) { if (prime[j] * i > n) break; flags[prime[j] * i] = true; if (i % prime[j] == 0) break; } } return prime.ToArray(); } }}
[解决办法]
很霸道嘛...沙发板凳都自个占了..
[解决办法]
学习学习
[解决办法]
应该可以看到System.Numerics是怎么实现的吗？
是不是傅里叶变换就看的出来撒
我没测试过...
[解决办法]
mark
[解决办法]
楼主 开个专题 讲一下大数运算啊
[解决办法]
[解决办法]
帮顶一个
[解决办法]
两个留一个塞。
[解决办法]
接分，学习
[解决办法]
膜拜一下撒
[解决办法]
看看先
[解决办法]
学学看吧
[解决办法]
[解决办法]
膜拜一下撒，学习学习
[解决办法]
顶顶顶顶顶顶顶顶顶顶顶顶顶
[解决办法]
- -
[解决办法]
才有才了。。。
[解决办法]
能说点听得懂的不?
[解决办法]
哈哈，楼主霸气啊
[解决办法]
讲点大数的运算啊！
[解决办法]
递归 ， 耗内存大
[解决办法]
学习！
[解决办法]
很不错，学习了。
[解决办法]
学习
[解决办法]
我也得学习一下.
[解决办法]
很不错，学习了。
[解决办法]
向高手学习
[解决办法]
我想问的是，.net框架中的System.Numerics.BigInteger有提供阶乘函数吗？
如果阶乘是这样的程序计算，估计谁的大数类也发挥不了潜力。
话说回来，System.Numerics.BigInteger这种效率是挺让人失望的。
[解决办法]
------解决方案--------------------
[解决办法]
[解决办法]
同学习
[解决办法]
[解决办法]
楼主好强，学习
[解决办法]
路过，学习
[解决办法]
我觉得还好了，百万级的大数乘法效率不错，intX那个程序算法上有优化，暴力算未必K得过BigInteger
[解决办法]
学习了
[解决办法]
学习，挺不错的
[解决办法]
jfjfjfjfjfjfjfjfjfjf
[解决办法]
mark
[解决办法]
厉害厉害 佩服佩服 LZ专研精神很 让人佩服
[解决办法]
[解决办法]
接分了。
[解决办法]
速度标记~~~
[解决办法]
M.A.R.K
[解决办法]
接分
回复内容太短了！
[解决办法]
[解决办法]
已绑定。。。
[解决办法]
都是高手，我来了
[解决办法]
楼主写个 bigint 给我们用用吧
[解决办法]
用 非递归 算法呀。。。。。。
[解决办法]
看看.
[解决办法]
路过，学习
[解决办法]
MARK
[解决办法]
效率的确很不错~
[解决办法]
学些了，这里全是高手啊
[解决办法]
接分啊啊啊啊啊
[解决办法]
................
[解决办法]
LOG一下
[解决办法]
LOG一下
[解决办法]
还是开源的好啊
[解决办法]
递归，不建议使用
[解决办法]
我运行半天都没反应
[解决办法]
mark
[解决办法]
Friendly UP~
[解决办法]
Friendly UP~
[解决办法]
看到标题就知道你要说BinInteger了~~
[解决办法]
C#效率是不是太差了?我用Java写了一个.
x86 jdk 1.6
9999: RS length:35656 成功生成（总时间：1 秒）
15000: RS length:56130成功生成（总时间：2 秒）
20000: RS length:77338成功生成（总时间：3 秒）
99999: RS length:456569成功生成（总时间：1 分钟 41 秒）
- Java code
public static void compBigInteger(int jc){ BigInteger bigi = BigInteger.ONE; BigInteger temp = null; for(int i=2;i<=jc;i++){ temp = new BigInteger(i+""); bigi = bigi.multiply(temp); } String rs = bigi.toString(); //System.out.println(rs); System.out.println(jc + ": RS length:"+rs.length()); } public static void main(String[] ars) { compBigInteger(99999); }
[解决办法]
膜拜一下撒
[解决办法]
up............
[解决办法]
C# Java 这些非原生的东西还最求什么效率，效率不是这些语言的优势，稳定安全才是它们的优势，有这样的结果应该很正常.什么东西都不可能是最好的。
[解决办法]
学习一下。
[解决办法]
学习了.
[解决办法]