Namaste. This is wrt the TOMS748 math root finding implementation: Given that `if(fa == 0)` is handled at: https://github.com/boostorg/math/blob/develop/include/boost/math/tools/toms7... … and the function returns in case of the above condition, it is not clear to me what the need is for the `if (fa != 0)` at: https://github.com/boostorg/math/blob/develop/include/boost/math/tools/toms7... Note that I do not find the condition being applied at the SciPy implementation of this algorithm at: https://github.com/scipy/scipy/blob/v1.6.0/scipy/optimize/zeros.py#L1220 Now I also note similar checks at: https://github.com/boostorg/math/blob/develop/include/boost/math/tools/toms7... https://github.com/boostorg/math/blob/develop/include/boost/math/tools/toms7... … but regarding those lines, while I can understand the need for checking there after more bracketing work is done, it is not clear to me why `(fa == 0)` is alone checked for, and not `(fb == 0)` as well. I would have thought the algorithm is not biased towards a or b. Indeed, in the last steps from: https://github.com/boostorg/math/blob/develop/include/boost/math/tools/toms7..., … both the conditions are checked for, which is what I would expect even in the intervening steps. Now the lines seem to have originated in the very first commit implementing this algorithm: https://github.com/boostorg/math/commit/79a8199f9c26ba353fb52ec4543f75ffc2a8... … but I do not see a way to contact the author jzmaddock other than posting to this list, so I hope someone/they see here and reply. Thanks! -- Shriramana Sharma ஶ்ரீரமணஶர்மா श्रीरमणशर्मा 𑀰𑁆𑀭𑀻𑀭𑀫𑀡𑀰𑀭𑁆𑀫𑀸
On 26/01/2021 15:46, Shriramana Sharma via Boost-users wrote:
Namaste.
This is wrt the TOMS748 math root finding implementation:
Given that `if(fa == 0)` is handled at:
https://github.com/boostorg/math/blob/develop/include/boost/math/tools/toms7...
… and the function returns in case of the above condition, it is not clear to me what the need is for the `if (fa != 0)` at:
https://github.com/boostorg/math/blob/develop/include/boost/math/tools/toms7...
You're quite right - it's superfluous, will fix.
Now I also note similar checks at:
https://github.com/boostorg/math/blob/develop/include/boost/math/tools/toms7... https://github.com/boostorg/math/blob/develop/include/boost/math/tools/toms7...
… but regarding those lines, while I can understand the need for checking there after more bracketing work is done, it is not clear to me why `(fa == 0)` is alone checked for, and not `(fb == 0)` as well. I would have thought the algorithm is not biased towards a or b.
When bracket() is called, it updates either fa or fb with the next value (fc), and when fc is zero then fa is always set to zero, and the result is always a. So checking fb == 0 is unnecessary after a bracket() call.
Indeed, in the last steps from:
https://github.com/boostorg/math/blob/develop/include/boost/math/tools/toms7...,
… both the conditions are checked for,
Somewhat different situation - at this point the loop has terminated, and we're just tightening up our interval in the case that one of a or b is right on the root. This is a nicety not required by the algorithm as such, and indeed the fb == 0 branch *may* be superfluous, but I would want to think very carefully indeed before changing it ;) Best, John Maddock. -- This email has been checked for viruses by Avast antivirus software. https://www.avast.com/antivirus
Thanks for replying. Will ask here if I have any further questions. On Wed, Jan 27, 2021 at 6:38 PM John Maddock via Boost-users <boost-users@lists.boost.org> wrote:
On 26/01/2021 15:46, Shriramana Sharma via Boost-users wrote:
Namaste.
This is wrt the TOMS748 math root finding implementation:
Given that `if(fa == 0)` is handled at:
https://github.com/boostorg/math/blob/develop/include/boost/math/tools/toms7...
… and the function returns in case of the above condition, it is not clear to me what the need is for the `if (fa != 0)` at:
https://github.com/boostorg/math/blob/develop/include/boost/math/tools/toms7...
You're quite right - it's superfluous, will fix.
Now I also note similar checks at:
https://github.com/boostorg/math/blob/develop/include/boost/math/tools/toms7... https://github.com/boostorg/math/blob/develop/include/boost/math/tools/toms7...
… but regarding those lines, while I can understand the need for checking there after more bracketing work is done, it is not clear to me why `(fa == 0)` is alone checked for, and not `(fb == 0)` as well. I would have thought the algorithm is not biased towards a or b.
When bracket() is called, it updates either fa or fb with the next value (fc), and when fc is zero then fa is always set to zero, and the result is always a. So checking fb == 0 is unnecessary after a bracket() call.
Indeed, in the last steps from:
https://github.com/boostorg/math/blob/develop/include/boost/math/tools/toms7...,
… both the conditions are checked for,
Somewhat different situation - at this point the loop has terminated, and we're just tightening up our interval in the case that one of a or b is right on the root. This is a nicety not required by the algorithm as such, and indeed the fb == 0 branch *may* be superfluous, but I would want to think very carefully indeed before changing it ;)
Best, John Maddock.
-- This email has been checked for viruses by Avast antivirus software. https://www.avast.com/antivirus
_______________________________________________ Boost-users mailing list Boost-users@lists.boost.org https://lists.boost.org/mailman/listinfo.cgi/boost-users
-- Shriramana Sharma ஶ்ரீரமணஶர்மா श्रीरमणशर्मा 𑀰𑁆𑀭𑀻𑀭𑀫𑀡𑀰𑀭𑁆𑀫𑀸
https://github.com/boostorg/math/blob/develop/include/boost/math/tools/toms7... Couldn't `if(boost::math::sign(fa) * boost::math::sign(fb) > 0)` be simplified to `if (fa * fb > 0)` or is it just a case of being generic and Boost-ish templatable? https://github.com/boostorg/math/blob/develop/include/boost/math/tools/toms7... Is this test of `if((b - a) < 2 * tol * a)` where tol is 2×epsilon meaningful given that eps_tolerance has a minimum of 4×epsilon? I would have thought that tol(a, b) will catch this before it ever arrives here. Or is it needed because that is relative tolerance and this is absolute? On Wed, Jan 27, 2021 at 9:47 PM Shriramana Sharma <samjnaa@gmail.com> wrote:
Thanks for replying. Will ask here if I have any further questions.
On Wed, Jan 27, 2021 at 6:38 PM John Maddock via Boost-users <boost-users@lists.boost.org> wrote:
On 26/01/2021 15:46, Shriramana Sharma via Boost-users wrote:
Namaste.
This is wrt the TOMS748 math root finding implementation:
Given that `if(fa == 0)` is handled at:
https://github.com/boostorg/math/blob/develop/include/boost/math/tools/toms7...
… and the function returns in case of the above condition, it is not clear to me what the need is for the `if (fa != 0)` at:
https://github.com/boostorg/math/blob/develop/include/boost/math/tools/toms7...
You're quite right - it's superfluous, will fix.
Now I also note similar checks at:
https://github.com/boostorg/math/blob/develop/include/boost/math/tools/toms7... https://github.com/boostorg/math/blob/develop/include/boost/math/tools/toms7...
… but regarding those lines, while I can understand the need for checking there after more bracketing work is done, it is not clear to me why `(fa == 0)` is alone checked for, and not `(fb == 0)` as well. I would have thought the algorithm is not biased towards a or b.
When bracket() is called, it updates either fa or fb with the next value (fc), and when fc is zero then fa is always set to zero, and the result is always a. So checking fb == 0 is unnecessary after a bracket() call.
Indeed, in the last steps from:
https://github.com/boostorg/math/blob/develop/include/boost/math/tools/toms7...,
… both the conditions are checked for,
Somewhat different situation - at this point the loop has terminated, and we're just tightening up our interval in the case that one of a or b is right on the root. This is a nicety not required by the algorithm as such, and indeed the fb == 0 branch *may* be superfluous, but I would want to think very carefully indeed before changing it ;)
Best, John Maddock.
-- This email has been checked for viruses by Avast antivirus software. https://www.avast.com/antivirus
_______________________________________________ Boost-users mailing list Boost-users@lists.boost.org https://lists.boost.org/mailman/listinfo.cgi/boost-users
-- Shriramana Sharma ஶ்ரீரமணஶர்மா श्रीरमणशर्मा 𑀰𑁆𑀭𑀻𑀭𑀫𑀡𑀰𑀭𑁆𑀫𑀸
-- Shriramana Sharma ஶ்ரீரமணஶர்மா श्रीरमणशर्मा 𑀰𑁆𑀭𑀻𑀭𑀫𑀡𑀰𑀭𑁆𑀫𑀸
Hello. Another point I note: https://github.com/boostorg/math/blob/develop/include/boost/math/tools/toms7... ``` else if(c <= a + fabs(a) * tol) { c = a + fabs(a) * tol; } else if(c >= b - fabs(b) * tol) { c = b - fabs(b) * tol; } ``` If the intent is that a + fabs(a) * tol and b - fabs(b) * tol are the values closest to a and b allowable for c, shouldn't the tests above them test only for < and > and not <= and >=? I mean if the variable is already equal to the allowed value, then why compute the value again and assign it to the variable?
Another question: https://github.com/boostorg/math/blob/develop/include/boost/math/tools/toms7... Can you elucidate which step from the original paper this quadratic step corresponds to? IIANM the whole implementation is based on the algorithm 4.2 of the paper and not 4.1, because e and fe don't figure in 4.1 and the secant step on L347 is 4.2.1 same as 4.1.1. But I don't see a separate compulsory quadratic step after 4.2.1 other than the quadratic/ipzero branch at 4.2.3, however this code seems to have such a compulsory step ie a step without the option of ipzero. L380 starts the branch at 4.2.3 and L402 starts the branch at 4.2.5, but apart from that I don't see anything in the steps given in the paper to indicate a non-branching quadratic step beforehand. Or maybe I'm missing something. Please clarify. Thanks!
On Thu, Jan 28, 2021 at 5:57 PM Shriramana Sharma <samjnaa@gmail.com> wrote:
https://github.com/boostorg/math/blob/develop/include/boost/math/tools/toms7...
Can you elucidate which step from the original paper this quadratic step corresponds to?
On more careful examination I see that 4.1.3 and 4.2.3 of the original paper have a n == 2 option, which would lead to a compulsory quadratic evaluation. Sorry about that. My apologies. Would like to have your feedback on the rest of the questions though…
On Thu, Jan 28, 2021 at 10:11 PM Shriramana Sharma <samjnaa@gmail.com> wrote:
On Thu, Jan 28, 2021 at 5:57 PM Shriramana Sharma <samjnaa@gmail.com> wrote:
https://github.com/boostorg/math/blob/develop/include/boost/math/tools/toms7...
Can you elucidate which step from the original paper this quadratic step corresponds to?
On more careful examination I see that 4.1.3 and 4.2.3 of the original paper have a n == 2 option, which would lead to a compulsory quadratic evaluation.
But still as per the paper, the step after such a compulsory quadratic step would branch into a quadratic_interpolate with count = 3, but in this implementation such a step is missed. I have no idea whether this will lead to inaccuracy, since further steps would definitely refine the bracket, but just placing this on record here. I was also thrown a bit by the redefinition of max_iter as “The maximum number of function invocations to perform in the search for the root”. To my understanding an iteration is defined by the loop in the algorithm, and the paper speaks of “3 or 4 function evaluations per iteration”. I realize I'm quibbling at semantics, and one may be free to either limit the number of iterations or function calls (mostly the former is done I think) but it may be better to rename the variable to max_funcalls or such to clarify its purpose and highlight the deviation from the original paper. Thanks, and please do respond when you can. -- Shriramana Sharma ஶ்ரீரமணஶர்மா श्रीरमणशर्मा 𑀰𑁆𑀭𑀻𑀭𑀫𑀡𑀰𑀭𑁆𑀫𑀸
participants (2)
-
John Maddock -
Shriramana Sharma