fx-5800P 素因数分解 - さらなる高速化
追記修正:2020/12/05
バグフィックス:2021/01/02
今回は高速化するために、あらゆる使えるものを総動員して fx-5800P Casio Basic プログラムを効率よく作成する、一風変わったアプローチを採用することになりました。
▋fx-5800P の Casio Basic プログラムをPCで編集
カシオは、fx-5800PのプログラムやデータをPCリンクする手段を提供していませんが、takumako様によりPCリンクするハードウェアとソフトウェア - CcLinker が提供されています。さらに fx-5800P の Casio Basic プログラムをPCで編集するためのエディタ - CcEditor が提供されています。
それぞれの使い方については、以下を参照してください。
▶ CcLinker - ついに fx-5800P がPCリンク可能になった を参照
▶ CcEditor - fx-5800P Casio Basic をPCでコーディング - CcEditor を参照
▍fx-5800P のプログラムをファイルに変換する
今回改造する fx-5800P の Casio Basic プログラム - Factor-F1 を CcLinker でPCに転送します。
▶ FACTOR-F1 のダウンロード [2021/01/02 バグフィックス]
バグフィックス:終了時に配列変数を解放しない点を修正し、不要な WhileEndを削除しました。
※ ダウンロードした zip ファイルには、fx-5800P で使う2つの ccl ファイルとそれらのテキストファイルを含んでいます。FACTOR-F1.cll と WFSUB.ccl を fx-5800P に転送すれば、FACTOR-F1 を走らせられます。
CcLinkerドングルをPCに刺してから、fx-5800P をつなぎ、CcLinker ソフトウェアを起動します。

fx-5800P 素因数分解 - 高速化 で作ったプログラム FACTOR-F1 を fx-5800P から PC へ転送すると、転送したファイルを保存するコモンダイアログが現れます。

ファイル名を FACTOR-F1.ccl にして、[開く] をクリック。
この場合は、Download フォルダにダウンロードしているので、Download フォルダに FACTOR-F1.ccl が作成されます。
FACTOR-F1 は サブルーチンとして WFSUB を使っています。結論から言えば WFSUB は変更しないので、そのままにしておきます。
▍FACTOR-F1.ccl を CcEditor で開く
今回編集するプログラムがファイル FACTOR-F1.ccl になったので、それを編集するために CcEditor で開きます。

