fx-5800P 素因数分解 - さらなる高速化

2020/12/04
追記修正:2020/12/05
バグフィックス:2021/01/02


fx-5800P 素因数分解 - 高速化 で、Casio Basic プログラムによる素因数分解 の大幅な高速化を紹介していますが、今回はそれをさらに高速化できたので紹介します。

今回は高速化するために、あらゆる使えるものを総動員して 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.cllWFSUB.ccl を fx-5800P に転送すれば、FACTOR-F1 を走らせられます。


CcLinkerドングルをPCに刺してから、fx-5800P をつなぎ、CcLinker ソフトウェアを起動します。
CcLinker_StartUp 

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

ファイル名を FACTOR-F1.ccl にして、[開く] をクリック。
この場合は、Download フォルダにダウンロードしているので、Download フォルダに FACTOR-F1.ccl が作成されます。

FACTOR-F1 は サブルーチンとして WFSUB を使っています。結論から言えば WFSUB は変更しないので、そのままにしておきます。


FACTOR-F1.ccl を CcEditor で開く
今回編集するプログラムがファイル FACTOR-F1.ccl になったので、それを編集するために CcEditor で開きます。
CcEditor_Loaded

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個
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↵
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保護機能に引っかかる にまとめていますので、参考にしてください。

このアプリの重要なコードは以下のようにしています (ご参考まで)。
SearchNum11CB_code

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


さて、SearchNum11_10digits.exe を起動したところ:
SearchNum11CB_10digits_starinting

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

テキストボックスでは、改行したり編集ができます。そこで、これをカットアンドペーストにより、プログラムをエディタで開き、必要なところに貼り付ければ、プログラム修正が簡単にできます。

例えば、上のテキストボックスの中でクリックしてから、[Ctrl]+[A] で全部を選択してから、[↑] キーを押して 最後の行の Goto 1 まで選択した状態にして、[Ctrl]+[C] でコピーしてから、

CcEditor エディタで、

While 1

WhileEnd


の間にカーソルを移動して、[Ctrl]+[V] とすればペーストできます。 


編集したコードを FACTOR-F2.ccl としてPCに保存する

CcEditor で メニューの右にある Project を FACTOR-F1 から FACTOR-F2 に変更します。
CcEditor_FACTOR-F2

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

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

関数、コマンド、文字列ごとに異なる色が付きますが、これは fx-5800P Casio Basic の特殊コードの種別に応じて色分けされた結果です。色分けがおかしなところは、文法に合わないコードなので、fx-5800P で実行するとエラーになる可能性が高いわけです。色分けのおかしなところは、よく見て必要ならば修正します。 この色分けは CcEditor の親切機能で、お好みの色分け設定に変更できます。

慣れないとよく分からないかも知れませんが、その場合は次の操作へ進んで下さい。最終的に fx-5800P でエラーが発生したら、その部分を fx-5800P 上で修正するか、CcEditor で修正すれば良いです。

そして、[File] - [Build] を選択して、FACTOR-F2.ccl ファイルを作成 (ビルド) します。
CcEditor_Build

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

※参考
 CcEditor では、少し待つ間に上の例のようにタイトルバーに (応答なし) と表示されることがあります。これは CcEditor のバグではなくて仕様です。マルチスレッド処理を行わない普通のWindowsアプリでは、アプリがCPUを独占して使う時間が少し長めになると、ウィンドウ表示の更新など内部で行われるマルチタスク処理が止まってしまうので、(応答なし) と表示してしまうのが、この表示の正体です。なのでアプリの処理が終わるまで少し待てば良いことが殆どです。但しアプリのバグで処理が終わらない場合も同じように (応答なし) と表示され、アプリの処理に時間がかかっているだけなのか、バグなのかの区別が付かないのも事実ではあります。

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

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

すると、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.cclCcLinker で fx-5800P に転送します。

さて、サブプログラム WFSUB は変更せず、そのまま使用します。FACTOR-F2 で、7,849,516,203 (= 3 x 9811 x 88897) を素因数分解し、その実行時間を計ってみます。

FACTOR-F1FACTOR-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 での最速素因数分解プログラム だと、ここでは言い切ってしまいます。

全く異なるスーパーロジックが、将来見つかるかも知れませんが、そのときが楽しみです!




応援クリックをお願いします。励みになるので...
にほんブログ村 IT技術ブログ 開発言語へ


 


keywords: プログラム関数電卓、fx-5800P、素因数分解、Casio Basic

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

テーマ : プログラム関数電卓
ジャンル : コンピュータ

fx-5800P 素因数分解 - 高速化

追記修正 2020/05/25
バグフィックス:2021/01/02


[2020/01/24]
ソースコード表示を追加し、C.Basicでの実行例の説明を追加しました。
[2020/05/25] 動作可能モデルの記述を更新しました。
[2021/01/02] FACTOR-F1 の終了時に配列変数を解放しない問題を修正しました。

今回は、fx-5800P の素因数分解プログラムの高速化の話題です。

素因数分解の一般的な方法は、"エラストテレスのふるい" と言われるものです。最初に入力した数 N を小さい順に素数で割り算を繰り返す方法です。最大の素因数は N の平方根以下の整数なので、平方根以下の整数を対象に2と3以上の奇数で割り算を行う方法で fx-5800P での素因数分解プログラムを作っています。
⇒ fx-5800P 素因数分解 - バグ修正と表示変更

さらに高速化する方法は無いものかと、色々と考えたり、試したりしていました。
例えば Casio 関数電卓の素因数分解 など。



最速の素因数分解プログラム

最近、目からうろこの高速化を達成した記事を見つけました。
A fast prime factorizing program for Casio fx-5800P 
このトピックで、作者の slugrustle 様 は、2つのプログラムを公開されています。いずれもプログラム名は FACTOR です。
オリジナルは、上のサイトをご覧ください。

これらには、面白い工夫がなされています。その部分には手を付けず、表示やユーザーインターフェースの不具合(と私が思うだけですが...)を解消するために、チョット変更しました。


1本目のプログラムの変更版:
結果の表示を 3^2 と乗数を表示し、List にも乗数の結果が FREQ に反映するように変更しました。
FACTOR-M1 のダウンロード

FACTOR-M1_1 FACTOR-M1_2 
FACTOR-M1 の結果出力 - 左: 乗数表示、- 右: [MODE] [3] で現れる List表示


2本目のプログラムの変更版:
オリジナルプログラムでは、結果表示画面を、複数ページで切り替えて自由に見られるようになっています。[EXE] [▲] [▶] [+] で次のページを表示、[(ー)] [▼] [◀] で前のページを表示、[EXIT] [DEL] でプログラムを終了するようになっています。計算が高速化しているだけでなく、結果表示も良くなっています。

このキーの使い方がチョット馴染まないので、[▼] で次のページ、[▲] で前のページ、[+] は使えないようにし、指定以外のキーを押した時の誤動作を抑制するように修正しました。時間をかけて計算できた結果が、誤動作で見えなくなるのは嫌ですから...
さらに、オリジナルはキーを軽く押しても応答せず長押しが必要、つまり応答がとても悪いので、キー入力待ちを最小のループにして応答を十分高速にしました。軽くキーを1回押すだけで、チョット待ちますが必ず画面が変わります。
またオリジナルでは結果表示一覧で素因数として 1 が表示されますが、1 は素数ではないので、素因数として 1 が表示されないように修正しました。
FACTOR-F1 のダウンロード [2021/01/02 バグフィックス]
ソースコードはこのページの一番下に掲載

FACTOR-F1_1  FACTOR-F1_2 
FACTOR-F1 の結果表示 - 全結果を画面切り替えで確認、左: 2/1ページ、右: 2/2ページ


比較のための以前作った PRIME DECOMP:
PRIME DECOMP のダウンロード

Prime_Decomp_2 Prime_Decomp_3 


上記でダウンロードしたZIPファイルには、それぞれ CCL ファイルと TEXT ファイルが含まれています。CCL ファイルは CcLinker を使って fx-5800P に転送できます。或いは、下のリンクからテキストファイルを参考にしてください。



計算時間の比較

先ずは、fx-5800P でどのくらい高速化されたかの結果を示します。

PRIME DECOMP
ソースコード
FACTOR-M1
ソースコード
FACTOR-F1
ソース (メインルーチン)
ソース (サブルーチン)
123,456,789
= 32 x 3607 x 3803
170 秒60 秒
3 倍高速化
42 秒
4 倍高速化
6,666,666,667
= 19 x 1627 x 215659
77 秒27 秒
3 倍高速化
20 秒
4 倍高速化
7,849,516,203
= 32 x 9811 x 88897
458 秒165 秒
3 倍高速化
111 秒
4 倍高速化

1本目の FACTOR-M1 で3倍高速化、さらに2本目の FACTOR-F1 は4倍高速化されていることが分かります。

素因数分解は、与えられた数を小さい数から順に割ってゆく時、その操作の回数を減らせば、高速化に繋がります。
PRIME DECOMP では入力した数に、先ず平方根をとって一気に探査範囲を狭め、2と3以上の奇数で小さい方から順に割り算してゆく作戦です。

