Factoring and primes

The number theoretical section consists of unrelated sections and is hence split.
Subjects:

The horst algorithm

The Horst algorithm is a combination of base conversion (from base 10 to base 11 to base 12 etc.) and the observation that a number is divisable by 10 if the last digit is zero. There was an explanation of the algorithm in the hcc newsletter 1982, volume 4, April. Some lack of modesty is needed to name a combination of a well known algorithm and a trivial observation after yourself... Here are some implementations.

The sieve

Sieving for primes started with the greek Erathostenes. It is rather straightforward, I sort of reinvented it myself at elementary school. Improved automated versions are abundant. The principle is that you have all numbers written down. Then you erase every second number, because it is divisible by two, every third number because it is divisible by three, etc.

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.

The Lucas Lehmer test

The Lucas-Lehmer test is described in Knuth, the art of computer programming part volume 2 page 391. It can be used to prove that a number of the form 2^N-1 (a Mersenne number) is prime. These numbers are large and the proof is easy. So the world largest known prime number has almost always been a Mersenne number that was prime.

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.

The worlds largest prime discovered by you?

You may wonder what the current world records is. Well before 14th of December 2001 it was 2^6972593-1, discovered by Hajratwala e.a. In January 2002 Roland Clarkson e.a. found the next record: 2^3,021,377-1. Since then some more have been discovered; it becomes hard to keep track. Both have been established on personal computers. A few other large primes detected were
213,466,917-1.
224,036,503-1.
and
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.

Calculating Pi(N)

You need no sieve for calculating how many primes there are less or equal to a given number N. Traditionally this function is called Pi(N). I once had found a program for it, but I lost it. So I invented an algorithm that turned out to be simplification of a classical algorithm by Meissel (1871). See Paulo Ribenboim's "The Book of Prime Number Records" page 178. Yes, in his "New Book of Prime Number Records" it is on page 236.

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

Go to the home page of Albert van der Horst