mdbtxt1
mdbtxt2
Proceed to Safety

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 InverseSymbolicCalculator (described on Wikipedia here). 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 an "Online RIES server" (later disabled by my web hosting provider).

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. 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 (see also [5]) 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 (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.

A true bidirectional search requires that the two "search frontiers" eventually meet. ries cannot guarantee that: as already mentioned, only a countable number of solutions could ever be reached by its search. So ries reports close matches, and ensures that each reported result is "closer" than any reported so far.

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 finds two values that are closer than anything it has found so far, it reports an equation that expresses a newer, better approximation to the target.

Since ries is exploring expressions, and its bidirectional search finds two paths that meet somewhere in the middle, 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.

Optimising 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 √7-1 without repeating the calculation of √7.

ries uses a stack-based execution design, but preserving function arguments when they are "popped" off the stack so they can be pushed back on for re-use. To accomplish this I use the "meta-stack" abstraction, so-called 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 "un-push" or "un-pop" 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 one-byte 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, 47 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 1-symbol expressions, then all 2-symbol 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 Linux1, but it also compiles in Mac OS X. 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

Windows Instructions

For Windows 10, 11, or later, the best way to get RIES running is to start by installing the Windows Subsystem for Linux (WSL). Look up instructions online (the specific steps depend on your Windows version and other details). Once you have WSL, then find instructions on how to install a C compiler. Then use it to compile ries.c as you would with any other command-line program.

If you have an older Windows system and the MinGW compiler tools, or with Cygwin, you can try compiling ries.c the normal way you would compile another command-line program.

If you have access to a working Microsoft Visual C (or C++) development system, you can look at the Windows wrapper source file which includes its own instructions.


Approximating Multiple Unknowns

Several readers have suggested that ries be enhanced to consider several unknowns simultaneously.

ries is as fast as it is only because it uses a bidirectional search. It cannot count on the two searches ever "meeting" (there is unlikely to be an exact solution), so ries has to use successive approximation, a technique femiliar to those who have done rational approximation by continued fractions. Anything it finds is given a "closeness rating", and each next answer must be better. It must use derivatives, so that the "closeness" is normalised to be expressed in terms of the "unknown" or "target" value.

For ries to simultaneously consider multiple unknown or "target" values, each new match would embody formula(s) for one or more of the unknowns. The algorithm must consider the derivatives of each formula with respect to each unknown. If there are 2 unknowns, there will be 4 derivatives; if 3 unknowns, there will be 9 derivatives, and so on.

There is a need to take these multiple pieces of information and combine them into a single "closeness" value that can be used to make the successive-refinement bidirectional search work. One technique that does something like this is least squares adjustment with more degrees of freedom than dependencies; an example application is the CODATA physical constants. ries would need to be told how the unknowns are related to each other (for example, b/a is proportional to c2).

I cannot suggest an algorithm for such a task, but I doubt it would bear much resemblance to ries.


Detailed Examples of Restricted-Class 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} (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 mrob.com/ries    (x-1)/3 = (4*6)^2 ('exact' match) {97} (Stopping now because an exact match was found.)

This method was used to create my large table of simplest expressions for integers involving single-digit constants. In that table, everything is given as a single expression, like for 1729, x=8×63+1 instead of (x-1)/3 = (4×6)2. This was done using the --one-sided option.

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 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 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 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 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 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 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 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 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 includes 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 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} (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 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 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 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    Nerdy Math Tricks    Semiserious Math Tricks    Links and miscellaneous


Robert Munafo's home pages on AWS    © 1996-2024 Robert P. Munafo.    about    contact
This work is licensed under a Creative Commons Attribution-NonCommercial 4.0 International License. Details here.
s.30