Casio Python - Python らしい反復処理:高速素因数分解(2)

Python Casio Python
 Casioグラフ関数電卓の Python を使ってみる
     - Python らしい反復処理:高速素因数分解(2) 
目次


初版:2020/07/25
修正:2020/07/26
追記修正:2020/11/14

前の記事 - 8. シェル画面入力の工夫 |  次の記事 - 10. 大きな数の計算


9. Python らしい反復処理:高速素因数分解(2) <fx-CG50 OS3.40以降>

前回は、Casio Basic プログラムを、とりあえず動かすことを優先させ、できるだけ忠実に Casio Python に移植しました。
291行もある長大なスクリプトです。似たような処理が何度も繰り返されており、無駄が満載です。

オリジナルの Casio Basic のコードは、その言語仕様から長大なソースになっていますが、今回は、Python らしい反復処理を用いて、大幅にスリム化します。主に、以下に示した5項目 の変更を行って、無駄を減らします。

(1) farc() 関数をユーザーモジュールに追加し、ここでの関数定義を削除する
(2) 不要な記述を削除する
(3) disp() 関数内を、反復処理に置換えて、記述を簡潔にする
(4) を反復処理に置き換えて、記述を簡潔にする
(5) を反復処理に書き換えて、記述を簡潔にする



前回作ったスクリプト - FactorG1.py のダウンロード

fx-CG50 Pythonモード:高速素因数分解 - FactorG1.py
"""Sample script

Exercise;
ported from Casio Basic
"Prime Factor 10 digits"
factorG.py
ver 1.0

by Krtyski/e-Gadget
"""

from u import *

def ckpwr():
 global a,b,c,d,e,z
 e+=1
 z[e]=b
 while 1:
  a=int(d)
  z[e+11]+=1
  d=a/b
  if frac(d):
   break
 c=int(sqrt(a))

def disp():
 global a,b,c,d,e,f,z
 if a>1:     ◀ (3) disp() は素因数探索が終わって最後に実行されるので、
  e+=1      ◀ (3) この if 文も 探索囚虜後に1度だけ実行される。
  z[e]=a    ◀ (3) この if 文は、最後に探索した素因数を z[ ] に格納する処理で、
  a=1       ◀ (3) 表示処理の一部ではないので、ここから削除し、
  z[e+11]=1   ◀ (3) disp() 関数実行の直前に記述することにする。
 d=int(e/6)   ◀ (2) 複数ページ切替のためのページ番号 d を計算⇒ 不要、削除する
 if e-6*d>0:   
 (2) 複数ページ切替のためのページ番号 d を計算⇒ 不要、削除する
  d+=1     ◀ (2) 複数ページ切替のためのページ番号 d を計算⇒ 不要、削除する
 c=1

 clear_screen()
 locate(00f3'm'0)
 b 6*(c-1)+1   (3) 複数ページ切替機能を使わないので、bは常に1 ⇒ b=1 と書き換える
 locate(0, 1, z[b], 1, 'm', 0) ◀ (3) ここから disp() 関数終わりまでは反復処理に置き換える
 locate(10, 1, '^(', 2, 'm', 0)                    ↓
 locate(12, 1, z[b+11], 1, 'm', 0)
 locate(15, 1, ')', 2, 'm', 0)
 if b+1<=e:
  locate(0, 2, z[b+1], 1, 'm', 0)
  locate(10, 2, '^(', 2, 'm', 0)
  locate(12, 2, z[b+12], 1, 'm', 0)
  locate(15, 2, ')', 2, 'm', 0)
 if b+2<=e:
  locate(0, 3, z[b+2], 1, 'm', 0)
  locate(10, 3, '^(', 2, 'm', 0)
  locate(12, 3, z[b+13], 1, 'm', 0)
  locate(15, 3, ')', 2, 'm', 0)
 if b+3<=e:
  locate(0, 4, z[b+3], 1, 'm', 0)
  locate(10, 4, '^(', 2, 'm', 0)
  locate(12, 4, z[b+14], 1, 'm', 0)
  locate(15, 4, ')', 2, 'm', 0)
 if b+4<=e:
  locate(0, 5, z[b+4], 1, 'm', 0)
  locate(10, 5, '^(', 2, 'm', 0)
  locate(12, 5, z[b+15], 1, 'm', 0)
  locate(15, 5, ')', 2, 'm', 0)
 if b+5<=e:
  locate(0, 6, z[b+5], 1, 'm', 0)
  locate(10, 6, '^(', 2, 'm', 0)
  locate(12, 6, z[b+16], 1, 'm', 0)
  locate(15, 6, ')', 2, 'm', 0)
 if b+6<=e:
  locate(0, 7, z[b+6], 1, 'm', 0)
  locate(10, 7, '^(', 2, 'm', 0)
  locate(12, 7, z[b+17], 1, 'm', 0)
  locate(15, 7, ')', 2, 'm', 0)
 if b+7<=e:
  locate(0, 8, z[b+7], 1, 'm', 0)
  locate(10, 8, '^(', 2, 'm', 0)
  locate(12, 8, z[b+18], 1, 'm', 0)
  locate(15, 8, ')', 2, 'm', 0)
 if b+8<=e:
  locate(0, 9, z[b+8], 1, 'm', 0)
  locate(10, 9, '^(', 2, 'm', 0)
  locate(12, 9, z[b+19], 1, 'm', 0)
  locate(15, 9, ')', 2, 'm', 0)
 if b+9<=e:
  locate(0, 10, z[b+9], 1, 'm', 0)
  locate(10, 10, '^(', 2, 'm', 0)
  locate(12, 10, z[b+20], 1, 'm', 0)
  locate(15, 10, ')', 2, 'm', 0)
 if b+10<=e:
  locate(0, 11, z[b+10], 1, 'm', 0)
  locate(10, 11, '^(', 2, 'm', 0)
  locate(12, 11, z[b+21], 1, 'm', 0)    
  locate(15, 11, ')', 2, 'm', 0)     ◀ (3) ここまでを反復処理で置き換える
 locate(0, 0, '', 0, 'm', 1)

