How to create a computationally cheap function passing through given points?

Question

I am trying to develop a function which goes through the follow points. The function will be calculated on a microprocessor which has 20 mHz.

List of given points:

P1 = (36541  ,120)
P2 = (37811  ,110)
P3 = (39527  ,100)
P4 = (41414  ,90)
P5 = (44475  ,80)
P6 = (48848  ,70)
P7 = (55468  ,60)
P8 = (67241  ,50)
P9 = (103755 ,40)

I allready tried to interpolate the function in geogebra and in Wolfram|Alpha but my result are to complicated to be calculated in a fraction of a second. Cubic or quadratic functions are to inaccurate.

Answer 1

A decent approximation for those points is

$$ \frac{0.0000436715 x^2+20.6277 x+516955}{x-25462.4}. $$

In the comments on hardmath's answer, SimpleMath also gives the points (35891,120),(37141,110),(38197,100),(40259,90),(42541,80),(46356,70),(53179,60)‌​,(66204,50),(102805,40).

An approximation of the same form for these points is

$$ \frac{-0.0000158011 x^2+32.4074 x-156608}{x-27708}, $$

which was found with the Mathematica command

(a x^2 + b x + c)/(x + d) /. FindFit[{{35891, 120}, {37141, 110}, {38197, 100}, {40259, 90}, {42541, 80}, {46356, 70}, {53179, 60}, {66204, 50}, {102805, 40}}, (a x^2 + b x + c)/(x + d), {a, b, c, d}, x]

Answer 2

Probably the simplest is to use a piecewise linear function. Which variable is your input? For regularly spaced data like this (if your input is $y$), you can find which two points you are between easily. Otherwise you can use a binary search to find your place in not more than four compares. You can precompute the line between neighboring points, so if it is between P8 and P9 it is $y-50=10\cdot \frac {x-67421}{103755-67421}$ Of course you can turn that into $y=ax+b$, but I left it that way to show where the numbers come from. THe error then comes from the curvature. Is this good enough? It will be fast.

Answer 3

The Question provides little in the way of context, only that a function is sought to match given points that can be computed quickly by a relatively slow processor. I will indulge myself in some speculation about the missing context.

This problem reminds me of working out a formula for the "time bonus" awarded by a well-known computer game. The faster the solution is found, the greater the bonus.

As here, the data points always involved integer values: time X measured in something like whole seconds vs. bonus points Y that were always a multiple of a small integer.

It is striking that the function appears not only monotone decreasing (for the limited amount of available data), but also that those seemingly erratic input values result in output values that are whole multiples of ten.

The use of integer arithmetic on a slow CPU seems attractive or at least consistent with the stated "performance" goal. In the other "computer game" context, a formula was found of the form:

Y = C * FLOOR(M/X)

where X,Y were the integer input and output respectively, and C,M were (positive) integer parameters that succeeded in exactly fitting all observed data.

For the present Question I found no such simple formula could be made to fit the data exactly, but the following slightly more elaborate rule does:

Y = 10*(FLOOR(170000/(X-20000))+2)

I make no claim that this rule is unique for fitting the given data exactly, but it seems a good place to start in trying to optimize an integer arithmetic formula.

---

Update: In the Comments below the OP asks about fitting an additional data set and expresses a desire to know how such formulas can be obtained.

In many respects the new data set is very similar to the original one. The output values are the same multiples of ten, again appearing in descending order (for an ascending sequence of nine input values). The difference is only which nine input values are given, with slightly smaller values for corresponding outputs.

1st Inputs      2nd Inputs     Outputs
----------      ----------     -------
     36541           35891         120
     37811           37141         110
     39527           38197         100
     41414           40259          90
     44475           42541          80
     48848           46356          70
     55468           53179          60
     67241           66204          50
    103755          102805          40

I wondered if it would be possible to alter the formula given above for the first data set in a way that would simultaneously fit the second data set. The best I found was a pair of formulas that differ only in one of the three parameters (constants).

For the first data set I got this exactly fitting rule:

Y = 10*(FLOOR(86000/(X-27500))+3)

The second data set can then be exactly fit with this rule:

Y = 10*(FLOOR(80000/(X-27500))+3)

Let me briefly sketch how these formulas were found. As previously discussed, these rules by design will only output integer multiples of ten, and the OP's Comments below put this in an electromechanical context.

In my earlier post, I'd used a shift of +2 for the outputs, but I found that +3 worked better with the second data set, and also worked well with the first data set. Thus the problem becomes, after omitting the factor of ten and the shift of +3, how do we get monotone outputs 9,8,7,6,5,4,3,2,1 for the respective inputs?

In other words, knowing that we want N=(Y-3)/10 to be those consecutive digits, I created a pair of spreadsheet columns that compute the respective expressions:

       = (X - offset)*N          = (X - offset)*(N+1)

where X references the respective input values, N is correspondingly 9,...,1, and offset is a constant that I choose to make the resulting columns produce non-overlapping ranges. Ideally the first column would be nearly constant, say less than C, and the entries in the second column would be strictly greater than C (and thus greater than every entry in the first column).

In such a case the expression C/(X - offset) will be more than the respective digit N, but not as much as N+1. Thus a rule of the following form gives an exact fit:

Y = 10 * (FLOOR(C/(X - offset)) + 3)