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

追記修正 2019/08/28

今回は、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 のダウンロード

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 までのテスト中

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



グラフ関数電卓用に移植

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

グラフ関数電卓用 FactorG のダウンロード

FactorG 
FactorG の結果表示


今回は、slugrustle 様による投稿の解説記事になってしまいましたが、私としては十分楽しませてもらったので、記事にして残そうと思いました。




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


 


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

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

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

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【ゲーム】:もぐら叩き~まとめ~

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


普通のプログラム作成の記事と異なり、多少冗長な内容になっており、(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-9860Gシリーズ、fx-9750シリーズ(生産終了)
 メーカーサイト / 取扱説明書

・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-9860GIIfx-9860G II  fx-9860GII版もぐら叩きのダウンロード >
fx-CG20fx-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で素因数分解

2013/11/01:追記
2015/01/25:追記
2019/07/10:追記


 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倍程度速いことからも、プログラム実行にはかなり余分な処理を伴っていることがよく分かる。


[2019/07/10 追記]
fx-5800P で最速の素因数分解プログラムを紹介している。
 ⇒ fx-5800P 素因数分解 - 高速化

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

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





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


 


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

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

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

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プログラミングプログラム関数電卓

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

続きを読む

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

Casio 関数電卓の素因数分解

  追記 2015/06/18

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

 ・ fx-5800P で素因数分解
 ・ fx-5800P で素因数分解再び
 ・ fx-5800P 素因数分解 - バグ修正と表示変更
 ・ fx-9860GII への移植 - 素因数分解
 ・ VBAで素因数分解

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

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

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


 
私の手持ちの電卓で素因数分解ができるのは、最初から機能が内蔵されている 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以上の奇数で順次割り算する単純なロジックても、それぞれの実行時間をほぼ説明できそうだ、と今のところの結論です。(追記終わり)



素数は整数論の一分野で研究されていて、素数が無限個存在することは、紀元前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なのですね。

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

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

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

カシオの高精度計算サイト Ke!san のココでも取り上げられています。
ここでは、明確に書かれていませんが、s=-1 で、実数の世界を複素数の世界に拡張(解析接続)しています。ゼータ関数の性質として、これはやっても良いこと(s=1 以外で解析接続できてしまう)なので、間違っちゃいないのですが、紛らわしいですね。

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

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


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




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


 



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

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

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

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、 ピタゴラス数

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

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

fx-5800P 素因数分解 - バグ修正と表示変更

2014/11/15: 掲載プログラムの転記ミスを修正しました。


素因数分解再び の記事で紹介したプログラムについて、すけっぴぃさんから、バグの報告 (「素因数分解再び」のコメント) を頂きました。

素因数分解した結果に、素数の2乗が含まれる時、その素数の2乗が素数に分解されず、そのまま残って、素数でないのに素数として結果表示されると言う問題です。

例えば、45 ( = 32 × 5) の素因数分解の結果が 9 × 5 となってしまうが、135 ( = 33 × 5) は、正しく結果表示されると言う問題です。


かなり前に頂いたご指摘なのに、すぐに対処できないまま時間が経ってしまい申し訳ありません。最近時間に余裕が少しできたので、調べたところ、原因が分かりました。


本文にあるコードの赤文字の部分の1行目(あるいは以下のプログラムの10行目)にある

Y≦D



Y<D

に変更することで、バグの解消ができました。


これまでのプログラムは、素因数を見つけるたびに表示するようにしていましたが、実はこの仕様にしっくりきていませんでした。
そこで、素因数分解の計算を終了後、まとめて結果を表示するように変更してみました。


プログラムを起動した時の画面:

素因数分解Startup


数を入力する:

素因数分解Input 


素因数分解を最後まで計算したあとで、結果を表示:

素因数分解DisplayResult 

1行表示されたら [EXE] キーを押して次の行を表示させます。
これを繰り返して、上のように <EXE> が表示されたらそれが最後の素因数です。
ここで、 [EXE] キーを押せば最初の入力画面に戻ります。

4行を超える結果になる場合は、再び1行目から上書きします。


プログラムは以下のようにしました。かなりヒドイ転記ミスがありましたので、修正したものを再掲載します [2014/11/15]

 素因数分解_改造版ソース 
 
LpWhile Y≧1 の下に、表示のための処理を追加してみました。
 
また、17行目、Do ループの中に表示のために必要な配列変数への代入処理を入れています。

配列変数は、通常の変数よりもアクセスにかなり時間がかかることが分かっていますので、今回の改造で、全体の計算速度が低下する筈です。

そこで、計算速度を、前回のプログラムと比較してみました。

入力した自然数結果前回プログラムでの計算時間今回プログラムでの計算時間
123453 x 5 x 8232.5秒2.2秒
12345626 x 3 x 6433秒2.6秒
1234567127 x 972176.5秒
123456782 x 32 x 47 x 145938秒6.6秒
12345678932 x 3607 x 38033分2分43秒
98765432132 x 172 x 37972133秒28秒
9876543223 x 37 x 33366743秒27秒
98765433 x 227 x 1450312秒11秒
9876542 x 3 x 97 x 16976.5秒5秒
987655 x 197538秒7秒
987622 x 3 x 8233秒2秒

それほど大きな違いは出ていません。結果として、Doループを何度も回る時間に比べて配列変数アクセスによる速度低下が無視できる程度だと思います。

fx-5800P は同じ計算でも計算時間に結構なバラツキがあることが、最近分かってきました。これについては、クロック回路に起因する可能性が考えられるとの情報があり、その場合はクロック精度が数%バラツクのも説明できそうで、温度の影響もありそうです。

このあたりは、こちら (fx-5800Pの速度差) (fx-5800P プログラムのバックアップ のコメント) が 情報源です。

従って、今回の測定から、処理速度はほぼ同じ、と言うべきでしょう。但し、1234567 の素因数分解だけは、どうもよく分からない結果ですね。

手元で測り直したら7秒程度でした。本エントリーはボロボロでした(-_-;)

ご指摘頂いた santaro様、ありがとうございます。



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


 



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

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


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

fx-5800P:Hit&Blow【完成版】

以前 fx-5800P【ゲーム】:Hit&Blow で取り上げ、fx-5800P で3桁の数字を当てる仕様で実際にプログラムを作りました。

その後、桁数を3桁、4桁および5桁に自由に変えて遊べる Hit&Blow を作って遊んでみました。

3桁が一番面白く、4桁は難易度が高くなりますがそれなりに面白いと思います。5桁バージョンは、難し過ぎてゲームとしてはつまらないかも知れません。

そこで、桁数を自由に変えて遊べる Hi&Blow を紹介します。


※ プログラムライブラリに収録しています ⇒ ここ


ゲームの仕様

ゲーム開始画面
1.ゲーム開始時に、数字の桁数を、3、4、5から選択・設定する
2.開始画面には、以下を表示する
  ・HIT And BLOW のゲームタイトル
  ・3~5の桁数の選択機能
  ・
:START、< ? >:ANSWER
3.開始画面で、秘密のキー(キーの同時押し)で正解を表示する


hb_Start4hb_Start5hb_Start3 
※ 桁数の選定は、矢印キー [▲] と [▼] で3~5が順次変化するようにする。
fx-5800P の16桁X4桁画面をフルに活かした画面設計にする。

ゲーム進行画面
4.電卓が出題する正解数を、△HIT、◇BLOW と言うヒントを元に当ててゆく
5.正解数は、各桁0~9各の異なる数字とし、一番左の桁は0であっても良い
6.入力する数字の桁に同じ数字があると、エラーを表示して正しい入力を促す
7.入力する数字の桁が、最初に指定した桁より多いと、エラーを表示して正しい入力を促す
8.何回目の回答かを、表示する
9.10回以内に正解すると、EXCELLENT と表示する
10.10回を超えても正解しない時は、QUIT? と表示する。
11.10回を超えて正解すると、GOOD と表示する。

hb_3d_3hb_4d_4hb_3d_bingo  

※ ゲーム進行画面は、既に作っている Hit&Blowと基本的に同じになる。


ゲーム終了画面
12.正解すると、終了画面で YOU WIN IN xx TRIES と正解するまでの回答数を表示する
13.正解できず、QUIT? の表示で[DEL]キーを押すと、終了画面で正解を示す
14.正解できずに終了すると、終了画面で YOU GAVE UP   ANSWER = xxxxx と表示する
15.終了画面では、
:QUIT、<0>:TRY AGAIN とメニューも併せて表示する

hb_FInish_win 



プログラムコード

以下の4つのルーチンから構成します。
ルーチン種別プログラム名説明
メインルーチンHIT AND BLOWプログラムの流れと表示を主に行う
サブルーチン1S1HB345入力数を各桁の数に分解する
サブルーチン2S2HB345正解の数を生成する
サブルーチン3S3HB345回答を入力させる、ゲーム本体の処理を行う
サブルーチン4S4HB345入力した数の判定及びその結果表示を行う

fx-5800P はパソコンとの通信機能が無いので、コードを手で入力するしかありません。チョット長いコードになりますが、入力して遊んでみてください。

今回のプログラムに関連した、幾つかのプログラミングTIPS を今後紹介する予定です。何かリクエストやご提案があれば、是非お聞かせください。


メインルーチン: "HIT AND BLOW" (41行)

HB345_Code_main   

サブルーチン: "S1HB345" (24行)
HB345_Code_sub1   

サブルーチン: "S2HB345" (27行)
HB345_Code_sub2       

サブルーチン: "S3HB345" (32行)
HB345_Code_sub3       

サブルーチン: "S4HB345" (38行)
HB345_Code_sub4   



プログラムの基本構成と簡単な説明

メインルーチン: "HIT AND BLOW"
 初期設定
   ↓
 Lbl 0
   ↓
 開始画面表示
   ↓
 桁数選択と決定
   ↓
 正解数を決める <---> 正解数生成サブルーチン: "S2HB345"
   ↓
 回答の入力 <------> 回答サブルーチン: "S3HB345"
   ↓             Lbl 0
 終了画面          回答数の桁分解 <-> 桁分解サブルーチン: S1HB345"
   ↓            入力エラー処理
 Goto 0             回答数の判定 <--> 回答判定サブルーチン: S4HB345"
                 正解でない時 Goto 0
                 正解すればメインルーチンへ戻る


このように、メインルーチンと4つのサブルーチンからプログラム全体を構成します。


メインルーチン: HIT AND BLOW"
ゲーム全体の流れの制御と主なメニュー表示を行い、正解数決定サブルーチン(S2HB345) と  回答サブルーチン(S3HB345) を呼び出す。

最初の画面の<?>:ANSWER のメニューで正解を知るための秘密のキーは、キーコードが1桁になるようなキー入力をすれば良い。そのためには、複数のキーの同時押しを行う。例えば[4]と[7]のキーを同時押しする。詳しくは
ここ を参照してください。

最初の画面で決めた桁数は変数Gに格納される(G = 3, 4, 5)。

回答サブルーチン で正解表示フラグが1 (D=1) になってメインルーチンへ戻ってきた場合は、"YOU GAVE UP" の表示及び正解表示 "ANSWER = xxx" を行う。


正解数作成サブルーチン: "S2HB345"
決定された桁数(3、4、5桁)に従って、正解数を決定する。全ての桁が異なる数になるようにするところがポイント。

桁数(G)に応じた桁数で正解を生成する。整数乱数を生成する関数 IntRan#()を使用し各桁ごとに任意の1桁の数を得る。ここではDoループを用いて、各桁で同じ数になる場合はDoループ回し続け、全ての桁が異なる数になる時にDoループを抜ける。

メインルーチンで<秘密のキー>を押すと変数Dに1が入り、このルーチンにおいてD=1の時には正解を表示する。


回答サブルーチン: "S3HB345"
ゲーム進行画面を表示し、数字の入力をさせ、各桁の数を得るための桁分解サブルーチンと、入力された数の回答判定サブルーチンを呼び出す。正解が得られるまで処理を繰り返し、正解が得られたらメインルーチンへ戻る。

入力したn桁(n = 3, 4, 5)の数で同じ数が含まれる場合は、桁分解サブルーチンがエラーグラフEに1を格納する。このルーチンでは E=1 の時、「同じ数が含まれている(ERROR SAME NUMBER FOUND IN DIGITS)」とエラー表示をして、再入力させる。

このルーチン全体をDoループの中に収める。桁数Gでヒット数がGになれば正解となるので、H≠Gである限り、Doループで回答サブルーチンを回し続け、H=Gになった場合だけメインルーチンへ戻る(return)。つまり、このルーチンがゲーム本体となる。


桁分解サブルーチン: "S1HB345"
入力された数を、各桁の数に分解する。桁数(G)に応じた3つのルーチンを含む。入力したn桁(N = 3, 4, 5)の数で同じ数が含まれる場合は、エラーフラグ(変数E)に1を格納する。


回答判定サブルーチン: "S4HB345"
入力された数に対して、HIT数とBLOW数の判定を行い、その結果を表示する。結果が表示されたら、[EXE]キーを押させて 回答サブルーチン(S3HB345)へ戻る。

10回以内で正解が得られると "EXELLENT" と表示する。11回以上で正解が得られると "GOOD" と表示する。11回以上で正解が得られない時は "QUIT?"(やめますか?) "<DEL>"と表示する。[DEL]キーを押すと正解表示フラグ(変数D)に1を格納してメインルーチンへ戻る。



主な変数

G:桁数(3,4,5のいずれか)

A:正解のn桁数
K:数Aの1番左の桁の数
L:数Aの左から2桁目の数
M:数Aの左から3桁目の数
I:数Aの左から4桁目の数
J:数Aの左から5桁目の数

N:回答するn桁数
X:数Nの1番左の桁の数
Y:数Nの左から2桁目の数
Z:数Nの左から3桁目の数
V:数Nの左から4桁目の数
W:数Nの左から5桁目の数

H:ヒット数
B:ブロー数

C:回答回数
D:正解表示フラグ:
 D=0:正解表示をしない
 D=1:正解表示する
E:回答数エラーフラグ:
 E=0:エラーなし
 E=1:同じ数の桁があるエラー

K:取得したキーコード




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


 



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

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

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

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

やす (Krtyski)

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


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

実際に触って気づいたこと、自作プログラム、電卓プログラミングについて書いています。

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


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

リンク
月別アーカイブ
Sitemap

全ての記事を表示する

ブロとも申請フォーム

この人とブロともになる

QRコード
QR