fx-5800Pで素因数分解

2013/11/01：追記
2015/01/25：追記
2019/07/10：追記
2020/05/25：追記
2020/12/24：追記

 CASIO の最新関数電卓：fx-995ESでは、幾つかの新しい機能が追加されている。

   
　　　　　　fx-995ES　　　　　　　　 fx-5800P


今回発売された fx-995ES に追加された新機能のうち、あったら便利だと思うのは総積と計算結果の初期表示を小数点にする機能くらいだと思う。

他の新機能、例えば

・原子量を得る機能
・PreAns機能
・素因数分解

などのうち、素因数分解を日常的に使う人は居ないだろう。

実用性とは別に、興味を惹いたのが素因数分解だ。
そこで、fx-5800P に素因数分解を実装してみようと思った。


素因数分解

全ての自然数は、素数の積で現され、その組み合わせは１通りしかない。

と言う素数の性質があるので、任意の自然数Nの素因数を探す時の順序は関係ないわけだ。

そこで、与えられた自然数Nに対して、２から順に１つづつ大きな数で割り算をして割り切れるかどうかを繰り返す、絨毯爆撃を行えば、全ての素因数を割り出せる。

そもそも素数は奇数なので、３以上は奇数だけで調べれば良い。


fx-5800P専用
素因数分解プログラム
======================
Lbl 0
Cls
"FACTORIZING"
"INPUT INTEGER"?→A
C→0:2→D:A→X
Do
X÷D→Y
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"
"<AC>:QUIT"
While Getkey≠67
WhileEnd
Goto 0
======================


実行すると、最初にプログラムの説明を表示する。

-----------------
FATORIZING
INPUT INTEGER?
-----------------

ここで、12345 を入力して[EXE]キーを押すと、

-----------------
　　　　　　　　        3
TO THE
　　　　　　　　        1
-----------------
と表示される。３の１乗と言う意味の英語にしてある。


さらに[EXE]キーを押すと、
-----------------
　　　　　　　　       5
TO THE
　　　　　　　　       1
-----------------
と表示。５の１乗と言うことだ。


さらに[EXE]キーを押すと、少し時間がかかるが
-----------------
　　　　　　         823
TO THE
　　　　　　　　        1
-----------------
823の１乗と表示される。
割と大きな素数が出てきた。


さらに[EXE]キーを押すと、
-----------------
COMPLETED

<->:TRY OTHERS
<AC>:QUIT
-----------------
と表示され、続けるか終わるかを聞いてくる。


上記の 12345 の素因数分解では、素数 823 が出てくるのに23秒かかった。比較のために、fx-995ESで12345の素因数分解を行うと、２秒程度で答えが出てくる。組み込み機能は１０倍速い。

一方で、fx-955ESに組込まれている素因数分解機能は、素因数が３桁まででないと計算しない仕様になっている。

方や、fx-5800Pのプログラムでは、時間をかければ、もっと大きな素因数でも答えを出してくれる。

例えば、987654321 = ３^２ x １７^２ x 379721 と、６桁の素因数が得られた。
但し、この計算には３時間もかかるので、これ以上は試していない。


いずれにせよ、電卓でプログラムを組むと遅い。

EXCELのVBAで同じロジックのプログラムを作って動作させてみると、上記の 987654321の素因数分解でも一瞬で答えが出る。

参照： ＶＢＡで素因数分解　【2013/11/1 追記】



電卓の遅い処理時間の実感を掴むために、処理速度を調べてみた。

そして、色々な自然数で素因数分解をしてみた結果から、
Do～LpWhileループが回る時間が、45m秒程度かかることが分かった。

全くの推測だが、太陽電池で動作させる程度の省電力が要求されるため、かなりクロックを落としているものと思われる。
その上、各コマンドの実行には、エラー検知やある程度余計な内部処理が含まれることも、処理速度に影響しているのだろう。

最初から機能として組み込まれている fx-955ES の処理速度が１０倍程度速いことからも、プログラム実行にはかなり余分な処理を伴っていることがよく分かる。


==========

その後、素因数分解プログラムの高速化や多くの機種への移植を行ってきたので、その歴史を以下にまとめる。

[2020/12/24 追記]
C.Basic を使って fx-CG50 で素因数分解する数を15桁まで拡張しました。
　⇒ グラフ関数電卓 - 高速素因数分解、15桁対応

[2020/10/22 追記]
Pythonモードを使って fx-CG50 で15桁の高速素因数分解スクリプトの作成；
fx-CG50 Casio Basic プログラムを Casio Python に移植しました。
　⇒ Casio Python - シェル画面入力の工夫：高速素因数分解(1) 
　⇒ Casio Python - Pythonらしい反復処理：高速素因数分解(2)
　⇒ Casio Python - 大きな数の計算：高速素因数分解(3)
　⇒ Casio Python - 関数呼出オーバーヘッド：高速素因数分解(4)
　⇒ Casio Python - 要素数の多いリスト：高速素因数分解(5)
　⇒ Casio Python - 10進数除算の出力と精度：高速素因数分解(7)

[2020/12/05 追記]
fx-5800P で最速の素因数分解プログラムをさらに高速化できました。
　⇒ fx-5800P 素因数分解 - さらなる高速化

[2019/07/10 追記]
fx-5800P で4敗に高速化した素因数分解プログラムを紹介しています。
fx-CG50など主なグラフ関数電卓へ移植したプログラムもダウンロードできます。
　⇒ fx-5800P 素因数分解 - 高速化

[2015/01/25 追記]
fx-5800P を使った素因数分解については、続編として以下のエントリーがあります。
　⇒ fx-5800P で素因数分解再び
　⇒ fx-5800P 素因数分解 - バグ修正と表示変更

fx-9860GII への移植
　⇒ fx-9860GII への移植 - 素因数分解




応援クリックをお願いします。励みになるので．．．

にほんブログ村

人気ブログランキング

FC2ブログランキングへ

 


keywords: fx-5800P、素因数分解、fx-995ES、プログラミング、プログラム関数電卓

---

リンク集　|　ブログ内マップ