CcEditor で fx-5800P のプログラム FACTOR-F1 が編集できるようになりました。
▋素因数分解の基本的アルゴリズム
あらゆる整数は、素数の積で表せるので、その素数の積を求めるのが素因数分解です。
ところで、素数とは、1と自分自身以外で割り切れない (1と自分自身以外の約数がない) 整数です。
ちなみに、1は素数ではなく、2,3、5、7,11,13、17、19,23 ... と素数は無限にあります。
与えられた数 (自然数) をそれより小さい自然数 (=探索数) で割って、割り切れるかどうかを調べます、割り切れるかどうかを調べる自然数を探索数と呼ぶことにします。
- 与えられた数を最小の素数2で割って割り切れたら、2は素因数の1つです。2で割り切れる場合は、何回2で割り切れるかを調べます。そして、2の倍数を探索数から除外します。
- 2の次に大きな素数は3なので、与えられた数が3で割り切れるかどうかを調べ、割り切れる場合は何回3で割り切れるかどうかを調べます。そして、3の倍数も探索数から除外します。
- 3の次に大きな素数は5なので、与えられた数が5で割り切れるかどうかを調べます。割り切れる場合は何回5で割り切れるかを調べます、そして探索数から5の倍数も除外します。
与えられた数が平方数 (平方根が整数になる数) の場合、その平方根が素数であることもあり、その場合は最大の素因数になります。与えられた数の平方数でなくても、その平方根 より小さく。その平方根に一番近い整数が最大の探索数になります。
プログラムファイルのサイズの上限が限られ、プログラム実行速度が遅い fx-5800P の Casio Basic では、割り算に用いる探索数をどうやって効率よく絞り込むかが、プログラム高速化のポイントになります。
▋高速素因数分解のアルゴリズム
以前紹介した高速素因数分解のアルゴリズムは、エラストテレスの篩い を効率化したもので、具体的には以下の方法で探索数を絞り込んでいます。
▶ 探索数増分数を48個使って、効率よく探索数を絞り込む方法
a) 素数 2, 3, 5, 7, 11 を探索数として除算を繰り返し、
b) 13以上で 2, 3, 5, 7 のいずれかの倍数でもない探索数は 13~222 までには 210個の整数のうち48個あり、その48個の探索数で除算を繰り返し、
a) b) それぞれの除算の結果から素因数を調べます。13~222までの210個の整数のうち48個まで探索数を絞り込んでいます。詳しくは、前回の記事 を参照してください。
a)
Int(√(A))→C↵
2→B:A÷B→D:Frac(D)=0⇒Prog "WFSUB":B>C⇒Goto 1↵
3→B:A÷B→D:Frac(D)=0⇒Prog "WFSUB":B>C⇒Goto 1↵
5→B:A÷B→D:Frac(D)=0⇒Prog "WFSUB":B>C⇒Goto 1↵
7→B:A÷B→D:Frac(D)=0⇒Prog "WFSUB":B>C⇒Goto 1↵
11→B:A÷B→D:Frac(D)=0⇒Prog "WFSUB":B>C⇒Goto 1↵
探索数 B に 2、3、5、7、11 を適用しています。探索数が与えられた整数 A の平方根より小さく、それに近い整数 C よりも探索数が大きくなれば Goto 1 で探索が終わります。
1回の探索を1行で表現しています。
b)
While 1↵
B+2→B:A÷B→D:Frac(D)=0⇒Prog "WFSUB":B>C⇒Goto 1↵
B+4→B:A÷B→D:Frac(D)=0⇒Prog "WFSUB":B>C⇒Goto 1↵
B+2→B:A÷B→D:Frac(D)=0⇒Prog "WFSUB":B>C⇒Goto 1↵
・・・・・
・・・・・
B+2→B:A÷B→D:Frac(D)=0⇒Prog "WFSUB":B>C⇒Goto 1↵
B+10→B:A÷B→D:Frac(D)=0⇒Prog "WFSUB":B>C⇒Goto 1↵
B+2→B:A÷B→D:Frac(D)=0⇒Prog "WFSUB":B>C⇒Goto 1↵
B+10→B:A÷B→D:Frac(D)=0⇒Prog "WFSUB":B>C⇒Goto 1↵
WhileEnd↵
この While ループには48行の処理が含まれています。
a) で探索数 B は 11 になっており、増分 2、4、10 などを加えて新たな探索数にして、素因数探索を1行で処理しています。探索数が整数 A よりも小さく、さらに探索数が整数 C よりも大きい場合は、Goto 1 で探索が終わり、While ループを脱出します。ここで、ポイントはこの増分をどうやって求めるかです。48個程度なら手計算やエクセルを使って求められます。
今回は、同じロジックですが、エラストテレスの篩いをさらに効率化、つまり探索数の絞り込みをより効率化し、
探索の無駄をさらに減らすことによる計算の高速化
を試みます。
素数を探索数に用いる部分と、While ループ内の48行の探索部分を以下のように拡張します。
▶ 探索数増分を増やして、素因数探索をさらに効率化する方法
A) 素数 2, 3, 5, 7, 11, 13 を探索数として除算を繰り返し、
B) 17以上で 2, 3, 5, 7, 11 のいずれかの倍数でもない探索数は、17~2326 までには480個あり、その480個の探索数で除算を繰り返し、
A) B) のそれぞれの除算の結果から素因数を調べます。17~2326 までの2310個の整数のうち480個の探索数まで絞りこんでいます。
探索数の取りこぼしを防ぐためには、周期2310の範囲で探索する必要があります。
念のため、探索数を 17~2326 の範囲で探し、それが480個になる説明は以下のようになります。
- 2, 3, 5, 7, 11 の最小公倍数は 2310
- 2, 3, 5, 7, 11 のいずれかの倍数でない探索数の増分は 2310 の周期
- 探索数を17から調べるので、1周期の終わりは 2326
- 2, 3, 5, 7, 11 のいずれの倍数でない整数の個数:480個
- これの算出方法は以下の通り;
- 2 の倍数の個数:2310/2 = 1155
- 3 の倍数の個数:2310/3 = 770
- 5 の倍数の個数:2310/5 = 462
- 7 の倍数の個数:2310/7 = 330
- 11 の倍数の個数:2310/11 = 210 ⇒ 以上の合計:2927個
- .
- 2と3の公倍数の個数:2310/6 = 385
- 2と5の公倍数の個数:2310/10 = 231
- 2と7の公倍数の個数:2310/14 = 165
- 2と11の公倍数の個数:2310/11 = 105
- 3と5の公倍数の個数:2310/15 = 154
- 3と7の公倍数の個数:2310/21 = 110
- 3と11の公倍数の個数:2310/33 = 70
- 5と7の公倍数の個数:2310/35 = 66
- 5と11の公倍数の個数:2310/55 = 42
- 7と11の公倍数の個数:2310/77 = 30 ⇒ 以上の合計:1358個
- .
- 2と3と5の公倍数の個数:2310/2/3/5 = 77
- 2と3と7の公倍数の個数:2310/2/3/7 = 55
- 2と3と11の公倍数の個数:2310/2/3/11 = 35
- 2と5と7の公倍数の個数:2310/2/5/7 = 33
- 2と5と11の公倍数の個数:2310/2/5/11 = 21
- 2と7と11の公倍数の個数:2310/2/7/11 = 15
- 3と5と7の公倍数の個数:2310/3/5/7 = 22
- 3と5と11の公倍数の個数:2310/3/5/11 = 14
- 3と7と11の公倍数の個数:2310/3/7/11 = 10
- 5と7と11の公倍数の個数:2310/5/7/11 = 6 ⇒ 以上の合計:288個
- .
- 2と3と5と7の公倍数の個数:2310/2/3/5 = 11
- 2と3と5と11の公倍数の個数:2310/2/3/5/11 = 7
- 2と3と7と11の公倍数の個数:2310/2/3/7/11 = 5
- 2と5と7と11の公倍数の個数:2310/2/5/7/11 = 3
- 3と5と7と11の公倍数の個数:2310/3/5/7/11 = 2 ⇒ 以上の合計:28個
- .
- 2と3と5と7と11の公倍数の個数:2310/2/3/5/7/11 = 1個
- .
- 以上から 2927 - 1358 + 288 - 28 + 1 = 480個
Int(√(A))→C↵
2→B:A÷B→D:Frac(D)=0⇒Prog "WFSUB":B>C⇒Goto 1↵
3→B:A÷B→D:Frac(D)=0⇒Prog "WFSUB":B>C⇒Goto 1↵
5→B:A÷B→D:Frac(D)=0⇒Prog "WFSUB":B>C⇒Goto 1↵
7→B:A÷B→D:Frac(D)=0⇒Prog "WFSUB":B>C⇒Goto 1↵
11→B:A÷B→D:Frac(D)=0⇒Prog "WFSUB":B>C⇒Goto 1↵
13→B:A÷B→D:Frac(D)=0⇒Prog "WFSUB":B>C⇒Goto 1↵
探索数の素数に 13 を追加します。CcEditor で一番下の赤文字の行を追加します。
b)
While 1↵
B+4→B:A÷B→D:Frac(D)=0⇒Prog "WFSUB":B>C⇒Goto 1↵
B+2→B:A÷B→D:Frac(D)=0⇒Prog "WFSUB":B>C⇒Goto 1↵
B+4→B:A÷B→D:Frac(D)=0⇒Prog "WFSUB":B>C⇒Goto 1↵
・・・・・
・・・・・
B+12→B:A÷B→D:Frac(D)=0⇒Prog "WFSUB":B>C⇒Goto 1↵
B+2→B:A÷B→D:Frac(D)=0⇒Prog "WFSUB":B>C⇒Goto 1↵
B+12→B:A÷B→D:Frac(D)=0⇒Prog "WFSUB":B>C⇒Goto 1↵
WhileEnd↵
この While ループには、480行の素数探索処理が含まれます。この赤文字の部分の特に探索数の増分をどうやって効率よくかつ間違いなく計算し、480行もの入力をどうやって間違いなく効率よく行うのか、そこが問題です。そこで、今回は赤文字の部分を自動的に作成することにしました。
▋コードの自動作成
さて、手計算やエクセルで480個の探索数増分を計算して、それに基づき480行もの大量の記述を間違いなくタイプして入力するのは、現実的ではなく、あまりにも非効率です。そこで、探索数の増分の計算や、480行のプログラムコード作成を自動化するWindowsアプリを作ります。使えるものは何でも使う作戦です。これにより、カット&ペーストで CcEditor の画面に追記するだけで、480行の追加を簡単かつ確実に行えます。
この480個の探索数の増分を計算し、480行の Casio Basic のコードを自動作成する Windows デスクトップアプリ SearchNum11_10digits.exe を Visual Studio 2019 Community の C# で作りました。少しだけ C# を使ったことがあれは、マウスクリックだけで殆どを自動作成してくれ、全部で20行程度のコーディングを行うだけで、比較的簡単に出来ると思います。
⇒ 480行のコードを生成するWindowsデスクトップアプリ
- SearchNum11_10digits のダウンロード
ダウンロードファイルには、アプリの実行ファイル (SearchNum11_10digits.exe) だけでなくソースコードも同梱していますので、ご興味があればご覧頂くなり、ご自分でビルドしたり改造してお使いください。
※ C# については、以前軽く紹介しています ⇒ プログラム電卓のための Windowsプログラミング
ところで、新しいWindowsアプリは、初めて実行するとき Windowsの保護機能により、まるで危ないソフトのように扱われます。これはこれまで使った人が少ないというだけでも、保護機能が発動するようになっています。自作のWindowsアプリを自分で作って起動しても保護機能が発動してしまいます。この保護機能が発動したときに対処方法について 自作プログラムがPC保護機能に引っかかる にまとめていますので、参考にしてください。
このアプリの重要なコードは以下のようにしています (ご参考まで)。

