【300分】如何算99999的阶乘?

vrhero 2010-04-14 11:15:48
加精
刚刚测试了一下System.Numerics.BigInteger类,最简单的阶乘...结果吓了我一跳...

先来月经的递归算法...
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即堆栈溢出...

于是优化一下,改为循环算法...
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#!但是...明天上午我有事要早睡,以后有空再介绍吧...
...全文
13865 446 打赏 收藏 转发到动态 举报
写回复
用AI写文章
446 条回复
切换为时间正序
请发表友善的回复…
发表回复
张志来 2010-11-02
  • 打赏
  • 举报
回复
# include<stdio.h>
int main()
{
long int n,i;
n=1;
for(i=1;i<=99999;i++)
n=n*i;
printf("%ld",n);
}
输出结果是 wo kao
hicaru000000 2010-08-10
  • 打赏
  • 举报
回复
用FPGA乘法器


很方便。


倒霉熊 2010-07-28
  • 打赏
  • 举报
回复
[Quote=引用 14 楼 mars199 的回复:]
你这个沙发板凳不留的作风不太好批评的同时进行膜拜
[/Quote]
+1
wq326431904 2010-07-16
  • 打赏
  • 举报
回复
座了沙发

Valefish 2010-07-16
  • 打赏
  • 举报
回复
Mark
s8975565 2010-07-16
  • 打赏
  • 举报
回复
lyn0032 2010-04-26
  • 打赏
  • 举报
回复
C#?阶乘?恩!
ALAN1416 2010-04-26
  • 打赏
  • 举报
回复
学习了~
o老猫钓鱼o 2010-04-26
  • 打赏
  • 举报
回复
学习了....
Crzjtp_AN 2010-04-25
  • 打赏
  • 举报
回复
学习了.
yinfie 2010-04-25
  • 打赏
  • 举报
回复
ACM竞赛里面这种大数常有,每次都是用数组转存的,呵呵。
tyzqqq 2010-04-25
  • 打赏
  • 举报
回复
oh..
zchlyl 2010-04-25
  • 打赏
  • 举报
回复
顶一个!!!!!
zn88358800 2010-04-24
  • 打赏
  • 举报
回复
学习了。。。MARK
shine333 2010-04-23
  • 打赏
  • 举报
回复
多线程的恐怖速度!!!!!!

结果长度:35656 用时:156
结果长度:56130 用时:344
结果长度:77338 用时:609
结果长度:456569 用时:20047 ------> “惊人”的20秒!!!!

当然,花了2分钟时间计算toString()长度。

手头VS没有4.0 BigInteger,用了个Java版的,C#理论上只可能更快。我是双核。

import java.math.BigInteger;
import java.util.ArrayList;
import java.util.List;
import java.util.concurrent.Callable;
import java.util.concurrent.ExecutorService;
import java.util.concurrent.Executors;
import java.util.concurrent.Future;

public class F {

static final int cnt = Runtime.getRuntime().availableProcessors() * 4;

static final ExecutorService threadPool = Executors.newFixedThreadPool(cnt);

public static void main(String[] args) throws Exception {
int[] tests = new int[] {
9999, 15000, 20000, 99999
};
for (int i : tests) {
long start = System.currentTimeMillis();
BigInteger result = f(i);
long end = System.currentTimeMillis();
System.out.printf("结果长度:%s 用时:%s\n", result.toString().length(), end
- start);
}
threadPool.shutdown();
}

public static BigInteger f(final int n) throws Exception {

List<Callable<BigInteger>> taskList = new ArrayList<Callable<BigInteger>>();
for (int i = 1; i <= cnt; i++) {
final int threadNo = i;
Callable<BigInteger> task = new Callable<BigInteger>() {

public BigInteger call() {
BigInteger result = BigInteger.ONE;
for (int j = threadNo; j <= n; j += cnt) {
result = result.multiply(BigInteger.valueOf(j));
}
return result;
}
};
taskList.add(task);
}
List<Future<BigInteger>> futureList = threadPool.invokeAll(taskList);
BigInteger f = BigInteger.ONE;
for (Future<BigInteger> future : futureList) {
f = f.multiply(future.get());
}
return f;
}
}
Tony2251 2010-04-23
  • 打赏
  • 举报
回复
MARK
  • 打赏
  • 举报
回复
等待高人
  • 打赏
  • 举报
回复
[code=Java]等待高人[code]
gzliaojian 2010-04-22
  • 打赏
  • 举报
回复
mark!!!!
killerer09 2010-04-22
  • 打赏
  • 举报
回复
学习了。。
加载更多回复(424)

7,763

社区成员

发帖
与我相关
我的任务
社区描述
.NET技术 非技术区
社区管理员
  • 非技术区社区
加入社区
  • 近7日
  • 近30日
  • 至今
社区公告
暂无公告

试试用AI创作助手写篇文章吧