The Nine Billion Names of God

Sometime in the mid-1970s, my grandmother gave me a book of Arthur C. Clarke's short stories. The first story in the book, The Nine Billion Names of God, was written in 1953. It's about a computer manufacturer who is commissioned by Tibetan monks to run a program to produce all the possible names of God. The monks have already been working on this task for three centuries. They've calculated it will take 15,000 years for them to write out all of the names by hand. The Automatic Sequence Computer (Mark V) in Clarke's story is reputably capable of managing the same task in just a hundred days.

The story provides the outline of an algorithm for generating the names, but before I describe it, the first question I want to answer is whether it's possible to generate nine billion lines of output in less than a hundred days. To save paper (the format required in the story) I wrote a small C program to write the numbers 1 to 9,000,000,000 to a terminal.

include <stdio.h>

int main()
{
  long i;
  for (i=1;i<=9000000000;i++) printf ("%ld\n",i);
  return 0;
}

On a quad-core Raspberry Pi 5, it takes a single core 3 hours and 41 minutes to complete the program.

I could, of course, chop the task up into four equal pieces and it should take less than an hour on the same machine.

The output part of task is easily feasible on a modern computer - and printer(s), if the monks really need to commit all the names of God to paper.

But what about 1953 machinery? To achieve this task in the required 100 days, the Automatic Sequence Computer will need to be capable of calculating and printing 3.75 million names per hour - or just under 1,042 names per second - assuming 24x7 running.

24x7 operation is unlikely to be feasible for a 1953 vintage computer, so let's be generous and say that we can get 16 hours of running each day, allowing an 8 hour maintenance window for replacing valves, delay lines or whatever. It means we need to produce 5.625 million names per hour - or 1,563 names per second. Hmm. That's quite a powerful computer by 1953 standards. But what about all the printing?!

Even if the Automatic Sequence Computer can produce these names quickly enough to meet the 100 day target, we're going to need a lot of very heavy and noisy printers, plus (literally) tonnes of paper.

Assuming A4 sheets at 100 names per sheet (single sided, as the story says they are pasted by the monks into books), that's 180,000 reams assuming no printer jams.

180,000 reams of A4 paper weighs 506,250 kilogrammes if we use decent 90gsm paper. These are the names of God, after all. Let's hope that our monastery isn't too inaccessible and has strong floors.

Implementing The Nine Billion Names of God Algorithm

From Clarke's story we know that:

• All of the names of God can be written with no more than nine letters of a specially devised alphabet
• There are a number of 'ridiculous' combinations of letters which can be eliminated - the example given is that no letter can occur more than three times in succession
• There are approximately nine billion names to find
• ... and that's it.

So there's not enough information to create the complete algorithm from scratch. Which is probably a good thing, as the story's premise is that if all nine billion names can be written down, man's purpose is fulfilled and the universe ends.

But we can, of course, invent our own alphabet and use the rules we do have to generate approximately nine billion names.

Now C is a great language, but it's terrible at handling character strings and C clearly isn't period appropriate. So I'm going to use FORTRAN instead. I'm not enough of a masochist to use the dialect of FORTRAN that John Backus invented in 1954 (close enough to 1953 for my purposes) but FORTRAN 77 will be able to do the job, and is still retro enough.

I've written the program very simply and there are obvious ways of shortening the code. If you're interested, you can find it in my nine billion github repository.

I'm allowing single letter names (Revelation 22:13, "I am the alpha and omega ..."), so it would seem churlish not to allow all possible lengths up to and including 9 letters. The only check I'm making is to rule out names that have four or more of the same letters in succession.

To generate at least nine billion names, I therefore need an alphabet with a minimum of 13 letters. Better mathematicians than me have worked out that 13 letters will generate around 11.5 billion names, but remember that we don't know all of the rules for eliminating 'ridiculous' names. It's therefore quite possible that the task needs an alphabet of 14 or more letters!

By way of example, here's my subroutine for generating all of the legal 5 character names. The ALPHA array is initialised in the main program to contain the letters A to M inclusive.

      SUBROUTINE GEN5
      CHARACTER*1 ALPHA(13)
      INTEGER*8 TOTAL
      COMMON /NINEB/ TOTAL,ALPHA
      INTEGER L1,L2,L3,L4,L5
      DO 100, L1 = 1,13
      DO 200, L2 = 1,13
      DO 300, L3 = 1,13
      DO 400, L4 = 1,13
      DO 500, L5 = 1,13
      IF ((.NOT.((L1.EQ.L2) .AND. (L2.EQ.L3) .AND. (L3.EQ.L4))) .AND.
     +    (.NOT.((L2.EQ.L3) .AND. (L3.EQ.L4) .AND. (L4.EQ.L5)))) THEN
         WRITE(*,*) ALPHA(L1),ALPHA(L2),ALPHA(L3),ALPHA(L4),ALPHA(L5)
         TOTAL=TOTAL+1
      END IF
  500 CONTINUE
  400 CONTINUE
  300 CONTINUE
  200 CONTINUE
  100 CONTINUE
      RETURN
      END

Running a single threaded version of my program to generate the 11.5 billion-ish possible names from an alphabet of 13 letters takes around 5 hours and 36 minutes on a Raspberry Pi 5.

"Overhead, without any fuss, the stars were going out."