def frac(x):          ◀ (1) この関数をユーザーモジュール u.py ver 1.4 に追加し
 retuen x-int(x)         これを削除する


while
1:
 try:
  inp=str(eval(input('Number:')))
 except (SyntaxError,TypeError,NameError) as e:
  print(e)
  print('*must be number or\n expression')
  continue
 if '.' in inp:
  print('*must be integer')
  continue
 elif inp.isdigit():
  if len(inp)>10:
   print('*must be 10 or less')
   continue
  else:
   f=int(inp)
   break
 else:
  continue

z=list(range(23))
for e in range(1,23):
 z[e]=0
z[1]=0    ◀ (2) 上の for文で 0 に初期化されているので不要、削除する
z[12]=0    
◀ (2) 上の for文で 0 に初期化されているので不要、削除する
e=0
a=f
c=int(sqrt(a))

b=2;d=a/b         ◀ (4) ここから whle 1: の上までを反復処理に置き換える
if frac(d)==0:ckpwr()        
if b>c:disp()          disp() 関数は、素因数探索が終わってから実行される
b=3;d=a/b           ので、ここで disp() を実行する必要が無い。
if frac(d)==0:ckpwr()     そこで、この部分の disp() は break に置換えても
if b>c:disp()          問題ない。disp() は最後に1度だけ実行すれば良い
b=5;d=a/b
if frac(d)==0:ckpwr()
if b>c:disp()
b=7;d=a/b
if frac(d)==0:ckpwr()
if b>c:disp()
b=11;d=a/b
if frac(d)==0:ckpwr()        
if b>c:disp()        ◀ (4) ここまでを反復処理で置き換える

