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? – Hans Lundmark 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). – B. Elliott 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? – Hans Lundmark 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. – B. Elliott 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). – Hans Lundmark Jan 10 '15 at 10:51

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\}\}$$