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 180-MHz machine. Such a machine could easily test over 1010 equations in less than a minute. On a 733-MHz Pentium-III, ries -l4 tested over 1.4×1012 equations in 62 seconds; on a 2.33-GHz 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

level equations memory time
-l0.0 79487660 1.125 MiB 0.03s
-l0.5 251038899 2.000 MiB 0.05s
-l1.0 829353000 3.562 MiB 0.10s
-l1.5 2901779280 6.625 MiB 0.21s
-l2.0 9950377520 12.25 MiB 0.45s
-l2.5 33038198379 22.25 MiB 1.03s
-l3.0 111380226936 41.06 MiB 2.21s
-l3.5 378637262754 75.12 MiB 5.04s
-l4.0 1278241441568 138.8 MiB 11.3s
-l4.5 3413645169984 226.4 MiB 21.5s
-l5.0 14873617111876 471.9 MiB 56.0s
-l5.5 39982521358250 773.3 MiB 1m 46.0s
-l6.0 178259475271954 1.593 GiB 4m 31.6s
-l6.5 480694547629890 2.615 GiB 8m 26.2s
-l7.0 1664959882602016 4.891 GiB 18m 16s
-l7.5 5740777527022706 9.033 GiB 41m 43s
-l8.0 12149489523059625 14.08 GiB 1h 10.8m

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)

machine time
333 MHz Intel Celeron 24.4 s
800-MHz PowerPC G4 (PC133 DRAM) 14.3 s
800-MHz PowerPC G4 (PC2100 DDR SRAM) 12.8 s
2 GHz PowerPC G5 (PC3200 DDR SRAM) 6.6 s
1.83-GHz Core 2 Duo (PC2-5300 DDR2 SDRAM) 3.59 s
2.33-GHz Core 2 Duo (PC2-5300 DDR2 SDRAM) 2.72 s
Xeon E5520 at 2.27 GHz (PC3-8500 DDR3 ECC SDRAM) 2.19 s
Core i7-2720QM at 3.3 GHz (PC3-10600 DDR3 SDRAM) 1.60 s

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 like-minded 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 equation-generator within about 2 weeks (Feb 7th through 21st, 2000).

The program had its own page at mrob.com/ries/index.html at least as early as Aug 18th 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
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
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
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?
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 closed-form 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 Aleph0 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 "breadth-first" manner, starting with the shortest paths and gradually extending the boundaries of explored space. 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 21/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 T2 = 6.2815... Combining these into an equation gives T2 = 2π, and the solution of that equation is T=√ = 2.5066... which is not exactly the target value 2.5063, but it's a lot closer than 21/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.

Source Code