while 1:
 b+=2;d=a/b       ◀ (5) ここから disp() の前までを反復処理に置き換える
 if frac(d)==0:ckpwr()       
 if b>c:break
 b+=4;d=a/b
 if frac(d)==0:ckpwr()
 if b>c:break
 b+=2;d=a/b
 if frac(d)==0:ckpwr()
 if b>c:break
 b+=4;d=a/b
 if frac(d)==0:ckpwr()
 if b>c:break
 b+=6;d=a/b
 if frac(d)==0:ckpwr()
 if b>c:break
 b+=2;d=a/b
 if frac(d)==0:ckpwr()
 if b>c:break
 b+=6;d=a/b
 if frac(d)==0:ckpwr()
 if b>c:break
 b+=4;d=a/b
 if frac(d)==0:ckpwr()
 if b>c:break
 b+=2;d=a/b
 if frac(d)==0:ckpwr()
 if b>c:break
 b+=4;d=a/b
 if frac(d)==0:ckpwr()
 if b>c:break
 b+=6;d=a/b
 if frac(d)==0:ckpwr()
 if b>c:break
 b+=6;d=a/b
 if frac(d)==0:ckpwr()
 if b>c:break
 b+=2;d=a/b
 if frac(d)==0:ckpwr()
 if b>c:break
 b+=6;d=a/b
 if frac(d)==0:ckpwr()
 if b>c:break
 b+=4;d=a/b
 if frac(d)==0:ckpwr()
 if b>c:break
 b+=2;d=a/b
 if frac(d)==0:ckpwr()
 if b>c:break
 b+=6;d=a/b
 if frac(d)==0:ckpwr()
 if b>c:break
 b+=4;d=a/b
 if frac(d)==0:ckpwr()
 if b>c:break
 b+=6;d=a/b
 if frac(d)==0:ckpwr()
 if b>c:break
 b+=8;d=a/b
 if frac(d)==0:ckpwr()
 if b>c:break
 b+=4;d=a/b
 if frac(d)==0:ckpwr()
 if b>c:break
 b+=2;d=a/b
 if frac(d)==0:ckpwr()
 if b>c:break
 b+=4;d=a/b
 if frac(d)==0:ckpwr()
 if b>c:break
 b+=2;d=a/b
 if frac(d)==0:ckpwr()
 if b>c:break
 b+=4;d=a/b
 if frac(d)==0:ckpwr()
 if b>c:break
 b+=8;d=a/b
 if frac(d)==0:ckpwr()
 if b>c:break
 b+=6;d=a/b
 if frac(d)==0:ckpwr()
 if b>c:break
 b+=4;d=a/b
 if frac(d)==0:ckpwr()
 if b>c:break
 b+=6;d=a/b
 if frac(d)==0:ckpwr()
 if b>c:break
 b+=2;d=a/b
 if frac(d)==0:ckpwr()
 if b>c:break
 b+=4;d=a/b
 if frac(d)==0:ckpwr()
 if b>c:break
 b+=6;d=a/b
 if frac(d)==0:ckpwr()
 if b>c:break
 b+=2;d=a/b
 if frac(d)==0:ckpwr()
 if b>c:break
 b+=6;d=a/b
 if frac(d)==0:ckpwr()
 if b>c:break
 b+=6;d=a/b
 if frac(d)==0:ckpwr()
 if b>c:break
 b+=4;d=a/b
 if frac(d)==0:ckpwr()
 if b>c:break
 b+=2;d=a/b
 if frac(d)==0:ckpwr()
 if b>c:break
 b+=4;d=a/b
 if frac(d)==0:ckpwr()
 if b>c:break
 b+=6;d=a/b
 if frac(d)==0:ckpwr()
 if b>c:break
 b+=2;d=a/b
 if frac(d)==0:ckpwr()
 if b>c:break
 b+=6;d=a/b
 if frac(d)==0:ckpwr()
 if b>c:break
 b+=4;d=a/b
 if frac(d)==0:ckpwr()
 if b>c:break
 b+=2;d=a/b
 if frac(d)==0:ckpwr()
 if b>c:break
 b+=4;d=a/b
 if frac(d)==0:ckpwr()
 if b>c:break
 b+=2;d=a/b
 if frac(d)==0:ckpwr()
 if b>c:break
 b+=10;d=a/b
 if frac(d)==0:ckpwr()
 if b>c:break
 b+=2;d=a/b
 if frac(d)==0:ckpwr()
 if b>c:break
 b+=10;d=a/b
 if frac(d)==0:ckpwr()       ↓
 if b>c:break        (5) ここまでを反復処理で書き換える

disp()



9.1 frac() 関数をユーザーモジュール (u.py) に追加

この関数は、浮動小数点の数値から小数部を取り出すもので、Casio Python には備わっていないません。便利な関数なのでユーザー関数としてユーザーモジュールに追加します。バージョンアップしたユーザーモジュールは下記からダウンロードできます。

ユーザーモジュール - u.py ver 1.4 のダウンロード


9.2 不要な処理を削除

上記の5箇所 (赤文字で表記した部分) を削除します。


9.3 disp() 関数のスリム化

disp() 関数の冒頭にある if 文
 if a>1:
  e+=1
  z[e]=a
  z[e+11]=1

を削除します。

というのは、この部分は最後に探索した素因数を リスト z[ ] に格納する処理なので、disp() から切り離し、disp() の直前に記述するように変更します。disp() は全ての素因数を見つけた後に、1度だけ実行されるので、この切り離しは機能に影響はなく、ソースの見やすさが改善されると思います。

