### Table of Contents

## Bingo Algorithm

A (very) long time ago, as a trainee programmer, I was given the task of writing a computer algorithm to simulate the action of a Bingo caller. The requirement is to draw each of the numbers from 1 to 100 in a random order, and the point of the exercise is to write the computer simulation of this in the most efficient way possible.

This article describes some of the techniques that can be used to do this, explaining the relative merits of each solution, and hopefully will provide some useful instruction to a novice programmer.

## Method 1

My first idea was to fill up an array with the numbers, and then start generating random numbers (in the range 1 to 100). On each occasion we set the number in the array to 0 as we match it, and if we select a number at random which matches one we have already called, then we simply try again and select another number.

### Pros and Cons

**Pros**: A simple and easy to understand algorithm.

**Cons**: As more and more numbers are drawn, it becomes more and more likely that the next random number will correspond to a number that has been already drawn, so more and more random numbers will need to be generated for each number called, slowing down the program.

### Code

% cat hat1.c #include <stdio.h> #include <stdlib.h> #include <sys/time.h> #include <math.h> #include <unistd.h> #define BINGO_SIZE 20000000 long numbers[BINGO_SIZE] ; main (int argc, char **argv) { // init random seed struct timeval tp ; gettimeofday (&tp, NULL) ; srandom (tp.tv_usec) ; // create the bingo numbers long i = 0 ; for (i=0;i<BINGO_SIZE;i++) { numbers[i] = i + 1 ; } // now call them long remaining = BINGO_SIZE ; while (remaining) { // choose a random element in the array long pos = random() % BINGO_SIZE ; // if we haven’t already selected this number, it is our next result if (numbers[pos] != 0) { if (remaining < 50) printf ("%d, ", numbers[pos]) ; // mark the number as selected numbers[pos] = 0 ; remaining-- ; } } printf ("etc \n") ; }

### Performance

You will notice looking at the program code that it is not dealing with only 100 bingo numbers but in fact a staggering 20 million. I should point out that the programs I am presenting in this article are not the originals from this trainee programmer exercise of nearly 30 years ago (1985) but my recent recreation of the programs using the same algorithms. The original programs were run in interpreted BASIC ^{1)} on what used in those days to be termed an “IBM compatible” PC . Because of the advancements in processing power over the years, I have had to increase the size of the data set to make it easier to measure the relative merits of each of the algorithms in terms of performance. All the algorithms I am presenting run almost instantaneously as compiled code ^{2)} on a modern system if the size of the data set is left as 100 numbers.

Believe it or not, my recollection is that the performance of the original programs (to operate on only 100 numbers using interpreted BASIC on the IBM compatible PC of the time) was somewhat worse than the performance of the new versions I have created that manipulate 20 million numbers.

Here is the output from a timed run of the program

% time ./hat1 9609161, 7290025, 10692180, 4540009, 5159560, 19385050, 14157180, 2695951, 18591275, 15897045, 16002389, 14153865, 4344174, 6411181, 14217771, 18360853, 710570, 11780676, 5720755, 6495986, 13588493, 18458123, 16437398, 1387770, 11920787, 4414674, 2575774, 16885899, 7742104, 2867165, 8899627, 9679329, 7261282, 18995627, 6371500, 18043792, 10369864, 19905308, 9513110, 8142800, 4623736, 16613533, 19747558, 2502960, 8637128, 12438735, 5184601, 10509484, 16774046, etc [2] 21770 exit 5 ./hat1 ./hat1 27.53s user 0.20s system 98% cpu 28.222 total

## Method 2

After some thought on the matter I realized that if each number in the array is swapped with another number (at random) then the whole array of numbers would be randomized. All that would then be necessary is to read out the numbers from the array elements in order, since the contents are now randomized.

As it turned out, this was the solution that my mentor was hoping for.

### Pros and Cons

**Pros**: The data set only has to be parsed once to create the randomisation, and thus is much more efficient than Method 1. Also it is easy to describe what is going on. In software engineering this is usually preferable to a more efficient but harder to follow design, since the code may well have to be maintained by other people in the future.

**Cons**: It is not the absolute fastest algorithm.

### Code

