|
高速化手法 |
|
級数演算 |
| 最終更新日：2006/12/14
新規 |
●概要
標準的な級数の型における演算について解説する。
●Linear
Xk / k
○演算内容
黒が直前の値。赤は追加される演算アイテム。
| k |
演算 |
| 1 |
X
/ 1 |
| 2 |
X・X
/ 2 |
| 3 |
X2・X
/ 3 |
○演算カーネル
SX = 1
Xk
SM = 0 総和
k = 1 To ??????
SX = SX * X
SM = SM + SX / k
Loop
○演算種
k ＜ Baseと仮定する。Numは多倍長。
| 演算 |
XがBase未満 |
XがNum |
| MulI |
1 |
|
| Mul |
|
1 |
| DivI |
1 |
1 |
| Add |
1 |
1 |
●LinearOdd X2k+1
/ (2k + 1)
○演算内容
黒が直前の値。赤は追加される演算アイテム。
| k |
演算 |
| 0 |
X
/ 1 |
| 1 |
X・X・X
/ 3 |
| 2 |
X3・X・X
/ 5 |
○演算カーネル
XX = X・X
SX = X X2k+1
SM = X 総和
k = 1 To
??????
SX = SX * XX
SM = SM + SX / (2k + 1)
Loop
○演算種
k ＜ Baseと仮定する。
| 演算 |
XがBase未満 |
XがNum |
| MulI |
1 |
|
| Mul |
|
1 |
| DivI |
1 |
1 |
| Add |
1 |
1 |
●Factorial
Xk /
k!
○演算内容
黒が直前の値。
| k |
演算 |
| 0 |
1 |
| 1 |
X
/ 1 |
| 2 |
X・X
/ 1・2 |
| 3 |
X2・X
/ 1・2・3 |
○演算カーネル
SX = 1
Xk/ k!
SM = 0 総和
k = 1 To
??????
SX = SX * X
SX = SX / k
SM = SM + SX
Loop
○演算種
k ＜ Baseと仮定する。
| 演算 |
XがBase未満 |
XがNum |
| MulI |
1 |
|
| Mul |
|
1 |
| DivI |
1 |
1 |
| Add |
1 |
1 |
●FactorialEven
X2k / (2・k)!
○演算内容
黒が直前の値。
| k |
演算 |
| 0 |
1 |
| 1 |
X・X
/ 1・2 |
| 2 |
X2・X・X
/ 1・2・3・4 |
| 3 |
X4・X・X
/ 1・2・3・4・5・6 |
○演算カーネル
SX = 1
X2k / (2・k)!
SM = 0 総和
XX = X・X
k = 1 To
??????
SX = SX * XX
SX = SX / ((2k
–
1)・2k)
SM = SM + SX
Loop
・カーネルの高速化
2k ＞
Sqrt(Base) の場合は、SX = SX / ((2k
–
1)・2k) は、以下のように二回に分ける。
SX = SX /
(2k –
1)
SX = SX / 2k
多倍長の除算1回より、DivI
(多倍長/Base) 2回の方が圧倒的に早いからである。
○演算種
| 演算 |
XXがBase未満 |
XがNum |
| MulI |
1 |
|
| Mul |
|
1 |
| DivI |
1 or 2 |
1 or 2 |
| Add |
1 |
1 |
●FactorialOdd
X2k+1 / (2・k + 1)!
○演算内容
黒が直前の値。
| k |
演算 |
| 0 |
X |
| 1 |
X・X・X
/ 1・2・3 |
| 2 |
X3・X・X
/ 1・2・3・4・5 |
| 3 |
X5・X・X
/ 1・2・3・4・5・6・7 |
○演算カーネル
SX = X
X2k+1 / (2・k + 1)!
SM = X 総和
XX = X・X
k = 1 To
??????
SX = SX * XX
SX = SX / (2k・(2k
+ 1))
SM = SM + SX
Loop
・カーネルの高速化
(2k + 1)
＞ Sqrt(Base) の場合は、SX = SX /
(2k・(2k
+ 1)) は、以下のように二回に分ける。
SX = SX / 2k
SX = SX / (2k + 1)
多倍長の除算1回より、DivI
(多倍長/Base) 2回の方が圧倒的に早いからである。
○演算種
| 演算 |
XXがBase未満 |
XがNum |
| MulI |
1 |
|
| Mul |
|
1 |
| DivI |
1 or 2 |
1 or 2 |
| Add |
1 |
1 |
●FactorialDoubleEven
(2k-1)!!/((2k)!!(2k))・X-(2k)
○演算内容
黒が直前の値。緑はその項にだけ適用される数。
| k |
演算 |
| 1 |
(1
/ 2・2)
/ X・X |
| 2 |
(1・3
/ 2・4・4)/
X2・X・X |
| 3 |
(1・3・5
/ 2・4・6・6)/
X4・X・X |
○演算カーネル
XX = X・X
SX = 1
SM = 0
k = 1 To ????
SX = SX・(2k
– 1)
SX = SX / 2k
SX = SX / XX
SM = SM + SX / 2k
Loop
○演算種
| 演算 |
XXがBase未満 |
XがNum |
| |
2k ＜
Base |
2k ≧
Base |
2k ＜
Base |
2k ≧
Base |
| MulI |
1 |
|
|
|
| Mul |
|
1 |
1 |
1 |
| DivI |
3 |
1 |
2 |
|
| Div |
|
2 |
1 |
3 |
| Add |
1 |
1 |
1 |
1 |
●FactorialDoubleOdd
(2k-1)!!/((2k)!!(2k + 1))・X(2k+1)
○演算内容
黒が直前の値。緑はその項にだけ適用される数。
| k |
演算 |
| 0 |
X |
| 1 |
(1 / 2・3)・X・X・X |
| 2 |
(1・3
/ 2・4・5)・X3・X・X |
| 3 |
(1・3・5
/ 2・4・6・7)・X5・X・X |
○演算カーネル
XX = X・X
SX = X
SM = X
k = 1 To ????
SX = SX・(2k - 1)
SX = SX / 2k
SX = SX ・XX
SM = SM + SX / (2k + 1)
Loop
○演算種
| 演算 |
XXがBase未満 |
XがNum |
| |
(2k + 1) ＜
Base |
(2k + 1) ≧
Base |
(2k + 1) ＜
Base |
(2k + 1) ≧
Base |
| MulI |
2 |
1 |
1 |
|
| Mul |
|
1 |
1 |
2 |
| DivI |
2 |
|
2 |
|
| Div |
|
2 |
|
2 |
| Add |
1 |
1 |
1 |
1 |
|