-
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
they're good algorithms for finding a zero of a function Brent #2731
Conversation
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.
First round of review, I'll need to read the papers to review more deeper.
if (f_b == zero) { | ||
return b; | ||
} | ||
CHECK(Sign(f_a) != Sign(f_b)) |
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.
CHECK_NE
.
double const x, | ||
int* const evaluations, | ||
bool const expect_brent_calls) -> double { | ||
double const f_a = -100; |
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 is weird. Comment?
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 is the ϵ < 0.
numerics/root_finders_test.cpp
Outdated
} | ||
// [WG13] define f only on X. We extend it as a step function, returning the | ||
// value for the element of X nearest to the given x. | ||
int j; |
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.
Document how this relates to m
in the paper.
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.
It does not; m
is constant in the paper.
numerics/root_finders_body.hpp
Outdated
b += Abs(d) > δ ? d : δ * Sign(m); | ||
f_b = f(b); | ||
if (Sign(f_b) == Sign(f_c)) { | ||
goto interpolation; |
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 realise that you are trying to stick to the paper, but I am going to claim that two nested loop would read better and, unlike, say, integrators, the control structure is not hard to transform into loops (break
if the signs match, return
if the condition at line 116 is false).
numerics/root_finders_body.hpp
Outdated
p = -p; | ||
Difference<Argument> const δ = 2 * ϵ * Abs(b - Argument{}); | ||
Difference<Argument> const m = 0.5 * (c - b); | ||
if (!(Abs(m) > δ && f_b != zero)) { |
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.
All hail De Morgan!
numerics/root_finders_test.cpp
Outdated
X[k], | ||
X[k - 1], | ||
f_a, | ||
f(X[k - 1], /*evaluations=*/nullptr, /*expect_brent_calls=*/false)); |
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.
One column.
The other Brent method should speed up #2400; implement
zero
before the trickierlocalmin
.