Casio Python Casioグラフ関数電卓の Python を使ってみる
- 要素数の多いリスト：高速素因数分解(5)
初版：2020/08/03
大幅な追記修正：2020/08/06
Windowsアプリ修正：2020/08/13
追記修正：2020/11/14
▲ 前の記事 -
11. 関数のオーバーヘッド |
▼ 次の記事 -
13. 10進数除算の出力と精度12. 要素数の多いリスト：高速素因数分解(5) <fx-CG50 OS3.4以降>
前回、関数呼出を無くして、１５桁対応素因数分解を少し高速化しました。
※ 高速素因数分解 15桁対応、僅かに高速化版 - FactorF4.py のダウンロード以下のように素因数が15桁になるケースでは、実行時間が 23分30秒 もかかり、素因数探索のループを回る回数が 435万回程度になります (
search:4349444)。
ここでは以下のロジックで探索数を決めています。今回は、同じロジックで、探索数を拡張する方法を検討します。
▶ 要素数48個の探索数増分リストを用いる方法現在のロジックは、探索数の重複を効率よく減らせる点に特徴があり、
a) 素数
2, 3, 5, 7, 11 を探索数として除算を繰り返し、
b) 13～
222 の整数で
2, 3, 5, 7 のいずれかの倍数でない探索数で除算を繰り返し、
エラストテレスの篩いで素因数を調べる、という手法を採用しています。
12.1 増分リストを拡張する同じロジックで、探索数を拡張してみます。それにより探索の無駄をさらに減らして、高速化を試みます。
要素数48個の増分リストを以下のように拡張します。
▶ 探索数増分リストを拡張する方法A) 素数
2, 3, 5, 7, 11, 13 を探索数として除算を繰り返し、
B) 17～
2326 の整数で
2, 3, 5, 7, 11 のいずれかの倍数でない探索数で除算を繰り返し、
エラストテレスの篩いで素因数を調べる、
素因数探索で取りこぼしを防ぐために
17～
2326 までの整数のうち 2, 3, 5, 7, 11 のいずれかの倍数でない整数を用いると、その探索数は
480 個あります。つまり探索数増分リスト
increment[ ] の要素は 480 個になります。スクリプトとして書き出す際は、１行８要素として、リストの定義に60行必要になります。
探索数を 17～2326 の範囲で探し、それが480個になる詳しい説明は、
fx-5800P 素因数分解 - 高速化 を参照してください。
簡単にまとめると、
- 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個
この480個の増分リスト
increment[ ] の要素は、エクセルを使って半手動で求めることができますが、計算の正確さ、計算結果をスクリプトに転記する作業の正確さ(これが最大の目的)、そして時間の節約のために、アプリ
SearchNum11.exe を Visual Studio 2019 Community の C# で作りました。C# はマウスクリック操作でプロパティ設定を変更するだけでコードのほとんどを自動作成してくれ、具体的なコーディングは30行程度で済みました。
⇒ 要素数480の探索数増分リストの要素を出力するWindowsデスクトップアプリ
- SearchNum11 のダウンロードダウンロードファイルには、アプリの実行ファイル (
SearchNum11.exe) だけでなくソースコードも同梱していますので、ご自由にお使いください。どのように計算しているのかに興味があれば、上からダウンロードしたzipファイルに含まれる
SearchNum11.cs を右クリックして ”編集" を選んぶとソースコードがメモ帳で開きます(Windows10)。肝心の計算は
private void CalcNum() にあります (480個、60行程度の出力なので簡易的なコードにしています。より出力が多くなる場合は、プログラムがCPUを占有しないようにチョット工夫が必要です。)
SearchNum11.exe を起動したところ：
右上の
[Calculate] ボタンを押すと、各要素とコンマ
, がテキストボックスに出力されます。
出力されると
[Calculate] ボタンを押せなくしています。
1行あたり 8要素で改行するように出力しています。
テキストボックスでは、改行したり編集ができます。そこで、これをPC上でカットアンドペーストにより、エディタで開いた スクリプトに貼り付ければ、増分リストの要素を簡単に書き込めます。
例えば、上のテキストボックスの中でクリックしてから、
[Ctrl]+[A] で全部を選択してから、
[↑] キーを押して 最後の 12, のコンマの前まで (12 まで) 選択した状態で、
[Ctrl]+[C] でコピーしてから、
エディタで、
increment=/
[ ]の
[ ] の中にカーソルを移動して、
[Ctrl]+[V] とすればペーストできます。
12.2 要素数480個の探索数増分リスト先ずは、480個の探索数増分を要素数にするリスト
increment[ ] を採用して、どの程度の実行速度改善が見られるのか、調べて見ます。
prime_list=[2,3,5,7,11,13]
for b in prime_list:
search+=1
d=a/b
if frac(d)==0:
e+=1
z[e]=b
while 1:
a=int(d)
z[e+21]+=1
d=a/b
if frac(d):
break
c=int(sqrt(a))
if b>c:breakincrement=\
[4,2,4,6,2,6,4,2,
4,6,6,2,6,4,2,6,
4,6,8,4,2,4,2,4,
14,4,6,2,10,2,6,6,
4,2,4,6,2,10,2,4,
2,12,10,2,4,2,4,6,
2,6,4,6,6,6,2,6,
4,2,6,4,6,8,4,2,
4,6,8,6,10,2,4,6,
2,6,6,4,2,4,6,2,
6,4,2,6,10,2,10,2,
4,2,4,6,8,4,2,4,
12,2,6,4,2,6,4,6,
12,2,4,2,4,8,6,4,
6,2,4,6,2,6,10,2,
4,6,2,6,4,2,4,2,
10,2,10,2,4,6,6,2,
6,6,4,6,6,2,6,4,
2,6,4,6,8,4,2,6,
4,8,6,4,6,2,4,6,
8,6,4,2,10,2,6,4,
2,4,2,10,2,10,2,4,
2,4,8,6,4,2,4,6,
6,2,6,4,8,4,6,8,
4,2,4,2,4,8,6,4,
6,6,6,2,6,6,4,2,
4,6,2,6,4,2,4,2,
10,2,10,2,6,4,6,2,
6,4,2,4,6,6,8,4,
2,6,10,8,4,2,4,2,
4,8,10,6,2,4,8,6,
6,4,2,4,6,2,6,4,
6,2,10,2,10,2,4,2,
4,6,2,6,4,2,4,6,
6,2,6,6,6,4,6,8,
4,2,4,2,4,8,6,4,
8,4,6,2,6,6,4,2,
4,6,8,4,2,4,2,10,
2,10,2,4,2,4,6,2,
10,2,4,6,8,6,4,2,
6,4,6,8,4,6,2,4,
8,6,4,6,2,4,6,2,
6,6,4,6,6,2,6,6,
4,2,10,2,10,2,4,2,
4,6,2,6,4,2,10,6,
2,6,4,2,6,4,6,8,
4,2,4,2,12,6,4,6,
2,4,6,2,12,4,2,4,
8,6,4,2,4,2,10,2,
10,6,2,4,6,2,6,4,
2,4,6,6,2,6,4,2,
10,6,8,6,4,2,4,8,
6,4,6,2,4,6,2,6,
6,6,4,6,2,6,4,2,
4,2,10,12,2,4,2,10,
2,6,4,2,4,6,6,2,
10,2,6,4,14,4,2,4,
2,4,8,6,4,6,2,4,
6,2,6,6,4,2,4,6,
2,6,4,2,4,12,2,12]
while 1:
for i in increment:
search+=1
b+=i; d=a/b
if frac(d)==0:
e+=1
z[e]=b
while 1:
a=int(d)
z[e+21]+=1
d=a/b
if frac(d):
break
c=int(sqrt(a))
if b>c: break
if b>c: break
▶ 大きな要素数のリストここで気になるのは、480個の整数要素のリストが正しく扱えるのかどうか？という点なので、チョット確認してみます。
というのも、以下のスクリプトを実行すると MemoryError が発生します。
lst = list(range(480))
print(lst)
ところで、要素数を 480 から 123 に変更して、
lst = list(range(123))
print(lst)
を実行すると、MemoryError が発生しなくなります。
つまり、この MemoryError は、print() が使用するスタックメモリが不足して発生していることが分かり、これは Casio Python 特有の仕様だと思われます。
さて、以下のスクリプトを試します。
n=480; s=0
lst = list(range(n))
for i in range(n):
s+=lst[i]
print(len(lst))
print(s)
これは、
・リスト
lst = [0, 1, 2, ... , 477, 478, 479] を作り、
・各要素の和を計算して 変数
s に格納
・リスト
lst の要素数と 変数
s の値を表示
するスクリプトです。
実行結果は、
480
114960となり、正しい値だと分かります。正解は
(0+480)×480/2 で簡単に検算できます。
従って、要素数 480 個の整数リスト自体は問題無く使えそうです。
12.3 探索数を拡大した15桁対応高速素因数分解のスクリプト2, 3, 5, 7, 11 のいずれの倍数でもない数を探索数とし、探索数を
480 個に拡大したスクリプトは以下のようになります。
※ 高速素因数分解：15桁入力対応、探索数拡張版 - FactorG5.py のダウンロードfx-CG50 Pythonモード：高速素因数分解 - FactorG5.py"""Sample script
Exercise;
ported from Casio Basic
"Prime Factor 15 digits"
factorG.py
ver 5.0
by Krtyski/e-Gadget
"""from u import *
digit=15
search=0
def disp(): global a,e,f,z
clear_screen()
locate(0, 0, f, 3, 'm', 0)
locate(16, 0, ': ' + str(len(inp)) + ' digits', 3, 'm', 0)
locate(16, 11, 'search:'+str(search), 2, 'm', 0)
line(0,15,383,15,1,0)
for i in range(1, 15):
if i<=e:
dx=int(i/12)*16
dy=int(i/12)*11
locate(0+dx, i-dy, z[i], 1, 'm', 0)
locate(10+dx, i-dy, '^(', 2, 'm', 0)
locate(12+dx, i-dy, z[i+21], 1, 'm', 0)
locate(15+dx, i-dy, ')', 2, 'm', 0)
locate(0, 0, '', 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)>digit:
print('*must be '+str(digit)+' digit\n 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:
search+=1
d=a/b
if frac(d)==0:
e+=1
z[e]=b
while 1:
a=int(d)
z[e+21]+=1
d=a/b
if frac(d):
break
c=int(sqrt(a))
if b>c:break
increment=\
[4,2,4,6,2,6,4,2,
4,6,6,2,6,4,2,6,
4,6,8,4,2,4,2,4,
14,4,6,2,10,2,6,6,
4,2,4,6,2,10,2,4,
2,12,10,2,4,2,4,6,
2,6,4,6,6,6,2,6,
4,2,6,4,6,8,4,2,
4,6,8,6,10,2,4,6,
2,6,6,4,2,4,6,2,
6,4,2,6,10,2,10,2,
4,2,4,6,8,4,2,4,
12,2,6,4,2,6,4,6,
12,2,4,2,4,8,6,4,
6,2,4,6,2,6,10,2,
4,6,2,6,4,2,4,2,
10,2,10,2,4,6,6,2,
6,6,4,6,6,2,6,4,
2,6,4,6,8,4,2,6,
4,8,6,4,6,2,4,6,
8,6,4,2,10,2,6,4,
2,4,2,10,2,10,2,4,
2,4,8,6,4,2,4,6,
6,2,6,4,8,4,6,8,
4,2,4,2,4,8,6,4,
6,6,6,2,6,6,4,2,
4,6,2,6,4,2,4,2,
10,2,10,2,6,4,6,2,
6,4,2,4,6,6,8,4,
2,6,10,8,4,2,4,2,
4,8,10,6,2,4,8,6,
6,4,2,4,6,2,6,4,
6,2,10,2,10,2,4,2,
4,6,2,6,4,2,4,6,
6,2,6,6,6,4,6,8,
4,2,4,2,4,8,6,4,
8,4,6,2,6,6,4,2,
4,6,8,4,2,4,2,10,
2,10,2,4,2,4,6,2,
10,2,4,6,8,6,4,2,
6,4,6,8,4,6,2,4,
8,6,4,6,2,4,6,2,
6,6,4,6,6,2,6,6,
4,2,10,2,10,2,4,2,
4,6,2,6,4,2,10,6,
2,6,4,2,6,4,6,8,
4,2,4,2,12,6,4,6,
2,4,6,2,12,4,2,4,
8,6,4,2,4,2,10,2,
10,6,2,4,6,2,6,4,
2,4,6,6,2,6,4,2,
10,6,8,6,4,2,4,8,
6,4,6,2,4,6,2,6,
6,6,4,6,2,6,4,2,
4,2,10,12,2,4,2,10,
2,6,4,2,4,6,6,2,
10,2,6,4,14,4,2,4,
2,4,8,6,4,6,2,4,
6,2,6,6,4,2,4,6,
2,6,4,2,4,12,2,12]
while 1:
for i in increment:
search+=1
b+=i; d=a/b
if frac(d)==0:
e+=1
z[e]=b
while 1:
a=int(d)
z[e+21]+=1
d=a/b
if frac(d):
break
c=int(sqrt(a))
if b>c: break
if b>c: break
if a>1:
e+=1
z[e]=a
a=1
z[e+11]=1
disp()
12.4 探索数拡大による高速化前回作成した
Ver 4.0 と今回作成した
Ver 5.0 の実行速度を比較しました。
比較対象は、前回と同じく以下の10個のケースを用います。
表2- 探索数拡大による実行時間の違い - Ver 4.0 と Ver 5.0 の比較 | Ver 4.0 | Ver 5.0 |
| 入力値 | serach | 実行時間
[秒] | search | 実行時間
[秒] | 高速化
[秒] | search
減少率[%] |
| 547,896,321,054,789 | 30,445 | 9.6 | 27,679 | 8.7 | 0.9 | 9.1 |
| 7,845,162,037,849 | 39,969 | 12.5 | 36,337 | 11.4 | 1.1 | 9.1 |
| 748,159,026,374,815 | 47,824 | 15.0 | 43,478 | 13.7 | 1.3 | 9.1 |
| 36,209,518,473,620 | 55,241 | 17.1 | 50,221 | 15.5 | 1.6 | 9.1 |
| 986,753,421,098,675 | 90,872 | 28.6 | 82,612 | 26.0 | 2.6 | 9.1 |
| 96,835,724,130,261 | 189,426 | 58.1 | 172,207 | 52.7 | 5.4 | 9.1 |
| 748,159,026,396,835 | 263,027 | 80.5 | 239,116 | 73.1 | 7.4 | 9.1 |
| 96,835,724,136,209 | 343,013 | 104.5 | 311,832 | 95.3 | 9.2 | 9.1 |
| 748,159,026,336,209 | 2,025,804 | 644.0
(10分44秒) | 1,841,642 | 585.0
(9分45秒) | 59.0 | 9.1 |
| 362,095,184,736,209 | 4,349,444 | 1,361.0
(22分41秒) | 3,954,042 | 1,235.6
(20分35.6秒) | 125.4 | 9.1 |
search回数は、どの入力値でも一律に
9.1% 減少して、高速化していることが分かります。実行速度は 9～10%程度の高速化となりました。
12.5 増分リストをさらに拡張する ところで、さらに探索数を拡大して、2, 3, 5, 7, 11, 13 のいずれかの倍数でない探索数を得るための増分リストに拡張してみました。
▶ 要素数5760個の探索数増分リストを用いる方法A-2) 素数
2, 3, 5, 7, 11, 13, 17 を探索数として除算を繰り返し、
B-2) 19～
30048 の整数で
2, 3, 5, 7, 11, 13 のいずえかの倍数でない探索数で除算を繰り返し、
エラストテレスの篩いで素因数を調べる。
この場合は、取りこぼしを防ぐためには、
2, 3, 5, 7, 11, 13 のいずれかの倍数でない整数は
5750 個あります。この個数の求め方は、上と同様に計算して得られます。
Casio Python のスクリプトファイルは、以前の記事で 300行が上限だと確認しています。
リスト
increment[ ] の定義以外に103行使っているので、リスト定義を 196行以内に納める必要があります。
そこで、1行あたり30個の要素を並べることにすれば、要素の記述に192行必要となり、スクリプト全体で 295 行とぎりぎり収まります。
2, 3, 5, 7, 11, 13 のいずれかの倍数でない探索数の増分リストを出力するたツール
SearchNum13.exe も作りました。アルゴリズムは
SearchNum11.exe と同じで、要素数を増やしているだけです。
⇒ 要素数 5760 の探索数増分リストの要素を出力するWindowsデスクトップアプリ
- SearchNum13 のダウンロードこれを起動したところ；
右上の
[Calculate] ボタンをクリックすると、求める要素とコンマ
, が出力されます。
1行30要素で192行となるように出力されます。コピー＆ペーストでエディタで追加すると楽です、というか唯一の現実的な方法ですね！
さて、5760個の整数リストはかなりメモリを使うので、
Casio Python で使えるかどうかを調べます。
▶ 要素数 5760 個のリストn=5760; s=0
lst = list(range(n))
for i in range(n):
s+=lst[i]
print(len(lst))
print(s)
を実行すると、
5760
16585920
と出力され、0 + 1 + 2 + ・・・ + 5758 + 5769 = 16585920 と、正しい計算結果になります。正解は、(0+5760)×5760/2 で簡単に検算できます。これにより、整数の要素数 5760 個に拡張しても、整数リストは問題無く動作することは確認できました。
5760個の整数リストが使えることが分かったので、実際にコピー＆ペーストしてスクリプトを作りました。
※ 高速素因数分解：15桁入力対応、さらに探索数拡張版 - FactorG6.py のダウンロードこれを実行すると、以下のようなエラーが表示されます。
エラーメッセージ：
RuntimeError: pystack exhaustedCasio Python が動作する際に確保するスタックを使い果たした、という意味だと考えられます。
制御構造は、
FactorG5.py と同じなので、構造制御のために使うスタック数は同じです。すると、スタックを使い果たす原因は、長大なリストにある筈です。
スタックがどのように使われているのかは不明ですが、リスト
increment[ ] の定義で使っている改行がスタックを増やしているかも知れないと考え、1行の文字数を長くして行数を減らし、何通りか試してみました。
すると、実行すると
Invalid Data size エラーが発生して実行出来ないケースと
RuntimeError: pystack exhausted エラーが発生して実行できないケースの両方があることが分かりました。
Invalid Data size エラーが発生する時のスクリプトファイルサイズは、
pystack exhausted エラーの時のファイルサイズよりも大きくなっています。
Invalid Data size エラーが発生する条件が、必ずしもファイルサイズが大きいだけでもないことも分かりました。
今回は、アルゴリズムの要請から極端に大きな要素数のリストを使う事例となり、その結果エラーに阻まれて、探索数をさらに拡張できませんでした。
Casio Python では、スクリプトファイルサイズの制限が厳しいことも判りました。
何かお気づきの方は、コメント欄に情報をお寄せください。
keywords: fx-CG50、Python、fx-9750GIII、fx-9860GIII、プログラム関数電卓
- 関連記事
-
テーマ : プログラム関数電卓
ジャンル : コンピュータ
プログラムライブラリ - 高速素因数分解
2021/06/10
プログラムライブラリ - ３桁区切り出力 (汎用サブルーチン)
2021/06/10
プログラムライブラリ - 入力ボックス 2.1G
2020/11/28
プログラムライブラリ - RGB指定による色確認プログラム
2020/10/31
プログラムライブラリ - OS内蔵ファンクションメニュー探索
2020/01/13
