RIES - Find Algebraic Equations, Given Their Solution

Quick Links
RIES Source Code (build instructions in header comment)
License (GPL 2.0)
Manual:
PostScript
Plain ASCII
Source (nroff)

Contents
Overview
Benchmarks
Motivation and History
Stupid Math Tricks
"Classical" Approximations
Mystical Pre-Destiny
Four Fours
Secret Code
A Visit by Dr. Matrix
Semiserious Math Tricks
Finding Exact Solutions
Forgotten Identities
Enlightened Discovery
See Also

Overview

ries is a program that takes any number (for example, 2.5063) and produces a list of equations very much like the following:

bash# ries 2.5063 Your target value: T = 2.5063 www.mrob.com/ries 2 x = 5 for x = T - 0.0063 {49} 8 x = e^3 for x = T + 0.00439212 {66} x^2 = 2 pi for x = T + 0.000328275 {55} x^x = 1+9 for x = T - 0.000115854 {69} (x-1)^2 = tanpi(1/e) for x = T + 0.000108368 {75} x^2+e = 9 for x = T + 3.56063e-05 {63} ln(6) x = sqrt(pi)+e for x = T + 2.73037e-05 {93} x/4+1 = 4,/7 for x = T + 6.24679e-06 {91} ln(sqrt(x)-1) = -(phi/3) for x = T + 1.4647e-06 {97} 1/(1-ln(x)) = (1/e+pi)^2 for x = T - 3.89197e-07 {106} x+e,/4 = 7-sqrt(8) for x = T - 3.26098e-07 {109} x+pi/8 = 8 cospi(phi) for x = T + 3.89451e-08 {111} 1/(2-x)+1 = cospi(7,/phi) for x = T + 6.16902e-09 {116} x+1/e^(1/x) = 5^(e-2) for x = T - 2.25977e-09 {118} x sqrt(phi x) = 2(pi-1/phi) for x = T - 1.71971e-09 {126} (for more results, use the option '-l3') e = base of natural logarithms, 2.71828... cospi(X) = cos(pi * x) ln(x) = natural logarithm or log base e tanpi(X) = tan(pi * x) phi = the golden ratio, (1+sqrt(5))/2 sqrt(x) = square root A,/B = Ath root of B pi = 3.14159... --LHS-- --RHS-- -Total- max complexity: 67 61 128 dead-ends: 2848836 4250702 7099538 CPU time: 0.296 expressions: 228357 318227 546584 distinct: 111700 89860 201560 Memory: 12608KiB Total equations tested: 10037362000 (1.004e+10)

Notice the answers are ordered by increasing closeness to your number. It should also be apparent that the simplest equations come first and the more complex ones later on. ries follows the example of continued fractions — as you go to longer equations, you get a closer approximaion to your number, and each approximation is the closest approximation that is available with an equation of that complexity.

ries is highly customizable. You can have it omit functions and symbols (like the sine and cosine functions, or the symbol for phi, the Golden Ratio) if you don't want it to use them in solutions. You can give it an integer and specify that it limit its search to calculations that come out to be exact integers, and it will figure out the shortest way to construct your number from the digits 1 through 9. If you want easily inverted solutions you can specify that there be only one x on the left-hand side, omitting things like "x-sin(x)". ries can find the simplest way to (for example) express the value 27 using only the digit 4 and the four basic operators plus, minus, times and divide.

ries Profiles

It is common to want to use several ries options together, and to use the same options in many different commands. To facilitate this, ries supports the use of "profiles" specified by the -p option. A profile is a text file containing one or more ries command-line options, with whatever spacing you desire and optional comments delimited by the '#' character. Here is an example:

# old.ries Profile for all the old RIES behaviour --trig-argument-scale 1 # Radians -NT # old RIES had no tangent function -l1 # The default searchlevel was -l1 --significance-loss-margin 15 # There were no sig-loss checks

If this file is in the current directory, a ries command with the option -pold.ries (or --include old.ries) will produce pretty much the same results as ries did prior to 2012.

Benchmarks