さらに、
b = 6*(c-1)+1

b=1
に変更します。

というのも、変数 c は、結果表示のページを示し、c=1 の時は1ページ目、c=2 の時は2ページ目を示します。
現在の Casio Python ではインタラクティブなキー入力を取得する機能が実装されていないので、全ての素因数を1ページ内に表示する仕様に変更しています。従ってページ数のカウントは不要になり、常に c=1 となります。すると
b = 6*(c-1)+1 は、常に b=1 となるので、変数 b の初期化をこのように書き換えます。

これまでをまとめると、 disp() は下記になります。

def disp():
 global a,b,c,d,e,f,z
 clear_screen()
 locate(00f3'm'0)
 b=1                  (3) 複数ページ切替機能を使わないので、常に b=1、b=1 に書き換えた
 locate(0, 1, z[b], 1, 'm', 0) ◀ (3) ここから disp() 関数終わりまでは反復処理に置き換える
 locate(10, 1, '^(', 2, 'm', 0)                    ↓
 locate(12, 1, z[b+11], 1, 'm', 0)
 locate(15, 1, ')', 2, 'm', 0)
 if b+1<=e:
  locate(0, 2, z[b+1], 1, 'm', 0)
  locate(10, 2, '^(', 2, 'm', 0)
  locate(12, 2, z[b+12], 1, 'm', 0)
  locate(15, 2, ')', 2, 'm', 0)
 if b+2<=e:
  locate(0, 3, z[b+2], 1, 'm', 0)
  locate(10, 3, '^(', 2, 'm', 0)
  locate(12, 3, z[b+13], 1, 'm', 0)
  locate(15, 3, ')', 2, 'm', 0)
 if b+3<=e:
  locate(0, 4, z[b+3], 1, 'm', 0)
  locate(10, 4, '^(', 2, 'm', 0)
  locate(12, 4, z[b+14], 1, 'm', 0)
  locate(15, 4, ')', 2, 'm', 0)
 if b+4<=e:
  locate(0, 5, z[b+4], 1, 'm', 0)
  locate(10, 5, '^(', 2, 'm', 0)
  locate(12, 5, z[b+15], 1, 'm', 0)
  locate(15, 5, ')', 2, 'm', 0)
 if b+5<=e:
  locate(0, 6, z[b+5], 1, 'm', 0)
  locate(10, 6, '^(', 2, 'm', 0)
  locate(12, 6, z[b+16], 1, 'm', 0)
  locate(15, 6, ')', 2, 'm', 0)
 if b+6<=e:
  locate(0, 7, z[b+6], 1, 'm', 0)
  locate(10, 7, '^(', 2, 'm', 0)
  locate(12, 7, z[b+17], 1, 'm', 0)
  locate(15, 7, ')', 2, 'm', 0)
 if b+7<=e:
  locate(0, 8, z[b+7], 1, 'm', 0)
  locate(10, 8, '^(', 2, 'm', 0)
  locate(12, 8, z[b+18], 1, 'm', 0)
  locate(15, 8, ')', 2, 'm', 0)
 if b+8<=e:
  locate(0, 9, z[b+8], 1, 'm', 0)
  locate(10, 9, '^(', 2, 'm', 0)
  locate(12, 9, z[b+19], 1, 'm', 0)
  locate(15, 9, ')', 2, 'm', 0)
 if b+9<=e:
  locate(0, 10, z[b+9], 1, 'm', 0)
  locate(10, 10, '^(', 2, 'm', 0)
  locate(12, 10, z[b+20], 1, 'm', 0)
  locate(15, 10, ')', 2, 'm', 0)
 if b+10<=e:
  locate(0, 11, z[b+10], 1, 'm', 0)
  locate(10, 11, '^(', 2, 'm', 0)
  locate(12, 11, z[b+21], 1, 'm', 0)    
  locate(15, 11, ')', 2, 'm', 0)     ◀ (3) ここまでを反復処理で置き換える
 locate(0, 0, '', 0, 'm', 1)



変数 b に着目すると、b は リスト z[ ] のインデックスとして利用されていて、このインデックスは、1 から 11 まで 1 づつ増えています。そこで、それぞれの if 節にある locate() 関数4行分をワンセットとして、for 文による反復処理に書き換えます。

ついでに、入力値の桁数を表示する機能を追加します。

