There is a set of points on the plane, (for simplicity, suppose that these are points with x coordinates from 0 to n)
For example, a = [0, 1, 4, 9] , where a[x] = f(x) .

It is necessary to write an algorithm that would classify the function of a chart constructed from these points.
I have already written the linear function classifier:

 def is_linear(a): difference = a[1] - a[0] for i in range(len(a) - 1): if a[i + 1] - a[i] != difference: return False return True

Now we need a classifier of a power function (well, or at least a quadratic form, y = ax ^ 2 + bx + c)

  • 2
    on a logarithmic scale, the power function will be linear. You can find the most appropriate coefficients using the least squares method ( numpy.polyfit() ). Examples - jfs
  • @jfs, somehow difficult, not? - Qwertiy ♦
  • @Qwertiy what's the difficulty? call a function? polyfit(log(x[x>0]), log(a[x>0]), def=1) - jfs
  • @jfs, why not the answer? - Qwertiy ♦
  • @Qwertiy: the details of the question are not clear (integer / non-integer, exact values ​​/ with noise, valid ranges of arguments, functions, which context). The author of polyfit () may not be needed, but future visitors with a similar problem from the search engine may be useful. - jfs

2 answers 2

The derivative of a quadratic function will be linear. And from cubic - quadratic. And so on. The derivative is represented by the difference of neighboring elements. Since the difference is 1 less than the points, sooner or later the array will be reduced to 2 elements, which are guaranteed to form a linear function, i.e. the algorithm is finite. I note that such a polynomial is called interpolation — for any n points, you can construct a polynomial of degree n-1 passing through all these points.

Here is the code for js, it should be easy to rewrite to python:

 var EPS = 1e-6 function isConstant(a) { if (a.length <= 1) { return true } for (var q=1; q<a.length; ++q) { if (Math.abs(a[q]-a[q-1]) > EPS) { return false } } return true } function getDegree(a) { for (var d=0; ; ++d) { if (isConstant(a)) { return d } for (var q=1; q<a.length; ++q) { a[q-1] = a[q] - a[q-1] } --a.length } } console.log(getDegree([1,2,3,4,5,6,7].map(x => 2*x**3 + x**2 - 12*x + 7)))

    It seems to me very similar to your task, the keyword is the "least squares method" http://www.michurin.net/computer-science/scipy/scipy_least_squares.html