RIES  Find Algebraic Equations, Given Their Solution
First page . . . Forward to page 3 . . . Last page (page 6)
Benchmarks
ries is very fast. When it was created, results like those shown above took less than 2 seconds on a 180MHz machine. Such a machine could easily test over 10^{10} equations in less than a minute. On a 733MHz PentiumIII, ries l4 tested over 1.4×10^{12} equations in 62 seconds; on a 2.33GHz Intel Core 2, the same thing finishes in only 13.5 seconds.
This first table shows the increase in time and memory requirements as the search level is increased, using the command ries lN 2.50631415926535897932 for various values of N. ries accepts a fractional value for the l (search level) parameter. These tests were performed on an Intel Core i7 running at 2.26 GHz.
Time and Memory by Search Level

The next table shows the time needed by the command ries l3 2.5063141592653589 on a variety of machines dating back to 2000.
Time by PCMS (Processor/Cache/Memory System)

RIES Background and Philosophy
Motivation and History
I wrote ries after I was frustrated by services such as Plouffe's Inverter and the Inverse Symbolic Calculator. In case you're wondering, the things that frustrated me are described here. I had also been getting occasional emails from members of the Cult of 137, and likeminded people claiming formulae for such things as the area of the Mandelbrot set. I thought it would be nice to be able to demonstrate how easy it is to find a formula for any number.
After a particularly inspired email missive from a person who had a magic unproven formula for some number, I decided to write ries and had a working equationgenerator within about 2 weeks (Feb 7^{th} through 21^{st}, 2000).
The program had its own page at mrob.com/ries/index.html at least as early as Aug 18^{th} 2000. Soon I moved it to Earthlink, at home.earthlink.net/~mrob/pub/ries/index.html, where it remained for several years, before moving back to mrob.com at its present location, mrob.com/pub/ries/index.html. (Old ries pages at these URLs can be seen at archive.org).
The core functionality and implementation have remained the same, although various new features and options were added in late 2011 and early 2012, and more in 2013.
In April 2012, ries was used by Randall Munroe for an xkcd strip. In response to growing interest, I added the Online RIES server.
Algorithm
Think of the Real numbers as being points in space (not arranged along a straight line, as is more commonly taught). Instead of placing them close to each other based on their actual value, imagine the real numbers are close together if they have a simple algebraic relationship. Think of them as being connected by lines whenever two real numbers have a simple relationship. Two real numbers with a simple relationship are like cities on a map, connected by roads. For example, the numbers 2 and 3 would be connected because they differ by exactly 1, and the numbers π and 1/π would be connected because they are reciprocals. This abstract "map" of real numbers connected by lines is called a graph in the branch of mathematics called graph theory.
Somewhere on this infinite graph, which has a vertex for every real number, is the "mystery number" specified by the user of the ries program. This number is called the Target.
Perhaps we could explore the infinite graph by starting with the integers on the left and the Target on the right. As we explore the graph we start with very simple operations, like adding or subtracting 1:
left: a few integers; right: the target T along with T±1
Next we try negating values, or taking the reciprocal:
Some negatives and reciprocals
We can also use square root or more exotic functions, and two values on the graph can be combined (such as by adding or multiplying) to make new values:
More possibilities and combinations
Continuing in this manner, we make more and more different values. It is clear that eventually we will find a value on the left that is very close (numerically) to some value on the right. Will we ever find an exact equality?
Search for an equality: Do any of the paths meet?
If we could find such a path, we would have an equation, whose solution or root would give an exact representation (and perhaps a closedform expression) for the target number T. If we could find the shortest path then we would have the simplest exact representation of the target number.
An Exact Answer is Unlikely
I suggested that all the real numbers are on a graph like this. However the graph is infinite and there are limits to what can be reached in a finite number of steps. It has been shown that not all real numbers are connected by the "algebraic" operations, like subtraction, division and square root. In fact, the transcendental numbers far outnumber the algebraic numbers. Furthermore, even if we add constants like π and e, plus more functions like natural logarithm and cosine, making some transcendental numbers reachable, there will always be an infinity of real numbers that we'll never reach. That is because we only have a finite number of options at each step, and we are only taking a finite number of steps, so the total number of combinations of operations, and thus reachable nodes, will always be the "countable infinity" Aleph null — the same as the number of integers. The real numbers are a continuum, a set with more than Aleph_{0} members.
Since there might be no finite path connecting the fundamental constants like the integers and π to the target number (or equivalently, a path that converges on the target might be infinitely long), ries cannot hope to always find an exact match. However, paths of finite length should be able to come arbitrarily close to the target value. (Numerical roundoff error will often cause an 'exact' match, and these might or might not correspond to actual mathematical equality.)
The central ries algorithm is a bidirectional search of a graph similar to the search illustrated in the figures above. The graph is traversed in a "breadthfirst" manner, starting with the shortest paths and gradually extending the boundaries of explored space (sometimes called "iterative deepening"). Ideally ries would generate all possible expressions in order of increasing Kolmogorov complexity. The actual algorithm is a practical approximation to this.
ries explores the graph for short paths that start at the target number, and simultaneously it looks at short paths starting from fundamental constants like 1 and π. While it explores, it "marks" every spot it has visited by adding an entry into a database in memory. The database is kept sorted by value: in the example illustrated above, the entry for 2^{1}/_{2} will be close to the entry for the target value 2.5063. Whenever ries ever finds two values that are closer than anything it has found so far, it has found a newer, better approximation to the target.
Since ries is exploring expressions and it takes two expressions to link the fundamental constants to the target value, any approximation ries finds is in effect an equation whose root constitutes an approximation to the target. For example, on the left we will eventually compute 2π = 6.2831... and on the right we'll compute T^{2} = 6.2815... Combining these into an equation gives T^{2} = 2π, and the solution of that equation is T=√2π = 2.5066... which is not exactly the target value 2.5063, but it's a lot closer than 2^{1}/_{2}.
There is a staggering amount of calculation that might be needed to find a close match. If the matches were distributed randomly, then it might take a million failed attempts before finding a single example that matches to within 6 significant digits. The bidirectional search approach helps with this, and ries incorporates extensive design for efficiency, with multiple levels of abstraction and pruning at each level. A match to within 10 significant digits is usually attainable in just a few seconds.
A detailed example of the search for a formula for 2.5063, showing the actual values ries calculates as it searches, is shown in detail below: A Detailed Example of the RIES Algorithm.
Optimizing the Bidirectional Search
ries does not generate full expressions and then evaluate each one; it evaluates each symbol as it goes along. This allows it to avoid repeating calculations when multiple expressions have common parts. For example it goes from √7+1 to √71 without repeating the calculation of √7.
ries uses a stackbased execution design, but preserving function arguments when they are "popped" off the stack so they can be pushed back on for reuse. To accomplish this I use the "metastack" abstraction, socalled because it is used like a "stack of stacks". One can also think of it as a stack with an undo list, itself a sort of stack: whenever something is pushed or popped on the normal stack, the "undo instructions" are pushed onto the "undo stack"; and when you "unpush" or "unpop" it pops instructions off the undo stack and alters the normal stack accordingly.
Millions of expressions need to be generated, and stored in memory so that ries can display an answer in symbolic form when it finds a match. For memory efficiency the expressions are as strings of onebyte symbols, in postfix format so that no extra storage is needed for parentheses. For example, "√7+1" is represented in postfix as "7 √ 1 +", which is encoded in ASCII as 7q1+.
ries needs to give different "weights" to the various digits, constants and functions in order to produce output that makes sense. (For example, 4^{7} should be thought of as "more complex" than 4×7, which itself is "more complex" than 4+7).
Since ries wants to perform iterative deepening, and do so in such a way as to generate expressions approximately in order of increasing score (as measured by the sum of the "weights" of the symbols in each expression). This means that the iterative deepening cannot simply generate all 1symbol expressions, then all 2symbol expressions, and so on. Instead the deepening needs to look at the complexity score (sum of weights) of partial expressions and see if it's possible to lengthen each partial expression without exceeding the complexity score. This depends on the number of additional symbols that might be needed to complete the expression. That could be measured by looking at the number of items on the expression's stack, but I decided instead to generate expression "forms" that are used as "templates" to generate expressions whose binary expression tree is identical.
In expression "forms", the letter "a" represents a scalar value (like 7 or π), a "b" represents a function of one argument (like sine or square root), and a "c" represents a function of two arguments. For example the form corresponding to the postfix expression 7q1+ is "abac".
The forms are also generated by iterative deepening. Given a length n, all forms of length n are generated recursively, with pruning when an initial substring cannot be completed in length n. (It is equivalent to generating the Motzkin numbers.)
Source Code
ries was first created for Linux^{1}, but it also compiles in Mac OS X, Windows with the MinGW compiler tools, or in Visual C++ with fairly minimal effort. It uses only the standard C math and stdio libraries. The source code is distributed under GPL 2.0. You can also get the manpage source. If you don't already have a copy, you should also retrieve the GNU General Public License version 2.0, which defines the terms under which this source code is made available to you, here.
RIES Source Code Files:
Main Program (C) (build instructions are in a block
comment near the beginning)
msal_math64.c
(optional standalone math functions)
License (GPL 2.0)
Manual:
RIES manual, PDF format
RIES manual, PostScript format
RIES manual, in Plain ASCII
RIES manual, Source (nroff) format
Detailed Examples of RestrictedClass Searches
Searching for Integer Solutions
Use the ries option i to search for a solution that entirely involves integers. For example:
ries i 1729 Your target value: T = 1729 mrob.com/ries 9 x = 5^6 for x = T + 7.11111 {79} (x1)/3 = (4*6)^2 ('exact' match) {97} 9(x+1) = 5^6 for x = T + 6.11111 {93} x+6^2 = (6*7)^2 for x = T  1 {95} 3^3 x = 6^6+1 for x = T  0.962963 {111} 4(x6) = (9^2+2)^2 for x = T  0.75 {112} 4(x7) = (9^2+2)^2 for x = T + 0.25 {112} 3*(3 x)^2 = 2*7^9 for x = T  0.0823981 {122} . . .In an integer search, the equations that ries gives, when treated as inequalities, evaluate to integers on both sides of the = sign. For example, in the first answer "9x=5^{6}", put in the target number (1729) for x and the left side is 9×1729=15561, and the righthandside is 5^{6}=15625. This is a nearequality; ries also tells us that if x is 7.11111... (7 ^{1}/_{9}) higher, the equation works out: 9×(1729+7^{1}/_{9}) = 9×1729+9×7+1 = 15625.
The second solution "(x1)/3 = (4*6)^{2}" is an exact match, because (17291)/3 is 576, which is 24^{2}. If you want ries to give you only the exact match for an integer problem, use the option maxmatchdistance 0, meaning that no match should be more than 0 from equality:
ries i 1729 maxmatchdistance 0 Only give an 'exact' match (if any) then exit. Your target value: T = 1729 mrob.com/ries (x1)/3 = (4*6)^2 ('exact' match) {97} (Stopping now because an exact match was found.)Searching for Rational Solutions
Use the ries option r to search for rational approximations, i.e. solutions that entirely involve ratios of integers. For example:
ries r 2.50618414558877 Your target value: T = 2.50618414558877 mrob.com/ries 2 x = 5 for x = T  0.00618415 {49} 2 x5 = 1/(9*9) for x = T  1.13061e05 {103} 1/(2 x5) = 9*91/4 for x = T + 7.80488e06 {131} 1/(1/(2x)+2) = 8(1/9+5) for x = T + 5.67559e06 {140} 1/(2 x5) = 9*91/8 for x = T  1.76537e06 {134} (for more results, use the option 'l3')The r option limits ries to only using the digits 1 through 9 and the operations +, , *, /, negative, and reciprocal; and each solution will have only one x on the lefthandside; this means that when solved for x, all answers will work out to a fraction. To get ries to do the solving for you, add the s option:
ries r 2.50618414558877 s Your target value: T = 2.50618414558877 mrob.com/ries x = 5/2 for x = T  0.00618415 {50} x = (1/(9*9)+5)/2 for x = T  1.13061e05 {103} x = (1/(9*91/4)+5)/2 for x = T + 7.80488e06 {131} x = 21/(1/(8(1/9+5))2) for x = T + 5.67559e06 {142} x = (1/(9*91/8)+5)/2 for x = T  1.76537e06 {134} (for more results, use the option 'l3')The answers aren't simplified, but you can see that they all work out to rational numbers.
Searching for "Constructible" Solutions
Use the ries option c to search for solutions that are constructible_numbers. These are numbers corresponding to distances that can be "constructed" with a straightedge and compass, using the methods of Euclid's Elements. c allows everything allowed by r, but also allows squares, square roots, and the golden ratio constant Φ. For example:
ries c 2.50618414558877 Your target value: T = 2.50618414558877 mrob.com/ries 2 x = 5 for x = T  0.00618415 {49} (x/2)^2 = sqrt(sqrt(6)) for x = T  0.00411734 {78} 4x = sqrt(sqrt(5)) for x = T  0.00153293 {77} xsqrt(2) = sqrt(sqrt(sqrt(2))) for x = T  0.00146285 {82} x+1/9 = phi^2 for x = T + 0.000738732 {72} xsqrt(5) = phi/6 for x = T  0.000443837 {87} . . .You can also add s to shift everything to the righthandside:
ries c 2.50618414558877 s Your target value: T = 2.50618414558877 mrob.com/ries x = 5/2 for x = T  0.00618415 {50} x = 2 sqrt(sqrt(sqrt(6))) for x = T  0.00411734 {77} x = 4sqrt(sqrt(5)) for x = T  0.00153293 {78} x = sqrt(sqrt(sqrt(2)))+sqrt(2) for x = T  0.00146285 {81} x = phi^21/9 for x = T + 0.000738732 {73} x = phi/6+sqrt(5) for x = T  0.000443837 {86} . . .Searching for Algebraic Solutions
Use the ries option a to search for solutions that are algebraic_numbers. These are real numbers that are roots of polynomial equations like x^{5}+x7=0. a allows everything allowed by c, but also allows N^{th} powers, N^{th} roots, the trigonometric functions (but only with the argument is a rational multiple of π). Significantly, it allows more than one x on the lefthandside of the equation, which the above options do not. Here is an example:
ries a 2.50618414558877 Your target value: T = 2.50618414558877 mrob.com/ries 2 x = 5 for x = T  0.00618415 {49} x+sqrt(3) = phi^3 for x = T  0.00216698 {82} xsqrt(2) = 8"/2 for x = T  0.00146285 {81} xsqrt(x) = cospi(1/8) for x = T + 0.0011526 {83} x+1/9 = phi^2 for x = T + 0.000738732 {72} . . . x^4x = 8(3+phi) for x = T + 1.68687e07 {117} . . .With a there may sometimes be more than one x in each equation, which the s option cannot "solve". However, most of the answers will have just one x so s is still useful:
ries a 2.50618414558877 s Your target value: T = 2.50618414558877 mrob.com/ries x = 5/2 for x = T  0.00618415 {50} x = phi^3sqrt(3) for x = T  0.00216698 {83} x = 8"/2+sqrt(2) for x = T  0.00146285 {80} x = cospi(1/8)+sqrt(x) for x = T + 0.0011526 {82} x = phi^21/9 for x = T + 0.000738732 {73} . . . x = 4"/(8(3+phi)+x) for x = T + 1.68687e07 {117} . . .Variations of the a Option
Using a with Ox tells ries to limit its answers to algebraic numbers that are expressible in closed form. This prevents ries from finding an exact answer for 1.132997565885066 (which is a solution to x^{5}+x3=0); but it still finds an answer for 1.551133518071245... (which is (2+√3)^{(1/3)} ).
Using a with Ox and anyexponent gives solutions expressible in closed form, but allows many transcendental numbers that are not the roots of any polynomial by relaxing the restrictions on exponents. With these options ries finds an answer for 1.632526919438153... (which is √2^{√2}).
Chow's "ClosedForm" or "ExponentialLogarithmic" Numbers
In his 1998 paper What is a closedform number? [4], Timothy Chow describes several definitions of classes of numbers. He starts by describing the difference between "closedform function" and "closedform number":
Recall that a function is elementary if it can be constructed using only a finite combination of constant functions, field operations, and algebraic, exponential, and logarithmic functions. [...]
what we need [...] is a notion of a closedform number rather than a closedform function. The distinction is important; we cannot, for example, simply define an "elementary number" to be any number obtainable by evaluating an elementary function at a point, because all constant functions are elementary, and this definition would make all numbers elementary. [...]
Intuitively, "closedform" implies "explicit", and most algebraic
functions have no simple explicit expression. So the set of purely
transcendental elementary functions is a better prototype for our
purposes than the set of elementary functions. ("Purely
transcendental" simply means that the word "algebraic" is dropped
from the definition.)
 Chow 1998 [4]
