Surreal Arithmetic, Lazily
Lloyd Allison · 2026
Read Surreal Arithmetic, Lazily by Lloyd Allison (2026) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2604-17885.txt.
Introduction
Allison asks how far lazy evaluation and recursive data structures can carry an efficient implementation of Conway's surreal numbers. The system, named by Knuth, extends the reals with infinities and infinitesimals. The note tests surreal arithmetic built this way. It reports a considerable speedup over more direct approaches. Delaying computation until values are actually needed, Allison shows, pays off for this unusual number system.
Catalog record
| CREATOR | Lloyd Allison |
|---|---|
| YEAR | 2026 |
| COLLECTION | PAPERS |
| FORMAT | TXT |
| FILE SIZE | 11485 |
| LICENSE | http://creativecommons.org/licenses/by/4.0/ |
| RIGHTS | CC BY |
| SOURCE | arXiv |
Source: https://arxiv.org/abs/2604.17885
Browse the full library · About the Tower of Babel
Full text
The opening of the work, from the library's hosted text:
Surreal Arithmetic, Lazily Lloyd Allison Abstract . Conway’s surreal numbers were aptly named by Knuth. This note examines how far one can get towards implementing surreals and the arithmetic operations on them so that they execute efficiently. Lazy evaluation and recursive data structures yield a considerable speed up. keywords: surreal numbers, arithmetic, functional programming, circular program, corecursion \setcopyright none \orcid 0000-0002-9020-3164 1. Introduction Conway defined the surreal numbers as described in his ‘ONAG’ book 2 ; initially he had simply called them ‘numbers’ but Knuth coined the name ‘surreal numbers’ 3 which is very appropriate given the bewitching universe of numbers that the system created and it was readily accepted 4 . From the simplest of beginnings the full surreal numbers propagate to include integers, rationals, irrationals and even transfinite numbers, forming the largest ordered field 1 . Various authors have played more or less deeply in the programming of surreals to see how much to do with them can be implemented in computer programs. Perhaps the most practical prior work of this kind, as its title suggests (although “practically” can be read in two ways), is by Roughan 5 who used the programming language Julia as the means. In considering earlier efforts he noted that “There are several prior implementations of the surreals in various programming languages … Most of these are very incomplete” which pretty much holds today. This note describes a more practical way of implementing surreal numbers that have finite representations, with the operators \leq,<,\geq,>,=,\neq,+,-,\times on them, as they are specified by Conway, and that runs quickly through the use of laziness and mutually recursive data-structures and functions. An interactive calculator has been programmed and is available 1 1 1 Calculator and further notes at www.cantab.net/users/mmlist/ll/Maths/surreal.html to play with. ⬇ if x=\langle L_{x}|R_{x}\rangle and y=\langle L_{y}|R_{y}\rangle , x_{L} a typical member of L_{x} , x_{R} of R_{x} , y_{L} of L_{y} , y_{R} of R_{y} then x\geq y iff no x_{R}\leq y and no y_{L}\geq x , x+y=\langle x_{L}+y,x+y_{L}|x_{R}+y,x+y_{R}\rangle , -x=\langle-x_{R}|-x_{L}\rangle , x-y=x+(-y) , x\times y=\langle x_{L}y+xy_{L}-x_{L}y_{L},x_{R}y+xy_{R}-x_{R}y_{R}\text{\penalty\ }| x_{L}y+xy_{R}-x_{L}y_{R},x_{R}y+xy_{L}-x_{R}y_{L}\rangle Figure 1. Definitions (see 2 (p.4)) 2. Surreal Numbers In ONAG notation 2 a surreal form is written \langle L|R\rangle where L and R are sets of surreal numbers – sets that can be empty, finite or infinite. If no member of R is less than or equal to any member of L the surreal form denotes a surreal number . Strictly speaking a surreal number is an equivalence class and can be represented in many different ways but it is common practice to gloss over this where possible. Conway defines \leq,+,-,\times (figure 1 ) and shows that they have the usual properties expected of arithmetic, and then some. The simplest, and oldest, surreal number is \langle|\rangle which can be called zero or \underline{0} because it behaves like a zero should: x+\langle|\rangle=x and x\times\langle|\rangle=\langle|\rangle for any x . Zero is said to be born in generation 0. Note that L=R=\emptyset in zero and they are omitted traditionally. Zero has two children born in generation 1, \langle\langle|\rangle|\rangle and \langle|\langle|\rangle\rangle (or \langle\underline{0}|\rangle and \langle|\underline{0}\rangle ) which we can call \underline{1} and \underline{-1} because of their behaviours, e.g., \langle\underline{0}|\rangle\times x=x , \underline{1}+\langle|\underline{0}\rangle=\underline{0} , and so on. After the birth of its two children there is generation 2 of zero’s four grandchildren including \underline{2}=\langle\underline{1}|\rangle and \underline{1/2}=\langle\underline{0}|\underline{1}\rangle , subsequently its eight great grandchildren and so on. The surreal numbers that are born in finite generations in the above way are equivalent to the dyadic rationals – numbers of the form i/2^{j} for integer i and non-negative integer j . Each surreal born in a finite generation has a canonical representation x=\langle L_{x}|R_{x}\rangle where each of L_{x} and R_{x} is either empty or contains a single surreal number that was born before x was born. All attempts at “everyday” programming with surreals limit themselves to “short” surreals – those having finite representations. Values like 1/3,\sqrt{2},e, and \pi do not have finite representations as surreals although each of these examples is computable in that we can write a program that returns a short surreal that is as close as desired to the real value. The focus therefore has been on implementing the short surreals, the comparisons and the operators +,-,\times . Before getting down to the business, there is the matter of the rules of the game. If we just wanted to evaluate expressions with short surreals as quickly as possible we would likely convert them to rational numbers, which some languages and some hardware already support, compute with those and convert the result back to surreals. However that would be cheating . Instead the ethical path is to implement Conway’s definitions as far as is possible and to see what emerges from that. ZERO = ⟨|⟩ -- in ONAG notation SNs = Tree ZERO (left ZERO) (right ZERO) left ⟨L|R⟩ = let x = ⟨L|⟨L|R⟩⟩ in Tree x (left x) (right x) right ⟨L|R⟩ = let x = ⟨⟨L|R⟩|R⟩ in Tree x (left x) (right x) canonical x = let search (Tree s lft rgt) = if x < s then search lft else if x > s then search rgt else s -- x=s in search SNs Figure 2. SNs, the "Genealogy" Tree of Surreals We can define the “Genealogy” Tree of surreals, SNs , as in figure 2 . It is an infinite Tree but just finite parts are built, only as necessary from use. Given an arbitrary representation, x , the function canonical searches for the node where the surreal that x represents was born and returns that. The functions LE ( \leq ), plus , times , implement Conway’s definitions 2 (and figure 1 ) in the obvious way and negate , minus and the other comparisons follow on. However as can be seen, these definitions are highly recursive, for example, multiplying numbers from generations i and j can involve multiplying and adding numbers from generations i-1 and j and from generations i and j-1 , and so on, recursively until we get down to at least one zero. Many sub-multiplications and sub-additions appear multiple times in this process to the extent that, in a naive implementation, times 3 3 takes a fraction of a second but times 4 4 takes minutes and times 5 5 is hardly to be entertained. The cure for this problem of inefficiency is to use multiplication- and addition-tables which are in fact Trees of Trees, as defined in figure 3 . Here map (apply to all) is the obvious function on Trees rather than lists. Two new functions, (*) and (+) are introduced which look in the tables for the results of x\times y and x+y respectively. Functions times and plus are rewritten to call (*) and (+) internally where they used to call themselves. This ensures that the result of each x\times y and each x+y is only ever calculated once and subsequently looked up more quickly in the tables. TimesTable = map (\x -> map (\y->times x y) SNs) SNs PlusTable = map (\x -> map (\y-> plus x y) SNs) SNs (*) x y = select (select TimesTable x) y (+) x y = select (select PlusTable x) y select