Sieve of Eratosthenes: Difference between revisions
Content deleted Content added
→Eulerian optimisation: finishing touches for integer code |
|||
Line 1,770:
====Eulerian optimisation====
While slower than the optimised Sieve of Eratosthenes before it, the Sieve of Sundaram above has a compatible compression scheme that's more convenient than the conventional one used beforehand. It is therefore applied below along with Euler's alternative optimisation in a reversed implementation that lacks backward-compatibility to ZX80 BASIC. This program is designed around features & limitations of the QL, yet can be rewritten more efficiently for 1K ZX80s, as they allow integer variables to be parameters of <code>FOR</code> statements (& as their 1K of static RAM is equivalent to L1 cache, even in <code>FAST</code> mode). That's left as an exercise for ZX80 enthusiasts, who for o%=14 should be able to generate all primes < 841, i.e. 3 orders of (base 2) magnitude above the limit for the program listed under Sinclair ZX81 BASIC. In QL SuperBASIC, o% may at most be 127--generating all primes < 65,025 (almost 2x the upper limit for indices & integer variables used to calculate them ~2x faster than for floating point as used in line 30
<lang qbasic>
10 INPUT "Enter highest value of diagonal index q%: ";o%
15 LET z%=o%*(2+o%*2) : h$=FILL$("
30 FOR p=m TO q STEP -1: h$(
42 GOTO 87
61 IF h$(p%)="1"
62 IF p%<q%
63 LET p%=p%-1 : GOTO 61
87 LET q%=q%+1 : IF h$(q%)="1"
90 LET p%=z% DIV (2*q%+1) : IF q%<=o%
100 LET z%=z%-1 : IF z%=0: PRINT N%(z%) : STOP
110 GOTO 100
127 DEF FN N%(i)=0^i+1+i*2
</lang>
| |||