Subjects:

- my algorithm for factoring
- sieving for primes
- the hunt for large primes
- counting primes
- counting twin primes

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 ( 74473.2626@compuserve.com ). It has discovered all the largest prime numbers since the Cray's days are over.

2^{13,466,917}-1.

2and^{24,036,503}-1.

2But currently (2006 sep) it is^{25,964,951}-1.

2a number with almost 10 million digits detected by Dr. Curtis Cooper and Dr. Steven Boone's CMSU team e.a. And ... this^{232,582,657-1. }-1.

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.

You can comment via email