teratail
回答率
85.37%
teratail 10th-anniversary
teratail 10th-anniversary
質問するログイン新規登録
トップC++に関する質問【C++】大きな数の階乗計算が途中で止まってしまう

編集履歴

回答編集履歴

5

削除

2020/08/21 21:17

投稿

mjk
mjk

スコア303

test CHANGED
@@ -1,189 +1 @@
1
- > nの大きさとしては10万以下を想定しているのですが
2
-
3
- > n = 26033 までは正常に動作するのですが
4
-
5
-
6
-
7
- ##**そもそも**
8
-
9
- C++で扱える整数型の最大値を21!の時点で超えているはずです。
10
-
11
- %MODの計算をする以前に21!を計算した時点で桁あふれによって変数の値がおかしくなっているはずです。
12
-
13
- unsigned long long 型変数の最大値を使ったとしても20!までしか正確な計算は出来ないはずです。
14
-
15
-
16
-
17
- 20桁を超える計算をするには多桁計算を実装したりBOOSTの多倍長整数を利用するなどが必要かと思います。
18
-
19
-
20
-
21
- `constexpr unsigned long long INF = std::numeric_limits<unsigned long long>::max();`
22
-
23
- unsigned long long 型変数の最大値(20桁) = 18,446,744,073,709,551,615
24
-
25
-
26
-
27
- ##Win10の関数電卓で計算
28
-
29
- 20!では超えていませんが、21!でunsigned long long 型変数の最大値を超えてしまっています。
30
-
31
- ![](909402925e328c023d681398db1c05ef.jpeg)
32
-
33
-
34
-
35
- ##n!出力して20!と21!を確認するサンプル
36
-
37
- ![イメージ説明](aac179b55299882850c6c330c9e50384.jpeg)
38
-
39
- INF-n!が減り続けるはずなのに21!以降の結果を見ると増えたり減ったりしている。
40
-
41
- 21!以降では桁あふれによってn!の値が正確でないことが確認出来る。
42
-
43
-
44
-
45
- ```C++
46
-
47
- #include <bits/stdc++.h>
48
-
49
- std::vector<unsigned long long> v;
50
-
51
- constexpr unsigned long long INF = std::numeric_limits<unsigned long long>::max();
52
-
53
-
54
-
55
- int main() {
56
-
57
- std::cin.tie(0);
58
-
59
- std::ios::sync_with_stdio(false);
60
-
61
-
62
-
63
- unsigned long long N;
64
-
65
- std::cin >> N;
66
-
67
- v.resize(N + 1, 0);
68
-
69
-
70
-
71
- v[0] = 1;
72
-
73
- for (unsigned long long i = 1; i <= N; ++i) {
74
-
75
- v[i] = v[i - 1] * i;
76
-
77
- }
78
-
79
-
80
-
81
- for (unsigned long long i = 0; i <= N; ++i) {
82
-
83
-
84
-
85
- std::cout << std::setfill('0') << std::right << std::setw(2) << i;
86
-
87
- std::cout << " : INF:" << INF << " -i!:";
88
-
89
- std::cout << std::setfill('0') << std::right << std::setw(20) << v[i] << " ";
90
-
91
- std::cout << std::setfill('0') << std::right << std::setw(20) << INF - v[i];
92
-
93
-
94
-
95
- if (i == 20 or i == 21) {
96
-
97
- std::cout << "***";
98
-
99
- }
100
-
101
- std::cout << std::endl;
102
-
103
- }
104
-
105
-
106
-
107
- getchar();
108
-
109
- return 0;
110
-
111
- }
112
-
113
- ```
114
-
115
-
116
-
117
- ##本題の再帰処理テスト
118
-
119
- 自環境で階乗計算のみ再帰計算させて確認したところ、`n=32503`　以降で例外エラーとなりました。
120
-
121
- 途中から桁あふれてるので計算結果は全て0となっています。
122
-
123
- 仮に桁あふれを考慮して正確な計算をしたとしても再帰処理が深くなりすぎると処理が継続出来なくなるということです。
124
-
125
-
126
-
127
- > 再帰呼び出しを繰り返していくとスタックを消費しますので、再帰できる回数には限度があります。
128
-
129
- maisumakunさんがすでに回答されているとおりです。
130
-
131
-
132
-
133
- `例外が発生しました`
1
+ ご指摘がありましたの回答を削除しました。
134
-
135
- `Segmentation fault`
136
-
137
- 実行環境やコンパイル環境で多少の差は出ると思います。
138
-
139
- ![イメージ説明](3d7f107ed3c4f48f4ac78a4c2de73dc0.jpeg)
140
-
141
-
142
-
143
- ```C++
144
-
145
- #include <bits/stdc++.h>
146
-
147
-
148
-
149
- const long long MOD = 1E+09 + 7;
150
-
151
- long long f(const long long &n) {
152
-
153
- if (n == 0) {
154
-
155
- return 1;
156
-
157
- }
158
-
159
- return f(n - 1) * n;
160
-
161
- }
162
-
163
-
164
-
165
- int main() {
166
-
167
- std::cin.tie(0);
168
-
169
- std::ios::sync_with_stdio(false);
170
-
171
-
172
-
173
- long long n = 100000;
174
-
175
- for (long long i = 0; i <= n; i++) {
176
-
177
- std::cout << "(" << i << "!) % " << MOD << " = " << f(i) % MOD << std::endl;
178
-
179
- }
180
-
181
-
182
-
183
- getchar();
184
-
185
- return 0;
186
-
187
- }
188
-
189
- ```

