Title: Surreal Numbers

A few weeks ago there was an intense discussion on the International C Standards reflector about introducing a built-in complex number type in C9X. I suppose 95% of programmers have no interest in such a type and most of the remaining 5% would be happy with the kind of implementation that they will find in the C++ Standard Library. Just a few will be aware that there is an IEEE specification for the complex type that includes such oddities as infinities, signed zeroes and NaNs (not a number). What was the point of the discussion? Well you cannot have a built-in type complex that meets everyone's needs.

Does this mean that we should abandon such a type? Whatever your answer, what can be done to provide the basic building blocks so that those who have such specialist needs as signed zeroes can construct what they need? This is not a trivial question, and though it may be totally insignificant to the majority, it is of vital concern to a small number. Our attitude to such minority needs is important because many of us have needs for specialist tools. As long as we can build them from the general bits that a language makes available we will be quite happy. But that does not mean we should discard the needs of others as no concern of ours.

During the debate someone said 'The next thing you will be asking for is Conway's Surreals as built-ins.' Now that is a show stopper if ever I heard one. Very few people will have the slightest idea as to what those are. Before I give you a hint, a topic area where they are useful, a short reading list and then a challenge let me explore a couple of other oddities.

C specifies that the representation of integers shall be binary with the possible exception of the high order bit. There are at least three different ways that negative integers can be represented.

In all three systems negative numbers are identified by the high bit being set. Both the first two methods provide a signed zero. The third method has a number of advantages for hardware, not least that the number system wraps around. The bit pattern for the most negative number is the successor to that for the most positive. This version is so widespread that many programmers think that it is the only representation of signed integers. Note that the representation has serious implications when you come to apply bit operations to negative integers.

The above is pretty old hat and is largely the consequence of trying to represent positive and negative numbers with a single sensible set of bit patterns. How many of you know that mathematics has no need for a negative sign? Some time in the fifties a young mathematician (sorry, I have forgotten who) realised that negative binary is an entirely valid numerical system that requires no symbol for negative. Let me list a few values in negative binary (I'll just use 4-bits for simplicity):

I am quite sure that this representation of numbers would be ruled out by C on the grounds that negative binary is not a binary system, but I wonder if they even thought about it. It does have the advantage that there is no artificial convention for identifying negative numbers (rather like a natural language that has no word for 'true' but uses 'false false')- that is about its only advantage and the system is quite unsuitable for ordinary arithmetic (that does not mean that there might not be some problem domain where such a representation makes otherwise obscure solutions 'obvious'). So far we have only been talking about representations, the underlying set of values represented remains the same.

In inventing (I think that is appropriate, rather than discovering) Surreal Numbers Dr Conway (probably best known for being the inventor of 'Life', but he has a vivid inventive mind and delights in producing instructive games that are fun to play. He was also the inventor of 'Sprouts' and when it had become the most popular leisure pursuit at Cambridge, under pressure invented 'Brussels Sprouts'. One is a challenging intellectual game the other is a total waste of time, the problem was that it took the students two weeks to discover that while Dr Conway smiled happily in temporary peace.) produced something arcane that was much more than a weird way of deriving number. This is not the place to try to summarise what took him over 200 pages (On Numbers and Games - Academic Press 0 12 186350 6) to describe. All I will say here is that Surreal Numbers include all the more traditional real numbers as well as an unlimited range of new ones (no, I am not talking about traditional infinities). The second part of the book shows how Surreal Numbers can be given meaningful interpretations and represent a particular kind of information.

Surreals are of significant and useful in analysing strategies in complete knowledge games. Most of you are familiar with the game of nim. Some of you may know how to analyse a nim position to determine whether it is a winning one (perfect play will result in a win for the person next to play) or a losing one. Of course the best methods will not only determine that a position is a winning one, but what move you should make.

As it is nearing Christmas (well it was when I first wrote this) let me give you a couple of nim type games. First take the opening game from Winning Ways (a two volume work by Berlekamp, Conway and Guy, Academic Press, 0 12 091101 9 & 0 12 091102 7) called Blue-Red Hackenbush. You have a stick picture (like the one on this page) in which the lines joining nodes are either blue (continuous) or red (broken). In turn two players choose a line of their own colour to remove. After the chosen line has been removed, any part of the drawing that is no longer connected to the ground by some continuous route (without regard to the colour of the arcs) is also removed.

Figure 1.

Suppose that you have a choice of first move, or colour, which choices should you make. That is, does the first player win (lose) regardless as to colour or does one colour win (lose) regardless of who has first move?

Winning ways is a two volume work using Surreal Numbers to answer such questions.

Here's one more game for fun. Lay out five rows of five matchsticks (counters or whatever). When it is your move you may remove an entire row or column of contiguous matches. So the first move must be to select any single row (column) of five matches. But after this move the layout will normally be in two (exceptionally if a boundary row or column has been removed it will still be in one part) disparate parts. Now you can remove a whole contiguous row or column from either part (but not both) and so on until there are no more matches left. Last to move wins. If both players play perfectly, should the first to play win or lose?

Write a program to play this last game. (Hint, generalise the problem. Yes its tougher than it looks, which is why Surreal Numbers are useful)

Write a program to play Red-Blue Hackenbush (Well you might start by writing a program that can display a bi-coloured graph - network to the non-mathematicians - such as the crude diagram here.)

(By the way, those that want ideas for strategy type computer games might find 'Winning Ways' an excellent source of inspiration and programming perfect strategies for the computer would teach you a lot about this kind of task.)

Go out and find a copy of either of the books mentioned above (or there is a book called Surreal Numbers but I have no other details) and start to develop a Surreal type in C++.

One last thing, both books are a mixture of deep maths and pure fun, but that is typical of much of Dr Conway's work. His automata game, 'Life', gave much pleasure to those that just played with it while requiring several (I think it was more than ten) years of expert analysis to determine if it met the full target criteria (can you build a programmable computer out of Life cells would be one phrasing of the critical question? The answer is yes but that is another story)