current community

your communities

more stack exchange communities

Stack Exchange
tour help
Take the 2-minute tour ×
Programming Puzzles & Code Golf Stack Exchange is a question and answer site for programming puzzle enthusiasts and code golfers. It's 100% free, no registration required.
up vote 2 down vote favorite
1

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?

share|improve this question
    
Does "ignore parsing issues" mean that we can assume the polynomial data is in any convenient form? E.g. can I accept the example polynomial as a list of coefficients [-12, 0, 0, 4, 0, 0, 6]? –  DLosc May 26 at 5:49
    
What should be the output for polynomials whose minimum value is negative infinity, such as x^3? –  DLosc May 26 at 5:50
    
@DLosc yes that is acceptable, and I guess I should exclude those that don't have a finite number. Let's assume they exist in the space of R2, and are rational numbers. –  ibanez221 May 26 at 5:59
    
Is a local minimum acceptable ? –  Mig May 26 at 6:28
    
@Mig yes, but ideally the program will find all minima and select the smallest one (not just magnitude, so -100 is lower than -2). –  ibanez221 May 26 at 6:32

1 Answer 1

up vote 5 down vote

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
share|improve this answer
1  
I think you can do the polynomial evaluation shorter recursively: A=lambda p,x:p>[]and p[0]+x*A(p[1:],x). –  xnor May 26 at 11:39
    
How do you guarantee that Newton's method converges? –  Peter Taylor May 26 at 17:44
1  
@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. –  primo May 26 at 23:58
    
I was more interested in the case where there is a local minimum, but Newton's method goes in circles. –  Peter Taylor May 27 at 7:04

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.