clear_screen() 以下を書き換えます。

 clear_screen()
 locate(00f3'm'0)
 locate(160': ' str(len(inp)) + ' digits'3'm'0) #入力値の桁数表示
 line(0,15,383,15,1,0)
 for i in range(112):
  if i<=e:
   locate(,,z[i], 1'm'0)
   locate(10i'^('2'm'0)
   locate(12iz[i+21], 1'm'0)
   locate(15i')'2'm'0)
 locate
(00''0'm'1)


さて、このように書き換えた結果、変数 b, c, d  はこの関数内では不要になりました。従ってグローバル変数の宣言において、不要になった変数 b, c, d を削除して、gobal 文を書き換えます。

range(1, 23) は、リスト [1, 2, 3, 4, 5, ... ,21, 22, 23] を生成して、その要素を最初から最後まで順に i に適用して反復を行います。range(23) は 要素が 0 から始まりますが、range(1, 23) とすれば、要素は 1 から始まります。

Note: range() の書式:
range(start=0, stop, step=1)
・引数が1つの場合は、range(stop) で、デフォルト start=0、step=1 が適用されます。
・引数が2つの場合は、range(start, stop) で、デフォルト step=1 が適用されます。
・引数が3つの場合は、range(start, stop, step) と全てを明示的に指定します。


完成した disp() 関数は下記のようになります。スッキリと無駄を省けました。

def disp():
 global a,e,f,z
 clear_screen()
 locate(00f3'm'0)
 locate(160': ' str(len(inp)) + ' digits'3'm'0)
 line(0,15,383,15,1,0)
 for i in range(112):
  if i<=e:
   locate(,,z[i], 1'm'0)
   locate(10i'^('2'm'0)
   locate(12iz[i+21], 1'm'0)
   locate(15i')'2'm'0)
 locate
(00''0'm'1)



9.4  素数が素因数かどうかをチェックする部分のスリム化

以下の部分を反復処理に置き換えます。

b=2;d=a/b
if frac(d)==0:ckpwr()
if b>c:disp()
b=3;d=a/b
if frac(d)==0:ckpwr()
if b>c:disp()
b=5;d=a/b
if frac(d)==0:ckpwr()
if b>c:disp()
b=7;d=a/b
if frac(d)==0:ckpwr()
if b>c:disp()
b=11;d=a/b
if frac(d)==0:ckpwr()
if b>c:disp
()


上の方針でも書きましたが、disp() は本来 (Casio Basic プログラムを見れば分かります) 全ての素因数探索が終わったあとで実行されます。従って、ここに disp() は不要で、break に置き換えることで、無駄な関数呼び出しを避けます。これにより実行時間も多少は短くなります。disp() は今回のスクリプトの最後で1度だけ実行されれば問題ありません。

なお、ここでは if 文 は1行で書いていますが、Python の公式サイトでは、この書き方を推奨していません。

変数 b に着目すると、b の値が 2, 4, 5, 7, 11 と異なるだけで、あとは同じ処理が列挙されています。これを反復処理に書き換えるには、リストを使った for 文が使えます。

この b の値は素数なので、これらの素数を要素としたリスト prime_list = [2, 3, 5, 7, 11] を定義して使うことにします。リストは、かぎ括弧を使って定義できます。

そして、以下のような for 文が書けるのは、Python のようなオブジェクト指向言語に 特有の便利なところです。

反復処理への書き換えは、以下のようになります。


prime_list=[2,3,5,7,11]
for b in prime_list:
 d=a/b
 if frac(d)==0ckpwr()
 if b>c: break


リスト prime_list の要素を最初から最後まで順に b に適用し、反復処理を行うことができます。リストの要素の最後が適用されれば反復が終わります。このように、反復回数を明示的に設定せずに、リストというシーケンス型オブジェクトに依存して for 文の反復が行えるのは、オブジェクト指向言語の大きな特徴です。Casio BasicC 言語のような関数型言語では出てこないと思います。

余談になりますが、for i in range(10): という記述は、i を 0 ~ 9 まで1つづつ適用するのですが、実はリストの要素を生成しながら、その要素を順次適用して反復を行うといった内部動作をしていて、リストの要素を最初おから最後まで順に適用しているわけです。

