A very long time ago Byte published this sieve program in a number of language to be used as a benchmark to compare computers as well as languages. sieve.frt contains the classical byte benchmark in the language Forth.
A straightforward implementation of the sieve can only handle as much
numbers as will fit in the memory of the computer. The program presented
here, super sieve 3.2, has not that limitation,
besides it is very economical with memory space to start with. It packs
all the 16-bit primes in slightly over 2 Kbyte. This sieve program uses
batches, and it is, as far as I know, unique in this respect. That means
that it reuses a sieve after having investigated it for primes. A warning
is in order. Based on the batches an option was added to start at an arbitrary
point, say for a table of one million numbers starting at one hundred million,
you could type:
ssieve 100000000 101000000
But this option doesn't work properly, so don't use it.
Be warned that limits are rounded to a multiple of thousand. The archive contains the Forth source and an MSDOS executable.
The executable program manages to sieve up till 2,000,000,000 although it uses 16 bit numbers. Ironically, it requires a 386 or higher. Normally running a Forth program requires a Forth interpreter, however this program was turned into a stand alone program using the "turn key facility" of CHForth 1.2.5. This is a public domain Forth that supports the new ANSI standard for Forth. It is an effort of the Dutch Forth Chapter, in particular Coos Haak.
If run on the transputer Forth tForth (or most any 32 bit Forth), you can go much farther. Typically the program then sieves 210,000,000 numbers in one go and can handle numbers up to 18 digits. This figure is for a 7 Megabyte sieve, as I use on my Parsytec transputer board.
The program has the nicest output I have ever seen for an implementation of the sieve. By configuring the source you can adapt the output format to print your own prime number tables. You can wear out your laser printer this way. Take that literally!
For those who are interested in primes the place to start is Chris Caldwell at the University of Tennessee.
I plan to make available the z80 assembler version for the Osborne, as soon as I manage to read the single density disk drive it sits on.
My Pentium (90 MHz) is able to recalculate the previous world record's 2^859433-1 and 2^1257787-1 in a matter of days (say 50 hours and 75 hours). The record with number 2^1257787-1 (announced September 3th 1996, but established in April) was established by Slovinsky on a Cray that used 19 hours for the proof. The excellent program I use was written by George Woltman ( firstname.lastname@example.org ). It has discovered all the largest prime numbers since the Cray's days are over.
225,964,951-1.But currently (2006 sep) it is
2232,582,657-1. -1.a number with almost 10 million digits detected by Dr. Curtis Cooper and Dr. Steven Boone's CMSU team e.a. And ... this e.a. includes yours truly. You can contribute too. George Woltman web page contains a lot of information about the Lucas Lehmer test and Mersenne numbers and the program referred to in the preceeding paragraph for performing the Lucas Lehmer test under Windows 3.1, windows 95 or Windows NT. He is asking all Pentium owners to contribute computer time. He has organized the search around a database such that results can be double checked and no effort is wasted on numbers already tested. Join us and maybe you are going to be the next world record holder.
The Forth program to calculate PI(N) is called pipi.frt Again the program is accompanied by an executable version for MSDOS. A version implemented in in ISO-Forth with only the core set benchpin.frt can be used as a benchmark for recursive function calls. I am promoting this program in the Forth community as a benchmark for recursive calls to replace the Ackerman function that computes nothing useful.
A Pascal program to calculate PI(N) is supplied also. It contains a substantial effort to document the rather difficult algorithm.
My transputer page has a couple of number-theoretical parallel programs to show off the transputer's prowess (or lack there off). In particular I tried my hand in the multiple quadratic sieve for factoring, and the counting of twin primes.
Go to the home page of Albert van der Horst