fx-5800Pで素因数分解再び
【2014/10/29 再修正】
【2013/12/04 修正】
【2014/12/05 誤字修正】
以前、fx-5800Pで作った素因数分解のプログラムを紹介した。
以前の記事は、fx-5800Pで素因数分解を参照。
素因数を見つけるループの1回の実行時間を推定したところ、45ミリ秒ほどかかっていることが分かった。全ての自然数を検索する方法では実測値が[素因数の数和] × 45ミリ秒 の計算値とほぼ一致したことから、このループの実行時間はほぼ45ミリ秒程度とと考えている(その後、奇数のみを調べるようにプログラムを変更している)。
これを読んで下さったKENさん(長野県)からコメント(非公開)を頂き、「条件にもよるが大幅に高速化できる」という具体的なプログラムソースの改善案を頂いた。
=========================
ある数Xの素因数をするときにはsqrtXまで調べれば十分であることを使いました。(例えば51を素因数分解するのに、7まで調べたら9以上は調べる必要がない)
以下Lp Whileの前後に追加したソースです。
---
If C=0 And D>Y
Then 0→Y
If End
Lp While Y≧1
If Y=0 And X≠1
Then X⊿
"TO THE":1⊿
If End
---
いかがでしょうか。
こうすることで特に(素因数分解の最後に残る)大きい素数が、一つだけ出てくるときに効果を発揮します。
12345の素因数分解(823の素数判定)はわずか1秒ほどで終わります。ただし、521×523=272483のように最大の素数とそれに次ぐ素数の差が小さいときは、ソースが増えた分、元のプログラムよりも数秒余計にかかってしまうようです。
3時間以上かかったという987654321は30秒で終わりました。
この案、是非いかがでしょうか。
=========================
ありがとうございます。改めてKENさんにお礼を申し上げます。
頂いたコンセプトに従って、具体的にプログラムの改良を試みたので紹介する。
元のプログラムソースに、赤で示した3行を追加することで、このコンセプトの追加ができた【修正】。
なお、元のプログラム名「Factorizing」は因数分解と言う意味で不適切だったので、素因数分解:Prime Decompositionから、プログラム名を「PRIME DECOMP」と変更した(青字で変更を示した)。
fx-5800P用
素因数分解改良プログラム
PRIME DECOMP
====================
Lbl 0
Cls
"PRIME DECOMP"
"INPUT INTEGER"?→A
0→C:2→D:A→X
Do
X÷D→Y
If C=0 And Y<D : 2014/10/29 修正
Then X→D:X÷D→Y
IfEnd
If Frac(Y)=0
Then Y→X:Isz C
Else
If C≠0
Then
D▲
"TO THE":C▲
0→C
IfEnd
If D=2
Then Isz D
Else Isz D:Isz D
IfEnd
IfEnd
LpWhile Y≧1
Cls
"COMPLETED"
""
"<->:TRY OTHERS"
":QUIT"
While Getkey≠67
WhileEnd
Goto 0
====================
KENさんのご提案よりも変更部分の少ない修正にしてみた(赤の部分)。
なお、この If C=0 And Y<D [2014/10/29 修正] による判定はループが回るたびに必ず1回実行されるが、中の Then x→D:X÷D→Y は1回しか実行されないので、ループの実行速度は、KENさんのご提案と変わらない。
この If 文の判定だが、If C=0 And Y≦√(X) としても良いが、123456789 の素因数分解では15秒ほど余計に時間がかかる。
平方根よりも小さくなる時、KENさんの案では Y を 0 にしている。私の案では D を X に変更することで、結果的に Y が 1 になる。いずれもDoループを抜けるための方策である。この点でも実行速度に大きな違いは無い。
私の案は、結果表示を新たに追加しないでプログラムを改造するという点にチョットこだわった。D を X に変更すると、結果的に Y が 1 になり、従って最後にもう一回ループが回ることから、Do ループを抜けた後に結果表示のコードを書く必要が無くなるわけだ。
この変更により、実行時間が以下のように大幅に改善された【修正】。
目を見張るべき時間短縮となった( ^o^)ノ
KENさんのご指摘のように、大きな素因数が1つだけ出てくる場合に速度向上が顕著だ。しかし、32 x 3607 x 3803 のように似たような3桁の素因数が含まれる場合は、それほど大きな高速化はできない。√X の効果が出るまでに、D を2づつ増やすのに時間がかかるためと考えている。その証拠に一旦 3607 が出ると、次の 3803 がほぼ瞬時に得られる。
なお、今回の改善で計算速度は向上したが、 カシオの最新の関数電卓 fx-995ES に内蔵されている素因数分解の計算速度には及ばない。
応援クリックをお願いします。励みになるので...
【2013/12/04 修正】
【2014/12/05 誤字修正】
以前、fx-5800Pで作った素因数分解のプログラムを紹介した。
以前の記事は、fx-5800Pで素因数分解を参照。
素因数を見つけるループの1回の実行時間を推定したところ、45ミリ秒ほどかかっていることが分かった。全ての自然数を検索する方法では実測値が[素因数の数
これを読んで下さったKENさん(長野県)からコメント(非公開)を頂き、「条件にもよるが大幅に高速化できる」という具体的なプログラムソースの改善案を頂いた。
=========================
ある数Xの素因数をするときにはsqrtXまで調べれば十分であることを使いました。(例えば51を素因数分解するのに、7まで調べたら9以上は調べる必要がない)
以下Lp Whileの前後に追加したソースです。
---
If C=0 And D>Y
Then 0→Y
If End
Lp While Y≧1
If Y=0 And X≠1
Then X⊿
"TO THE":1⊿
If End
---
いかがでしょうか。
こうすることで特に(素因数分解の最後に残る)大きい素数が、一つだけ出てくるときに効果を発揮します。
12345の素因数分解(823の素数判定)はわずか1秒ほどで終わります。ただし、521×523=272483のように最大の素数とそれに次ぐ素数の差が小さいときは、ソースが増えた分、元のプログラムよりも数秒余計にかかってしまうようです。
3時間以上かかったという987654321は30秒で終わりました。
この案、是非いかがでしょうか。
=========================
ありがとうございます。改めてKENさんにお礼を申し上げます。
頂いたコンセプトに従って、具体的にプログラムの改良を試みたので紹介する。
元のプログラムソースに、赤で示した3行を追加することで、このコンセプトの追加ができた【修正】。
なお、元のプログラム名「Factorizing」は因数分解と言う意味で不適切だったので、素因数分解:Prime Decompositionから、プログラム名を「PRIME DECOMP」と変更した(青字で変更を示した)。
fx-5800P用
素因数分解改良プログラム
PRIME DECOMP
====================
Lbl 0
Cls
"PRIME DECOMP"
"INPUT INTEGER"?→A
0→C:2→D:A→X
Do
X÷D→Y
If C=0 And Y<D : 2014/10/29 修正
Then X→D:X÷D→Y
IfEnd
If Frac(Y)=0
Then Y→X:Isz C
Else
If C≠0
Then
D▲
"TO THE":C▲
0→C
IfEnd
If D=2
Then Isz D
Else Isz D:Isz D
IfEnd
IfEnd
LpWhile Y≧1
Cls
"COMPLETED"
""
"<->:TRY OTHERS"
"
While Getkey≠67
WhileEnd
Goto 0
====================
KENさんのご提案よりも変更部分の少ない修正にしてみた(赤の部分)。
なお、この If C=0 And Y<D [2014/10/29 修正] による判定はループが回るたびに必ず1回実行されるが、中の Then x→D:X÷D→Y は1回しか実行されないので、ループの実行速度は、KENさんのご提案と変わらない。
この If 文の判定だが、If C=0 And Y≦√(X) としても良いが、123456789 の素因数分解では15秒ほど余計に時間がかかる。
平方根よりも小さくなる時、KENさんの案では Y を 0 にしている。私の案では D を X に変更することで、結果的に Y が 1 になる。いずれもDoループを抜けるための方策である。この点でも実行速度に大きな違いは無い。
私の案は、結果表示を新たに追加しないでプログラムを改造するという点にチョットこだわった。D を X に変更すると、結果的に Y が 1 になり、従って最後にもう一回ループが回ることから、Do ループを抜けた後に結果表示のコードを書く必要が無くなるわけだ。
この変更により、実行時間が以下のように大幅に改善された【修正】。
入力した自然数 | 結果 | 改造前の時間 | 改造後の時間 |
12345 | 3 x 5 x 823 | 20秒 | 2.5秒 |
123456 | 26 x 3 x 643 | 20秒 | 3秒 |
1234567 | 127 x 9721 | 4分 | 1秒 |
12345678 | 2 x 32 x 47 x 14593 | 6分 | 8秒 |
123456789 | 32 x 3607 x 3803 | 約5分 | 3分 |
987654321 | 32 x 172 x 379721 | 3時間以上 | 33秒 |
98765432 | 23 x 37 x 333667 | 2.5時間 | 43秒 |
9876543 | 3 x 227 x 14503 | 6分 | 12秒 |
987654 | 2 x 3 x 97 x 1697 | 7秒 | 6.5秒 |
98765 | 5 x 19753 | 8分 | 8秒 |
9876 | 22 x 3 x 823 | 20秒 | 3秒 |
目を見張るべき時間短縮となった( ^o^)ノ
KENさんのご指摘のように、大きな素因数が1つだけ出てくる場合に速度向上が顕著だ。しかし、32 x 3607 x 3803 のように似たような3桁の素因数が含まれる場合は、それほど大きな高速化はできない。√X の効果が出るまでに、D を2づつ増やすのに時間がかかるためと考えている。その証拠に一旦 3607 が出ると、次の 3803 がほぼ瞬時に得られる。
なお、今回の改善で計算速度は向上したが、 カシオの最新の関数電卓 fx-995ES に内蔵されている素因数分解の計算速度には及ばない。
応援クリックをお願いします。励みになるので...