# Algorithm for Converting Rational Into Surreal Number

I'm writing a library in Haskell that represents the class of surreal numbers, which like many things can be read about here. I've run into a problem in converting between other classes of numbers (specifically, rational numbers), and surreals. In an attempt to write a function that converts a rational number into a surreal number, I've noted a few things:

• Not all rational numbers have finite representations as surreal numbers (in fact, I believe any rational number that is represented fractionally with a denominator that is not a power of 2 fails in this respect); I'm willing to ignore these for now
• The function is likely to be defined recursively, like most operations on or concerning surreal numbers
• I have already defined addition, multiplication, negation (and by extension subtraction), and a function that converts an integer into a surreal number
• I would use division of two surreal numbers obtained via integer conversion (the numerator and denominator of the rational number), except that I'm having trouble defining division without already having defined division (simply a quirk with how surreal number division is defined)

I've glanced briefly through "the book" on the topic of surreal numbers (On Numbers and Games by John H. Conway), and while he mentions that the rational numbers are fully contained within the surreals (as are all ordered fields), the only thing he noted that I found that looks something like a conversion equation is the following:

If x is a rational number whose denominator divides $2^n$, then $x = \{x-(1/2)^n|x+(1/2)^n\}$

This seems circularly defined, and unsuitable for an algorithm (at least, as far as I have tried to use it, though that could simply be inexperience). Is there a sensible mapping between the rational numbers and surreal numbers that I can use to input a rational and get out a surreal, and if so, how does it work?

• How are you representing the surreals? Left and right sets? Strings of "left" and "right" turns starting from the root of the surreal number tree? Jan 9 '15 at 7:16
• @HansLundmark I'm using the original left/right set formulation with {L|R}, though I'm considering changing it (somehow) to allow for better representations of infinite sets (which themselves could be represented as series, in many cases). Jan 9 '15 at 7:49
• That notation is a bit ambiguous ($\{L_1|R_1\}$ and $\{L_2|R_2\}$ can define the same surreal number). Perhaps you could be more specific about exactly what data you would need the algorithm to supply? Jan 9 '15 at 13:30
• I am inputting a rational number represented as a pair of Ints (numerator and denominator) that automatically reduce to their coprime form, due to the data structure they live in (Ratio Int). Preferably, I would obtain each surreal number in its canonical form (my fromInteger function already does this), the earliest and simplest form produced by birthday style construction, but I also have a function to convert a non-canonical surreal into a canonical one by simplifying/removing unnecessary members of left and right sets, recursively. Jan 9 '15 at 15:14
• Well, in that case it's easy, since Conway's formula is exactly what you need; it gives you the simplest left and right member of $x$. Given a non-integer dyadic rational $x=k/2^n$ (with $k$ odd and $n>0$), just let $x_L=(k-1)/2^n$ and $x_R=(k+1)/2^n$ (and reduce to lowest terms). Jan 10 '15 at 10:51

Julia code that does the the translation is described at https://www.sciencedirect.com/science/article/pii/S2352711018302152

Tricker is translating an arbitrary, finite surreal to a Rational, but that paper described an algorithm for that as well.

It is the binary precision of the fractional part of the number that determines n.
Ask how many bits in a computer would it take to store the fractional part? n would be the number of bits of that register.

Here is 3/2, π and e rounded to some binary precision and represented according to the formula:

given 1.5 is the fraction 3/2 with denominator 2 dividing 2^(-1.0)
then x = {x - (1/2)^(-n)|x + (1/2)^(-n)}
says 1.5 = {1.5 - (1/2)^(-1.0)|1.5 + (1/2)^(-1.0)}
or 1.5 = {1|2}

given 3.140625 is the fraction 201/64 with denominator 64 dividing 2^(-6.0)
then x = {x - (1/2)^(-n)|x + (1/2)^(-n)}
says 3.140625 = {3.140625 - (1/2)^(-6.0)|3.140625 + (1/2)^(-6.0)}
or 3.140625 = {25/8|101/32}

given 3.14154052734375 is the fraction 51471/16384 with denominator 16384 dividing 2^(-14.0)
then x = {x - (1/2)^(-n)|x + (1/2)^(-n)}
says 3.14154052734375 = {3.14154052734375 - (1/2)^(-14.0)|3.14154052734375 + (1/2)^(-14.0)}
or 3.14154052734375 = {25735/8192|3217/1024}

