计算 1000! 源代码

win_hate

1. 
   
2. (define (factorial n)
   
3.   (define (f p i)
   
4.     (if (> i n) p
   
5.       (f (* i p) (+ i 1))))
   
6.   (f 1 1))
   

复制代码

很土的实现，没用任何技巧。不过 guile 在背后使用 gmp，所以大整数乘法是由 gmp 做的，但没有用 gmp 的阶乘函数。

看一下时间：

[ 本帖最后由 win_hate 于 2007-4-29 22:19 编辑 ]

醉卧水云间

gmp的结果是：
real    0m0.193s
user    0m0.080s
sys     0m0.000s

1. 
   
2. #include <stdio.h>
   
3. #include <gmp.h>
   
4. 
   
5. void show(mpz_t show)
   
6. {
   
7.         char* str=mpz_get_str(NULL,10,show);
   
8.         printf("%s\n",str);
   
9.         free(str);       
   
10. }
    
11. int main()
    
12. {
    
13.         mpz_t mul,res,one;
    
14.         mpz_init(mul);
    
15.         mpz_init(res);
    
16.         mpz_init(one);
    
17.         mpz_set_ui(mul,1L);  //mul=1;
    
18.         mpz_set_ui(res,1L);        //res=1;
    
19.         mpz_set_ui(one,1L);        //one=1;
    
20. 
    
21.         int i;
    
22.         for(i=0;i<10000;i++)
    
23.         {
    
24.                 mpz_mul(res,res,mul);        //res=res*mul;
    
25.                 mpz_add(mul,mul,one);        //mul++;
    
26.         }
    
27.        
    
28.         show(res);
    
29. 
    
30.         return (0);
    
31. }
    

复制代码

醉卧水云间

原帖由 win_hate 于 2007-4-29 21:52 发表
gmp 是这样处理的：

1） n! 分解成 2^m p_1^a_1 p_2^a_2 ... p_r^a_r

2）2^m 只不过是移位

3）其余素因子按方幂分组，即同次的放在一起，变成 (q_1 q_2 ... q_t)^a 的形式。由于我们能快速计算方幂，所以 ...

gmp中求n!的函数是哪个？我没找到啊！

win_hate

是这个吧：

1. 
   
2. void mpz_fac_ui (mpz t rop, unsigned long int op)
   

复制代码

1. 
   
2. #include <stdio.h>
   
3. #include <gmp.h>
   
4. 
   
5. int
   
6. main ()
   
7. {
   
8.         int n=10000;
   
9.         mpz_t r;
   
10. 
    
11.         mpz_init (r);
    
12.         mpz_fac_ui (r, n);
    
13.         mpz_out_str (stdout, 10, r);
    
14. }
    

复制代码

[ 本帖最后由 win_hate 于 2007-4-29 23:19 编辑 ]

doctorjxd

还是Gmp快.
大数的运算一般来说是没有必要自己实现的.

我也看过一个基于gmp计算圆周率的数值程序, 速度比日本人写的Super Pai要快.

doctorjxd

FreeBSD中ports里面的libgmp对gmp如下评述

GMP is believed to be faster than any other similar library. The
advantage for GMP increases with the operand sizes for certain
operations, since GMP in many cases has asymptotically faster
algorithms.

emacsnw

原帖由 doctorjxd 于 2007-4-29 16:55 发表
还是Gmp快.
大数的运算一般来说是没有必要自己实现的.

我也看过一个基于gmp计算圆周率的数值程序, 速度比日本人写的Super Pai要快.

super \pi算法其实不快的，主要用来测cpu速度了，呵呵。

doctorjxd

原帖由 emacsnw 于 2007-4-30 09:01 发表


super \pi算法其实不快的，主要用来测cpu速度了，呵呵。

同意, 但是一开始这个项目是用来在大型机上计算Pai的.

softsongs

恩，学习了，谢谢！
等哪天需要更加快速的计算大数阶乘时，我可能会考虑GMP算法。

原帖由 win_hate 于 2007-4-29 21:52 发表
gmp 是这样处理的：

1） n! 分解成 2^m p_1^a_1 p_2^a_2 ... p_r^a_r

2）2^m 只不过是移位

3）其余素因子按方幂分组，即同次的放在一起，变成 (q_1 q_2 ... q_t)^a 的形式。由于我们能快速计算方幂，所以 ...

softsongs

看来俺的速度gmp还有一个数量级的差距。
主要原因是没有利用计算机计算方幂快的性质， 恩。

谢谢醉卧水云间 兄的关注！

原帖由 醉卧水云间 于 2007-4-29 22:34 发表
gmp的结果是：
real    0m0.193s
user    0m0.080s
sys     0m0.000s

[code]
#include <stdio.h>
#include <gmp.h>

void show(mpz_t show)
{
        char* str=mpz_get_str(NULL,10,show);
         ...