% cat hat2.c #include <stdio.h> #include <stdlib.h> #include <sys/time.h> #include <math.h> #include <unistd.h> #define BINGO_SIZE 20000000 static long numbers[BINGO_SIZE] ; main (int argc, char **argv) { long tmp = 0 ; // init random seed struct timeval tp ; gettimeofday (&tp, NULL) ; srandom (tp.tv_usec) ; // create the bingo numbers long i = 0 ; for (i=0;i<BINGO_SIZE;i++) { numbers[i] = i + 1 ; } // now shuffle the array. Swap each array element with another one at random for (i=0;i<BINGO_SIZE;i++) { // select a random position in the array long newpos = random() % BINGO_SIZE ; // swap this element with the element in the randomly selected position tmp = numbers[newpos] ; numbers[newpos] = numbers[i] ; numbers[i] = tmp ; } // now call them for (i=0;i<BINGO_SIZE;i++) { if (i < 50) printf ("%d, ", numbers[i]) ; } printf ("etc \n") ; }

### Performance

% time ./hat2 6068748, 14802624, 13687226, 13221347, 17912271, 490687, 4072190, 17374265, 2422813, 11019818, 16238890, 10670013, 12996111, 4848285, 17737360, 15205892, 1231741, 10708433, 4905488, 18869997, 3638096, 2252122, 13964663, 16523510, 12875497, 1805864, 5543236, 19460394, 19653573, 15778226, 4355475, 4345297, 1800775, 2430728, 17064313, 15628445, 6205914, 11965925, 3814169, 12642794, 16710733, 4586916, 19291519, 9706843, 1007785, 2614954, 139317, 6490882, 5839738, 9876470, etc [2] 21757 exit 5 ./hat2 ./hat2 2.55s user 0.18s system 98% cpu 2.777 total

## Method 3

There is a faster solution than my mentor’s preferred solution (Method 2). With 30 years of programming experience behind me, this solution is obvious to me, but it certainly was not obvious at the time when I was just starting out as a programmer, so I will present it here as it may be instructive for others.

The array is filled up with the numbers 1 to 100 as in the other solutions. This corresponds to array elements 0 to 99. A random number is drawn in the range 0 to 99 and the content of that array element is our first result. Instead of setting it zero (as in Method 1) and thus leaving a gap in our data, we instead copy in the value from the last array element (element 99). Now we have a smaller data set (0 to 98) and we generate another random number for our next result, but this time we generate a number in the range 0 to 98. The content of that element of the array is our next result. Now we copy in the value from array element 98 to the element selected at random. With each iteration we reduce the range of the random number by 1, and also reduce the part of the array that we are looking at by 1.

### Pros and Cons

**Pros**: This is the fastest solution to the problem (at least that I can come up with)

**Cons**: It is harder to describe what the code is doing than in Method 2, and thus maintainability of the code is reduced.

### Code

borg02{msgmedia}8531% cat hat3.c #include <stdio.h> #include <stdlib.h> #include <sys/time.h> #include <math.h> #include <unistd.h> #define BINGO_SIZE 20000000 static long numbers[BINGO_SIZE] ; main (int argc, char **argv) { // init random seed struct timeval tp ; gettimeofday (&tp, NULL) ; srandom (tp.tv_usec) ; // create the bingo numbers long i = 0 ; for (i=0;i<BINGO_SIZE;i++) { numbers[i] = i + 1 ; } // now call them // select a number at random and reduce the size of the data set // each time for (i=BINGO_SIZE;i>0;i--) { long pos = random() % i ; if (i < 50) printf ("%d, ", numbers[pos]) ; numbers[pos] = numbers[i-1] ; } printf ("etc \n") ; }

### Performance

% time ./hat3 7113522, 4100963, 8762511, 8244692, 14209354, 16080200, 9326632, 8741749, 7328258, 15641102, 8987140, 18932018, 16949197, 793406, 2483526, 12392363, 18642963, 9416116, 10161641, 19224275, 2608833, 2242183, 14912980, 7342075, 17903118, 19980261, 13088727, 6064406, 9884282, 19840516, 1705854, 15227216, 4154276, 7085028, 12331318, 14030105, 6270425, 9399990, 5887938, 3650571, 15201167, 19175301, 13045451, 6914858, 14493332, 11135082, 8551081, 13575993, 2345387, etc [2] 21758 exit 5 ./hat3 ./hat3 1.99s user 0.15s system 98% cpu 2.183 total

As you can see runtime is 2.183 seconds compared with 2.777 seconds for Method 2. Unless performance is paramount I would prefer Method 2 for the clarity of what is being done.