given 2.71826171875 is the fraction 5567/2048 with denominator 2048 dividing 2^(-11.0)
then x = {x - (1/2)^(-n)|x + (1/2)^(-n)}
says 2.71826171875 = {2.71826171875 - (1/2)^(-11.0)|2.71826171875 + (1/2)^(-11.0)}
or 2.71826171875 = {2783/1024|87/32}


...from python code...

from surreal import Surreal
from fractions import Fraction
from math import log,pi,e,sqrt
def surreal_representation(x):
f = Fraction(x)
d = f.denominator
n = log(d,2)
a = Fraction(x - 2**(-n))
b = Fraction(x + 2**(-n))
print("""
given {} is the fraction {} with denominator {} dividing 2^(-{})
then x = {{x - (1/2)^(-n)|x + (1/2)^(-n)}}
says {} = {{{} - (1/2)^(-{})|{} + (1/2)^(-{})}}
or {} = {{{}|{}}}
""".format(x,f,d,n,x,x,n,x,n,x,a,b))

represent = [
(3/2,  5),
( pi,  7),
( pi, 14),
(  e, 12)
]
for n,p in represent:
p = 2**p
surreal_representation(int(n*p)/p)


using the surreal class

The key is to amend your statement to If x is a rational number with odd numerator whose denominator is $$2^n$$, then $$x = \{x-(1/2)^n|x+(1/2)^n\}$$

The point is that both fractions now have a smaller power of $$2$$ in the denominator, so the recursion will terminate. For example, if $$x=\frac 58$$ we can use this to find that $$x=\{\frac 12|\frac 34\}=\{\{0|1\},\{\frac 12|1\}\}=\{\{0|1\},\{\{0|1\}|1\}\}$$

The correct way to store Surreal Numbers in binary is to store the Dyadic rational value in a binary form that is equal to the nth birth number of that surreal. You can do so by encoding it as 1LRRLRLLLR applying L's and R's as your would move left and right down the binary tree to reach the target surreal value. Just switch the L to 0's and R to 1's... 1LRRLRLLLR = 1011010001 in sinary. Sinary is a name I made up for Surreal encoded bit format.

In this encoding the length of the number is the surreal birth day. The greatest number in the left set will be its sinary with its tail trimmed back to the first '1'. And the least number in its right set will be its sinary trimmed back to the first '0'.

Example evaluation of sinary 1011010001:

1011010001
1-++-+---+
= 0 - 1 + 1/2 + 1/4 - 1/8 + 1/16 - 1/32 - 1/64 - 1/128 + 1/256
= −93/256


and the left side will be:

1011010001 trimmed to last '1' is: 101101000
1011010001 trimmed to last '0' is: 10110100


Evaluating the left...

10110100
= 0 - 1 + 1/2 + 1/4 - 1/8 + 1/16 - 1/32 - 1/64
= −46/128


Evaluate the right...

101101000
= 0 - 1 + 1/2 + 1/4 - 1/8 + 1/16 - 1/32 - 1/64 - 1/128
= −47/128


The birth day of this number is its bit length minus one = 9

The birth order number is the binary evaluation of its sinary = 721

Therefore, we see that the 721st Surreal number was born on the 9th day and it is −93/256 and has a {L|R} representation of {−46/128 | −47/128}

Surreal math operations can use this representation directly without needing to convert into standard binary representation.

I think it is incorrect to store a surreal number as two numbers (right and left), when it is shown that the left and right sets are both portions of the same binary pattern. ie: one side will be a trimmed subset of the other. So it is better to store the number in a single binary surreal representations and just chop of the ends of the sinary when you need to access the right or left sides.

• "The correct way" is a rather strong statement here. Especially given that the surreal numbers you can represent that way are exactly those that you can also represent by arbitrary precision floating point numbers. Jun 14 '20 at 7:31
• Numbers in a computer will be finite and stored in binary. Dyadics. And the correct way to write one in decimal is "1". And the correct what to write one for surreal number is "3". Because one is the 3rd surreal. The birth index is the correct way to store a sureal number in a computer because it is equievelent to its binary tree with a one prefix (since negative number do not lose their integer precision (because binary does not honour left sided zeros). Jun 17 '20 at 15:35
• There is a binary format for finite surreal numbers. The surreal birth order in binary IS the tree path taken to arrive at that number. Just store this number. Its binary and the surreal number birth order IS the binary tree pattern with a one prefixed. There is no reason for conversion. ex: 3rd surreal = binary 11 = 0+1 = a value of 1 13th surreal = binary 1101 = 0+1-1/2+1/4 = a value of 3/4 Jun 17 '20 at 16:02