C# を使えば、上記の20行と、この関数を呼び出すための1行、合わせて21行をタイプしてコーディングするだけで、あとはマウスのクリック操作をチョコチョコと行うことで、デスクトップアプリが簡単かつ迅速に作れてしまうのが良いところです。
さて、SearchNum11_10digits.exe を起動したところ:

右上の [Calculate] ボタンを押すと、While ループ内のコードがテキストボックスに出力されます。

出力されると [Calculate] ボタンを押せなくしています。
テキストボックスでは、改行したり編集ができます。そこで、これをカットアンドペーストにより、プログラムをエディタで開き、必要なところに貼り付ければ、プログラム修正が簡単にできます。
例えば、上のテキストボックスの中でクリックしてから、[Ctrl]+[A] で全部を選択してから、[↑] キーを押して 最後の行の Goto 1 まで選択した状態にして、[Ctrl]+[C] でコピーしてから、
CcEditor エディタで、
While 1
WhileEnd
の間にカーソルを移動して、[Ctrl]+[V] とすればペーストできます。
▋編集したコードを FACTOR-F2.ccl としてPCに保存する
CcEditor で メニューの右にある Project を FACTOR-F1 から FACTOR-F2 に変更します。

[File] - [Ceck] を選択します。

しばらく待つと、コードの種類別に色が付きます。