ries is also 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 10¹⁰ equations in less than a minute. On a 733-MHz Pentium-III, ries -l4 tested over 1.4×10¹² equations in 62 seconds; on a 2.33-GHz Intel Core 2, the same thing finishes in only 13.5 seconds.

The 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

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.

ries was first created for Linux¹, but is is easily ported to Mac OS X, and nearly any OS with a C compiler. 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.

Stupid Math Tricks

Here are a few cute and/or fun things you can do with ries:

Classical Approximations

The new --min-match-distance option can be used to find approximations to known values without hitting on the exact formula. Combine this with the -N option to avoid using modern functions like sine and logarithm, and you get "classical" approximations. For example, try this command from the ries manual:

ries 3.141592653589 -NpSCTlLeEv^ --min-match-distance 1e-10

The output starts with x=19/6 and x=22/7, the two most common simple fraction approximations for π.

A little bit further is 1/(x-3) = 5 sqrt(2), which turns into the nifty approximation 3+√1/50 = 3+√2/10 = 3.14142135... You can also spot two others that contain "(x-3)" on the left-hand-side: 1/(x-3)+1 = sqrt(8^2+1) and 1/(x-3)-1 = 1/4^2+6, both of which will solve to x = 3 + something.... The second of these is also equivalent to 355/113=3.14159292..., an excellent simple fraction approximant to π.

Fans of the Golden ratio will like x/phi^2 = 1/5+1 which gives 6Φ²/5 = 3.1416407... We also get (x²-8)²=sqrt(√5)+2, which if you solve for x turns into the nested radical approximation:

= 3.14158959... = π - 3.057×10^-6

for related (and more devious) tricks see below...

Mystical Pre-Destiny

Take your phone number and a friend's phone number and insert a decimal point: 123-4567 becomes 123.4567 and 555-1212 becomes 555.1212. Then take the ratio: 555.1212/123.4567 = 4.496485. Put this into ries and pick a formula that can be solved for x (for example, I used x+⁹√π=6-1/e). Solve it for x (in this case getting x=6-1/e-⁹√π), and then multiply the whole thing by the phone number that you originally put in the denominator and you get the other phone number:

(6 - 1/e - ⁹√π) × 123.4567 = 555.121234525

If the answer doesn't have all 7 digits, try another of the formulas that ries gave. If you don't find a nice formula, start with something else, like 5.551212+1.234567 or 5.551212-1.234567, and transform the result in the appropriate way.

Now go to your friend and announce that you have found the mystic formula that links their phone number to yours. For extra credit, write the formula in an old school notebook and claim it was given as a problem in class long before you met.

Four Fours

At one time this type of problem was popular: How do you reach various values using four 4's and any number of symbols (for example: 44/44 = 1, 4/4+4/4 = 2, (4+4+4)/4 = 3, etc.). Solutions of a similar type of problem can be found with a command like:

ries '-S4+-*/' -Ox 17
x-4*4 = 4/4 (exact match)

which corresponds to the solution 4/4+4×4 = 17. Note that -S4+-*/ specifies the "symbols" that can be used in solutions, the quotes prevent the shell from performing filename globbing, and -Ox tells ries that x should only appear once in each equation. Also, although this example happens to have four 4's, ries cannot be told how many 4's to use. So, although its answers for 3, 5, 6, 9 and 17 yield equations with four 4's, other numbers give more or fewer.

Secret Code

Convert letters to numbers, generate an equation with ries, convert to an expression, then transmit to your friends. They use a calculator as the "secret decoder ring". Not very efficient, but pretty darn obscure.

Example: Convert "D A V E" to numbers (D=04, A=01, V=22, E=05). Make this to a single number (4.012205). Since we don't care what digits come after that, add another 5. Typing ries 4.0122055 generates the equation sqrt(x^2-5) = 4,/pi+2 (this result has an error term that is less than 5×10^-7, which is the extra '5' we added.) Solving for x gives x=sqrt(5+(sqrt(sqrt(pi))+2)^2). The value is 4.01220579...# which has the needed encoding of "DAVE".

If your friend's calculator does not have a π key or the trig and other scientific functions, exclude things with the -N option, for example, ries 4.0122055 -NSCTplLfveE^.