一方で、理想的なのは、小さい素数から素数だけで順に割り算してゆくことです。それには素数リストが必要ですが、それがあれば苦労しません。素数を算出する計算式などありません。

さて、slugursite様の工夫は、高い確率で素数を見つけるだけでなく、割り算する候補 (例えば、2 や 3 だけでなく、一旦割り算で使った素数の倍数) を効果的にふるい分ける手法にあります。そして、最初の FACTOR-M1 よりも 次の FACTOR-F1 の方が、素数を見つける確率が高くなっているので、さらに高速化されています。



最速プログラムでの工夫 [2019/07/31]

読者のまつ様から、高速プログラムの考え方をご説明頂きました。私はこれに大変納得しましたので、それを掲載致します。以前の記述は撤回させて頂きます。

素因数分解プログラムで通常行われている割り算では,「2,および,3以上の奇数」を割る数としています。
これですと,ご存知のように,例えば3で割り切った後に9でも割るという無駄が出てしまいます。
FACTOR-M1は,「2, 3, 3より大きい3の倍数を除く奇数」を割る数としており,3で割ったあと9や15で割ることはないようにしています。

3より大きい3の倍数を除く奇数について考えてみます。

まず,3より大きい3の倍数でない整数は次の(1),(2)のどちらかです。
 3m+1 (1)
 3m+2 (2)
 (m>=1)

次に(1),(2)が奇数となる式をそれぞれ求めます。

(1)は (2m+1)+m と変形できます。2m+1 は奇数ですから,(1)が奇数であるためには m が偶数である必要があります。そこで m=2n (n>=1) とおけば,(1)は 6n+1 となります。

(2)は 2(m+1)+m と変形できます。2(m+1) は偶数ですから,(2)が奇数であるためには m が奇数である必要があります。そこで m=2n+1 (n>=1) とおけば,(2)は 6n+5 となります。

5とこれらの式を並べ,さらに,隣り合う式の差も書き加えると次のようになります。(n=1とします)
式の並び隣り合う式の差
52
6n + 14
6n + 52
6(n+1) + 14
6(n+1) + 52
6(n+2) + 14
6(n+2) + 52
:
:
:
:
このような訳で,2, 4, 2, 4, ... と加算していると思われます。
この繰り返しは,6n+1 および 6n+5 の式からも分かるように,2と3の最小公倍数6を周期としています。

FACTOR-F1は,これを拡張して,割る数として
 奇数,かつ,3の倍数でない,かつ,5の倍数でない,かつ,7の倍数でない整数
を順番に求めていく方法をとっていると思われます。
2,3,5,7の最小公倍数は210ですから,隣り合う割る数の差(2,4,6,8など)の並びは210が1周期です。
FACTOR-F1の場合は,13+210n〜13+210(n+1)-1 [n>=0]の範囲で,2,3,5,7のいずれの倍数でもない整数を並べて,隣り合う整数の差をリストにしていると思われます。

ちなみに,13〜222の210個の整数のうち,
 奇数,かつ,3の倍数でない,かつ,5の倍数でない,かつ,7の倍数でない整数
の個数は,FACTOR-F1の「While 1」の下にある
 B+2→B:A÷B→D:Frac(D)=0⇒Prog "WFSUB":B>C⇒Goto 1
のパターンの行数と同じ48個です。

48個となる理由は次の通りです。

まず,2,3,5,7の倍数に関わるそれぞれの個数を求めます。

2の倍数の個数=210/2=105
3の倍数の個数=210/3= 70
5の倍数の個数=210/5= 42
7の倍数の個数=210/7= 30
 
2と3の公倍数の個数= 6の倍数の個数=210/ 6=35
2と5の公倍数の個数=10の倍数の個数=210/10=21
2と7の公倍数の個数=14の倍数の個数=210/14=15
3と5の公倍数の個数=15の倍数の個数=210/15=14
3と7の公倍数の個数=21の倍数の個数=210/21=10
5と7の公倍数の個数=35の倍数の個数=210/35= 6
 
2,3,5の公倍数の個数= 30の倍数の個数=210/ 30=7
2,3,7の公倍数の個数= 42の倍数の個数=210/ 42=5
2,5,7の公倍数の個数= 70の倍数の個数=210/ 70=3
3,5,7の公倍数の個数=105の倍数の個数=210/105=2
 
2,3,5,7の公倍数210の個数=210/210=1

重複を考慮すると,
2,3,5,7のいずれかの倍数の個数
=(105+70+42+30)-(35+21+15+14+10+6)+(7+5+3+2)-1
=162

従って,2,3,5,7のうちどの倍数でもない整数の個数は,
 210-162=48
で 48個となります。


素因数分解の正しい動作を検証

この作者は自分のプログラムを検証するテストプログラムまで作って、ソースコード (C++) を公開しています。fx-5800P 用なので、素因数分解する数は最大10桁と決まっています。この条件下でアルゴリズムの正しさを検証しています。

検証プログラムのソースコードが公開されています。そこで Visual Studio 2019 Community でビルドしました。


 FACTOR-F1 のテストプログラム Factor.exe のダウンロード [2019/08/28 リンクを修正]

コマンドプロンプトで、Factor.exe のあるデイレクトリに移動し、そこで

 Factor 1000 50000 4

と入力してエンターキーで実行すると、1000 から 50000まで 4 刻みで入力を変化させて FACTOR-F1 を実行した結果を一気に連続して自動実行してくれます。そして、結果が素数がどうか判定し、素数でないものが出てくるとエラーを出し、素数であれば実行を継続します。正常終了すれば、正しく素因数分解が実行されたことになります。

factor_1
正常終了しているので、1000 から 50000 までの素因数分解は問題ないことが検証されました。


fx-5800P 用のプログラムなので、入力値は 1 ~ 9,999,999,999 (10桁) の範囲なので、完璧にテストするには、

 Factor 1 9999999999 1

とすれば良いのですが、試しに私のPCだと、1晩で150億回分の検査が済みました。 10桁に相当する (1000億 - 1) 個全部のテストは、夜のみ終夜運転で計算させるとして1週間程度必要になりそうです。

factor_2
1 ~ 9,999,999,999 までのテスト中

テストが正常終了すれば、このアルゴリズムが正しいことが検証されます。但し、他のパラメータ設定でも正しい組み合わせは有りそうです。



グラフ関数電卓用に移植 [2020/05/25 更新]

FACTOR-F1 をグラフ関数電卓用に移植しました。素因数分解の計算部分は変更の余地がありませんが、結果表示は7行全部を使うように変更しました。

グラフ関数電卓用 FactorG のダウンロード [2021/01/02 バグフィックス]
  バグフィックス:終了時に行列解放しない点を修正しました。

FactorG 
FactorG の結果表示

ここで作成したプログラムは、Casio Basic が搭載されたグラフ関数電卓で動作すると思われます。
カシオが過去に発売したグラフ関数電卓全てを調べていませんが、おそらく 1995年発売のフランス専用モデル GRAPH20、そして1996年発売の世界モデル fx-7400G 以降のモデルでは、このプログラムが動作すると思われます。 

実際に動作確認したモデル (若干の手直し移植を含む)
 ・CFX-9850G (若干の手直し、プログラムダウンロード)
 ・CFX-9850GC PLUS (若干の手直し、プログラムダウンロード)
 ・fx-9860G / fx-9860G Slim (そのまま動作)
 ・fx-9860GIIシリーズ - SH3/SH4A、SDモデル (そのまま動作)
 ・fx-CGシリーズ - CG10/CG20/CG50 (そのまま動作)
 ・fx-9750GIII / fx-9860GIII (そのまま動作)
※ これらは純正Casio Basic での動作

なお、上の画面は、fx-CG50 にインストールした アドインCasio Basic  - C.Basic for CG で実行した画面です。C.Basic は純正Casio Basic のほぼ上位互換なので、グラフ関数電卓用 FactorG.g3m がそのまま実行できます。C.Basic は純正Casio Basic よりもかなり高速に動作するので、上記の例だと一瞬で結果が表示されます。
アドインCasio Basic - トップページ



Factor-F1 (fx-5800P用) のソースコード

FACTOR-F1 – fx-5800P code
0→DimZ↵
22→DimZ↵
"NUMBER"?→F↵
If F<1 Or F≧1x₁₀10↵
Then "NUMBER□MUST□BE□□≧1□ And <1x₁₀10"↵
Stop↵
IfEnd↵
If F≠Int(F)↵
Then "NUMBER□MUST□BE□□AN□INTEGER"↵
Stop↵
IfEnd↵
For 1→E To 22↵
0→Z[E]↵
Next↵
0→Z[1]↵
0→Z[12]↵
0→E↵
F→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↵

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+4→B:A÷B→D:Frac(D)=0⇒Prog "WFSUB":B>C⇒Goto 1↵
B+6→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+6→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+4→B:A÷B→D:Frac(D)=0⇒Prog "WFSUB":B>C⇒Goto 1↵
B+6→B:A÷B→D:Frac(D)=0⇒Prog "WFSUB":B>C⇒Goto 1↵
B+6→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+6→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+6→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+6→B:A÷B→D:Frac(D)=0⇒Prog "WFSUB":B>C⇒Goto 1↵
B+8→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+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+8→B:A÷B→D:Frac(D)=0⇒Prog "WFSUB":B>C⇒Goto 1↵
B+6→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+6→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+6→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+6→B:A÷B→D:Frac(D)=0⇒Prog "WFSUB":B>C⇒Goto 1↵
B+6→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+4→B:A÷B→D:Frac(D)=0⇒Prog "WFSUB":B>C⇒Goto 1↵
B+6→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+6→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+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+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↵

