Find formula from values

Is there any "algorithm" or steps to follow to get a formula from a table of values.

Example:

Using this values:

X                Result
1                3
2                5
3                7
4                9


I'd like to obtain:

Result = 2X+1


Edit

Maybe using excel?

Edit 2

It is not going to be always a polynomial and it may have several parameters (I think 2).

• Unless you have an assumed functional form, your problem is insoluble. Nov 23 '10 at 12:44
• @J.M.: I thought so too - but then I found the tool mentioned below! Nov 23 '10 at 13:08

The best tool for doing this is that impressive piece of software: http://www.nutonian.com/products/eureqa/

Edit: For your abovementioned very easy example, even WA will find the right formula: http://www.wolframalpha.com/input/?i=3,+5,+7,+9,...

Edit 2: Unfortunately Nutonian was bought by DataRobot and their product is no longer freely available (not even for academic use). Yet in many cases other solutions exist, see e.g. my blog post here: Symbolic Regression, Genetic Programming… or if Kepler had R.

• The "using building blocks" portion of the software is assuming a functional form (or a family of them as the case may be)... my point is that one cannot just pull a formula from his arse without insight on where the data came from! Nov 23 '10 at 13:12
• @J.M.: Ok, now I understand what you mean - I agree with that! Nov 23 '10 at 13:14
• ...and more or less, Wolfram Alpha/ Mathematica did exactly what I'm doing in my answer. InterpolatingPolynomial[] uses the Newton divided-difference formula in its implementation. Nov 23 '10 at 13:15
• I didn't know that - interesting! Thank you Nov 23 '10 at 13:17
• The link is dead. Did you mean nutonian.com/products/eureqa ? Oct 3 '16 at 15:15

An easier method (assuming that the values were generated by a polynomial) would be to note that successive divided differences $\frac{y_{i+1}-y_i}{x_{i+1}-x_i}$ are constant and equal to 2; thus your function is of the form $y=2x+c$. The constant $c$ is then determined by replacing both $x$ and $y$ with appropriate values, and then solving for $c$.

I have made a sample in my C# genetic algorithms library, GeneticSharp, that solves your question.

The sample called "Function Builder" receives the function's arguments values and the expected result, then, using genetic algorithms, it try to discover the math function.

Take a look:

• It would be useful if there were binary downloads to get this console tool running with latest Mac OS X. Didn't found any link :-( Mar 19 '16 at 15:48
• Is there repo or source codes for this please? Jul 24 '18 at 20:26
• @PatrikValkovič yes, here: github.com/giacomelli/GeneticSharp/blob/master/src/… Jul 24 '18 at 22:41

One way to obtain the desired relationship is to use the regression analysis. In the case that you know what form of the relationship you are expecting, say you know that $f(x) = a * x + b$ it is very simple to find the parameters $a$ and $b$ (see for example). In the case that you don't know what form your formula may take, it is common to use the nonparametric regression techniques.

The Online Polynomial Regression solver http://www.xuru.org/rt/PR.asp finds the correct function and finds a function minimizing the error, when there is no exact polynomial.

The Regression Tools http://xuru.org/rt/TOC.asp also provide non-polynomial solvers.

(This is way too complicated to use it here, one can always expect a desired polynomial that fits all the points.)

One of the possible algorithm is Langrange Interpolating Polynomial.

For a polynomial $P(n)$ of degree $(n-1)$ passes through $n$ points: $$(x_1,y_1=f(x_1)),\ldots,(x_n,y_n=f(x_n))$$

We have

$$P(x)=\sum_{j=1}^n\left[y_j\prod^n_{k=1,k\neq j}\frac{x-x_k}{x_j-x_k}\right]$$

Explicitly, $$P(x)=\frac{y_1(x-x_2)\cdots(x-x_n)}{(x_1-x_2)\cdots(x_1-x_n)}+ \frac{y_2(x-x_1)(x-x_3)\cdots(x-x_n)}{(x_2-x_1)(x_2-x_3)\cdots(x_2-x_n)}+\ldots +\\\frac{y_n(x-x_1)\cdots(x-x_{n-1})}{(x_n-x_1)\cdots(x_n-x_{n-1})}$$

In this context,

\begin{align} P(n)&=\frac{3(n-2)(n-3)(n-4)}{(1-2)(1-3)(1-4)}+\frac{5(n-1)(n-3)(n-4)}{(2-1)(2-3)(2-4)}\\ &+\frac{7(n-1)(n-2)(n-4)}{(3-1)(3-2)(3-4)}+\frac{5(n-1)(n-2)(n-3)}{(4-1)(4-2)(4-3)} \end{align}

Simplify and we get

$$P(n)=-\frac13(2 n^3-12 n^2+16 n-15)$$

Whenever I am asked to find a formula from a range of values, I always use difference patterns.

Do with the data given:

x____________1_______2________3________4

y____________3_______5________7________9

$1^{st}$ diff:___________+2______+2________+2

I know that with the general formula $y = mx + c$ the difference pattern is:

x____________1_______2________3________4

y__________m + c____2m + c____3m + c_____4m + c

$1^{st}$ diff:_________+m______+m _______+m

So the first difference pattern is equal to $m$, i.e. $m = 2$.

I can then use $y(1) = m + c$ to find $c$

where $y(1) = 3$, and $m = 2$

$3 = 2 + c$

therefore $c = 1$

and putting it all together we get $y = 2x + 1$

You can use further difference patterns for polynomials such as $2^{nd}$ diff for $x^2$, $3^{rd}$ diff for $x^3$, etc. but note that for an exponential function you will need to look at a common ratio, rather than a difference pattern.

Here is a video posted to the SmarterEveryDay YouTube channel that shows how one guy uses nothing but circles and the Fourier Series to create any function: