Super Sieve
Super
Sieve is a brief
but lightning-fast
Sieve of Eratosthenes
prime number finder. It tests
numbers to see if they are prime
and also finds "nth" prime numbers.
This BASIC program works on all
8-bit Atari computers of
any memory size,
with disk or
cassette.
Prime numbers, those unbreakable integers that seem to pop up randomly, have interested mankind for thousands of years. The Greeks first studied them around 200 B.C. Since that time, primes have come to be important in communications and security coding. So they still have practical value as well as historic and aesthetic interest.
The ancient Greek mathematician Eratosthenes-who was also first to calculate the earth's correct circumference-proposed a mechanical sieve to filter prime numbers by sorting out all multiples of those numbers that were not themselves multiples of other numbers. Thus he kept 2 but threw out 4, 6, 8, etc. His sieve then kept 3 and rejected 6, 9, 12, etc.
This "Sieve of Eratosthenes" was an excellent idea but, as so often happens, the visionary inventor found it impossible to build the device with technology available during his lifetime. Today any computer can do the job and a "sieve test" has become the standard benchmark for rating comparative computer speeds. Your Atari 8-bit computer can find any of nearly a 1.5 million prime numbers in a few minutes, usually in just seconds.
SEARCH FOR SPEED
In the past, prime number research on microcomputers has suffered from
one or two serious problems. Either the programs used were pretty pokey
or they were severly limited by the memory size of the hardware. My SuperSieve
program doesn't suffer on either count. It can find any prime number between
1 and 16,777,216 (that's 256 cubed) and put much more expensive machines
to shame with its speed. It does so by using a small sieve array (255 bytes)
over and over again and doing it with a USR machine language call from
BASIC.
I wrote an earlier all-BASIC program that found each prime number and listed it to the screen. On an Atari with the screen turned on, the first million numbers took eight hours to process. This version runs the same data in 41 seconds. Numbers going by that fast are impossible to read so we turned the screen off and got down the time to under 28 seconds. Super Sieve processes more than 35,700 numbers per second!
One communications use for prime numbers is closely related to computers, specifically the high resolution two-color screens that are common on home machines. The search for extra-terrestrial life requires that we send and receive messages to and from civilizations that we know nothing about. If we draw a two-color picture on a TV screen with dimensions of 317 X 191 pixels-nearly an Atari Graphics 8 size-we can repeatedly send the message picture with confidence that a civilization technically on par with ours could easily figure out that the 60,547-bit signal was, in fact, a 317 X 191 display
Coding and decoding methods now use products of primes as a key. The
message can't be decoded without the two correct primes and large prime
numbers are not easily found.
processes over
35,700 numbers
in a second.
USING THE PROGRAM
Type in Listing 1, SIEVE.BAS, check it with TYPO II and SAVE a copy
before you RUN it. Listing 2, SIEVE.M65, provides the MAC/65 source code
for assembly language programmers to study. It is not necessary to type
Listing 2 in order to use the program.
SuperSieve will offer you three choices; test a number to see if it's prime, find an "nth" prime number, or exit the program. Choice 1 brings quick rejects if you try to test an even number, or a multiple of five, or something larger than 16,777,213. Any other positive number will be tested.
If your test number isn't a prime, SuperSieve will tell you what the next larger prime number is. Select choice 2 if you want to find the 4th, 97th, 1,400,032nd, or some other prime. Running time depends on the size of your test number.
The attract mode comes on while the screen is off, so you will see various
colors during the run. If you delete line 150, SuperSieve will test even
numbers and multiples of five, telling you what is the nearest larger prime
number.
Denis DeVries is an Engineering Manager for the City of Seattle. He debuts in Antic with his first assembler routine.
Listing 1: SIEVE.BAS Download
Listing 2: SIEVE.M65 Download / View