IchigoJamでウラムの螺旋を描く

IchigoJamでウラムの螺旋を描いてみた。
ウラムの螺旋とは、螺旋状に整数を並べ、そのうち素数に印をつけたものである。

予備実験：螺旋を描く

まずは、ウラムの螺旋に用いる螺旋を描いてみる。
これは以下のプログラムでできる。

10 ' ｳﾗﾑ ﾉ ﾗｾﾝ ﾖﾋﾞｼﾞｯｹﾝ
20 CLS:C=0:X=16:Y=12:Z=1:W=0:D=1:N=D
30 IF X<0 OR 31<X OR Y<0 OR 23<Y GOTO90
40 LOCATEX,Y:?C%10;:X=X+Z:Y=Y+W:C=C+1:N=N-1
50 IF N GOTO30
60 T=Z:Z=W:W=-T
70 IF Z D=D+1
80 N=D:GOTO30
90 LOCATE0,0

このプログラムを実行すると、以下のような螺旋が描かれる。(赤い線を加筆した)

これは以下のような手順で描くことができる。

1. 中心位置に移動する
2. 右に1マス動く
3. 上に1マス動く
4. 左に2マス動く
5. 下に2マス動く
6. 右に3マス動く
7. 上に3マス動く
8. …

すなわち、以下のアルゴリズムで描くことができる。

1. 現在位置を中心点に、動く距離を1に、動く方向を右に初期化する
2. 「動く方向」に「動く距離」マス動く
3. 動く方向を90度左に回転する
4. 動く方向が左または右ならば、動く距離を1増やす
5. 2に戻る

予備実験：素数判定

今回扱う描画領域の大きさを考えると、10,000までの数について素数判定ができればよい。
今回は素数の数を数えるプログラムにおいて、以下の方法を試してみた。

• 単純に対象の数の平方根以下の奇数で試し割りをする
• 最初にエラトステネスの篩で100以下の素数を求め、それらの素数で割る

単純な試し割り

まず、2以下の数について判定を行う。(2は素数、それ以外は素数ではない)
次に、(2を超える)偶数について判定を行う。(素数ではない)
その後、試し割りを行う。

10 ' ｿｽｳ ｶｳﾝﾄ (ｼﾝﾌﾟﾙ)
20 CLT:C=0
30 FOR I=0 TO 5000
40 IF I<3 C=C+(I=2):GOTO90
50 IF I%2=0 GOTO90
60 J=3
70 IF J*J>I C=C+1:GOTO90
80 IF I%J<>0 J=J+2:GOTO70
90 IF I%10=0 ?I,TICK()
100 NEXT
110 ?C

エラトステネスの篩

CLV 命令により配列の全要素を0で初期化し、3以上の奇数の要素について、素数を0、合成数を1で表す。
(奇数に奇数を足すと偶数なので、奇数の要素だけ扱うなら50行目のSTEPは2*Iでよかったな)
エラトステネスの篩により100以下の奇数の素数を求めておいた後、
「単純な試し割り」と同様に2以下の数と偶数の判定を行い、求めた奇数の素数で割っていく。
割り算の回数を節約できるが、エラトステネスの篩や配列参照のコストは加わる。

10 ' ｿｽｳ ｶｳﾝﾄ (ｴﾗﾄｽﾃﾈｽ)
20 CLT:C=0
30 CLV:FOR I=3 TO 7 STEP 2
40 IF [I] GOTO80
50 FOR J=I*I TO 100 STEP I
60 [J]=1
70 NEXT
80 NEXT
90 D=0:FOR I=3 TO 100 STEP 2
100 IF [I]=0 [D]=I:D=D+1
110 NEXT
120 FOR I=0 TO 5000
130 IF I<3 C=C+(I=2):GOTO180
140 IF I%2=0 GOTO180
150 J=0
160 IF [J]*[J]>I C=C+1:GOTO180
170 IF I%[J]<>0 J=J+1:GOTO160
180 IF I%10=0 ?I,TICK()
190 NEXT
200 ?C

比較

