大整数算法之求阶乘

View Post

这几天闲暇时研究了一些关于大整数计算和存储的算法。关于这些方法，无非是用数组代替内置类型对大整数进行存储，然后进行适当的运算技巧进行并得到结果。下面是一个求阶乘的算法。n! = n*(n-1)*(n-2)*...*2

#include <stdio.h>
2

unsigned long long int fac[2570]={0},low_bit,multiplicand,carry_bit = 0;
4

/* 计算阶乘 m*(m-1)*(m-2)*

*n */
5

void factorial(int m, int n)
6

{
7

carry_bit = 0;
8

multiplicand = m;
9

//分离被乘数m，a[1]放个位，a[2]放10位

while(multiplicand)
11

{
12

low_bit++; //fac数组的第0位不用
13

fac[low_bit] = multiplicand%10;
14

multiplicand = multiplicand/10;
15

}
16

for (int multiplicator = m-1 ; multiplicator >= n ; --multiplicator)
17

{
18

carry_bit = 0; //carry_bit表示进位
19

for(int j = 1 ; j <= low_bit ; ++j)
20

{
21

fac[j] = fac[j]*multiplicator + carry_bit;
22

carry_bit = fac[j] / 10;
23

fac[j] = fac[j] % 10;
24

}
25

while(carry_bit)
26

{
27

low_bit++;
28

fac[low_bit] = carry_bit % 10;
29

carry_bit=carry_bit / 10;
30

}
31

}
32

}
34

int main()
36

{
37

factorial(40,2);
38

for(int index = low_bit ; index>=1 ; index--)
39

{
40

printf("%d",fac[index]);
41

}
42

getchar();
43

return 0;
44

}
45

结果为：815915283247897734345611269596115894272000000000

前一阵子研究python时，对它的长整数那块颇感兴趣，因为在python中是有“无限精度”的整数一说的，有空要拿它的源码来学习一下。

posted on 2011-05-19 11:45 熊猫呵呵阅读(962) 评论(0) 编辑收藏引用所属分类: 算法

只有注册用户登录后才能发表评论。
【推荐】100%开源！大型工业跨平台软件C++源码提供，建模，组态！

相关文章: 大整数算法之gcd(最大公约数) 大整数算法之求阶乘

网站导航: 博客园 IT新闻 BlogJava 博问 Chat2DB 管理

CodePanada

常用链接

留言簿

随笔分类

随笔档案

常去的地方

搜索

最新评论

阅读排行榜

评论排行榜

View Post

大整数算法之求阶乘