Lbl 1↵
If A>1↵
Then Isz E↵
A→Z[E]↵
1→A↵
1→Z[E+11]↵
IfEnd↵
Int(E÷3)→D↵
E-3xD>0⇒Isz D↵
1→C↵

Lbl 2↵
Cls↵
Locate 1,1,F↵
Locate 12,1,C↵
Locate 13,1,":"↵
Locate 14,1,D↵
3x(C-1)+1→B↵
Locate 1,2,Z[B]↵
Locate 11,2,"^("↵
Locate 13,2,Z[B+11]↵
Locate 16,2,")"↵
If B+1≦E↵
Then Locate 1,3,Z[B+1]↵
Locate 11,3,"^("↵
Locate 13,3,Z[B+12]↵
Locate 16,3,")"↵
IfEnd↵
If B+2≦E↵
Then Locate 1,4,Z[B+2]↵
Locate 11,4,"^("↵
Locate 13,4,Z[B+13]↵
Locate 16,4,")"↵
IfEnd↵

Do↵
Getkey→K↵
LpWhile K=0↵

0→M↵
If K=34 Or K=73↵
Then 1→M↵
Else If K=86 Or K=85 Or K=47↵
Then 2→M↵
Else If K=83 Or K=84 Or K=57↵
Then 3→M↵
Else Goto 2↵
IfEnd:IfEnd↵
IfEnd↵

If M=1↵
Then Cls↵
"DONE"↵
Else If M=2↵
Then Isz C↵
C>D⇒1→C↵
Goto 2↵
Else If M=3↵
Then C-1→C↵
C<1⇒D→C↵
Goto 2↵
IfEnd:IfEnd↵
IfEnd↵

0→DimZ↵



WFSUB – fx-5800P code

E+1→E↵
B→Z[E]↵
Do↵
D→A↵
Z[E+11]+1→Z[E+11]↵
A÷B→D↵
LpWhile Frac(D)=0↵
Int(√(A))→C↵
Return↵





今回は、slugrustle 様の Universal Casio Forum への投稿プログラムの解説記事になってしまいましたが、私としては十分楽しませてもらったので、記事にして残そうと思いました。



応援クリックをお願いします。励みになるので...
にほんブログ村 IT技術ブログ 開発言語へ


 


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

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


テーマ : プログラム関数電卓
ジャンル : コンピュータ

Casio 関数電卓の素因数分解

  追記 2020/12/25

本ブログでは、素因数分解プログラムについて取り上げています。

 ・ fx-5800P で素因数分解
 ・ fx-5800P で素因数分解再び
 ・ fx-5800P 素因数分解 - バグ修正と表示変更
 ・ fx-9860GII への移植 - 素因数分解
 ・ VBAで素因数分解
 ・ fx-5800P 素因数分解 - 高速化 [2020/01/07 追記]
 ・ fx-5800P 素因数分解 - さらなる高速化 [2020/12/25 追記]

これらの記事の発端は、カシオのスタンダード関数電卓 fx-995ES に因数分解機能が搭載されたことです。素因数分解機能が内蔵されたのなら、プログラム電卓で作ってみようと思ったわけです。但し、自作プログラムは、逆立ちしたって内蔵機能よりも速く計算できません。これは、チョット気になっていました。

そこで、今回は、素因数分解のアルゴリズムの話題です。

実は、すけっぴぃ様から、素因数分解アルゴリズムの効率化に関するコメント(ここ)を頂いており、すぐには役に立つ情報を返信できなかったのですが、心の隅に引っかかっていたこともあって、この話題を少し掘り下げてみます。

[2020/12/25 追記]
すけっぴぃ様からのコメントを実際に実現できたのが、上に挙げた 2020/01/07 追記 の記事に相当します。このアルゴリズムを利用して素因数検索効率をさらに向上させ、fx-5800P のメモリ容量ギリギリまで使うことでさらに高速化したのが、上で挙げた 2020/12/25 追記の記事になります。

以下は、fx-5800P 用高速素因数分解のアルゴリズム以前にアレコレと考えていた時の話です。


 
私の手持ちの電卓で素因数分解ができるのは、最初から機能が内蔵されている fx-995ESfx-JP900、それに作ったプログラムが走る fx-5800P と fx-9860GII の4機種。
Int_fx-995ES Int_fx-JP900 Int_fx-5800P Int_fx-9860GII 
順に、fx-995ESfx-JP900、fx-5800P、fx-9860GII

最近、fx-JP900 を入手し、素因数分解機能を試したところ、fx-995ES よりも大幅に計算が速くなっていて、さらに得られる素因数の桁数が増えています。

幾つかの素因数分解結果を、fx-995ES、fx-JP900、fx-5800P のプログラム、カシオの高精度計算サイトKe!san で行った結果の一覧表を再掲載します。← Casio fx-JP900 (その3) から抜粋

整数fx-955ESfx-JP900fx-5800PKeisan
1,234,567127x(9721)127x9,721127x9721127x9721
98,765,43223x37x(333667)
(1.7秒)
23x37x333,667
(0.4秒)
23x37x333667
(27秒)
23x37x333667
9,516,208,47332x172x(3,658,673)32x172x(3,658,673)32x172x365867332x172x3658673
123,456,78932x(13717421)32x(13,717,421)32x3607x380332x3607x3803

因数分解できない場合は ( ) 付きで表示される仕様で、そこは fx-955ES も fx-JP900 も同じ。
但し、fx-995ES は素因数が4桁以上で ( ) 付きになっていましたが、fx-JP900 では素因数の桁数制限が大幅に緩和され、上の例ですと6桁まではOK。

また、fx-JP900 の取扱説明書17ページを見ると、素因数が 1,018,081 以上の素因数を持つ時は計算エラーになると書かれていますが、上の1つめ、2つめ、3つめの例では、( ) 付きで結果が表示されています。これ以上計算できないが、たまたまそれが素因数だったと解釈すれば良さそうです。( ) 付きの場合は、それが正しいかどうかの保証が無いと言うことでしょう。

4つめの例では、( ) 付きの結果は、さらに因数分解できるが、これ以上計算できないことを示しています。

[2015/06/18 追記]
コメント欄での sentaro様とのやりとりから、求める素因数の桁数を制限すること、そしてCPUの演算速度の簡単な比較から、2と3以上の奇数で順次割り算する単純なロジックても、それぞれの実行時間をほぼ説明できそうだ、と今のところの結論です。(追記終わり)

[2020/01/24 追記]
上記のすけっぴぃさんのご提案にあるように、一旦3で割ればその後は3の倍数でない奇数で割り算すると効率があがります。これを拡張して、割る数として 奇数、かつ 3でない、かつ 5でない、 かつ 7でない整数を順次求めて行くアルゴリズムで3~4倍の高速化ができました。⇒ fx-5800P 素因数分解 - 高速化



素数は整数論の一分野で研究されていて、素数が無限個存在することは、紀元前300年頃に証明されています。しかし、未だに素数を求める公式が見つかっていないし、素数の密度を求める式も見つかっていません。ケースバーケースの近似的な式があるだけです。それだけ神秘的な数が素数と言えるのですが、だからこそ素数は暗号通信の要として、実用上極めて重要なものになっています。応用工学で重要な素数だからこそ、数学教育において素数は重要だと考え、カシオは素因数分解機能を内蔵したのかも知れません。

ところで、遅いCPUを搭載した fx-5800P で走らせた素因数分解プログラムは、処理が遅いので、あまり凝ったアルゴリズムを実装できません。それに比べて内蔵機能の計算が桁違いに速いことが、気になっていました。

そんなとき、fx-JP900 の評価をしていて、正しく計算する条件として求める素数の桁数に制限があることを改めて考えてみました。桁数の制限をかけるアルゴリズムがあって、それを使えば Casio Basic でも速いアルゴリズムを実装できるかもしれないと思いました。そこで、具体的なプログラムにするには、まだ不完全ですが、取りあえず書いてみます。


fx-995ES では3桁以内の素因数に分解して表示することができるのですが、正しい計算が保証できるときの素因数が3桁と言うのは、どういうことか? 例えば、何十個かの素数の表をメモリ内に持っていて、それを使って計算すれば、かなり計算量が節約できるかも知れません。3桁つまり1~999の範囲にある素数は168個で、最大の素数は 997 です。168個程度のデータならメモリに入れておくのは現実的です。与えられた自然数をこの168個の素数で次々と割り算してゆけば、2と奇数で順次割り算するよりも、遙かに計算量が少なそうです。