もう少し詳しく言えば、range(10) は、リスト [0, 1, 2, 3, 4, 5, 6, 7, 8, 9] の要素を順次生成し、その要素を 変数 i  に適用しながら反復処理を行いますが、for 文ではリスト全体を生成するのではなく、要素を生成しながら適用させるといった働き (ジェネレータの動作) をしています。実際にメモリ上にリストを生成しているのではないので、リストを格納するメモリが節約されます。リストが非常に大きな場合は、メモリ節約の効果が極めて大きくなり、このような時にはジェネレータの効果が絶大になります。

一方、
num = list(range(10))

と書くと、実際にリストを生成して、リスト num = [0, 1, 2, 3, 4, 5, 6, 7, 8, 9] が定義されます。


9.5 素因数を探索する残りの部分のスリム化

以下の部分 (while 1: 以下 144行の部分) を反復処理で書き換えます。
while 1:
 b+=2;d=a/b
 if frac(d)==0:ckpwr()
 if b>c:break
 b+=4;d=a/b
 if frac(d)==0:ckpwr()
 if b>c:break
 ・・・
 ・・・
 ・・・
 b+=2;d=a/b
 if frac(d)==0:ckpwr()
 if b>c:break
 b+=10;d=a/b
 if frac(d)==0:ckpwr()
 if b>c:break

変数 b に着目すると、b を増やしながら同じ処理を列挙しています。但し b の増分に簡単な規則性はなく、簡単な計算では求められません。この増分がどうやって決められているのかは、Casio Basic プログラムを公開している記事を参照してください。
fx-5800P 素因数分解 - 高速化

Python の for 文では、既に上で紹介したように、b の増分を要素としたリストを使えば簡単に反復処理ができます!

増分 (インクリメント) のリストなので、リストの名前を increment とし、以下のように定義します。

increment = [2, 4, 2, 4, 6, 2, 6, 4, 2, 4, 6, 6, 2, 6, 4, 2, 6, 4, 6, 8, 4, 2, 4, 2, 4, 8, 6, 4, 6, 2, 4, 6, 2, 6, 6, 4, 2, 4, 6, 2, 6, 4, 2, 4, 2, 10, 2, 10]

要素数は48個あります。

反復処理に書き換えると、以下のようになります。

increment=[2, 4, 2, 4, 6, 2, 6, 4, 2, 4, 6, 6, 2, 6, 4, 2, 6, 4, 6, 8, 4, 2, 4, 2, 4, 8, 6, 4, 6, 2, 4, 6, 2, 6, 6, 4, 2, 4, 6, 2, 6, 4, 2, 4, 2, 10, 2, 10]
while 1:
 for i in increment:
  b+=i; d=a/b
  if frac(d)==0: ck_pwr()
  if b>c: break
 if b>c: break

反復処理への書き換えに伴い、赤文字と青文字部分を追加しています。

赤文字は、for 文による反復のために追加した部分です。
リスト increment の要素を最初から最後まで順に 変数 i に適用しながら、反復を行います。
for 文の中にある if b>c: break の break は、b>c が成立するときに  for ループから抜けるだけで、while ループからの脱出ができません。ここでは一気に while ループからも脱出する動作にしたいところです (オリジナルの Casio Basic のソースでは Goto によるジャンプで、一気にループから脱出しています) 。

そこで、for ループから抜けたところで、もう一度青文字で追加した if b>c: break を実行することで、while ループからも一気に抜けるようにします。

=====

ところで、リスト increment の定義は、要素が48個もあるので、長々と記述します。電卓の狭い画面では見づらいので、改行して見やすくします。

スクリプトの動作に影響を与えずにソースを改行するためには、改行したいところにバックスラッシュ \ を入れます。

但し、括弧の中は改行してもスクリプトの動作に影響を与えないので、電卓の画面で見やすいように適宜改行を入れます。

increment=\
[2,4,2,4,6,2,6,4,
 2,4,6,6,2,6,4,2,
 6,4,6,8,4,2,4,2,
 4,8,6,4,6,2,4,6,
 2,6,6,4,2,4,6,2,
 6,4,2,4,2,10,2,10]

while 1:
 for i in increment:
  b+=id=a/b
  if frac(d)==0ckpwr()
  if b>cbreak
 if b>c
break


格段に無駄を省いて、スリム化できました!


9.6 スリム化したスクリプト - FactorG2.py

291行もあったスクリプトが、反復処理を使って書き換えることで 91行までスリム化できました。