In this description, the term algebraic functions is being used as in the Wikipedia article Algebraic function. It is not a "function" in the ordinary way, where you put in a number and get a single number out. Rather, it is a binary relation between x and y such that all valid pairs of x and y satisfy an equation like:
P_{n}(y)x^{n} + ... + P_{2}(y)x^{2} + P_{1}(y)x + P_{0}(y) = 0
where each of the P_{i}(y) is a normal polynomial. This includes a lot of things, like quintic polynomials in x, that cannot usually be solved for x in closed form. This is what Chow is referring to when he says, "most algebraic functions have no simple explicit expression", and it is the reason he drops the word "algebraic" and goes to a definition based on "purely transcendental".
He goes on to define his class of ExponentialLogarithmic numbers, abbreviated EL or E, as a subfield of the complex numbers C as follows:
A subfield F of C is closed under exp and log if (1) exp(x) ∈ F for all x ∈ F and (2) log(x) ∈ F for all nonzero x ∈ F, where log is the branch of the natural logarithm function such that π < Im(log x) ≤ π for all x. The field E of EL numbers is the intersection of all subfields of C that are closed under exp and log. [...]
Set E_{0} = { 0 }, and for each n > 0 let E_{n} be the set
of all complex numbers obtained either by applying a field operation
to any pair of (not necessarily distinct) elements of E_{(n1)}
or by applying exp or log to any element of E_{(n1)} [...]
E is the union of all E_{n}. [...] E is countable, and [every]
element of E [has] an explicit finite expression in terms of
rational numbers, field operations, exp, and log.
 Chow 1998 [4]
