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 }
转载于:https://www.cnblogs.com/yysblog/archive/2011/11/27/2265147.html
相关资源：数据结构—成绩单生成器
