What is the shortest amount of code that can find the minimum of an inputted polynomial? I realize that you can import packages like Numpy and others, but using only user defined functions, what is the shortest way to do this? For example, if 6x6 + 4x3-12 is entered (ignore parsing issues), what would be the shortest amount of code to find the minimum value?
\$\begingroup\$
\$\endgroup\$
5
1 Answer
\$\begingroup\$
\$\endgroup\$
4
Python - 202 Bytes
D=lambda p:[i*p[i]for i in range(1,len(p))]
A=lambda p,x:p>[]and p[0]+x*A(p[1:],x)
def N(p):f=D(p);s=D(f);x=1.;y=-x;exec'x-=A(f,x)/A(s,x);y-=A(f,y)/A(s,y);'*99;return A(p,x),A(p,y)
print min(N(input()))
11 bytes saved due to @xnor.
Input is taken from stdin, and is expected to be in the following format: [x0, x1, x2, ...]. For example, the sample in the problem description would be entered as [-12, 0, 0, 4, 0, 0, 6].
Functions
D - Calculates the derivative of a polynomial p.
A - Applies a polynomial p to the value x.
N - Uses Newton's Method to calculate local minima/maxima of a polynomial p.
Note: For higher order polynomials, there may be several local minima. In these cases, this function is not guaranteed to find the global minimum.
Sample Usage
$ echo [-12, 0, 0, 4, 0, 0, 6] | python poly-min.py
-12.6666666667
-
1\$\begingroup\$ I think you can do the polynomial evaluation shorter recursively:
A=lambda p,x:p>[]and p[0]+x*A(p[1:],x). \$\endgroup\$xnor– xnor2015-05-26 11:39:05 +00:00Commented May 26, 2015 at 11:39 -
\$\begingroup\$ How do you guarantee that Newton's method converges? \$\endgroup\$Peter Taylor– Peter Taylor2015-05-26 17:44:12 +00:00Commented May 26, 2015 at 17:44
-
1\$\begingroup\$ @PeterTaylor if the first derivative isn't zero anywhere, for example x³ + x, it obviously won't. But this also implies that there isn't a local minimum anywhere, either. \$\endgroup\$primo– primo2015-05-26 23:58:31 +00:00Commented May 26, 2015 at 23:58
-
1\$\begingroup\$ I was more interested in the case where there is a local minimum, but Newton's method goes in circles. \$\endgroup\$Peter Taylor– Peter Taylor2015-05-27 07:04:59 +00:00Commented May 27, 2015 at 7:04
[-12, 0, 0, 4, 0, 0, 6]? \$\endgroup\$