Chow then gives several examples of numbers that qualify as members of E:
e = exp(exp(0))
i = exp(log(1)/2)
π = i log(1)
and for any value v ∈ E, the following are all in E:
v^{2/3} = exp((2 log v)/3)
sin v = (exp(i v)  exp(i v)) / 2i
tanh v = (exp(v)  exp(v)) / (exp(v) + exp(v))
arccos v = i log(v + exp(log(v^{2}1)/2) )
Using RIES to Search for Chow ClosedForm Solutions
Once Chow's definitions and examples are understood, it is easy to see that ries with the option Ox, which allows only one x in any reported result, finds only solutions that are "ExponentialLogarithmic numbers" by Chow's definitions, and does not report any solutions that are not of this type.
ries Ox 2.50618414558877 Your target value: T = 2.50618414558877 mrob.com/ries 2 x = 5 for x = T  0.00618415 {49} 8 x = e^3 for x = T + 0.00450797 {66} x^2 = 2 pi for x = T + 0.000444129 {55} (xpi)^2 = cospi(1/e) for x = T + 0.000386421 {79} x^2+e = 9 for x = T + 0.000151461 {63} x^2+pi = 4^phi for x = T  6.4912e05 {82} sqrt(log_pi(x)) = ln(sqrt(6)) for x = T  1.39889e06 {87} tanpi(x3) = pie^4 for x = T + 1.06848e06 {99} . . .Since there is only one x in each equation, the s option resolves all results into a closedform solution:
ries Ox 2.50618414558877 s Your target value: T = 2.50618414558877 mrob.com/ries x = 5/2 for x = T  0.00618415 {50} x = e^3/8 for x = T + 0.00450797 {67} x = sqrt(2 pi) for x = T + 0.000444129 {55} x = pisqrt(cospi(1/e)) for x = T + 0.000386421 {85} x = sqrt(9e) for x = T + 0.000151461 {64} x = sqrt(4^phipi) for x = T  6.4912e05 {83} x = pi^(ln(sqrt(6))^2) for x = T  1.39889e06 {84} tanpi(x3) = pie^4 for x = T + 1.06848e06 {99} . . .Liouvillian Numbers
In his 1998 paper [4], Timothy Chow describes the "Liouvillian numbers" L. As with E described above, they are a subfield of the complex numbers C. Referring to the work of J. F. Ritt (see [1], [2]), Chow wrote:
Ritt thought of elementary numbers as the smallest algebraically
closed subfield L of C that is closed under exp and log. It so
happens that terminology has evolved since Ritt, so that L is now
known as the field of Liouvillian numbers, and "elementary numbers"
are now numbers that can be specified implicitly as well as
explicitly by exponential, logarithmic, and algebraic operations.
 Chow 1998 [4]