ある整数の素因数分解を行う時、素因数はその整数の平方根以下になることを使い、さらに2と奇数を順に割り算して素因数を求める計算を、fx-5800P や fx-9860GII 用に書いたプログラムで行っています。このとき、3桁の素数で最大は 997 なので、9972 = 994009 以下の素因数分解は、メモリに保存された168個の素数で順割り算すれば、かなり計算量は節約できます。fx-5800P や fx-9860GIi で作ったプログラムでは、2と奇数で割り算するので、499個の数で割り算しています。つまり、計算量は 168÷499 = 0.3367 つまり 約33%、1/3 にに抑えられます。
Casio Basic での変数参照や配列参照のアクセスに比べて、関数計算する際のテーブル参照は遙かに速いと考えられるので、これで内蔵機能が速いことが説明できそうです。この方法を Casio Basic のプログラムに反映する際は、算術演算に 1~1.5ms 程度かかり、配列変数や行列へのアクセスに20ms程度かかること、そしてこの差を考慮して、本当に速くなるのかどうかを検討する必要があります。


一方 fx-JP900 は、1,018,081 以上の素因数を持っている整数ではエラーになる仕様です。ちなみに 1,018,081 は素数でなくて、これを素因数分解すると 10092 です。fx-5800P のプログラムで計算してみると、1,018,081 未満で最大の素数は、1,018,057 だと分かります。1,000,000 (100万)までの素数は 78,498個あるので、8万個近くある素数の表を不揮発メモリに持っておくのは、関数電卓としてはあまり現実的ではないでしょう。1,018,081 以上でエラーになることから、ひょっとしてこれを実装していることも考えられますが、素因数分解だけのために原価を押し上げるメモリを使うのは疑わしいわけです。

そこで、メモリに保存された素数テーブルを使わず、完全ではないものの、素数を計算して、それで順次割り算してゆく方法は、うまくすると計算量を減らして、高速化できるのかも知れません。或いは、メモリ上の素数テーブル参照と計算の併用も現実的な折衷案かも知れません。

素数の計算については、以下の式が非常に効率よく素数を計算するものとして知られています。
オイラの素数の式 
これはオイラーが見つけた、素数 p を求める式です。全ての素数をもれなく見つけることはできません。
ただ、この式の面白いのは、x  が 0 から 39 の時に得られる数が全て素数だと言う点にあります。但し、x=39 の時得られる素数 1601 以下には、この式で得られない素数が沢山あります。1601 以下の全ての素数を算出できるわけではありません。

さらに、 が 0 から 60 の時は、x = 40, 41, 42, 44, 49, 50, 57 の7個の x 以外で、 p は素数になります。素数を算出する効率は、x が 0 から 60 で計算した61個の値のうち88.5% が素数になります。繰り返しますが、これで得られる3071 以下には、この式の結果以外に多くの素数があります。

xpxpxp
0411322326743
1431425127797
2471528128853
3531631329911
4611734730971
57118383311033
68319421321097
79720461331163
811321503341231
913122547351301
1015123593361373
1117324641371447
1219725691381523
391601
 ・・・・・・
603701
10081017113

ちなみに、x = 1009 の時 p = 1,019,131、x = 1008 の時 p = 1,017,113 となります。つまり、x = 1008 で得られる1,017,113 がこの式でエラーにならない最大素因数 1,018,057 に最も近いものだと分かります。この式では、100万までの素数の47.5% が求められることが調べられていて、効率は半分以下に落ちます。しかし、現在 fx-5800P や fx-9860GII に実装しているプログラムのロジック「2と奇数で約 50万回近く割り算する」よりも、1000回程度の割り算をする方が、計算量が 1/500程度になります。仮に3分かかっていた計算は1秒以下になりそうです。

与えられた整数に対して、先ず先に、このオイラーの式で得られる計算値から素数を選んで、それで順次割り算して、残った余りについて、2と奇数で順次割り算して計算すると言うアルゴリズムが考えられます。オイラーの計算値から少ない計算量で素数を見つけられれば、テーブルと計算の併用で、高速化の可能性があります。x をどの範囲まで使うのか、38 までとするか、60 とするか、1008 までとするか、その中間のどこかにするか、も実際の計算量とコマンドの処理速度から最適点を検討する必要があります。仮に、x = 1000 まで使うなら、1000の47.5% に相当する 475 個の素数で順次割り算するので、500 / 500,000,000 = 0.001% となり、他の計算量と計算時間を低く抑えられれば、大幅な高速化ができるかも知れません。

プログラムの実装は、そのうちやってみようと思います。もし先にプログラムを作られた方は、是非コメント欄で発表してください。お待ちしております。



ところで、余計な話になりますが、

The Asahi Shinbun Blobe - 数学という力 (残念ながら削除されたようです) というサイトでは、素数と円周率の関係、素数と宇宙の真理の関係について解説されていて、なかなか面白いです。素数は現代数学の花形の1なのですね。

Zeta_Functio  
これは、リーマンと言う数学者が名付けたゼータ関数というものです。一番右の項は、オイラー積という総積計算で、素数 p がしっかり出てきます。

この式で、s=2 の時は、
ゼータ関数(s=2) 
となって、素数 p のオイラー積 と円周率 π が結びつくことが発見された歴史的な式をゼータ関数で表したものです。素数と円周率の関係式をより一般化したゼータ関数で表現することで、より深く調べることができるというわけです。上の記事によれば、この式を巡った素数の熱い研究が進められているようですね。簡単に素因数分解できる公式が存在するのかどうか?まだよく分かっていません。そのうち見つかる筈と言う人もいれば、存在しないかも知れないと言う人もいます。あまり簡単に計算できると、インターネットなどで使われている暗号が簡単に破られることに繋がるので、大問題です。

脱線すると、このゼータ関数で s=-1 の時は、
ゼータ関数(s=-1) 
なんて、なってしまいます。自然数を無限に足すと、-1/12 になる、なんとも受け入れられない結果です。実は、ゼータ関数は複素数の世界のものなので、一見あり得ない結果に見えるわけです。

カシオの高精度計算サイト Ke!san のココでも取り上げられています。
ここでは、明確に書かれていませんが、s=-1 で、実数の世界を複素数の世界に拡張(解析接続)しています。実はゼータ関数といっても、色々な派生バージョンがあって、s>1 でしか成り立たないゼータ関数では s=-1 は定義域の外側、言い換えれば s=-1 としてはいけません。そこで、このゼータ関数を拡張して(解析接続して) s=1 以外で成り立つようにできます。この時のζ関数は、拡張前のゼータ関数とは別のものです。そして拡張した別のζ関数では、s=-1 としても良く、-1/12 に収束します。殆ど詐欺というか、紛らわしい話ですね。

1+2+3+4+・・・  は実数の世界と誰でも思うので、自然数の無限和が負の数である -1/12 に収束するなどと言うのは、実数の世界では間違いです。でも複素数の世界では収束するので、ゼータ関数は物理の計算で重宝されているわけです。

素数は大きくなると、まばらになるのか?その密度はどうなっているのか? これもはっきりと分からない問題でしたが、2014年には素数は極端な偏りがなく万遍なく分布することが発見されました。→ こちら


素数の性質の研究は、非常にホットな分野ですね。まぁそれだけ分からないからこそ、暗号に使われるわけです。
深淵な研究は数学者に任せるとして、取りあえずプログラム電卓で素因数分解の高速化が出来るかも知れないということで、一旦区切ることにします。




応援クリックをお願いします。励みになるので...
にほんブログ村 IT技術ブログ 開発言語へ


 



keywords: fx-5800Pプログラミングプログラム関数電卓

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

テーマ : プログラム関数電卓
ジャンル : コンピュータ

fx-5800Pで素因数分解

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


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

fx-995ES fx-5800P_1  
      fx-995ES         fx-5800P


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

他の新機能、例えば

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

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

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


素因数分解

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

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

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

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


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
-----------------

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


さらに[EXE]キーを押すと、
-----------------
               5
TO THE
               1
-----------------

と表示。5の1乗と言うことだ。


さらに[EXE]キーを押すと、少し時間がかかるが
-----------------
               823
TO THE
                1
-----------------

823の1乗と表示される。
割と大きな素数が出てきた。


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

<->:TRY OTHERS
<AC>:QUIT
-----------------

と表示され、続けるか終わるかを聞いてくる。


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

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

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

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


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

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

参照: VBAで素因数分解 【2013/11/1 追記】



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

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

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

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


==========

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

