計算 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))
   

復(fù)制代碼

很土的實現(xiàn)，沒用任何技巧。不過 guile 在背后使用 gmp，所以大整數(shù)乘法是由 gmp 做的，但沒有用 gmp 的階乘函數(shù)。

看一下時間：

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

醉臥水云間

gmp的結(jié)果是：
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. }
    

復(fù)制代碼

醉臥水云間

原帖由 win_hate 于 2007-4-29 21:52 發(fā)表
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!的函數(shù)是哪個？我沒找到啊！

win_hate

是這個吧：

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

復(fù)制代碼

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. }
    

復(fù)制代碼

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

doctorjxd

還是Gmp快.
大數(shù)的運算一般來說是沒有必要自己實現(xiàn)的.

我也看過一個基于gmp計算圓周率的數(shù)值程序, 速度比日本人寫的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 發(fā)表
還是Gmp快.
大數(shù)的運算一般來說是沒有必要自己實現(xiàn)的.

我也看過一個基于gmp計算圓周率的數(shù)值程序, 速度比日本人寫的Super Pai要快.

super \pi算法其實不快的，主要用來測cpu速度了，呵呵。

doctorjxd

原帖由 emacsnw 于 2007-4-30 09:01 發(fā)表


super \pi算法其實不快的，主要用來測cpu速度了，呵呵。

同意, 但是一開始這個項目是用來在大型機上計算Pai的.

softsongs

恩，學(xué)習(xí)了，謝謝！
等哪天需要更加快速的計算大數(shù)階乘時，我可能會考慮GMP算法。

原帖由 win_hate 于 2007-4-29 21:52 發(fā)表
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還有一個數(shù)量級的差距。
主要原因是沒有利用計算機計算方冪快的性質(zhì)， 恩。

謝謝醉臥水云間 兄的關(guān)注！

原帖由 醉臥水云間 于 2007-4-29 22:34 發(fā)表
gmp的結(jié)果是：
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);
         ...