By "algebraically closed", Chow means that all roots of polynomials are in L. So, for example, this included the roots of x^{4}+x3=0 (which can be solved for x), and also the roots of x^{5}x+1=0 (which cannot be solved for x).
By "closed under exp and log", Chow means that if v is any number in L, exp(v) and log(v) are also in L. Thus L includes √2^{√2}; however it does not include the roots of x^{x}=7 or of cos(x)x=0 because those equations are not "algebraic" and cannot be solved for x using the elementary functions.
Ritt's L and Chow's E differ only in that L includes implicitly defined algebraic numbers (like the roots of all quintic polynomials) while E includes only those that can be expressed in closed form.
Use the ries option l to search for solutions that are Liouvillian numbers. This option is like a, but permits the natural logarithm and exponential functions, with any argument that does not contain an x. For example:
ries l 2.50618414558877 Your target value: T = 2.50618414558877 mrob.com/ries 2 x = 5 for x = T  0.00618415 {49} 8 x = e^3 for x = T + 0.00450797 {66} x^2 = 2 pi for x = T + 0.000444129 {55} (xpi)^2 = cospi(1/e) for x = T + 0.000386421 {79} x^2+e = 9 for x = T + 0.000151461 {63} x^2+pi = 4^phi for x = T  6.4912e05 {82} 1/(xsqrt(3)) = 7"/6 for x = T + 3.52319e05 {94} x (x2) = sqrt(ln(5)) for x = T + 1.51245e05 {91} x (x+pi) = e^e1 for x = T  1.30526e05 {96} . . .Add the s option to get answers with only one x on the left side of the equation. Since there may sometimes be more than one x in each equation, this cannot "solve" all results, but it works on most of them:
ries l 2.50618414558877 s Your target value: T = 2.50618414558877 mrob.com/ries x = 5/2 for x = T  0.00618415 {50} x = e^3/8 for x = T + 0.00450797 {67} x = sqrt(2 pi) for x = T + 0.000444129 {55} x = pisqrt(cospi(1/e)) for x = T + 0.000386421 {85} x = sqrt(9e) for x = T + 0.000151461 {64} x = sqrt(4^phipi) for x = T  6.4912e05 {83} x = 1/7"/6+sqrt(3) for x = T + 3.52319e05 {93} x = sqrt(ln(5))/(x2) for x = T + 1.51245e05 {92} x = (e^e1)/(x+pi) for x = T  1.30526e05 {97} . . .Elementary Numbers
Repeating part of the previous quote from Chow:
[...] [by current usage, the term] "elementary numbers"
[refers to all] numbers that can be specified implicitly as well as
explicitly by exponential, logarithmic, and algebraic operations.
 Chow 1998 [4]