A Visit by Dr. Matrix

Scientific American maths columnist Martin Gardner often referred to novel ideas and fringe theories attributed to a Dr. Matrix, usually with humorous intent. Perhaps the best known example was Ramanujan's constant, which "Doctor Matrix" claimed to be an integer. We can use ries (perhaps in an April Fool's stunt) to put forth similar claims.

For example, try the command

ries 3.141592653589 -NpSCT -l5

which simply tells ries to find approximations for π without using π itself or the sine and cosine functions. Look at the results and pick one you like, then turn it around into something you can type in a calculator. I like 1/(x-3)-1/2 = e sqrt(2)+e because it contains "x-3" which means that when you solve for x the formula will start with "x = 3 + ...". Then blog or text to your friends:

My friend Irving said to try this on my TI-89: 3+2/(1+e×(2+√8)). What do you get?

The Return of Dr. Matrix

For a little more sophistication, try the command:

ries 3.141592653589 --min-match-distance 1e-10

This tells ries to find formulas for π so long as the solution isn't within 10^-10 of your given value. Since π is not excluded as a symbol, this gives us formulas for π that use π as part of the formula, but a direct approach like x=π is not allowed because we gave the --min-match-distance option.

Among the output of this example is the equation x√π+1 = e³/π. Substitute x for any π's in the formula and find ways to rearrange it that have just one x on the left-hand side. One arrangement, namely x=(e⁶/(x+1))^(1/4), happens to converge (but it does not converge on π). Use it in a joke blog article:

