1 #include <iostream>
2 #include <vector>
3 #include <time.h>
4 #include <iomanip>
5 using namespace std;
6
7 //使用数组保存，一个int元素保存5位数
8 class LongInt1
9 {
10 public:
11 LongInt1 ();
12 LongInt1 &operator *(const int x);
13 friend ostream &operator <<(ostream & out, LongInt1 &longint);
14 private:
15 vector<int> vec;
16 };
17
18 LongInt1::LongInt1()
19 {
20 vec.push_back(1);
21 }
22
23 LongInt1 &LongInt1::operator*(const int x)
24 {
25 int carry = 0;
26 int product = 0;
27 for (vector<int>::iterator it = vec.begin(); it != vec.end(); it++)
28 {
29 //每一个元素乘x
30 product = (*it) * x + carry;
31
32 //超过5位产生进位
33 carry = product / 100000;
34
35 //5位以下为当前位
36 (*it) = product % 100000;
37 }
38 if (carry != 0)
39 {
40 //最后的进位
41 vec.push_back(carry);
42 }
43 return *this;
44 }
45 ostream &operator<<(ostream & out, LongInt1 &longint)
46 {
47 for (vector<int>::reverse_iterator rit = longint.vec.rbegin(); rit !=longint.vec.rend(); rit++)
48 {
49 cout << (*rit) << "";
50 }
51 return out;
52 }
53 class LongInt2
54 {
55 public:
56 LongInt2 (int len);
57 LongInt2 &operator *(const int x);
58 friend ostream &operator <<(ostream & out, LongInt2 &longint);
59 private:
60 int *num;
61 size_t size;
62 size_t high;
63 };
64
65 LongInt2::LongInt2(int len)
66 {
67 size= len / 5 + 1;
68 num = new int[size];
69 num[0] = 1;
70 high = 1;
71 }
72
73 LongInt2 &LongInt2::operator*(const int x)
74 {
75 int carry = 0;
76 int product = 0;
77 for (int i = 0; i < high; i++)
78 {
79 product = num[i] * x + carry;
80 carry = product / 100000;
81 num[i] = product % 100000;
82 }
83 if (carry != 0)
84 {
85 num[high++] = carry;
86 }
87 return *this;
88 }
89 ostream &operator<<(ostream & out, LongInt2 &longint)
90 {
91 for (int i = longint.high - 1; i >= 0; i--)
92 {
93 cout << longint.num[i] << "";
94 }
95 return out;
96 }
97
98 LongInt1 factorial1(int n)
99 {
100 LongInt1 re;
101 for (int i = 1; i <= n; i++)
102 {
103 re = re * i;
104 }
105 return re;
106 }
107 LongInt2 factorial2(int n)
108 {
109 /*可以将n!表示成10的次幂,即n!=10^M(10的M次方)则不小于M的最小整数就是 n!的位数，
110 对该式两边取对数，有=log10^n!即：
111 M = log10^1+log10^2+log10^3...+log10^n
112 循环求和,就能算得M值，该M是n!的精确位数。*/
113 double len = 1.0;
114 for(int i = 1; i <= n; i++)
115 len += log10((long double)i);
116 LongInt2 re((int)len);
117 for (int i = 1; i <= n; i++)
118 {
119 re = re * i;
120 }
121 return re;
122 }
123
124 int main()
125 {
126 int n = 10000;
127 clock_t start, end;
128 double d;
129 cout << setprecision(10) << fixed;
130 start = clock();
131 LongInt1 re1 = factorial1(n);
132 end = clock();
133 d = double(end - start)/CLOCKS_PER_SEC;
134 //cout << re1 << endl;
135 cout << d << endl;
136
137 start = clock();
138 LongInt2 re2 = factorial2(n);
139 end = clock();
140 d = double(end - start)/CLOCKS_PER_SEC;
141 //cout << re2 << endl;
142 cout << d << endl;
143 }