背景
こんなツイートを見つけました。
エラトステネスの篩で、32768未満の素数をリストアップする処理をさせたところ、LPC1114版では968秒ほどかかったのが、RISC-V版では202秒と、約4.8倍高速になってた。> IchigoDake
— 荒木 宏之 (@h_araki) January 6, 2022
エラトステネスの篩で32768未満の素数をリストアップする処理をさせたそうです。
32768個のフラグを管理するには、1個のフラグを1ビットで管理すると4096バイト使うことになります。
(1バイト＝8ビットとします)
IchigoDakeで使われているLPC1114FDH28は、
SRAM全体のサイズが4kB (4096バイト) しかなく、
エラトステネスの篩で普通に32768までの素数をリストアップするのは困難であると考えられます。
(フラグを外部のメモリやFlashに置いたり、マシン語のプログラムをFlashに置いて実行したり、
という方法が考えられ、不可能ではないでしょう)
具体的な実装は書かれていないようで、気になったので実装してみることにしました。
方針
32768未満の非負整数を表すビットを全部SRAMに載せようとするとメモリが足りなくなってしまうので、
メモリに収まる大きさのブロックに分割して処理します。
また、$n^2$以下の素数を求めるには、$n$以下の素数の倍数を落とす処理をすればよいことが知られています。
したがって、${181}^2=32761$、${182}^2=33124$なので、
32768未満の素数を求めるには182以下の素数を落とす処理をすればよいことがわかります。
今回は、キャラクターパターン領域を用い、1個のフラグを1 バイト で処理することにしました。
ブロックのサイズは256要素となります。
ビット単位ではなくバイト単位で処理することで、ビット演算をする手間を省けます。
2以外の偶数は素数ではないので、182以下の素数は高々92個であり、102要素ある配列に収まります。
そこで、ます最初のブロックは普通にエラトステネスの篩を行い、182以下の素数を配列に格納します。
次以降のブロックは、この配列に格納した素数を用いて処理します。
実装
10 ' ｴﾗﾄｽﾃﾈｽ ﾉ ﾌﾙｲ
20 POKE#700,0,0:FOR I=#702 TO #7FF:POKE I,1:NEXT
30 N=-1:FOR I=2 TO #FF
40 IF !PEEK(#700+I) GOTO 80
50 ?I;" ";
60 IF I<=182 N=N+1:[N]=I
70 IF I<16 FOR J=#700+I*I TO #7FF STEP I:POKE J,0:NEXT
80 NEXT
90 FOR K=#100 TO #7F00 STEP #100
100 FOR I=#700 TO #7FF:POKE I,1:NEXT
110 FOR I=0 TO N:P=[I]
120 FOR J=(K+P-1)/P*P-K+#700 TO #7FF STEP P:POKE J,0:NEXT
130 NEXT
140 FOR I=#700 TO #7FF
150 IF PEEK(I) ?I-#700+K;" ";
160 NEXT
170 NEXT
180 ?CHR$(10);
実行結果
IchigoDakeは持っていないので、IchigoKamuy (IchigoJam BASIC 1.4.1、VER()=14114)
および IchigoJam R (IchigoJam BASIC 1.5b、VER()=15001) で実行してみました。
その結果、32768未満の素数のリストが正しく求まりました。
答え合わせのため、素数表から32768未満の素数の部分をコピーし、
以下のRecipeで各素数の間に空白1個が入る形式に変換し、さらにSHA-256を求めました。
Find / Replace, 3 more - CyberChef
このSHA-256 bde5648268d480c606d7560e85d8aa685924dec7c432361972e325607327a119 を
プログラムの出力(最後の空白を除く)のSHA-256と比較し、一致することを確認しました。
実行時間は以下のようになりました。
| 機種 | ビデオ出力あり | ビデオ出力なし |
|---|---|---|
| IchigoKamuy | 9分40秒 (580秒) | 6分20秒 (380秒) |
| IchigoJam R | 1分13秒 (73秒) | 1分4秒 (64秒) |
IchigoJam R は IchigoKamuy に比べ、ビデオ出力ありの時は約7.9倍、
ビデオ出力なしの時は約5.9倍速い、という結果になりました。
また、ビデオ出力なしの時、冒頭で紹介したツイートで示されている秒数と比べ、
IchigoKamuy ではLPC1114版の約2.5倍、
IchigoJam R ではRISC-V版の約3.2倍速い結果になりました。
おわりに
- IchigoJamはjig.jpの登録商標です。
- IchigoKamuyは株式会社syushuの登録商標です。