[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 への移植 - 素因数分解




応援クリックをお願いします。励みになるので...
にほんブログ村 IT技術ブログ 開発言語へ


 


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

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

テーマ : プログラム関数電卓
ジャンル : コンピュータ

fx-5800P【ゲーム】:もぐら叩き~まとめ~

fx-5800Pでもぐら叩き
e-Gadget


fx-5800P で作る「もぐら叩き」ゲームのまとめ
コード修正 2014/03/20
fx-FD10 proに関する記述追加 2014/09/28
コード誤記修正 2016/05/12
  fx-CG20 に関する記述修正 2017/01/04
fx-CG50 に関する記述追加 2017/07/24
追記 2017/08/06
追記 2020/05/30



普通のプログラム作成の記事と異なり、多少冗長な内容になっており、(1)~(8)で、徐々にプログラムを作ってゆく様子を複数の記事で紹介した。


最終的なプログラムは、本ページの一番下に掲載した。またこれを一部改善したもの、および各機種へ移植したものを プログラムライブラリに収録している。[2017/08/06 追記]

プログラムライブラリ - もぐら叩き (fx-5800P)
プログラムライブラリ - もぐら叩き (fx-9860GII)
プログラムライブラリ - もぐら叩き (fx-CG20 / fx-CG50)


以下の記事は作りながら書いているので、プログラミング本のように最終形を想定した進め方になっていない。途中でロジックの変更や、バグ対策や、変数の変更など、実際にどうやって完成させたかをそのまま書いている (fx-5800P版)。

fx-5800P【ゲーム】:もぐら叩き(1)

fx-5800P【ゲーム】:もぐら叩き(2)

fx-5800P【ゲーム】:もぐら叩き(3)

fx-5800P【ゲーム】:もぐら叩き(4)

fx-5800P【ゲーム】:もぐら叩き(5)

fx-5800P【ゲーム】:もぐら叩き(6)

fx-5800P【ゲーム】:もぐら叩き(7)

fx-5800P【ゲーム】:もぐら叩き(8)


fx-5800P に搭載されているプログラミング言語は、Casio Basic というカシオの味付けをした BASIC言語 だ。

特に、もぐら叩きのようなゲームを作る際に特に重要かつ必要なものは、以下の機能だろう。
1) 広い表示画面
2) Getkeyコマンドによる、リアルタイムキー入力監視機能
3) Locateコマンドによる、柔軟な表示機能
4) 真 (0以外) と 偽 (0) による条件判定


さらに、昔のプログラム電卓に搭載されていた BASIC と異なり、構造化プログラミングの考えでコーディング可能な点も特筆できる。昔のプログラム電卓やポケコンに搭載されていた BASIC は行番号と GOTO コマンドでプログラムの流れを作っていたが、現在の Casio Basic は Goto コマンドを使わずに制御構造を作れるので、上から下へのシンプルな直線構造のコードの中に、1まとまりの処理ブロック1本に繋げる、いわゆるブロック構造にできるので、分かりやすくバグの入りにくいコードが書けるようになっている。

これらの機能が、fx-5800P を魅力的にしている。


CASIOの電卓の中で、上記を満たすプログラミング言語を搭載されているのは、下記のモデルだ。

・fx-9860Gシリーズ: グラフ関数電卓(生産終了)
 取扱説明書

・fx-9860G IIシリーズ: グラフ関数電卓(生産終了)
 メーカーサイト / 取扱説明書

・fx-9860GIII: グラフ関数電卓 (現行品、ヨーロッパ専用モデル)
 メーカーサイト / 取扱説明書

・fx-9750GIII: グラフ関数電卓 (現行品、北米専用モデル)
 メーカーサイト / 取扱説明書

・fx-CG20 / fx-CG10: カラーグラフ関数電卓(生産終了)
 メーカーサイト / 取扱説明書

・fx-FD10 pro:土木測量向けプログラム関数電卓 (現行品)
 メーカーサイト / 取扱説明書

・fx-CG50:カラーグラフ関数電卓 (現行品 - 2017/10/20 国内発売)
 メーカーサイト / 取扱説明書

・fx-5800P: プログラム関数電卓(現行品)
 メーカーサイト / 取扱説明書


fx-FD10 pro fx-FD10 pro < fx-9860GII版もぐら叩き >


fx-CG50 noce photo fx-CG50 < fx-CG50版もぐら叩きのダウンロード


fx-9860GII  fx-9860G II  fx-9860GII版もぐら叩きのダウンロード >


               fx9860GIII             fx-9860GIII  < fx-9860GIII版もぐら叩きのダウンロード


               fx-9750GIII_large             fx-9750GIII   < fx-9750GIII版もぐら叩きのダウンロード


fx-CG20  fx-CG20 fx-CG20版もぐら叩きのダウンロード >


    fx5800P_calc         fx-5800P <fx-5800P版モグラ叩き - ダウンロードも可 > 


各機種の画像の右に、対応する「もぐら叩き」プログラムのダウンロードリンクを示している。ダウンロードして転送するだけで楽しめる (fx-5800P は CcLinker を使ってダウンロードしたプログラムファイルを転送できる) ので、先ずは遊んでみてください。

完全互換でないのには理由がある。電卓の機種が異なると、ハードウェアの違いからキー配置が異なる。従って、Getkeyで得られるキーコードが異なるため、ソースレベルでの互換性は無い。これを除けば fx-5800Pのプログラムからの移植性は比較的高いと(旧来の命令の互換性については、少し注意が必要だ⇒こちらを参照)。

fx-5800P、fx-9860Gシリーズ (さらにOS載せ替えしたfx-9750Gシリーズ)、fx-CGシリーズ以外ではこのゲームは走らない。例えば、fx-72F、fx-71F 、fx-3600P、fx-3950Pなどはプログラム機能が十分でないので適用外だ。

ところで、fx-9860GII、fx-CG20、fx-CG50、fx-FD10 Pro は、1万円以上の価格だ。一方で、fx-5800P は 6千円台前半 (2017/01/01時点の Amazon価格) と格段に手軽な価格だ。この価格で、上記4つの条件を満たす言語を搭載しているのだから、改めて魅力的なマシンと言える。

※ 興味があれば、最近のCasio プログラム電卓の価格動向 をご参照。


当初は、fx-5800P のような電卓で、遊べるアクションゲームを作れるとは思っていなかった。たまたま、Goto~Lbl コマンドで、カウントタイマーを作ってみると、意外に速いことから、実際に遊べるレベルのアクションゲームを作れるかどうかを試したくなったのが、もぐら叩きを作り始めた動機だった。

パソコンで作るゲームと異なり、最初にゲーム仕様を作るのではなく、機能を追加した時にゲームとしてのスピード感を損なわないように探りつつ、様子を見ながら後付けでゲーム仕様を考えた。実際に私自身が考えたり試したりした事柄を、時系列で実況中継風に書いた結果、冗長な記事となってしまった。

できあがったゲームは、バリバリのゲーマーには物足りないのだが、普段からあまりゲームで遊ばない人間(=私)には、少しすつスキルアップして、得点が増えてゆくのが愉しい。


ご興味の有る方は、是非一度プログラムを入力して、遊んでみて欲しい。


もぐら叩きが意外にうまくいったので、最近はシューティングゲームができないものか?と、色々と動きのあるルーチンを作って遊んでみている。ひょっとしたら、何かシューティングゲームができるのかも知れない。

電卓の遅い処理速度、完全シングルタスク、広いといっても16×4 しかない画面で、動きやロジックを試しながら、遊べそうなゲームを模索してみようと思っている。


おしまい( ^o^)ノ



以下は、プログラムコード: [2016/05/15 誤記修正]

[2017/08/06 追記]
メインルーチンの3行目 Lbl 0 の下に、2行追加したものをプログラムライブラリに収録している。
追加した2行は、
While Getkey
WhileEnd


もぐら叩き: Wack -a-Mole by やす(Krtyski)

Wack-a-Mole_src 



応援クリックをお願いします。励みになるので...
にほんブログ村 IT技術ブログ 開発言語へ


 



keywords: fx-5800Pfx-CG20fx-9860G IIゲーム、プログラミングもぐら叩きプログラム関数電卓

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

テーマ : プログラム関数電卓
ジャンル : コンピュータ

fx-5800P 素因数分解 - 結果表示のバリエーション

追記修正 2019/07/15

今回は、fx-5800P の素因数分解プログラムの結果表示方法に関する話題です。

読者の まつ様 から素因数分解の結果表示についての投稿を頂きました。面白いので紹介します。

Result_Display 

今回のご提案は、このような表示もアリだというものです。

素因数分解の結果は、素数と乗数の組を 縦に並べて表示するのが見やすいと決めてかかっていたので、チョット新鮮です。

fx-5800P などの最近のカシオのプログラム電卓は、10桁に限られるから、16桁x4行のディスプレイでは、このように出力すれは1画面に収まるわけです。但し、素数や乗数が途中で改行しないように配慮されています。

ご投稿いただいたプログラムを勝手に Prime Factor として以下からダウンロードできるようにしました。
結果を1画面に表示する素因数分解プログラム:Prime Factor

※ これをダウンロードして fx-5800P に転送するには、CcLinker が必要になります。

ご投稿いただいたプログラムのタイプミスを1箇所だけ ( "[""^(" に) 修正し、結果表示のために ◢ を追加し、プログラムの最後で配列変数の領域を解放するように修正しただけで、まつ様のコードは殆どいじっていません。

Prime Factor by まつ
Prime_Factor_Src 







応援クリックをお願いします。励みになるので...
にほんブログ村 IT技術ブログ 開発言語へ


 




テーマ : プログラム関数電卓
ジャンル : コンピュータ

fx-5800P【ゲーム】:Hit&Blow

