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?
 A: 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.
A: 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\}\}$
A: 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.