4

追記　再帰処理のテスト

2020/08/21 21:16

投稿

mjk
mjk

スコア303

test CHANGED
@@ -116,7 +116,17 @@
116
116
 
117
117
  ##本題の再帰処理テスト
118
118
 
119
- 自環境で階乗計算のみ再帰計算させるて確認したところ、`n=32503`　以降で例外エラーとなりました。
119
+ 自環境で階乗計算のみ再帰計算させて確認したところ、`n=32503`　以降で例外エラーとなりました。
120
+
121
+ 途中から桁あふれてるので計算結果は全て0となっています。
122
+
123
+ 仮に桁あふれを考慮して正確な計算をしたとしても再帰処理が深くなりすぎると処理が継続出来なくなるということです。
124
+
125
+
126
+
127
+ > 再帰呼び出しを繰り返していくとスタックを消費しますので、再帰できる回数には限度があります。
128
+
129
+ maisumakunさんがすでに回答されているとおりです。
120
130
 
121
131
 
122
132
 

3

追記　再帰処理のテスト

2020/08/21 20:36

投稿

mjk
mjk

スコア303

test CHANGED
@@ -111,3 +111,69 @@
111
111
  }
112
112
 
113
113
  ```
114
+
115
+
116
+
117
+ ##本題の再帰処理テスト
118
+
119
+ 自環境で階乗計算のみ再帰計算させるて確認したところ、`n=32503`　以降で例外エラーとなりました。
120
+
121
+
122
+
123
+ `例外が発生しました`
124
+
125
+ `Segmentation fault`
126
+
127
+ 実行環境やコンパイル環境で多少の差は出ると思います。
128
+
129
+ ![イメージ説明](3d7f107ed3c4f48f4ac78a4c2de73dc0.jpeg)
130
+
131
+
132
+
133
+ ```C++
134
+
135
+ #include <bits/stdc++.h>
136
+
137
+
138
+
139
+ const long long MOD = 1E+09 + 7;
140
+
141
+ long long f(const long long &n) {
142
+
143
+ if (n == 0) {
144
+
145
+ return 1;
146
+
147
+ }
148
+
149
+ return f(n - 1) * n;
150
+
151
+ }
152
+
153
+
154
+
155
+ int main() {
156
+
157
+ std::cin.tie(0);
158
+
159
+ std::ios::sync_with_stdio(false);
160
+
161
+
162
+
163
+ long long n = 100000;
164
+
165
+ for (long long i = 0; i <= n; i++) {
166
+
167
+ std::cout << "(" << i << "!) % " << MOD << " = " << f(i) % MOD << std::endl;
168
+
169
+ }
170
+
171
+
172
+
173
+ getchar();
174
+
175
+ return 0;
176
+
177
+ }
178
+
179
+ ```

2

0!=1修正の画像差し替え

2020/08/21 20:30

投稿

mjk
mjk

スコア303

test CHANGED
@@ -34,7 +34,7 @@
34
34
 
35
35
  ##n!出力して20!と21!を確認するサンプル
36
36
 
37
- ![イメージ説明](a16f6733061b7a69f9fc6daa92a62943.jpeg)
37
+ ![イメージ説明](aac179b55299882850c6c330c9e50384.jpeg)
38
38
 
39
39
  INF-n!が減り続けるはずなのに21!以降の結果を見ると増えたり減ったりしている。
40
40
 

1

0!=1を修正

2020/08/21 19:37

投稿

mjk
mjk

スコア303

test CHANGED
@@ -36,6 +36,10 @@
36
36
 
37
37
  ![イメージ説明](a16f6733061b7a69f9fc6daa92a62943.jpeg)
38
38
 
39
+ INF-n!が減り続けるはずなのに21!以降の結果を見ると増えたり減ったりしている。
40
+
41
+ 21!以降では桁あふれによってn!の値が正確でないことが確認出来る。
42
+
39
43
 
40
44
 
41
45
  ```C++
@@ -64,9 +68,9 @@
64
68
 
65
69
 
66
70
 
67
- v[1] = 1;
71
+ v[0] = 1;
68
72
 
69
- for (unsigned long long i = 2; i <= N; ++i) {
73
+ for (unsigned long long i = 1; i <= N; ++i) {
70
74
 
71
75
  v[i] = v[i - 1] * i;
72
76