2013/11/07
追記 2018/10/30

※ CcLinker で fx-5800P に転送できるCCLファイルをダウンロードできるようにした [2018/10/31]


Hit&Blow と言うゲームをご存知だろうか?

フジテレビのNumer0nでの元になるもので、古くからある数当てゲームだ。

最初に、互いにN桁の数を決める。数の決め方には決まりがある。
・0から9までの数を使い、
・各桁は異なる数とする
・一番左の桁を0として良い

あなたが推測した数を相手に伝える。そして相手は、「2ヒット1ブロー」といったように、ヒット数とブロー数を答える。
・桁と数の両方が一致すれはヒット
・桁は違うが数だけ一致しればブロー



そこで、fx-5800PHit&Blow を作ってみた

ところで、fx-5800Pで素因数分解プログラムを作った時、処理速度の遅いことが骨身にしみている。そこで、電卓が出題した3桁の数を当てるゲームとした。

プログラム作成時に、主に以下の2点を考えた:
・16桁x4行の画面内で遊べるように、全てをうまく配置できるか?
 私なりのガイドライン(使いやすいプログラム参照)に従って、うまく配置してみた。

・HIT数とBLOW数の判定をどうするか?
 ここが、多分一番肝心なところ。2通りのロジックを試してみた。



プログラムの仕様

1) 試行10回以下で正解すればOKとする。

 ・この時、「VERY GOOD」と褒めてあげる。

2) 試行11回目以降でも、ゲーム継続を可能とする。
 ・但し、「QUIT?」(止めるか?)と表示する。
 ・ここで止めたら、「YOU GAVE UP」と釘をさして、正解を表示する。

3) 試行11回目以降で正解すれば、一応ねぎらう。
 ・「Good」と言葉をかける。

4) 正解を出した時は、試行回数を表示する。
 ・一応「YOU WIN」と認定してあげる。

4)  デバッグ目的で、ゲーム開始時に正解を見られるようにする
 ・秘密のキー入力で正解が分かるようにする。



プログラムファイルのダウンロード [2018/10/30:追記]

CcLinker で fx-5800P に転送してスグ使える CCLファイルのダウンロード
CcLinkerの紹介
 ここには、配列変数を使わない高速版(下記参照)を収録している。



ゲームの実行画面

こんな感じで完成した。

先ずは、メニューリストから、「HITBLOW」を選ぶ。

ManuList 



ゲームが起動した時の画面:

HB-Start 
 
ガイドラインに従って、メニュー表示をした。
< ? >は秘密のキーだ(ここでは、まだナイショ)。
ここで、[EXE]キーを押して、ゲーム開始。




HB-1 

ゲーム開始早々、405 で 2HIT だ!
右上の :1 は試行回数を示す。



さらに [EXE] キーを押すと...

HB-2 

試行2回目、ここまでくれは、こっちのものだ!!
[EXE]キーを押して...次は決まるか?



