Playing with prime numbers on RISC OSBy Martin Hansen. Published: 6th Jan 2007, 19:18:28 | Permalink | Printable
Prime time televisionPrime numbers, as well as being an interesting maths classroom subject, play an important role in encryption and related technologies. As the world hunts for ever larger primes, drobe.co.uk's resident mathematics fan Martin Hansen turns to DrawScript and his ARM-powered RISC OS computer to find and present prime numbers.
Let us begin by being brutal: thinking about prime numbers is not what anyone I know, including myself, would typically want to do on Christmas day. It's not that I don't like maths because I do, but even I, a 'mathaholic', know that maths and Christmas day do not mix. Yet it was the mathematics of the prime numbers that I found myself thinking about on December 25 at 7.15pm when I tuned in to the first of the Christmas 2006 Royal Institution lectures, The Num8er My5teries, on UK's Channel 5.
I tuned in initially because, as a teacher of mathematics to teenagers, I was curious to see what Professor Marcus du Sautoy, pictured above, had to say about the primes to his audience, many of whom looked around eleven or twelve years old. I have often thought that children are taught surprisingly little about the prime numbers.
They learn that a prime is a whole number with precisely two factors. These two factors are 1 and the number itself. If anything else divides into the given number then that number is not prime. Pupils learn that the positive integers which are not prime are called composite numbers and that these numbers can be written as a product of primes in, essentially, a unique way. They may be told that this vitally important result has the rather grand title "The fundamental theorem of Arithmetic". The number 1 is considered to be neither prime nor composite.
A method of finding primes, called the sieve of Eratosthenes, will be investigated. Typically a school mini-project will ask a class to use the sieve to find the 25 primes less than 100. Personally, in the days of the BBC Micro, I enjoyed exhibiting to my classes a delightfully short hybrid 6502 machine code/BBC BASIC program that used this sieve to find primes at what was then regarded as high speed.
If I recall correctly, to begin with, writing the information to the screen was the slowest part of that endeavour, although the sieve method finds it increasingly time consuming to make headway as the number to be tested for primeality gets larger. From a modern viewpoint, the sieve becomes unusable relatively quickly and methods based upon probabilities that tend towards certainty (except for known exceptions) take over and are confidently used by many of those who chase ever-bigger primes.
Professor Sautoy covered these basics with some fancy apparatus to make the enterprise more obviously lively and exciting: he had some large rotating blocks showing that 105 can be decomposed into the product of primes 3 x 5 x 7.
He showed how the Eratosthenian sieve works by wheeling on a grid of balloons numbered from 1 to 50. First of all, multiples of 2 but excluding the prime 2 were popped. Then multiples of 3, excluding the prime 3, went bang. In turn the multiples of 5, excluding the prime 5, were detonated and, finally, the multiples of 7, excluding the prime 7. Alas, when the divisible by two balloon numbered 32 popped it also took out the balloon numbered with the prime 31, but it was, none the less, a memorable demonstration of the sieve method. He stopped at 7 because it's the square root of the first square number less than 50, the total number of balloons. Oh, and 1 was also accidentally popped at some point.
In what seemed like a diversion, the professor told the famous story concerning grains of rice on a chess board. The full tale involves an emperor, his daughter and a mathematician who uses his intellect to win the fair maiden's hand. Without the frills, briefly, one grain of rice is placed on the first square of the chess board and each successive square then has double the number of grains of rice of the previous square.
Thus the first square has one grain of rice upon it, the second two, the next four, the next eight, and so on. The numbers get very big, very quickly as can easily be verified with a pocket calculator, which is usually the point of the story.
To my surprise, Marcus slickly then took us from the traditional ending back into the world of prime numbers. The key step is to consider the total number of grains of rice on the chess board. Understandably, with such a young audience, some of the steps were skipped at this point but they are, I think, quite interesting and not too difficult to understand.
Here is the number pattern that the lecture glossed over. Click here to see the table in text form
There is a lot going on here. Firstly, each of these sums is in Geometric Progression, and applying the well known formula for summing such series tells us that by the Nth square the chess board will have upon it one less than 2 to the power of N-1 grains of rice. Such numbers, as the professor pointed out, are the famous Mersenne numbers.
Scene of the prime
As hinted at by the number pattern above, and easily proved, Mersenne numbers are composite when the sum is taken over a composite number of squares. So, for example, by the sixth square the board has upon it 63 grains of rice, 63 clearly being divisible by 3 and so not prime. Interest thus focuses upon what can happen when we sum over a prime number of squares.
Initially, mathematical folk lore has it, the resulting number was thought to always be prime. In 1536 it was realised that the 11 squares result is not prime as had been anticipated: a potential prime finding formula had just bitten the dust: the useful ones always do it would seem - although it has not been proven that this must be so. To recap and be absolutely clear, in the above pattern observe that 2047, the 11 squares result, is not flagged as being prime. This is because 2047 = 23 x 89.
The Mersenne numbers have properties that make them good integers to work with and manipulate if you are trying to find some seriously big prime numbers, not least because it is suspected, although not proved, that an infinite number of Mersenne primes exist. So it seems likely that there will always be a next biggest Mersenne prime number to find.
They say prime doesn't pay
Marcus du Sautoy himself had left his laptop testing massive numbers for "primeness" while he presented his television lecture. The first person to find a 10 million digit prime number - hugely valuable to defence and commercial security systems - will earn themselves £50,000 from the Electronic Frontier Foundation. The current record, as of September 4, 2006, is 1 less than 2 to the power 32,582,657. This number has 9,808,358 digits; just not quite enough digits to claim the 50 grand.
Now, I have no interest in finding a 10 million digit prime number, but the lecture got me thinking about a project I'd played around with in 2002. This had been to print out some neatly formatted pages of prime numbers.
I wanted these because (as a mathematician) I kept bumping into relatively small numbers of seven or so digits that I wanted to look up the primality of without the hassle of switching on a computer, never mind going onto the internet to a website such as prime-numbers.org with all its tedious pop-ups and other in-your-face advertising. I'd not finished my 2002 project but professor Marcus du Sautoy's lecture inspired me to look at it afresh.
The project's scripts and directory layout. Click for bigger
The project breaks down into two parts. Firstly, generate primes. Secondly, format and present them in a compact but readable fashion.
It's quick and easy to grab the first fifteen million primes from the Internet from Chris Caldwell's excellent website. That gets us as far as the nine digit prime 275,604,541. However, I wanted more of a hands on feel for what it was like to generate some of these "at home".
My 600MHz Iyonix is, after all, 300 times faster than that BBC micro I used in 1985. A program that spent a year generating primes in 1985 should take around a day or so to do likewise now.
This situation reminds me of an argument as to why you should always do nothing except wait for tomorrow's technology. The argument begins by remarking that it is pointless to set off today in a spaceship bound for a distant star. The reasoning is that if you set off today, then after a decade of space flight you'd be overtaken by a faster and more modern craft built using technology developed a couple of years after you left Earth. Therefore, you should always wait for tomorrow's technology. QED.
Just in the nick of prime
Putting such paradoxical thoughts aside, I hacked together a very crude BBC BASIC prime finding program and, without even bothering to make it stop at the square root of the first square less than the number to be tested, set it to find the first six hundred thousand primes. I thought I had abundant computing power for this relatively modest task but my breathtakingly inefficient program took 2 days, 7 hours and 25 minutes to find a thirtieth of what I had downloaded from the Internet, using broadband, in around half an hour.
I am told that primes can be generated faster than they can be downloaded, although I'm not sure I believe that. "Was my effort really that feeble?" I asked myself.
My largest prime was a little under 9,000,000. On the positive side, I could use my primes to check the early part of Chris Caldwell's Internet list, and vice versa. It is interesting to note that the Austrian arithmetician JP Kulik (1773-1863) spent 20 years of his life preparing a table to 100 million by hand, but this was never published, and the volume for numbers from 12,642,600 to 22,852,800 has been lost. I'd got enough primes for six hundred A4 pages each of a thousand primes which, as I was pursuing a whim rather than making it my life's work, seemed plenty.
Every second counts, all 200,000 of them when it came to producing these 600,000 prime numbers on an Iyonix. Click for bigger
As an aside, a small part of me remains curious about how fast JP Kulik's primes to 100 million could be found on a modern Iyonix running ARM machine code. I think it should be fairly straightforward to generate all of JP's primes as 100 million is less than the ten digit number 2,147,483,647, this being the BASIC integer limit of the Iyonix, and, incidentally, the Mersenne prime, M31. To get beyond that number would involve a lot more effort: numbers would have to be handled as strings and any arithmetical operations to manipulate these strings also converted into machine code.
The smart way to do this might be to use Nick Craig-Wood's ingenious Big Numbers module which allows infinite precision integer arithmetic to be carried out. Gavin Wraith maintains a 32 bit version of this, ideal for Iyonix users, but I recommend that you find it via Nick's website as there is a lot of mathematical material of interest on Nick Craig-Wood's site. This includes, just in case you do fancy that £50,000, an ARM based Mersenne prime tester for "The Great Internet Mersenne Prime Search", or GIMPS for brevity.
Nick's program is currently usable but in beta form with a long to-do list to bring its performance up to full speed. He'd welcome help if any reader likes the idea of chasing the big primes using RISC OS. There are some big money prizes for primes of even more than 10 million digits: the fifty grand cash award for this next prime milestone seeming likely to be claimed before 2007 is out. I suppose that what I am saying is that someone starting out now to find a money making prime should focus on the targets beyond the 10 million digit prime. In other words, get busy building the faster spaceship.
In order to format the modest list of six hundred thousand "home grown" primes that I now had sitting on my hard drive, I fired up Joe Taylor's truly splendid, outstanding and polished piece of free software DrawScript. Did I mention that I think this is a good program? Well, it is.
DrawScript provides an easy means of writing Draw vector graphics files from a BBC BASIC program. With careful adjustments I found that I could fit a thousand primes on each page such that the draw file could be printed out as it stood without needing to be scaled or otherwise manipulated by any other program.
I have put the resulting zip file of 600 Draw files on my website, but remember you'll need a computer running RISC OS to view the files. As the Draw files are individually tiny, any old machine from an Archimedes (1987) onwards will do, or you can buy RISC OS to run on top of Windows XP from Virtual Acorn. Remember that you can obtain larger lists elsewhere on the web, but my contribution here is to have formatted them beautifully for printing out.
The project's final output in drawfile format. Click for bigger
Having a printed list of primes is a good starting point for "messing around with numbers" but real power comes from having the entire list of data in a computer and investigating it using simple programs. For now, I'm content that I've polished off a project that I left unfinished five years ago but maybe, should the mood take me, or a reader have an interesting mathematical proposition, I'll take it further.
Martin's website with downloadable drawfiles of prime numbers generated on RISC OS
Previous: The best of the Microdigital Mico manual
Next: 32bit Insignia released for free
DiscussionViewing threaded comments | View comments unthreaded, listed by date | Skip to the end
Please login before posting a comment. Use the form on the right to do so or create a free account.
Search the archives
Today's featured article
The Intel XScale conundrum
Chin up, could be worse
20 comments, latest by steelpillow on 26/8/05 6:53PM. Published: 25 Aug 2005
Sort out those arrays: Avisoft provides a fast solution
Discuss this. Published: 14 Nov 2000
News and media:
RISCOS Ltd •
RISC OS Open •
MW Software •
Advantage Six •
CJE Micros •
Liquid Silicon •
Chris Why's Acorn/RISC OS collection •
The Register •
The Inquirer •
Apple Insider •
BBC News •
Sky News •
Google News •