Note: Casio Python スクリプトファイルのサイズ制限
今回、実際に長大なスクリプトを編集している際、Casio Python は、300 行を超えると電卓上ではこれ以上改行がができなくなることが分かりました。
さらに、PC上のエディタで 300 行を超えるスクリプトを書いてから電卓に転送して、このスクリプトファイルを開こうとすると、"Invalid Data Size" という通信エラーが発生し、ファイルを開けません。
300 行で改行ができなくてなっても、既存行内への入力はできます。おそらくファイルサイズの上限までは行内の入力は可能で、保存も可能です。ファイルサイズの上限はまだ確認できていません。
1ファイルあたり最大 300 行の制限は CGモデル (fx-CG50) の Casio Python の仕様
1ファイルあたり最大 150行の制限は FXモデル (fx-9750GIII, fx-9860GIII) の Casio Python の仕様


高速素因数分解 - 10桁対応版:FactorG2.py のダウンロード

fx-CG50 Pythonモード:高速素因数分解 - FactorG2.py
"""Sample script

Exercise;
ported from Casio Basic
"Prime Factor 10 digits"
factorG.py
ver 2.0

by Krtyski/e-Gadget
"""

from u import *

def ckpwr():
 global a,b,c,d,e,z
 e+=1
 z[e]=b
 while 1:
  a=int(d)
  z[e+11]+=1
  d=a/b
  if frac(d):
   break
 c=int(sqrt(a))

def
disp():
 global a,e,f,z
 clear_screen()
 locate(00f3'm'0)
 locate(160': ' str(len(inp)) + ' digits'3'm'0)
 line(0,15,383,15,1,0)
 for i in range(112):
  if i<=e:
   locate(,,z[i], 1'm'0)
   locate(10i'^('2'm'0)
   locate(12iz[i+21], 1'm'0)
   locate(15i')'2'm'0)
 locate
(00''0'm'1)


while
1:
 try:
  inp=str(eval(input('Number:')))
 except (SyntaxError,TypeError,NameError) as e:
  print(e)
  print('*must be number or\n expression')
  continue
 if '.' in inp:
  print('*must be integer')
  continue
 elif inp.isdigit():
  if len(inp)>10:
   print('*must be 10 or less')
   continue
  else:
   f=int(inp)
   break
 else:
  continue

z=list(range(23))
for e in range(1,23):
 z[e]=0
e=0
a=f
c=int(sqrt(a))

prime_list=[2,3,5,7,11]
for b in prime_list:
 d=a/b
 if frac(d)==0ck_pwr()
 if b>c: break


increment=\
[2,4,2,4,6,2,6,4,
 2,4,6,6,2,6,4,2,
 6,4,6,8,4,2,4,2,
 4,8,6,4,6,2,4,6,
 2,6,6,4,2,4,6,2,
 6,4,2,4,2,10,2,10]

while 1:
 for i in increment:
  b+=id=a/b
  if frac(d)==0ck_pwr()
  if b>cbreak
 if b>c
break

if a>1:
 e+=1
 z[e]=a
 a=1
 z[e+11]=1

disp
()




FactorG2_output 

この入力値での実行時間は 0.8秒後半の 0.9 秒で、前回の FactorG1.py より僅かに速くなっています。




目 次

前の記事 - 8. シェル画面入力の工夫

次の記事 - 10. 大きな数の計算





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


 


keywords: fx-CG50Pythonプログラム関数電卓

リンク集 | ブログ内マップ
関連記事

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

コメントの投稿

非公開コメント

Re: 桁数が多くなると時間がかかる件

K様

処理速度は、1つでも桁数の大きな素因数があると、とたんに長くなってしまいます。

手元の15桁対応版に、素因数探索のための for と while でカウンタ変数 search をインクリメントして、最後に search の値を表示するようにしました。RTCを実装したいところですが...


> 私が作るとしたらbが今どの値まで大きくなっているかを1万刻みくらいで表示して
> 「まだ続けます?」的なUIにして逃げるところですw

確かに...
私は待ちくたびれたら [AC] で強制終了しちゃいます。


> 小さい順に割るのを試すアルゴリズムの限界のような気がします。

そうかもしれません。
現在のところ、素数 2, 3, 5, 7, 11 を探索数に使ったのち、2, 3, 5, 7 の倍数以外を探索数にしています。これを 2, 3, 5, 7, 11 以外の倍数を探索数に拡張しようと準備したところ、b の増分リストincrementの要素を 965個 にしないと取りこぼしが出てきてしまうことが分かりました。