ぶぅ~~(´д`)

HB-3 

あとは、組み合わせの問題....もうちょい...



で...

HB-4 

試行6回目で、当たり!!\(^_^)/

さらに [EXE]キーを押すと...




HB-YouWin 

試行6回で YOU WIN の表示。
ここで、[0]キーを押すと、最初の画面へ戻って、新たに出題される。 



ところで、最初の画面で秘密のキーを押すと...

HB-Sneak 

こんな感じで、正解がわかる...




プログラムの構造

メインルーチンと4つのサブルーチンを作った。

・メインルーチン:
 プログラム全体の流れを記述する。細かい作業はサブルーチンに任せる。

fx-5800P専用プログラム
プログラム名: HITBLOW
====================
Lbl 0

0→C:0→D:→E
            :初期化と初期画面表示
Cls
Locate 2,1,"Hit And BLOW"
Locate 2,3,"
:START"
Locate 2,4,"< ? >:ANSWER"

Do             
     :秘密のキーを押した時
Getkey→F              
fx-5800P:同時にキーを押してみる を参照
If F>0 And F<10
Then 1→D
Break:IfEnd
LpWhile Getkey≠47

                    :この2行が肝心
Prog "S2HB3"            :正解出題ルーチン
Prog "S3HB3"            :ゲームの中心部分

Cls                   :結果表示
If D=1:Then               
"   YOU GAVE UP" 
          :正解できなかった時 D=1
"THE ANSWER ="
Locate 14,2,A
Else
Locate 5,1,"YOU WIN"  
      :正解時の処理
Locate 3,2,"IN"
Locate 6,2,C
Locate 8+Int(log(C)),2,"TRIES"
      :関数電卓ならではの処理
IfEnd                  ⇒ 別記事で紹介予定
Locate 1,4,"<0>:TRY AGAIN"

Whle Getkey≠25 
           :もう一度遊ぶ
WhleEnd
Goto 0
====================



・サブルーチン(1):
 入力された3桁数を、各桁の数字に分解する。

fx-5800P専用プログラム
サブルーチン: S1HB3
入力された数字を各桁に分解し
変数 K、L、M に格納する
====================
Int(N÷100)→X          
     ⇒ 別記事で紹介するかも...
Int((N-100X)÷10)→Y
N-100X-10Y→Z
If X=Y Or Y=Z Or Z=X
Then 1→E:IfENd
====================



・サブルーチン(2)
 各桁の数字が同じにならないように、3桁数を作る。

fx-5800P専用プログラム
サブルーチン: S2HB3
各桁を重複しないように作り、
正解の変数、K、L、Mへ格納し、
正解の3桁数を変数Aに格納する
====================
RanInt#(0,9)→K

Do
RanInt#(0,9)→L
LpWhile L=K

Do
RanInt#(0,9)→M
LpWhile M=K Or M=L

100K+10L+M→A
If D=1:Then
"THE ANSWER =   "
Locate 14,1,A

IfEnd
====================



・サブルーチン(3)
 ゲームの核心の流れを記述する。

fx-5800P専用プログラム
サブルーチン: S3HB3
正解するか、諦めると
メインルーチンへ戻る
====================
10→DimZ
Do
0→E:Isz C

Lbl 0
Cls
Locate 12,1,":"
Locate 13,1,C
"3 DIGITS"?→N
Prog "S1HB3"

If E=1:Then
Locate 12,2,"ERROR"
Locate 6,3,"SAME NUMBER"
Locate 2,4,"FOUND IN DIGITS"
0→E:Goto 0
IfEnd

Prog "S4HB3"

If D=1:Then
Break:IfEnd
LpWhile H≠3

0→DimZ
Return
====================



・サブルーチン(4)
 回答を判定して、△HIT、◇BLOW を表示する

 2つの異なるロジックで作ってみた。


サブルーチン(4-1):桁数の拡張性を考えたロジック

For 文と配列変数Z[ ]を利用した。


fx-5800P専用プログラム
サブルーチン: S4HB3
ヒット数を Hへ、ブロー数をBへ
格納してサブルーチン S3HB3へ戻る
====================
0→S:0→T
0→H:0→B:0→D
X→Z[1]:Y→Z[2]
Z→Z[3]:K→Z[6}
L→Z[7]:M→Z[8]

For 1→S To 3
If Z[S]=Z[S+5]
Then Isz H
IfEnd:Next

For 1→S To 3
For 1→T To 3
If Z[S]=Z[T+5]
Then Isz B
IfEnd:Next:Next

Locate1,3,H
Locate 3,3,"HIT"
Locate 1,4,B-H
Locate 3,4,"BLOW"

If H≠3 And C>10
Then
Locate 12,3,"QUIT?"
Locate 12,4,""
IfEnd

If H=3:Then
If C>10:Then
Locate 13.3."GOOD"
Else
Locate 8,3,"VERY GOOD"
IfEnd:IfEnd

Do
Getkey→F
If F=34:Then
1→D:Break:IfEnd
LpWhilr F≠47
====================



処理速度が少し遅いように思われた。 For 文の実行分と、配列変数へのアクセスに多少余計に時間がかかるのかも知れない。配列変数に関しては単なる思い込みの可能性もあるが...

[2014/03/09:追記]
速度低下の主要因は配列変数へのアクセスが非常に遅いためである。通常変数に比べてアクセス速度が3倍近くかかるようだ。

[2018/10/30:追記]
桁数を拡張して3~5桁を選べるようにした Hit & Blow を作成している。
プログラムライブラリ - Hit & Blow
※ 拡張版 Hit & Blow ではメインルーチンは HitBlow と同じファイル名。そこで私は、3桁固定で配列変数を使わない高速オリジナル版のメインルーチンを HB に変更して、拡張版と一緒に fx-5800P に入れて遊んでいる。


サブルーチン(4-2):処理速度向上を狙って、If 文のみのロジック

2者択一の If文 は処理が速いと考え、それでも桁数拡張がしやすいロジックにしてみた。


fx-5800P専用プログラム
サブルーチン: S4HB
ヒット数を Hへ、ブロー数をBへ
格納してサブルーチン S3HB3へ戻る
====================
0→S:0→T:0→U
0→H:0→B:0→D

If X=K:Then
Isz H:1→S:IfEnd
If X=L:Then
Isz H:1→T:IfEnd
If Z=M:Then
Isz H:1→U:IfEnd

If X=L And T=0
Then Isz B:IfEnd
If X=M And U=0
Then Isz D:IfEnd
If Y≠X:Then
If Y=K And S=0
Then Isz B:IfEnd
If Y=M And U=0
Then Isz B:IfEnd
IfEnd
If Z≠X And Z≠Y:IfEnd
If Z=K And S=0
Then Isz B:IfEnd
If Z=L And T=0
Then Isz B:IfEnd
IfEnd

Locate 1,4,"                "
Locate1,3,H
Locate 3,3,"HIT"
Locate 1,4,B
Locate 3,4,"BLOW"

If H≠3 And C>10
Then
Locate 12,3,"QUIT?"
Locate 12,4,""
IfEnd

If H=3:Then
If C>10:Then
Locate 13.3."GOOD"
Else
Locate 8,3,"VERY GOOD"
IfEnd:IfEnd

Do
Getkey→F
If F=34:Then
1→D:Break:IfEnd
LpWhilr F≠47
====================



思った通り、配列変数とFor文で作ったサブルーチン(4-1)よりも、If 文だけで作ったサブルーチン(4-2)の方が、処理が速かった。

ちなみに、if 文が実行される回数を比較してみた:

(4-1):12回 (おそい)
(4-2):10回 (はやい)

if文が2回多いだけだ。

あきらかに体感できる範囲で、確実に速度差を感じる。If分の実行回数に違いがないとすると、やはりFor分の実行による時間が体感の違いの原因だろう[2014/12/14 追記]: 動作の非常に遅い配列変数を使ったことが主な原因だ。

fx-5800Pで素因数分解プログラムを作った時、Doループの実行速度を簡易的に計測して、ループが1回だけ回るのに45m秒程度かかっていることが分かっている。処理時間は、当然ループ内の処理内容に依存するわけだが、それでもパソコンに比べると恐ろしく遅い。

仮に、今回のFor文のループが1回だけ回るのに50m秒かかるとすると、0.05 x 12 = 0.6(秒) かかるわけだが、体感とほぼ合う。なんとなく納得できる範囲だ。

fx-5800Pは、単4電池1本で、1日に1時間使用したとして1年の寿命と仕様に記載されている。消費電力を抑えることをかなり高い優先度としていると思われる。消費電力抑制の効果的な方策の1つに、MPUのクロックを落とすことがある。つまりその分処理速度は遅くなるわけだ。

いずれ、検証してみたいと思う。 [2014/12/14 追記]: For 文と Lbl / Goto ループの速度差は無視できるほど小さい。非常に遅い配列変数を使ったことが主要因だと判明している。


また、ソースコードの詳細については、プログラミング入門向けに別の記事で取り上げる予定だ。



応援クリックをお願いします。励みになるので...
にほんブログ村 IT技術ブログ 開発言語へ


 


keywords: fx-5800PゲームプログラミングHit & Blowプログラム関数電卓

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

テーマ : プログラム関数電卓
ジャンル : コンピュータ

fx-5800P が大好き、だけど..

2017/11/11
追記 2018/02/25
最後に追記あり

I love fx-5800P still, but...

これは大声の独り言...

4年前に fx-5800P で Casio Basic の面白さに目覚めた。プアなハードウェアに結構使える言語、これを最大に活かすのが面白い。自分の研究メモ代わりにこのブログを始めた。

そのうち、グラフ関数電卓に移植し始めた。fx-5800P で動くなら、グラフ関数電卓でもサクサク動く。気がついたら、fx-9860GII が2台、fx-CG20、fx-9860GII SD、fx-CG50 が手元にある。

それでも fx-5800P が普段使いだ。理由はいくつかある。先ず使いやすい。グラフ関数電卓は、関数電卓としては使いにくい。fx-5800P の方が断然良い。もう一つの重要な理由はプログラムだ。まだグラフ関数電卓に移植していないプログラムが沢山ある。fx-5800P でしか使えない。小さく薄いので、カバンや上着のポケットに入れて持ち歩きやすいのも大切だ。

今、2番目のお気に入りは fx-CG50。これは、fx-9860GII 代わりに使える後継機種で、デザインが良い。当然 fx-5800P のプログラムは全て移植可能だ。だからこれも持ち歩いている。

ところが、である...

fx-5800P のプログラムを移植するには、全て手で入力しているわけだが、これが結構大変だ。昨日も1つのプログラム (サブルーチン2つ) を移植するのに、結局90分もかかった。かなり疲れた...

Casio Basic入門に掲載しているプログラムを打ち込む読者の気持ちも同じだろう。一旦移植してしまえば、fx-CG50 はカラー表示してより使いやすくなる。でも、まだまだ移植したいプログラムがある。先は長い...



[2018/02/25 追記]
ついにfx-5800P のPCリンクが実現した。利用をお勧めする。
 ついに fx-5800P がPCリンク可能になった

さらに、PCに保存したプログラムを編集したり、PCでプログラムが作れるようになった。PCでプログラムを編集・作成する時は fx-5800P の隠しフォントを活かして、より多くの変数が使えるようになった。
 fx-5800P Casio Basic をPCでコーディング - CcEditor


fx-5800P のもう一つの弱点は、ヒンジが壊れやすくてスグにハードカバーが取れてしまうことだ。
カシオの部品として交換用ヒンジが家電量販店で安く(ナント¥81で !!) 入手できた。さらに部品のハードカバーとラベルを一緒に入手して (総額¥486 !!)、 fx-5800P がニューアル! リニューアルした fx-5800P にさらに愛着を感じます。
 fx-5800P の破損ヒンジの交換、ついでにリニューアル



応援クリックをお願いします。励みになるので...
にほんブログ村 IT技術ブログ 開発言語へ


 



keywords: fx-5800Pfx-CG50、CasioBasic、プログラム関数電卓

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



テーマ : プログラム関数電卓
ジャンル : コンピュータ

fx-5800P のキーコード 【修正あり】

【2013/11/3 修正】
fx-5800Pのキーコード取得プログラムのソースに、1行抜けがあったので、それを修正。同時に、若干のスリム化をした。 お詫びして以下に修正を加える。

[2015/12/07 修正]
Casio Basicを使いこなす前に書いた記事だが、その後多くのプログラムを書いて Getkeyコマンドの有用性が分かってきたので、それに伴う修正を行った。



パソコンのプログラミング経験者は、キーボードのキー1つひとつに、固有の番号が割り当てられていることをご存じだろう。
この番号をキーコードと言う。

fx5800P_calc  

カシオプログラム関数電卓 FX-5800P

fx-5800Pもプログラミングでキーコードを使えるようになっている。
特定のキーが押されたかどうかを監視することができるわけだ。

fx-5800Pの専用プログラミング言語には、Getkey と言うコマンドが用意されている。

Getkeyコマンド
・引 数:なし
・戻り値:取得したキーコード
・動 作:Getkeyが実行された時、最後に押されたキーのキーコードを返す。何も押されていない場合は0を返す。

なお、[AC/ON]キーは例外で、それ以外の全てのキー(49個)のキーコードを取得できる。


直前に押されたキーのコードを取得することから、パソコンと同様に、キーバッファからキーコードを取得するようになっているのだろう。

※ fx-5800Pの取扱説明書:以下からPDFファイルをダウンロードできる
https://support.casio.jp/manualfile.php?cid=004007004



Getkeyを使う場面


Getkeyが有用なのは、プログラムが何か処理をしている時に押したキーに応じて処理を割り込ませる場合だ。テンキー以外のキーを使うメニュー処理にも有用だ。

そこで、[9]をキー入力してメニュー選択を行うプログラム作ってみる。

試しにGetkeyを使わないプログラムを作ってみると、以下のようになる。
ここでは、[9]を入力した時、入力した数字を表示させることにする。

======================
"INPUT NUMBER"?→K
"THE NUMBER = ":K◢ 

======================

このプログラムを実行すると、

------------------
INPUT NUMBER ?
------------------


と表示され、「9」を入力すると、

------------------
INPUT NUMBER ?
9
------------------

と表示され、一旦処理が止まる。

ここで、[EXE]キーを押すと、次の処理へ進んで、「入力した内容を表示する」処理が実行される。

------------------
INPUT NUMBER ?
9
THE NUMBER =   9
------------------

Getkeyを使わずに入力命令「?」を使うと、必ずプログラムが一旦停止するので、先へ進むにはどうしても [EXE]キーを押す必要がある。メニュー選択で余計なキー操作が必要だ。それでもテンキーを使ったメニュー処理なら、この方法は簡単ではある。


次に、Getkeyを使って、[9]を押してメニュー選択すると、[9]のキーコードを表示するプログラムを作ってみる。

======================
"INPUT NUMBER ?"
Do
Getkey→K
LpWhile K≠33
"THE NUMBER =":K◢ 

======================


キーが押されたかどうかを監視するには、Getkeyコマンドとループ処理と組み合わせる必要がある。

Do~LpWhile ループ処理では、キー入力監視を行い、数字キー[9]に相当するキーコードを取得しない限り、ル-プが回り続ける。キーコード33が取得されると、ループを脱出して、次の表示処理へ進む。

プログラムを実行すると、

--------------------
INPUT NUMBER ?   ■
--------------------

と表示される。

右端の■は、プログラムが動いていることを示す。つまり、ループが回り続けているわけだ。

ここで、[9]キーを押すと、

------------------
INPUT NUMBER ?
THE NUMBER =
            33
------------------

と[9]のキーコードである33が表示された。


Getkeyコマンドを使うと、メニュー選択のために何かキーを押すと、直ちに次の処理を行えることが分かる。さらに、テンキー以外のキーを使うには、Getkey を使うしかない。


キーコード取得プログラム
fx-5800Pの取扱説明書には、各キーのキーコードが記載されている。

Getkeyを利用するプログラムを書いている時、手元に取説が無いことが結構ある(私の場合は、通勤電車で電卓プログラミングを愉しんでいるので、こういうことになってしまう)。

そこで、キーコードを調べて表示するプログラムを作ってみた。

fx-5800P専用
キーコード取得プログラム:2013/12/20 修正
===============================
"Get KEYCODE"
Locate 6,3,"HIT ANY KEY"
Locate 8,4,"
:QUIT"
Lbl 0
Do
Getkey→K
LpWhile K=0
Cls
Locate 1,1,"KEYCODE =   "
Locate 11,1,K
Goto 0

================================


これを実行すると、

----------------
  GET KEYCODE

   HIT ANY KEY
     :QUIT
----------------

と、プログラムの説明を表示。

ここで、いきなり好きなキー(調べたいキー)を押す。

例えば、[DEL]キーを押すと、

-------------------
KEYCODE = 34    ■
    HIT ANY KEY
            :QUIT
-------------------

と表示される。

ここで表示されているキーコード34は、動作開始で押した[DEL}キーのキーコードだ。

さらに、好きなキーを押すと、そのキーコードが次々に表示される。 結構重宝している。



応援クリックをお願いします。励みになるので...
にほんブログ村 IT技術ブログ 開発言語へ


 



keywords: fx-5800PGetkeyコマンドキーコード, keycodeプログラミングプログラム関数電卓

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

続きを読む

テーマ : プログラム関数電卓
ジャンル : コンピュータ

fx-5800P でピタゴラス数

最終:2015年3月11日

プログラムにバグがあったので修正しました [2014/12/03]


a2 + b2 = c2 となる自然数の組 (a, b, c) をピタゴラス数といいます。(3, 4, 5) がピタゴラス数と言うのは、直角三角形の3平方の定理で有名です。

そこで、ピタゴラス数を調べる Casio Basic プログラムを fx-5800P で作ってみました。

実際の計算には、以下のようなピタゴラス数の性質を利用しました。

ピタゴラス数の性質 

例えば、(3, 4, 5)(6, 8, 10) は、いずれもピタゴラス数ですが、1つめを2倍すると2つめになり、これらは同じと見なすことにするので、「a, b, c の最大公約数は 1」と言う条件を付けています。(6, 8, 10) の最大公約数は、2 なので、条件から外れます。最大公約数が 1 の (a, b, c) を原始ピタゴラス数と言います。

m n の組み合わせに重複がなければ、全ての原始ピタゴラス数が重複なく得られると言うのが特長なので、この性質を利用して上の条件に合うような、mn を探して、見つかった mn からピタゴラス数 (a, b, c) を計算する作戦です。

先に M を決めて、そこから条件に合う N を探索し、N が 1 になった時はNの探索を終えて、次の M を決めて条件に合う N を探索する....これを繰り返します。



1) 最初、M を 3 とし、N を 1 とする。

2) 現在の M N からピタゴラス数を計算し、表示する

3) N 0 にならない範囲で 2 減らして、M÷N が割り切れないとき(MN が互いに素のとき)、その N を採用。割り切れる時は 3) を繰り返す。割り切れるかどうかは、M÷N の小数部分が 0 かどうかで判定。但し N が0 になると M÷N でエラー(0 で割り算できない)ので、その1歩手前の N が 1 の時には、Nの探索を終了する。

4) N0 以下になるとき、M を 2 つ増やし、M-2N に代入して、3) に戻り、正しい MN が見つかるまで 3) を繰り返す。

5) 2) へ戻る。 

文章よりも、2) ~ 4) のプログラムを見た方が分かりやすいでしょう。

Do
N-2→N
If N<0:Then
M+2→M:M-2→N
IfEnd
N=1⇒Break
LpWhile Frac(M÷N)=0




ピタゴラス数プログラム
3→M:1→N:1→D     (初期化処理)
Locate 1,2,"A="    
(初期画面表示)
Locate 1,3,"B="
Locate 1,4,"C="

Lbl 0

(M2-N2)÷2→A       
(ピタゴラス数の計算)
MN→B
(M2+N2)÷2→C

Locate 1,1,D        (見つかった回数の表示)
Locate 3,2,"       " (スペース14個)
Locate 3,2,A        
(ピタゴラス数の表示)
Locate 3,3,"       " (スペース14個)
Locate 3,3,B        (ピタゴラス数の表示)
Locate 3,4,"       " (スペース14個)
Locate 3,4,C        (ピタゴラス数の表示)

Locate 7,1,"EXE:Next"◢  
(操作法表示&プログラム一時停止)

Do               
(次の M と N を探す)
N-2→N
If N<0:Then
M+2→M:M-2→N
IfEnd
N=1⇒Break
LpWhile Frac(M÷N)=0
Isz D             
(見つかった回数を1つ増やす)

Goto 0


このプログラムは、Lbl 0 / Goto 0 の無限ループが基本構成ですので、終了するには [AC] キーを押します。

プログラムを起動すると、画面は以下のようになります。

Pytha1 

最初の原始ピタゴラス数 (4, 3, 5) が表示されています。
※ 左上: 探したピタゴラス数の個数。起動時なので 1
※ 右上: [EXE] キーを押すと次のピタゴラス数を探す


ここで、[EXE] キーを押すと、以下のように2つめのピタゴラス数がわかります。

Pytha2 

さらに、[EXE] キーを押すと、3つめのピタゴラス数を探します。

Pytha3 
※ 画像修正



今のプログラムだと、[EXE] キーを叩き続けなければ、大きなピタゴラス数が分からず、ちょっと物足りない。

そこで、[EXE] キーを長押しすると、ピタゴラス数の探索&表示を連続して行うように機能追加しました(連続モードの追加)。


※ 動画修正



使い方:
・起動すると、最初に作った「ステップモード」で、右上に EXE:Next  と表示。
[EXE] キーを押すと、次のピタゴラス数を計算して、表示します。

[EXE] キーを長押しすると「連続モード」になり、右上に (-): Stop と表示。
・連続モードでは、次々とピタゴラス数を計算して表示し続けます。
[(-)] キーを押すと「ステップモード」に戻り、右上の表示が EXE:Next に戻ります。

右上に EXE:Next と表示されていると、ステップモードだと分かります。(-):Stop と表示されていると、連続モードだとわかります。


連続表示のまま、しばらく置いておくと、以下のようになります。


※ 動画更新

ピタゴラス数が次々と表示されるのを見ていると、チョット面白いですね。


さて、キー長押しで機能選択する方法は、これまでも紹介していますが、今回のプログラムでも利用しています。この方法を知っていると、とても便利です。連続モードの機能追加には、[(-)] キーの通常押しの検出、[EXE] キーの長押しの検出を追加し、連続モードなら変数 E=0 、通常モードだと E=1 とし、表示を E の値に従って変更するようにしました。

これらのキー入力検知は以下のプログラムで処理します。

Getket=57⇒1→E
0→K
While Getkey=47
Isz K:K=7⇒Break
WhileEnd:K=7⇒0→E


次の短いプログラムを入力して、実際に遊んでみてください。

ピタゴラスの綴りが PYTHAGORAS なので、そのままファイル名としました。

(プログラム修正)

Pythagoras_Source 

※ Locateコマンドの空白は16個



応援クリックをお願いします。励みになるので...
にほんブログ村 IT技術ブログ 開発言語へ


 



keywords: プログラム関数電卓、fx-5800P、キー長押し、CasioBasic、 ピタゴラス数

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

テーマ : プログラム関数電卓
ジャンル : コンピュータ

最新記事
検索フォーム
最新コメント
カテゴリ
C# (3)
Visitors
Online Counter
現在の閲覧者数:
プロフィール

やす (Krtyski)

Author:やす (Krtyski)
since Oct 30, 2013


プログラム電卓は、プログラムを作って、使ってナンボ!

プログラム電卓を実際に使って気づいたこと、自作プログラム、電卓での Casio Basic や Casio Python プログラミングについて書いています。

なお管理人はカシオ計算機の関係者ではなく、Casio Basicが面白いと感じる1ユーザーです。


写真: 「4駆で泥んこ遊び@オックスフォード郊外」

リンク
月別アーカイブ
Sitemap

全ての記事を表示する

ブロとも申請フォーム

この人とブロともになる

QRコード
QR