上記のプログラムは、10個の数を判定するごとに所要時間(TICK単位)を出力するようになっている。
以下、いずれも画面出力オフ (VIDEO0) の状態で1回測定を行った。

IchigoKamuy (1.4.1) で実行した結果は、以下のようになった。

また、GIGA IchigoDake (1.5.0D) で実行した結果は、以下のようになった。

いずれの結果においても、最初は単純な試し割りの方が早く結果が求まったが、1700付近で逆転し、その後は差が広がっていった。
素数判定の回数が多くなるほど、除算回数の節約のメリットがエラトステネスの篩の初期化のコストを上回っていくことがうかがえる。

ウラムの螺旋を描く

「螺旋を描く」プログラムと「素数判定」のプログラムを合体し、「ウラムの螺旋を描く」プログラムを作成した。
「素数判定」はエラトステネスの篩バージョンを用いた。
なお、3,5,7は全て素数であるので、篩により候補を消す前の素数判定は省略した。

1文字を1マスとして扱う

10 ' ｳﾗﾑ ﾉ ﾗｾﾝ
20 CLV:FOR I=3 TO 7 STEP 2
30 FOR J=I*I TO 100 STEP I
40 [J]=1
50 NEXT
60 NEXT
70 D=0:FOR I=3 TO 100 STEP 2
80 IF [I]=0 [D]=I:D=D+1
90 NEXT
100 CLS:I=1:X=16:Y=12:Z=1:W=0:D=1:N=D
110 IF X<0 OR 31<X OR Y<0 OR 23<Y GOTO230
120 IF I<3 GOTO 180-(I=2)*10
130 IF I%2=0 GOTO180
140 J=0
150 IF [J]*[J]>I GOTO170
160 IF I%[J]<>0 J=J+1:GOTO150 ELSE GOTO180
170 LOCATEX,Y:?CHR$(1);
180 I=I+1:X=X+Z:Y=Y+W:N=N-1
190 IF N GOTO110
200 T=Z:Z=W:W=-T
210 IF Z D=D+1
220 N=D:GOTO110
230 LOCATE0,0

以下の結果が得られた。

実行時間は以下のようになった。

実行環境	バージョン	実行時間
IchigoJam web	1.4.3	約3分6秒
IchigoJam U	1.0.0	約33秒
IchigoKamuy	1.4.1	約11秒
GIGA IchigoDake	1.5.0D	約2秒

1文字を2×2マスとして扱う

10 ' ｳﾗﾑ ﾉ ﾗｾﾝ 2
20 CLV:FOR I=3 TO 7 STEP 2
30 FOR J=I*I TO 100 STEP I
40 [J]=1
50 NEXT
60 NEXT
70 D=0:FOR I=3 TO 100 STEP 2
80 IF [I]=0 [D]=I:D=D+1
90 NEXT
100 CLS:I=1:X=32:Y=24:Z=1:W=0:D=1:N=D
110 IF X<0 OR 63<X OR Y<0 OR 47<Y GOTO260
120 IF I<3 GOTO 180-(I=2)*10
130 IF I%2=0 GOTO180
140 J=0
150 IF [J]*[J]>I GOTO170
160 IF I%[J]<>0 J=J+1:GOTO150 ELSE GOTO180
170 IF VER()<13209 GOTO230 ELSE DRAWX,Y
180 I=I+1:X=X+Z:Y=Y+W:N=N-1
190 IF N GOTO110
200 T=Z:Z=W:W=-T
210 IF Z D=D+1
220 N=D:GOTO110
230 A=#900+Y/2*32+X/2
240 POKE A,PEEK(A)|#80|(1<<(Y%2*2+X%2))
250 GOTO180
260 LOCATE0,0

以下の結果が得られた。

実行時間は以下のようになった。

実行環境	バージョン	実行時間
IchigoJam web	1.4.3	約12分34秒
IchigoJam U	1.0.0	約2分34秒
IchigoKamuy	1.4.1	約52秒
GIGA IchigoDake	1.5.0D	約7秒

おわりに

• IchigoJamはjig.jpの登録商標です。
• IchigoKamuyは株式会社syushuの登録商標です。