ries was first created for Linux1, 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


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 www.mrob.com/ries   9 x = 5^6 for x = T + 7.11111 {79} (x-1)/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(x-6) = (9^2+2)^2 for x = T - 0.75 {112} 4(x-7) = (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=56", put in the target number (1729) for x and the left side is 9×1729=15561, and the right-hand-side is 56=15625. This is a near-equality; ries also tells us that if x is 7.11111... (7 1/9) higher, the equation works out: 9×(1729+71/9) = 9×1729+9×7+1 = 15625.

The second solution "(x-1)/3 = (4*6)2" is an exact match, because (1729-1)/3 is 576, which is 242. If you want ries to give you only the exact match for an integer problem, use the option --max-match-distance 0, meaning that no match should be more than 0 from equality:

ries -i 1729 --max-match-distance 0   Only give an 'exact' match (if any) then exit.   Your target value: T = 1729 www.mrob.com/ries   (x-1)/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 www.mrob.com/ries   2 x = 5 for x = T - 0.00618415 {49} 2 x-5 = 1/(9*9) for x = T - 1.13061e-05 {103} 1/(2 x-5) = 9*9-1/4 for x = T + 7.80488e-06 {131} 1/(1/(2-x)+2) = 8(1/9+5) for x = T + 5.67559e-06 {140} 1/(2 x-5) = 9*9-1/8 for x = T - 1.76537e-06 {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 left-hand-side; 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 www.mrob.com/ries   x = 5/2 for x = T - 0.00618415 {50} x = (1/(9*9)+5)/2 for x = T - 1.13061e-05 {103} x = (1/(9*9-1/4)+5)/2 for x = T + 7.80488e-06 {131} x = 2-1/(1/(8(1/9+5))-2) for x = T + 5.67559e-06 {142} x = (1/(9*9-1/8)+5)/2 for x = T - 1.76537e-06 {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 www.mrob.com/ries   2 x = 5 for x = T - 0.00618415 {49} (x/2)^2 = sqrt(sqrt(6)) for x = T - 0.00411734 {78} 4-x = sqrt(sqrt(5)) for x = T - 0.00153293 {77} x-sqrt(2) = sqrt(sqrt(sqrt(2))) for x = T - 0.00146285 {82} x+1/9 = phi^2 for x = T + 0.000738732 {72} x-sqrt(5) = phi/6 for x = T - 0.000443837 {87} . . .

You can also add -s to shift everything to the right-hand-side:

ries -c 2.50618414558877 -s   Your target value: T = 2.50618414558877 www.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 = 4-sqrt(sqrt(5)) for x = T - 0.00153293 {78} x = sqrt(sqrt(sqrt(2)))+sqrt(2) for x = T - 0.00146285 {81} x = phi^2-1/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 x5+x-7=0. -a allows everything allowed by -c, but also allows Nth powers, Nth roots, the trigonometric functions (but only with the argument is a rational multiple of π). Significantly, it allows more than one x on the left-hand-side of the equation, which the above options do not. Here is an example:

ries -a 2.50618414558877   Your target value: T = 2.50618414558877 www.mrob.com/ries   2 x = 5 for x = T - 0.00618415 {49} x+sqrt(3) = phi^3 for x = T - 0.00216698 {82} x-sqrt(2) = 8"/2 for x = T - 0.00146285 {81} x-sqrt(x) = cospi(1/8) for x = T + 0.0011526 {83} x+1/9 = phi^2 for x = T + 0.000738732 {72} . . . x^4-x = 8(3+phi) for x = T + 1.68687e-07 {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 www.mrob.com/ries   x = 5/2 for x = T - 0.00618415 {50} x = phi^3-sqrt(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^2-1/9 for x = T + 0.000738732 {73} . . . x = 4"/(8(3+phi)+x) for x = T + 1.68687e-07 {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 x5+x-3=0); but it still finds an answer for 1.551133518071245... (which is (2+√3)(1/3) ).

Using -a with -Ox and --any-exponent 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 √22).

Chow's "Closed-Form" or "Exponential-Logarithmic" Numbers

In his 1998 paper What is a closed-form number? [4], Timothy Chow describes several definitions of classes of numbers. He starts by describing the difference between "closed-form function" and "closed-form 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 closed-form number rather than a closed-form 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, "closed-form" 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:

Pn(y)xn + ... + P2(y)x2 + P1(y)x + P0(y) = 0

where each of the Pi(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 Exponential-Logarithmic 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 xF and (2) log(x) ∈ F for all nonzero xF, 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 E0 = { 0 }, and for each n > 0 let En be the set of all complex numbers obtained either by applying a field operation to any pair of (not necessarily distinct) elements of E(n-1) or by applying exp or log to any element of E(n-1) [...] E is the union of all En. [...] 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 vE, the following are all in E:
   v2/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(v2-1)/2) )

Using RIES to Search for Chow Closed-Form 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 "Exponential-Logarithmic 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 www.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-pi)^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.4912e-05 {82} sqrt(log_pi(x)) = ln(sqrt(6)) for x = T - 1.39889e-06 {87} tanpi(x-3) = pi-e^4 for x = T + 1.06848e-06 {99} . . .

Since there is only one x in each equation, the -s option resolves all results into a closed-form solution:

ries -Ox 2.50618414558877 -s   Your target value: T = 2.50618414558877 www.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 = pi-sqrt(cospi(1/e)) for x = T + 0.000386421 {85} x = sqrt(9-e) for x = T + 0.000151461 {64} x = sqrt(4^phi-pi) for x = T - 6.4912e-05 {83} x = pi^(ln(sqrt(6))^2) for x = T - 1.39889e-06 {84} tanpi(x-3) = pi-e^4 for x = T + 1.06848e-06 {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 x4+x-3=0 (which can be solved for x), and also the roots of x5-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 √22; however it does not include the roots of xx=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 www.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-pi)^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.4912e-05 {82} 1/(x-sqrt(3)) = 7"/6 for x = T + 3.52319e-05 {94} x (x-2) = sqrt(ln(5)) for x = T + 1.51245e-05 {91} x (x+pi) = e^e-1 for x = T - 1.30526e-05 {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 www.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 = pi-sqrt(cospi(1/e)) for x = T + 0.000386421 {85} x = sqrt(9-e) for x = T + 0.000151461 {64} x = sqrt(4^phi-pi) for x = T - 6.4912e-05 {83} x = 1/7"/6+sqrt(3) for x = T + 3.52319e-05 {93} x = sqrt(ln(5))/(x-2) for x = T + 1.51245e-05 {92} x = (e^e-1)/(x+pi) for x = T - 1.30526e-05 {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 closed-form number. This includes such things as the roots of xx=7 and x+ex=0. This corresponds exactly to what you get from ries with no options at all:

ries 2.50618414558877   Your target value: T = 2.50618414558877 www.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.88178e-16 {69} (Stopping now because best match is within 2.23e-15 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 www.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.88178e-16 {70} (Stopping now because best match is within 2.23e-15 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


Robert Munafo's home pages on HostMDS   © 1996-2014 Robert P. Munafo.   about   contact   Google+   mrob27   @mrob_27
This work is licensed under a Creative Commons Attribution-NonCommercial 2.5 License. Details here
This page was last updated on 2014 Oct 29.
s.11