実数型BASICで記述した10000までの素数を計算するプログラムの例を「SIEVE-MSF.BAS」に示します。

使用しているアルゴリズムは、エラトステネスのふるいと呼ばれるもので、素数と判断された数の倍数になっている数値を素数の候補から消していき、残った候補を素数とするというものです。

10 REM SIEVE-MSF.BAS
50 U=UPTIME(0)
100 S=100
110 M=S*S
120 DIM P(M)
130 PRINT "INIT TABLE"
140 FOR I=2 TO M
150   P(I) = 1
160 NEXT I
165 PRINT "DONE: "; UPTIME(0)-U; "sec"
170 PRINT "SIEVE CALC"
180 FOR I=2 TO S
190   IF P(I) <> 1 THEN GOTO 240
200     PRINT I; ",";
210     FOR J=I TO M/I
220       P(I*J) = 0
230     NEXT J
240 NEXT I
244 PRINT
245 E=UPTIME(0)-U
246 PRINT "DONE: "; E; "sec"
250 PRINT
260 PRINT "PRIME NUMBERS"
270 FOR I=2 TO M
280   IF P(I) = 1 THEN PRINT I; ",";
290 NEXT I
295 PRINT
296 PRINT "SIEVE CALC TIME: "; E; "sec"
300 END

SIEVE-MSF.BAS

「SIEVE-MSF.BAS」のプログラムでは、プログラムの実行時間を計測するために、移植時に追加したUPTIME関数を使用しています。

残念ながら、MITS ALTAIR 680 BASICでは計時機能が使えないので、UPTIME関数の記述を削除する必要があります。

素数の計算後に算出された多数の素数の表示に時間がかかり、またその時間はシリアル通信のボーレートに依存して変わるので、プログラムの実行時間は、算出された素数の表示を行う処理の前の時点で取得して表示するようにしています。

プログラムを6502-COREで実行した例を「エラトステネスのふるい：2MHzでの実行結果」に示します。

計算結果の表示を除く計算時間は73秒でした。

エラトステネスのふるい：2MHzでの実行結果

C言語でのプログラムと実行結果を\ref{sec:c-sieve}節に示しているのでご参照ください。C言語での実行時間は8秒で、BASICでの実行に対して9倍ほど高速なものとなっています。

BASICでの実行は、そもそもインタプリタということで不利なうえに、エラトステネスのふるいは整数演算で行う処理であるにもかかわらず、OSI 8K BASICでは実数演算で行っているために２重で不利な条件となっていることが、処理速度の大きな違いの要因になっていると考えられます。