"Implicitly" refers to numbers that are defined in terms of an equation that may or may not be solvable into a closedform number. This includes such things as the roots of x^{x}=7 and x+e^{x}=0. This corresponds exactly to what you get from ries with no options at all:
ries 2.50618414558877 Your target value: T = 2.50618414558877 mrob.com/ries 2 x = 5 for x = T  0.00618415 {49} 8 x = e^3 for x = T + 0.00450797 {66} x^2 = 2 pi for x = T + 0.000444129 {55} x^x = 1+9 for x = T  8.88178e16 {69} (Stopping now because best match is within 2.23e15 of target value.)Since there may sometimes be more than one x in each equation, the s option cannot "solve" all results, but it works on most of them:
ries 2.50618414558877 s Your target value: T = 2.50618414558877 mrob.com/ries x = 5/2 for x = T  0.00618415 {50} x = e^3/8 for x = T + 0.00450797 {67} x = sqrt(2 pi) for x = T + 0.000444129 {55} x = x"/(1+9) for x = T  8.88178e16 {70} (Stopping now because best match is within 2.23e15 of target value.)First page . . . Forward to page 3 . . . Last page (page 6)
Contents: ries overview Benchmarks History Stupid Math Tricks Semiserious Math Tricks Links and miscellaneous
s.11