This will be even more bizarre, although closer in spirit to the post in the Vintage {computers | microprocessors | microcontrollers } FB group on a Fortran program for counting primes.
Let's count primes less than 256 in Tandy/Radio Shack Extended Color Computer BASIC!
1 REM A PROGRAM TO COUNT PRIMES IN COLOR COMPUTER BASIC
2 REM JOEL MATTHEW REES, APRIL 2019, AMAGASAKI, JAPAN
3 REM COPYRIGHT 2019, JOEL MATTHEW REES
4 REM MAY BE FREELY USED FOR NON-COMMERCIAL PURPOSES.
10 MAX=25520 DIM PRIMES(MAX)
30 FINAL = MAX/2
40 PRIMES(0)=0
50 PRIMES(1)=0
60 FOR I=2 TO MAX: PRIMES(I)=1: NEXT
70 FOR I=2 TO FINAL
80 FOR J=I+I TO MAX STEP I
90 PRIMES(J)=0
100 NEXT J
110 NEXT I
115 COUNT=0
120 FOR I=0 TO MAX
130 PRINT I;" IS ";
140 IF PRIMES(I)=0 THEN PRINT "NOT "; ELSE COUNT=COUNT+1
150 PRINT "PRIME."
160 NEXT I
170 PRINT COUNT;" PRIMES LESS THAN "; MAX; "."
(This is essentially the same algorithm as in this post on a small sieve, which also points to some implementations of the same in Ada and Forth.)
(You can download this as a file on my OSDN Japan account, here. I was not successful in using imgtool to put it back in a DECB disk, however.)
And let's see how long it takes. (Counting seconds in my head.)
Constructing the sieve itself takes about ten seconds, printing the sieve (Not very meaningful when the list mostly ends up scrolling off the screen.) takes another nine.
54 primes less than 255. Yep. That other program says the same.
255 numbers in 10 seconds is about 25 numbers per second, average, although average here does not mean what it seems to mean.
Now this program is very easy to modify to count the first thousand or more primes up to something like 15,000 on a 32K Coco.
First, check your RAM:
PRINT MEM
If it says something over 22,000, there should be plenty of room. Let's try 8,192, a nice round number. Edit line 10:
EDIT 10
10 MAX=8192
RUN
Woops!
Byte arrays in BASIC aren't done that way. In fact, they aren't hardly done at all. We would have to go get BASIC09 to do byte arrays in a BASIC on the Color Computer, I think. (Or we could do it in BIF. Or assembler.)
(Would be faster. Maybe I need an excuse to fire up OS-9. Not Mac OS-9, Microware OS-9, which well predated the Macintosh itself. Tandy/Radio Shack missed serious opportunies on that. Tandy's stupid mistake of not letting the company's products compete with each other, as if there were only one prize to be won. Making money linear is the best way to lose. Put down the mike, I know, I know.)
Let's try again with only 1,024.
About 45 seconds to calculate the sieve, and another 35 to scroll the list off the screen.
Says 172 primes less than 1024. That checks with that other program, too.
Checking 1024 numbers in 45 seconds averages 1024/45 numbers per second, or about 23 per second, which seems nearly linear to the earlier time.
And it looks like we have some memory left. In fact, it looks like our array only costs about 4 bytes per integer, which means we should easily be able to get away with 4,096. And time may be linear.
But I'm going to use the clock instead of counting for more than 3 minutes.
Expect, if the time is no better than linear, something like 4096/23, or 178 seconds, about three minutes.
Executing it. Yep. About three minutes to calculate.
Why should the time be nearly linear? The print loop is just a single loop, not nested, no branching. That makes sense.
But the sieve itself is nested, scanning the array and blocking out non-primes once for each prime it sees. But, first, the scan is only from the prime's double, skipping by the prime, so the later loops become really quick. And the loop ignores scanning on the non-primes, because those have all been picked up by the first loops. So the scans really don't take nearly as much time as we might think.
The scans after initialization will be half the count of the initialization, then a third, then a fifth, then a seventh, ...
Printing takes a rather long time. But that's always true. Almost three minutes to print the count.
564 primes less than 4,096. Check that? Yep. That other program agrees.
If we could extrapolate to 100,000,000 (which we can't, at least not this way), we would expect the Color Computer to take (100000000/23)/(60*60*24) days, or about 50 days. But the Color Computer would need about 500 megabytes of RAM, quite possible on modern desktop computers with multiple gigabytes of RAM, but not on the Color Computer.
Maybe a sieve array that big could be simulated on hard disk, but that would incur more time costs.
Left over memory with just 4,096 entries -- 1,850. If we want to do more on a Coco, we need a more sophisticated method.
Also, since the list scrolls off the screen, it would make sense to, instead of printing the list, write a loop that would allow the user to type in a beginning and ending number and list primes between the two numbers.
Those are left as exercises for the reader, for now. (There is a way to check whether a number is prime after this program ends. Do you know how?)
No comments:
Post a Comment