この要素を計算で出せなくはないですが、それなりの時間が必要です。この計算時間を許容すれば、教えて頂いたジェネレータを活用できると思いますが、高速化アルゴリズムとしては本末転倒になりそうです。さすがに Casio Python で 965個の要素のリストはメモリ容量から無理ですし...

やはり、現行のアルゴリズムの限界かも知れません。


ところで、ckpwr() を削除して、その内容を while 内に書き下ろす方法で、どの程度高速化するか、これから調べてみようと思います。関数コールのオーバーヘッドを調べることを含めて、入力値15桁版の作成を、次回の記事にしてみようかと考えております。


桁数が多くなると時間がかかる件

200万番目の素数が32452843だそうなので、
15桁の素数ともなるとかなり効率的に素数を拾えていったとしても
2倍くらいしか速くならなさそうですね。
小さい順に割るのを試すアルゴリズムの限界のような気がします。
私が作るとしたらbが今どの値まで大きくなっているかを1万刻みくらいで表示して
「まだ続けます?」的なUIにして逃げるところですw

Re: No title

K様

貴重なアドバイス、大変ありがとうございます。

括弧内の改行について、バックスラッシュを付けないのが一般的とのこと。そのように変更しました。

disp() を何度も呼び出している点、おっしゃるように無駄でしかなく、実行時間を長くするだけです。
ご指摘を頂いて、改めて考えると、disp() はスクリプトの最後に1度だけ実行すれば問題ないですね。

なので、素数で探索する部分は、disp() を break に置き換えました。

ジェネレータについて、よく知りませんでした。ただ今勉強しています。
動作確認までして下さり、ありがとうございます。

おっしゃるように、ジェネレータで b の値を与えてやれば、素数で探索する部分とそれ以外で探索する部分は、すっきりと統合できます。

実は、ジェネレータを使わずに、これらを統合するのは検討しておりました。
increment[ ] の頭に、素数 2, 3, 5, 7, 11 を生成するような増分を追加することで、両者を統合しました。するとソースはスッキリとしました。

ところで、統合すると実行時間が長くなることから、敢えて分けています。

手元では、15桁の入力値を受け付けるように拡張していて、今の増分リストですと、桁数の増加に従って、非常に時間がかかるケースが出てきており、例えば15桁の素数を入力すると、whileループを 430万回程度回り、それに相当するかなりの時間がかかります。

15桁仕様に対して、増分リストを拡張すべきかどうか、ちょっと考えているところです。
最終的には、ジェネレ-タを使ったスッキリとしたソースと拡張した増分リスト increment[ ] の組み合わせて、スッキリかつ高速動作ができないかと、検討中です。

No title

カッコの中はわりと自由に改行できるので、
increment=[
 2,4,2,4,6,2,6,4,
 2,4,6,6,2,6,4,2,
 6,4,6,8,4,2,4,2,
 4,8,6,4,6,2,4,6,
 2,6,6,4,2,4,6,2,
 6,4,2,4,2,10,2,10,
 ]
のように書くのが一般的だと思います。

あと、小さい素数のところでdisp()が呼ばれまくっているのと
そのdisp()の中身の最初でまだ素因数の処理が続いている点、
breakやglobalが多い、といったところについて、
bの値を次々と生成するジェネレータを用意すれば、
次のような感じでスッキリすると思います。
# zのリストがちゃんと作られているところまでは確かめましたが、
# global宣言を全部なくしても大丈夫かどうかまでは未検証です^^;

def ckpwr():←これは関数ごと全部削除

def gen_b():
 for b in [2, 3, 5, 7, 11]:
  yield b
 increment = [
 (略)
 ]
 while True:
  for i in increment:
   b += i
   yield b

def disp():
 (↓この手前まで削除)
 clear_screen()

(中略)

a=f
c=int(sqrt(a))←ここまで変更なし
b=0
g=gen_b()

while b <= c:
 b = next(g)
 d = a / b
 if frac(d) == 0:
  e += 1
  z[e] = b
  while frac(d) == 0:
   a = int(d)
   z[e + 11] += 1
   d = a / b
  c = int(sqrt(a))
if a > 1:
 e += 1
 z[e] = a
 z[e + 11] = 1

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

やす (Krtyski)

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


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

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

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


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

リンク
月別アーカイブ
Sitemap

全ての記事を表示する

ブロとも申請フォーム

この人とブロともになる

QRコード
QR