Skip to content
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

Merged
merged 7 commits into from
Jul 17, 2020
Merged

Conversation

pleroy
Copy link
Member

@pleroy pleroy commented Jul 17, 2020

Will be needed for #2400.

}
}

return Barycentre<Argument, double>({lower, upper}, {1, 1});
Copy link
Member

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?

Copy link
Member Author

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.

@eggrobin eggrobin added the LGTM label Jul 17, 2020
@@ -53,6 +56,37 @@ TEST_F(RootFindersTest, SquareRoots) {
}
}

TEST_F(RootFindersTest, GoldenSectionSearch) {
Copy link
Member

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.

Sorry, something went wrong.

Copy link
Member Author

Choose a reason for hiding this comment

The reason will be displayed to describe this comment to others. Learn more.

Done.

Sorry, something went wrong.

@pleroy pleroy merged commit d78a0ac into mockingbirdnest:master Jul 17, 2020
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment
Labels
Projects
None yet
Development

Successfully merging this pull request may close these issues.

None yet

2 participants