Dr. Matrix visited me early last April. He claimed to have found an interesting converging iterative formula. Start with any value for x, such as 17 (the doctor's favourite number). Then calculate the value of the formula

Use the result as a new value for x, and repeat. Dr. Matrix told me that if I continue this process several more times, I would get a recognizable result. He plans to publish a proof of this remarkable formula in the Journal of Improbable Research later this year.

I tried this out, using my trusty SR-50 scientific calculator. Starting with 17 in the place of x in the formula, add 1, hit the = sign (18: so far, so good), then use the 1/x key to get the reciprocal, and multiply this by e⁶ (using the e^x key). Then press the √x (square root) key twice. I get:

5.603177687

Using this new value in the place of x, repeat the formula again, and so on:

2.175823167

3.357203326

3.101985520

3.149148874

You might want to try this yourself. The digits eventually settle down and should be familiar to most veteran readers. What is going on here?

Semiserious Math Tricks

Finding Exact Solutions (Newton's Method)

Because ries uses derivatives to report how far a match deviates from exactness, you can use it to iterate Newton's Method. Suppose you know that the cube root of 3 starts with the digits 1.442, and want to find more digits. ries 1.442 yields the result:

x^3 = 3 for X = T + 0.00024957 {51}

To get a better approximation, add 1.442 and 0.00024957:

ries 1.44224957
(other answers not shown)
x^3 = 3 for x = T + 3.07408e-10 {51}

Then add 3.07408×10^-10 (notice you have to add a zero):

ries 1.442249570307408
(other answers not shown)
x^3 = 3 for x = T + 2.22045e-16 {51}

(and so on...)

ries uses about 16 digits in its internal calculations, so this is about as precise as you can get. The actual value of the cube root of 3 (to 25 digits) is 1.4422495703074083823216383... Although this specific example is a case of extreme computational overkill, the same method can be used for things that cannot be computed directly, such as the value of x for which x^x=10.

Forgotten Identities

If you're like most people who took Trigonometry in high school, you remember that there was something called "trigonometric identities", but nothing more. Maybe you remember that sine could be turned into cosine somehow, but that's about it.

With ries you can rediscover all the identities, and probably a few more you never knew existed. For this example we'll use a profile called "rad.ries":

# rad.ries: Use trigonometry functions in radians --trig-argument-scale 1 # radians -NLleEv # No log, ln, e, e^x or arbitrary roots

Using a calculator (or a command like ries -prad.ries 1 --eval-expression 1S) you can find out the sine of 1 radian, which is 0.841470984807897. Naturally, if you give ries this number, it will tell you:

ries -prad.ries 0.841470984807897 x = sin(1) for x = T - 4.44089e-16 {38}

We want to discover other ways to get the same value without using the sine function. To do this we simply tell ries that sin() is not allowed using the -NS option:

ries -prad.ries 0.841470984807897 -NS x/cos(1) = tan(1) for x = T - 4.44089e-16 {66}

So ries has told us that our number x (which we know to be the sine of 1) divided by the cosine of 1 is equal to the tangent of 1. This is our first identity: sin(x)/cos(x) = tan(x).

Let's find another one: exclude the tangent function too:

ries -prad.ries 0.841470984807897 -NST x^2-1 = -(cos(1)^2) for x = T - 4.44089e-16 {78}

Move things around a bit with a little algebra, and this tells us that sin(1)² + cos(1)² = 1, which generalizes into another identity: sin²x+cos²x=1. (The square of a trig function is usually written "sin²x" rather than "sin(x)²" or "(sin(x))²" because the latter is a bit cluttered and the other might be confused with "sin(x²)").

Enlightened Discovery

I wrote a simple routine to compute the Lanczos approximation for the Gamma function using the simplest set of Lanczos coefficients I could find. It gave me the following approximate values:

Gamma(0.5) ≅ 1.772453850902053
Gamma(1.0) ≅ 1.000000000000000
Gamma(1.5) ≅ 0.886226925452798
Gamma(2.0) ≅ 1.000000000000000
Gamma(2.5) ≅ 1.329340388179131
Gamma(3.0) ≅ 2.000000000000000
Gamma(3.5) ≅ 3.323350970447838
Gamma(4.0) ≅ 5.999999999999997
Gamma(4.5) ≅ 11.631728396567436
Gamma(5.0) ≅ 23.999999999999993
Gamma(5.5) ≅ 52.342777784553668
Gamma(6.0) ≅ 119.999999999999872
Gamma(6.5) ≅ 287.885277815044162
Gamma(7.0) ≅ 719.999999999998863

The crudeness of the Lanczos approximation can be seen in the integer arguments: Gamma(4.0) should be exactly 3! which is 6. Similar errors are seen in Gamma(5.0) and higher.

I already knew each of the following things about the Gamma function:

Gamma(x) is equal to the Factorial of x-1 (for any positive integer x),

Gamma(x+1) is equal to x times Gamma(x) (for all x),

Gamma(x+1/2) has an exact formula that uses π,

and I wanted to figure out the exact formula involving π, but just for fun, I wanted to do it without applying the induction formula Gamma(x+1) = x Gamma(x).

Using ries to look at the half-integer arguments:

ries 1.772453850902053 x^2 = pi for x = T + 3.46301e-12 {38} ries 0.886226925452798 2 x = sqrt(pi) for x = T - 4.00791e-14 {55} ries 1.329340388179131 x/sqrt(pi) = 3/4 for x = T + 5.77316e-15 {79} ries 3.323350970447838 x/sqrt(pi) = 2-1/8 for x = T + 3.9968e-15 {87} ries 11.631728396567436 x/sqrt(pi)+1 = (3-1/4)^2 for x = T + 1.24345e-14 {109} ries -l3 52.342777784553668 x/(1-1/8^2) = 5*6 sqrt(pi) for x = T - 1.49214e-13 {136}

In some cases ries puts the √π on the left side, in other cases on the right. Everything else amounts to a simple ratio of integers: for example, "x/sqrt(pi) = 2-1/8" is x/√π = 15/8 or x = 15√π/8. Solving them all for x, getting the fractions into reduced form, and factoring the numerator of each fraction, we get:

Gamma(1/2) = √π
Gamma(3/2) = √π / 2
Gamma(5/2) = 3 √π / 4
Gamma(7/2) = 5×3 √π / 8
Gamma(9/2) = 7×5×3 √π / 16
Gamma(11/2) = 9×7×5×3 √π / 32

the pattern for Gamma(n+1/2) is then easy to see. The general formula is:

Gamma(n+1/2) = (2n-1)!! √π / 2ⁿ

using the Double factorial to get the products of odd numbers (Sloane's A001147).