NBASICで算出したプログラムのアルゴリズム変遷
NBASICで作成したプログラムのソースリストが発掘できました。
プリントアウトの日付を見てビックリしました。 1981年!
説明は20年も前なのでリストを見て怪しげな記憶をたどりながらなので。。。。
なお、オリジナルはプリントアウトしかありませんので転記ミスがあるかもしれません。
Ver 1.0 N=59 00:47:57
Ver 2.0 N=59 00:30:24
Ver 3.0 N=59 00:03:12
Ver 5.1 N=59 00:03:09 (宿敵、K君のNBASIC最終記録)
NBASICでは300桁までのぐるぐる数算出でアルゴリズムを改良し高速化を目指しました。
ぐるぐる数(カフェプロトマヤ参照)の候補Dは (10^(n−1)-1)/n であろう、と予想し、まず作成してみたのが Ver1.0 です。
10 REM Jyunkan suu Ver 1.0
100 DIM A(300),B(300),C(300)
110 GOSUB 1000 [画面初期設定と、計算スタート値N(桁数に相当)を入力]
120 GOSUB 2000 [(N−1)個、9が連続した値をNで割る。]
130 IF D<>0 THEN GOTO 190 [もし余りの値Dが0でなければ(割り切れない)チェック・印刷を省略]
150 GOSUB 5000 [計算結果が循環するかチェックする]
160 IF CHECK=0 THEN GOSUB 3000 [循環チェックOKなら算出した値を印刷する。]
190 N=N+1 [Nの値を+1した次の桁数の数値を計算させる]
200 N=<300 THEN GOTO 120 [最大300(299)桁まで計算させる。]
999 END
1000 REM
1010 CONSOLE 0,25,1,1 :COLOR 0,0,0 :WIDTH 80,25 :PRINT CHR$(12) 画面の初期設定をして、
1020 INPUT"START N=";N 計算スタートする初期数値Nを入力
1099 RETURN
2000 REM
2010 D=0 :LOCATE 0,0,1 :PRINT N;:PRINT TIME$
2020 FOR J=1 TO N-1 (N−1)個9が連続した値をNで割る。
2030 A(J)=INT((10*D+9)/N)
2040 D=(10*D+9)-(A(J)*N) D=余りの値
2050 NEXT J
2060 RETURN
3000 REM
3010 LPRINT "at N=";N;" ";:LPRINT TIME$
3020 FOR I=1 TO N-1
3030 IF (I-1)/5-INT((I-1)/5)=0 THEN LPRINT " ";
3040 IF (I-1)/50-INT((I-1)/50)=0 AND I<>1 THEN LPRINT
3050 LPRINT USING"#";A(I);
3060 NEXT I
3070 LPRINT :LPRINT
3080 RETURN
5000 REM ☆☆循環チェック☆☆
5010 TIME$="00:00:00" :CHECK=0 :M=2
時間はこのチェックルーチンに要する時間を計測しています。
M は、2000番台のルーチンで算出したぐるぐる数の候補値に掛ける値で、
M=2から1づつカウントアップさせていきます。
5060 FOR I=N-1 TO 1 STEP -1 :B(I)=(A(I)*M+F) MOD 10 :F=(A(I)*M+F-B(I))/10 :NEXT I
A(1)からA(N-1)に収められた算出値(ぐるぐる数の候補)にMの値を掛け、
B(1)からB(N-1)に収めます。
5070 FOR I-1 TO N-1 C(I)=B(I) :NEXT I
B() の数値を一桁づつずらす準備として、B()の値をC()に一旦コピー。
5110 G=1
5120 FOR I=1 TO N-1 :B(I)=C(I-1) :NEXT I :B(1)=C(N-1)
B()の値を一桁ずつずらし、最下桁の値を最上桁に移します。
5122 FOR I=1 TO N-1 :C(I)=B(I) :NEXT I
B()の値をC()にコピー
5130 E=0
エラーチェックのフラグをリセット
5140 FOR I=1 TO N-1 :IF A(I)<>B(I) THEN E=1
5145 NEXT I
最上位の桁から最下位の桁まで順次調べ違った値がひとつでも有ればE=1とします。
5150 G=G+1
ずらした桁数をカウント
5160 IF E=0 THEN GOTO 5190
E=0,つまり全桁の数値を比較して同一であれぱ、カウントアップしたMの値で調べる。
5170 IF E=1 AND G<N THEN GOTO 5120
一致しない桁があれば、全体桁を更にひとつずらして調べる。
5180 IF E=1 AND G=>N THEN CHECK=1
全桁ずらして調べても不一致であれぱエラーフラグ CHECK=1 とする。
5190 M=M+1
次に掛ける数をカウントアップする。
5200 IF M=N THEN RETURN
5210 GOTO 5060
計算結果(途中省略)
at N=59 00:47:57
01694 91525 42372 88135 59322 03389 83050 84745 76271 18644
06779 661
頭で考えたまま整理もせずプログラムしたものなのでミスがあります。
また、無駄な処理もかなり有りました。
プログラムの中で最も時間の掛かる、算出した数値が循環する事をチェックする 5000 番台のブルーチンを手直ししました。
5000 REM ☆☆循環チェック☆☆
5010 TIME$="00:00:00" :CHECK=0 :M=2
5060 FOR I=N-1 TO 1 STEP -1 :B(I)=(A(I)*M+F) MOD 10 :F=(A(I)*M+F-B(I))/10 :C(I)=B(I) :NEXT I
5070 FOR I-1 TO N-1 C(I)=B(I) :NEXT I
別のループで B()の値をC()にコピーしていたのを改めた。(ループ処理を減らした)
5110 G=1
5120 C0=C(N-1):FOR N-1 TO 1 STEP 1 :B(I)=C(I-1) :C(I)=B(I):NEXT I
:B(1)=C0 :C(1)=B(1)
5122 FOR I=1 TO N-1 :C(I)=B(I) :NEXT I
B() の数値を一桁づつずらしながらC() へも保存するように修正。(ループ処理を減らした)
5130 E=0
5140 FOR I=1 TO N-1 :IF A(I)<>B(I) THEN E=1 :I=N-1
A() と B() の値が不一致ならすぐループを抜けられるよう改良?
5145 NEXT I
5150 G=G+1
5160 IF E=0 THEN GOTO 5190
5170 IF E=1 AND G<N THEN GOTO 5120
5180 IF E=1 AND G=>N THEN CHECK=1 :RETURN
N回、桁ずらししても不一致なら、次の値(M)を掛けて調べる必要は無いので、
エラーフラグをセット(CHECK=1)してルーチンを抜けるよう修正。
5190 M=M+1
5200 IF M=N THEN RETURN
5210 GOTO 5060
計算結果(途中省略)
at N=59 00:30:24
01694 91525 42372 88135 59322 03389 83050 84745 76271 18644
06779 661
00:47:57 から 00:30:24、約63%に短縮。
算出した数値が循環する事をチェックするサブルーチンを更に改良しました。
(算出ルーチンでnの値を奇数にする、素数にするなどすれば更に高速化できますが、5000番台のサブルーチンでの所要時間と比べ微々たるものなのでプログラムミスの修正の他は手を着けていません。)
60 DEFINT A-Z
70 DIM A(300),B(600),C(300)
60 少しでも高速化できるよう、使用する変数を整数とします。
70 ぐるぐる数候補A() にMを掛けた値、B()を、A() の倍確保します。C() は使用しません。
5000 REM ☆☆循環チェック☆☆
5010 TIME$="00:00:00" :CHECK=0 :M=2 :L=N-1
チェックルーチンをより高速化するため大改造です。
都度 N-1 の計算をしなくて済むよう、L としてループの前でセットします。
5020 F=0 :FOR I=L TO 1 STEP -1 :C=A(I)*M+F:B(I)=C MOD 10 :F=C\10 :B(L+I)=B(I) :NEXT
ぐるぐる数候補値に数値Mを掛ける計算は整数演算式に改めました。
F は各桁ごとの掛け算する時に桁上がりする値ですが、計算前に F=0 とします。
(Ver1.0、Ver2.0 で見逃していたミスの修正。)
更に、B(L+I) にもB(I) と同じ値をセットします。
(N=7 の場合、A()は、[1][4][2][8][5][7] と保存され、
M=4 を掛けるとB()は、[5][7][1][4][2][8][5][7][1][4][2][8]となります。
5030 G=1 :H=0
G ぐるぐる数候補の各桁
H ぐるぐる数候補A() に、M を掛けた数値列 B() の各桁
5040 IF A(G)=B(G+H) THEN 5050 ELSE G=1:H=H+1:IF H>=L THEN CHECK=1 :RETURN
もし A(G)と B(G+H) が等しければ次の桁を調べるよう 5050 で G を+1 します。
しかし不一致なら G を最上位桁の1、H を +1 し、5050 で全桁チェックを行い、この判定ループに戻ります。
ただし、H の値が、全桁数を越えても不一致ならエラーフラグ(CHECK)を1として戻ります。
5050 IF G<L THEN G=G+1:GOTO 5040
5040 のチェックで A(G)=B(G+H) であり、調べる桁GがまだLより短ければGを+1して5050に戻り、
次の桁をチェックします。
5060 IF M<L THEN M=M+1:GOTO 5020
5050 で全桁チェック良であり、掛ける数が桁数Lより小さければ、Mを+1して5020に戻り、
M<Lの範囲で数値Mを掛けてもぐるぐる数として成立するかチェックします。
5070 RETURN
計算結果(途中省略)
at N=59 00:03:12
01694 91525 42372 88135 59322 03389 83050 84745 76271 18644
06779 661
Ver1.0 の 00:47:57 から 00:03:12 へ、約7%以下に短縮!
00:30:12 を記録して喜んだのもつかの間、宿敵K君は既に 00:03:09 を記録していました!
90 DEFINT A-Z
100 DIM A(300),B(300)
5000 '
5010 TIME$="00:00:00"
5020 CHECK=0
5030 M=2
5060 F=0:FORI=N-1TO1STEP-1:J=A(I)*M+F:B(I)=JMOD10:(B(N-1+I)B(I):F=J/10:NEXT
5110 G=1
5120 L=N-G
5130 I=1
5140 IFA(I)<>B(L)THEN5170
5145 L=L+1:I=I+1:IFI<NTHEN5140
5150 G=G+1:GOTO5190
5170 G=G+1:IFG<NTHEN5120
5180 CHECK=1:RETURN
5190 M=M+1
5200 IFM=NTHENRETURN
5210 GOTO5060
計算結果(途中省略)
at N=59 00:03:09
01694 91525 42372 88135 59322 03389 83050 84745 76271 18644
06779 661