Forgot–constants are converted to internal representation, so the listing may not show exactly what you entered.
INT(M) is always going to be <= M, so you can ditch one of the IF statements.
A BASIC09 version on a CoCo 3 (1.79 MHz) that uses REALs and keeps the inefficient logic (but tosses all the non-gone to line numbers) runs in 148 seconds. (With all the line numbers, it’s five seconds slower.)
Here’s a listing of a better version that stops checking after SQRT(N) without actually using SQRT, and uses INTEGER type variables. Run time: between four and six seconds.
PROCEDURE saneBenchmark
0000 DIM k,m,n:INTEGER
000F
0010 PRINT "Starting at "; DATE$
0022 FOR n:=2 TO 1000
0033 k:=2
003A LOOP
003C m:=n/k
0048 EXITIF m<k THEN
0055 PRINT n; " ";
005F ENDEXIT
0063 EXITIF m*k=n THEN ENDEXIT
0077 k:=k+1
0082 ENDLOOP
0086 NEXT n
0091 PRINT
0093 PRINT CHR$(7); "Finished at "; DATE$
Interesting … does BASIC require floor on integer conversions, and prohibit round toward zero? I just checked Microsoft BASIC and BBC BASIC and they both provide floor semantics.
In BASIC09, INT() truncates toward zero. I’d always seen INT() implementing floor() in other BASICs I’ve used, but that’s not very many. For this program, it doesn’t matter, because all the values it uses are non-negative.
UPDATE: just looked at the original Dartmouth BASIC manual, http://www.bitsavers.org/pdf/dartmouth/BASIC_Oct64.pdf. In section 3.3, it describes INT() and the examples it gives shows that in Dartmouth bASIC, INT() truncated towards zero.
1 Like
I fondly remember the idiom INT(R+0.5) for rounding. I think, this is universal behavior, regardless of the dialect.
1 Like
ANSI BASIC has it like this, as well,
INT(X) The largest integer not greater than X; e.g.,
INT(1.3) = 1 and INT(-1.3) = -2.
https://archive.org/details/federalinformat6821nati_0/page/42/
Yeah, I remember INT() rounding toward negative infinity, and FIX() rounding toward zero, but FIX() wasn’t nearly as ubiquitous in my experience.
I’m honestly learning about FIX() for the first time, so “not nearly as ubiquitous” may have some truth to it… 
It bugged me, so I looked at it one more time, with a goal of writing a version that
- Had the same complexity as the Interface Age version.
- Got rid of pointless IF statements.
Looking at the original code…
- Line 180 gets you out when K >= N, but line 190 does the GOTO when K > N/2, and after that you can quit looking for factors, so you know N is prime there, too, and earlier.
- We’re dealing with non-negative numbers here, so whether INT() truncates towards -infinity or towards zero, we know L <= M, so you need only check for M=L.
That means that we can write a version that’s still O(n), but cuts the constant down by a factor of two. This BASIC09 version still uses REAL, since some might say using integer is cheating, and in passing we clean up the output a bit. It runs on an emulated 6309 using NitrOS-9 Level 2 (hence a clock rate of 1.79 MHz) in between 1:32 and 1:34.
PROCEDURE moreIAish
0000 DIM K,L,M,N:REAL
0013
0014 PRINT "Starting at "; DATE$
0026 FOR N:=1. TO 1000.
003E FOR K:=2. TO 500.
0056 M:=N/K
0062 L:=INT(M)
006B EXITIF L=1. THEN \ PRINT USIHNG "I4>",N; \ ENDEXIT
008C EXITIF M=L THEN ENDEXIT
009C NEXT K
00A7 NEXT N
00B2 PRINT
00B4 PRIHT CHR$(7); "Finished at "; DATE$
Been trying to avoid coding this up, but reasons made me do it…
This is of-course both a terrible and a good benchmark at the same time. For many, many reasons.
One bad reason in the comment - it doesn’t discover/find the first 1000 prime numbers, it prints all the prime numbers up to 1000. (Bah! -) )
Another sub-optimal issue with it is the jump out of the inner FOR/NEXT loop. Some Basics really will choke on this - eventually… It misses another trick too, but hey ho.
Anyway - I tried it on my Ruby816 board which has a W65C816 running at 16Mhz and ran it in 65C02 emulation mode with BBC Basic4, EhBASIC and CBM2 Basic. So still retro enough for it to have some sort of meaning…
46 seconds in BBC Basic4, 67 seconds in EhBASIC and 65 seconds in CMB2 Basic.
That’s running the code as-is with no changes, same line numbers and so on with very minor additions to use the on-board timing facilities rather than a stopwatch.
A literal line for line translation into floating point BCPL, complete with GOTOs takes 54 seconds and is the most ugly code I’ve written in BCPL.
Re-writing it to use integers might be considered cheating, but that’s what we did back then when I was tinkering with supercomputers to fudge benchmarks, etc. and it’s now a more respectable 6.3 seconds.
Reasons? I’m in the middle of doing some benchmarking of my little Ruby board to see how my BCPL fares against the BASICs of the time (tl;dr - Very nicely, but could be better) and I’ll make a post on that soon, but here is the translated and “optimised” BCPL code for any old code heads to look at…
// INTERFACE AGEs benchmark program to
// 'discover' the first 1000 Prime numbers
// Re-coded in BCPL by me. Gordon Henderson
GET "libhdr.h"
GET "sys.h"
LET primeFP () BE
{
LET n,k = ?,?
LET m,l = ?,?
n := 1.0
WHILE n #<= 1000.0 DO
{
k := 2.0
WHILE k #<= 500.0 DO
{
m := n #/ k
l := FLOAT (FIX m)
IF l #= 0.0 THEN GOTO line230
IF l #= 1.0 THEN GOTO line220
IF m #> l THEN GOTO line220
IF m #= l THEN GOTO line240
line220:
k := k #+ 1.0 // Next k
}
line230:
writef ("%4d", FIX n)
line240:
n := n #+ 1.0 // Next n
}
}
AND primeINT () BE
{
LET isPrime = ?
FOR n = 1 TO 1000 DO
{
isPrime := TRUE
FOR k = 2 TO n / 2 DO // Ought to be square root
{
UNLESS (n MOD k) = 0 THEN // Still potentially prime
LOOP
isPrime := FALSE
BREAK
}
IF isPrime THEN
writef ("%4d", n)
}
}
AND try (fn, name) BE
{
LET tStart, tEnd = ?,?
writef ("Testing: %s*n", name)
tStart := sys (Sys_cputime)
fn ()
tEnd := sys (Sys_cputime)
newline ()
writef ("Time: %6.3d seconds*n", tEnd - tStart)
}
AND start () = VALOF
{
LET n,k = ?,?
LET m,l = ?,?
try (primeFP, "Floating Point")
try (primeINT, "Integer")
RESULTIS 0
}
Cheers,
-Gordon
2 Likes
OK. This time I’m really done. Here’s a Google Doc describing my findings.Fun With Trial Division.
3 Likes