関数、コマンド、文字列ごとに異なる色が付きますが、これは fx-5800P Casio Basic の特殊コードの種別に応じて色分けされた結果です。色分けがおかしなところは、文法に合わないコードなので、fx-5800P で実行するとエラーになる可能性が高いわけです。色分けのおかしなところは、よく見て必要ならば修正します。 この色分けは CcEditor の親切機能で、お好みの色分け設定に変更できます。
慣れないとよく分からないかも知れませんが、その場合は次の操作へ進んで下さい。最終的に fx-5800P でエラーが発生したら、その部分を fx-5800P 上で修正するか、CcEditor で修正すれば良いです。
そして、[File] - [Build] を選択して、FACTOR-F2.ccl ファイルを作成 (ビルド) します。

しばらく待つと、cclファイルを作成するかを聞いてくるので、[はい] をクリックします。

※参考
少し待てば、保存するファイル名を決めるコモンダイアログが現れます。

ここでは、ダウンロード先を Download フォルダに指定し、[開く(O)] をクリックします。
[開く(O)] をクリックする前にファイル名を FACTOR-F2.ccl に変更してもOKなので、ここではそのようにします。

すると、Download フォルダに FACTOR-F2.ccl が作成されます。
▶ FACTOR-F2.ccl のダウンロード [2021/01/02 バグフィックス]
バグフィックス: 終了時に配列変数が解放されない点を修正し、不要なWhileEndを削除しました。
※ ダウンロードしたzipファイルには、fx-5800P に転送する2つのcclファイルと、それらのテキストファイルを含んでいます。
▋FACTOR-F2 を fx-5800P に転送して実行する
fx-5800P のプログラムメモリ容量は、最大 28,432 バイトです。一方、今作成した FACTOR-F2.ccl のファイルサイズは、21,456 バイトと結構大きなファイルです。サブプログラム WFSUB.ccl は 147 バイトなので、合計で 21,603 バイト必要となり、容量ギリギリになります。
既に fx-5800P に多くのプログラムがあって、空き容量が足りない時は、FACTOR-F2 を転送できません。そこで、サブプログラム WFSUB 以外のプログラムを CcLinker でPCに待避させた後、WFSUB 以外のプログラムを削除しておき、FACTOR-F2.ccl を CcLinker で fx-5800P に転送します。
さて、サブプログラム WFSUB は変更せず、そのまま使用します。FACTOR-F2 で、7,849,516,203 (= 3 x 9811 x 88897) を素因数分解し、その実行時間を計ってみます。
FACTOR-F1 | FACTOR-F2 | 高速化 |
111秒 | 101秒 | 9.0% |
fx-5800P 素因数分解のさらなる高速化が達成できました!
▋最後に [2020/12/05 追記]
実は先に Pythonモードの Casio Python で素因数分解を高速化したのと同じ手法をfx-5800P のCasio Basic に適用したのが今回の記事です。詳しくは、Casio Python - 要素数の多いリスト:高速素因数分解(5) の表2で示しているように、ループが回る回数が 9.1% 減少し、高速化が 9~10% でした。一方、今回の fx-5800P での高速化が 9.0% であり、これは Casio Python での高速化の結果とほぼ一致しています。従って、素数以外の探索数で計算する While ループの実行回数を削減したことが高速化の主要因要因だといえます。
上で紹介した Casio Python での検討では、素数以外の探索数をさらに拡張して、Whileループの実行回数をさらに減らすことも試していて、さらに高速化できています。ただしプログラムファイル(スクリプトファイル)が恐ろしいほど大きくなってしまうことも判りました。同じことを fx-5800P 用に行っても、できあがるプログラムのファイルサイズが大きすぎて fx-5800P のメモリに収まりません。
今回の fx-5800P で高速化した Casio Basic プログラムファイルは、fx-5800P のメモリ容量ギリギリだったので、これ以上大きなプログラムファイルは実行できません。従って、今回作った FACTOR-F2 は、fx-5800P での最速素因数分解プログラム だと、ここでは言い切ってしまいます。
全く異なるスーパーロジックが、将来見つかるかも知れませんが、そのときが楽しみです!
応援クリックをお願いします。励みになるので...