-
Notifications
You must be signed in to change notification settings - Fork 69
New issue
Have a question about this project? Sign up for a free GitHub account to open an issue and contact its maintainers and the community.
By clicking “Sign up for GitHub”, you agree to our terms of service and privacy statement. We’ll occasionally send you account related emails.
Already on GitHub? Sign in to your account
Golden section search #2652
Golden section search #2652
Conversation
} | ||
} | ||
|
||
return Barycentre<Argument, double>({lower, upper}, {1, 1}); |
There was a problem hiding this comment.
Choose a reason for hiding this comment
The reason will be displayed to describe this comment to others. Learn more.
This feels a little bit cheesy, but OK.
Can you compute an upper bound on the distance (in ULPs) between lower
and upper
, and document the error of the result accordingly in the header?
There was a problem hiding this comment.
Choose a reason for hiding this comment
The reason will be displayed to describe this comment to others. Learn more.
I could probably prove that lower
and upper
are a few ULPs apart when the loop exits.
But that is irrelevant, see my comment in the test. Near its extremum the function is constant over tens of millions of ULPs. So we don't really care how close lower
and upper
are to each other. We would want to know how close they are to the extremum, but that's mostly unknowable.
The real solution here is to use Brent's method, which approximates the function by a parabola, and therefore gets a much better determination of its extremum.
@@ -53,6 +56,37 @@ TEST_F(RootFindersTest, SquareRoots) { | |||
} | |||
} | |||
|
|||
TEST_F(RootFindersTest, GoldenSectionSearch) { |
There was a problem hiding this comment.
Choose a reason for hiding this comment
The reason will be displayed to describe this comment to others. Learn more.
Add a test with a function that has multiple extrema on the search interval.
There was a problem hiding this comment.
Choose a reason for hiding this comment
The reason will be displayed to describe this comment to others. Learn more.
Done.
Will be needed for #2400.