Details

    • Type: Bug Bug
    • Status: Closed
    • Priority: Major Major
    • Resolution: Fixed
    • Affects Version/s: None
    • Fix Version/s: 3.0
    • Labels:
      None

      Description

      The following unit test:

      @Test
      public void testBug() {
          final UnivariateRealFunction f = new UnivariateRealFunction() {
                  @Override
                  public double value(double x) {
                      return Math.exp(x) - Math.pow(Math.PI, 3.0);
                  }
              };
      
          UnivariateRealSolver solver = new RegulaFalsiSolver();
          double root = solver.solve(100, f, 1, 10);
      }
      

      fails with

      illegal state: maximal count (100) exceeded: evaluations
      

      Using "PegasusSolver", the answer is found after 17 evaluations.

      1. ticket631.patch
        7 kB
        Dennis Hendriks

        Issue Links

          Activity

          Hide
          Gilles added a comment -

          Reported by Axel Kramer in MATH-599.

          Show
          Gilles added a comment - Reported by Axel Kramer in MATH-599 .
          Hide
          Gilles added a comment -

          The problem was due to the fact that at some point, the update formula always gave the same value: Nothing was being updated and the loop went on until the number of evaluations was exhausted.

          I've committed a tentative solution in revision 1154614.
          However:

          1. I'm not sure that it doesn't have any adverse side-effects on the bracketing property.
          2. It is quite probably not a pristine "regula falsi" algorithm anymore.

          Please review.

          Anyways, for the function that triggered the problem (see "testIssue631" in "RegulaFalsiSolverTest.java"), the (modified) RegulaFalsiSolver takes 3624 evaluations (versus 17 for PegasusSolver). We should probably add a word of warning in the class Javadoc.

          Show
          Gilles added a comment - The problem was due to the fact that at some point, the update formula always gave the same value: Nothing was being updated and the loop went on until the number of evaluations was exhausted. I've committed a tentative solution in revision 1154614. However: I'm not sure that it doesn't have any adverse side-effects on the bracketing property. It is quite probably not a pristine "regula falsi" algorithm anymore. Please review. Anyways, for the function that triggered the problem (see "testIssue631" in "RegulaFalsiSolverTest.java"), the (modified) RegulaFalsiSolver takes 3624 evaluations (versus 17 for PegasusSolver ). We should probably add a word of warning in the class Javadoc.
          Hide
          Dennis Hendriks added a comment -

          I just got back from a 3 week vacation, so I couldn't reply earlier.

          The documentation for the RegulaFalsiSolver states: "Unlike the Secant method, convergence is guaranteed by maintaining a bracketed solution." While this is theoretically true, in this case it is not so, because (if I understand correctly) only a single bound is updated repeatedly, and the update is too small to matter (has no effect), due to the double representation.

          The change you propose (which is difficult to see as you also change other things in the same commit) is to modify x0 and f0 if the new value of x and x1 are equal. As I see it, this changes the algorithm, and it is no longer the Regula Falsi method as known from literature. I'm therefore against this change.

          The problem that is identified in this issue is very similar to the well-known problem of the Regula Falsi method: it converges very slowly for certain problems, due to one side being updated all the time, while the other one stays the same. The Illinois and Pegasus algorithms solve exactly this problem, and are well-documented in literature.

          I therefore think it would be better if the RegulaFalsiSolver kept it's original implementation, and for this problem the Illinois or Pegasus method should then be used instead.

          The other changes (if statements to switch with default, extracting bound switch statements, etc) can be kept, if you wish.

          The suggestion to add a warning to the Secant and Regula Falsi solvers that this is a possible problem, and the solution (use Illinois or Pegasus), would indeed be a good idea. In general, adding a note that the Illinois and Pegasus algorithms perform better, would be a good idea regardless of this issue.

          Once more, to be clear, I don't think this issue is a bug. It is a result of the limited convergence of the Regula Falsi method combined with the implications of limited double precision. The limited convergence of the algorithm is a property of the algorithm, and should in my opinion not be changed. I also don't think that trying to work around the limited double precision would be a good idea.

          Show
          Dennis Hendriks added a comment - I just got back from a 3 week vacation, so I couldn't reply earlier. The documentation for the RegulaFalsiSolver states: "Unlike the Secant method, convergence is guaranteed by maintaining a bracketed solution." While this is theoretically true, in this case it is not so, because (if I understand correctly) only a single bound is updated repeatedly, and the update is too small to matter (has no effect), due to the double representation. The change you propose (which is difficult to see as you also change other things in the same commit) is to modify x0 and f0 if the new value of x and x1 are equal. As I see it, this changes the algorithm, and it is no longer the Regula Falsi method as known from literature. I'm therefore against this change. The problem that is identified in this issue is very similar to the well-known problem of the Regula Falsi method: it converges very slowly for certain problems, due to one side being updated all the time, while the other one stays the same. The Illinois and Pegasus algorithms solve exactly this problem, and are well-documented in literature. I therefore think it would be better if the RegulaFalsiSolver kept it's original implementation, and for this problem the Illinois or Pegasus method should then be used instead. The other changes (if statements to switch with default, extracting bound switch statements, etc) can be kept, if you wish. The suggestion to add a warning to the Secant and Regula Falsi solvers that this is a possible problem, and the solution (use Illinois or Pegasus), would indeed be a good idea. In general, adding a note that the Illinois and Pegasus algorithms perform better, would be a good idea regardless of this issue. Once more, to be clear, I don't think this issue is a bug. It is a result of the limited convergence of the Regula Falsi method combined with the implications of limited double precision. The limited convergence of the algorithm is a property of the algorithm, and should in my opinion not be changed. I also don't think that trying to work around the limited double precision would be a good idea.
          Hide
          Gilles added a comment -

          > (which is difficult to see as you also change other things in the same commit)

          Sorry, but I didn't hit the solution right away, i.e. before changing those two additional little things to make the code clearer (for me)...

          The only actual change is that the REGULA_FALSI enum was not used (i.e. with the switch little change, the corresponding case would have been empty) whereas now it contains the update of x0 to avoid an infinite loop.

          The other (cosmetic) change was to take these two statements

          x1 = x;
          f1 = fx;
          

          out of the previous if and else blocks, as they were duplicated there (which made me wonder whether it was a bug that they were not different).

          You say
          > [...] convergence is guaranteed [...]
          > [...] it converges very slowly for certain problems, [...]
          > [...] The limited convergence of the algorithm is a property of the algorithm, [...]

          All the above imply that one expects that the algorithm can find the solution.
          However, in this implementation, it can't.
          Therefore there is a bug, somewhere.

          I agree that it is a limitation of double precision. But, IMHO, leaving the code as-is is not a good idea because because it leads to the impression that the "Regula Falsi" mathematical algorithm can fail to converge, which is not correct (IIUC).
          Therefore, we could add a comment stating that the implementation with limited precision can fail to converge but that would be akin to saying to users: "Here is a code, but don't use it."
          Personally, I would prefer to say: "Because of limited precision, the implementation can fail to converge. In those cases, we slightly modified the original algorithm in order to avoid failure."

          Show
          Gilles added a comment - > (which is difficult to see as you also change other things in the same commit) Sorry, but I didn't hit the solution right away, i.e. before changing those two additional little things to make the code clearer (for me)... The only actual change is that the REGULA_FALSI enum was not used (i.e. with the switch little change, the corresponding case would have been empty) whereas now it contains the update of x0 to avoid an infinite loop. The other (cosmetic) change was to take these two statements x1 = x; f1 = fx; out of the previous if and else blocks, as they were duplicated there (which made me wonder whether it was a bug that they were not different). You say > [...] convergence is guaranteed [...] > [...] it converges very slowly for certain problems, [...] > [...] The limited convergence of the algorithm is a property of the algorithm, [...] All the above imply that one expects that the algorithm can find the solution. However, in this implementation, it can't . Therefore there is a bug, somewhere. I agree that it is a limitation of double precision. But, IMHO, leaving the code as-is is not a good idea because because it leads to the impression that the "Regula Falsi" mathematical algorithm can fail to converge, which is not correct (IIUC). Therefore, we could add a comment stating that the implementation with limited precision can fail to converge but that would be akin to saying to users: "Here is a code, but don't use it." Personally, I would prefer to say: "Because of limited precision, the implementation can fail to converge. In those cases, we slightly modified the original algorithm in order to avoid failure."
          Hide
          Luc Maisonobe added a comment -

          All the above imply that one expects that the algorithm can find the solution.
          However, in this implementation, it can't.
          Therefore there is a bug, somewhere.

          Here, the bug is in the algorithm itself, not in the implementation.

          it leads to the impression that the "Regula Falsi" mathematical algorithm can fail to converge, which is not correct (IIUC).

          It is correct. Regula Falsi fails to converge, or rather it can take a too large number of iteration to converge. This is exactly this behavior that has lead to the construction of other algorithms like Illinois or Pegasus. These two algorithms try to detect the case when the same end of the interval is always updated, and the other end remains unchanged. Once they have detected this, they slightly change the value at one end to trick the linear evaluation into choosing a value that is very likely to have the required sign to update this other end. In fact, in many cases depending of the sign of the curvature near the root, as soon as one end is very close to the root the linear interpolation will always remain on the same side of the root and hence will update this end.

          I agree with Dennis here, the change needed to ensure convergence is not tool long is to choose a better algorithm, such as Illinois, Pegasus ... or the nth order bracketing solver I recently added. Regula Falsi should remain the reference Regula Falsi, just as secant and Brent should remain the reference ones.

          Show
          Luc Maisonobe added a comment - All the above imply that one expects that the algorithm can find the solution. However, in this implementation, it can't. Therefore there is a bug, somewhere. Here, the bug is in the algorithm itself, not in the implementation. it leads to the impression that the "Regula Falsi" mathematical algorithm can fail to converge, which is not correct (IIUC). It is correct. Regula Falsi fails to converge, or rather it can take a too large number of iteration to converge. This is exactly this behavior that has lead to the construction of other algorithms like Illinois or Pegasus. These two algorithms try to detect the case when the same end of the interval is always updated, and the other end remains unchanged. Once they have detected this, they slightly change the value at one end to trick the linear evaluation into choosing a value that is very likely to have the required sign to update this other end. In fact, in many cases depending of the sign of the curvature near the root, as soon as one end is very close to the root the linear interpolation will always remain on the same side of the root and hence will update this end. I agree with Dennis here, the change needed to ensure convergence is not tool long is to choose a better algorithm, such as Illinois, Pegasus ... or the nth order bracketing solver I recently added. Regula Falsi should remain the reference Regula Falsi, just as secant and Brent should remain the reference ones.
          Hide
          Gilles added a comment -

          "fails to converge" and "large number of iteration to converge" are completely different things.

          The documentation says: "convergence is guaranteed". Is that false?

          Moreover, for the function reported in this issue, the problem is not that it takes a large number iterations, it is that the loop is literally infinite because at some point, nothing changes anymore.

          Stated otherwise: If implemented with larger/infinite precision, would it converge?
          In the affirmative, then in my opinion it means that the plain "Regula Falsi" method cannot be implemented with double precision (or that its convergence properties are not as stated in the docs) or that there is a bug in the implementation.

          In the former case, why keep something that will never be used (as we'll warn users that they should use "Pegasus" or "Illinois" but certainly not "RegulaFalsi")? IMHO, we could just state in the docs that "RegulaFalsi" was not implemented because it is demonstrably less efficient and sometimes fails to work.

          A less radical alternative would be to keep the test I've inserted in the code (at line 186) and throw a MathIllegalStateException if it passes. The previous behaviour (infinite loop) is a bug in CM.

          Show
          Gilles added a comment - "fails to converge" and "large number of iteration to converge" are completely different things. The documentation says: "convergence is guaranteed". Is that false? Moreover, for the function reported in this issue, the problem is not that it takes a large number iterations, it is that the loop is literally infinite because at some point, nothing changes anymore. Stated otherwise: If implemented with larger/infinite precision, would it converge? In the affirmative, then in my opinion it means that the plain "Regula Falsi" method cannot be implemented with double precision (or that its convergence properties are not as stated in the docs) or that there is a bug in the implementation. In the former case, why keep something that will never be used (as we'll warn users that they should use "Pegasus" or "Illinois" but certainly not "RegulaFalsi")? IMHO, we could just state in the docs that "RegulaFalsi" was not implemented because it is demonstrably less efficient and sometimes fails to work. A less radical alternative would be to keep the test I've inserted in the code (at line 186) and throw a MathIllegalStateException if it passes. The previous behaviour (infinite loop) is a bug in CM.
          Hide
          Luc Maisonobe added a comment - - edited

          The documentation says: "convergence is guaranteed". Is that false?

          It depends on what is called convergence.
          If convergence is evaluated only as the best of the two endpoints (measured along y axis), yes convergence is guaranteed and in this case it is very slow. This is what appears in many analysis books.
          If convergence is evaluated by ensuring the bracketing interval (measured along x axis) reduces to zero (i.e. both endpoints converge to the root), convergence is not guaranteed.

          The first case is achieved with our implementation by using the function accuracy setting. The second case is achieved with our implementation by using relative accuracy and absolute accuracy settings, which both are computed along x axis.

          I fear that there are several different references about convergence for this method (just as for Brent). So we already are able to implement both views.

          Without any change to our implementation, we reach convergence for this example by setting the function accuracy to 7.4e-13 or above, and it is slow (about 3500 evaluations). The default setting for function accuracy is very low (1.0e-15) and in this case, given the variation rate of the function near the root, it is equivalent to completely ignore convergence on y on only check the convergence on the interval length along x.

          Show
          Luc Maisonobe added a comment - - edited The documentation says: "convergence is guaranteed". Is that false? It depends on what is called convergence. If convergence is evaluated only as the best of the two endpoints (measured along y axis), yes convergence is guaranteed and in this case it is very slow. This is what appears in many analysis books. If convergence is evaluated by ensuring the bracketing interval (measured along x axis) reduces to zero (i.e. both endpoints converge to the root), convergence is not guaranteed. The first case is achieved with our implementation by using the function accuracy setting. The second case is achieved with our implementation by using relative accuracy and absolute accuracy settings, which both are computed along x axis. I fear that there are several different references about convergence for this method (just as for Brent). So we already are able to implement both views. Without any change to our implementation, we reach convergence for this example by setting the function accuracy to 7.4e-13 or above, and it is slow (about 3500 evaluations). The default setting for function accuracy is very low (1.0e-15) and in this case, given the variation rate of the function near the root, it is equivalent to completely ignore convergence on y on only check the convergence on the interval length along x.
          Hide
          Phil Steitz added a comment -

          I think we should either stick with the standard implementation of Regula Falsi or drop the class altogether. Different rootfinders are going to perform better / worse for different functions and parameter values and I don't think it is a good idea to try to modify our implementations of the algorithms to try to work around their shortcomings for problem instances for which they are not well-suited. It is much better to stick with standard algorithms, document them, and leave it to users to choose among implementations.

          Regula Falsi is not a good general-purpose rootfinder, but it does perform well for some problems (or parts of problems) and the original submission was a working implementation, so I would say revert the changes and keep it.

          Show
          Phil Steitz added a comment - I think we should either stick with the standard implementation of Regula Falsi or drop the class altogether. Different rootfinders are going to perform better / worse for different functions and parameter values and I don't think it is a good idea to try to modify our implementations of the algorithms to try to work around their shortcomings for problem instances for which they are not well-suited. It is much better to stick with standard algorithms, document them, and leave it to users to choose among implementations. Regula Falsi is not a good general-purpose rootfinder, but it does perform well for some problems (or parts of problems) and the original submission was a working implementation, so I would say revert the changes and keep it.
          Hide
          Gilles added a comment -

          I understand what you say. But however you put it, there is a bug; if not in the implementation, then in the API. It is not expected behaviour that something which must be changed (function accuracy threshold) to ensure correct behaviour (avoid an undetected infinite loop) is not a mandatory parameter.
          To debug this, I started by raising the absolute accuracy threshold (the first default parameter, thus the first obvious thing to do) to 1e-2 and was stunned that I couldn't get anything after 1000000 iterations!

          Therefore I maintain that, at a minimum, we put a line that will detect the infinite loop and raise an exception identifying that problem and not let the user wait for "TooManyEvaluationsException" to be raised, as that will induce the unaware (me) to just allow more evaluations and try again.

          This solution does not corrupt the algorithm; it just adds protection.

          Show
          Gilles added a comment - I understand what you say. But however you put it, there is a bug; if not in the implementation, then in the API. It is not expected behaviour that something which must be changed (function accuracy threshold) to ensure correct behaviour (avoid an undetected infinite loop) is not a mandatory parameter. To debug this, I started by raising the absolute accuracy threshold (the first default parameter, thus the first obvious thing to do) to 1e-2 and was stunned that I couldn't get anything after 1000000 iterations! Therefore I maintain that, at a minimum, we put a line that will detect the infinite loop and raise an exception identifying that problem and not let the user wait for "TooManyEvaluationsException" to be raised, as that will induce the unaware (me) to just allow more evaluations and try again. This solution does not corrupt the algorithm; it just adds protection.
          Hide
          Phil Steitz added a comment -

          I disagree with your statement about setting accuracy. All of this is configurable and if not set, you get the (documented) defaults. This is all documented. If the documentation is not clear, then we can improve it. A user who applies Regula Falsi to the problem instance being examined here will end up maxing iterations. I see no problem with that and in fact I see it as correct behavior (given the documented execution context of the algorithm).

          Show
          Phil Steitz added a comment - I disagree with your statement about setting accuracy. All of this is configurable and if not set, you get the (documented) defaults. This is all documented. If the documentation is not clear, then we can improve it. A user who applies Regula Falsi to the problem instance being examined here will end up maxing iterations. I see no problem with that and in fact I see it as correct behavior (given the documented execution context of the algorithm).
          Hide
          Gilles added a comment -

          How can it be correct to have an infinite loop?
          The problem is not slow convergence, which you can overcome by allowing more iterations.
          It is too low function value accuracy which you cannot overcome by allowing more iterations. Thus my point: We must raise the appropriate exception (the doc for which will state that it can happen if the function value accuracy is too low for the implementation to provide a result).

          Show
          Gilles added a comment - How can it be correct to have an infinite loop? The problem is not slow convergence, which you can overcome by allowing more iterations. It is too low function value accuracy which you cannot overcome by allowing more iterations. Thus my point: We must raise the appropriate exception (the doc for which will state that it can happen if the function value accuracy is too low for the implementation to provide a result).
          Hide
          Gilles added a comment -

          [My comment starting with "I understand what you say." was an answer to Luc. I hadn't read Phil's previous one which was posted while I was writing mine.]

          I agree that it is better not to change the standard algorithm, as I indicated in my first comment.
          The fix which I'm proposing is not an algorithm change, it is an implementation detail similar to the many hundreds checks performed in CM. Just it is not a precondition test. It adequately indicates that something went wrong and can help the user figure out what it was. It makes the implementation more robust.

          Show
          Gilles added a comment - [My comment starting with "I understand what you say." was an answer to Luc. I hadn't read Phil's previous one which was posted while I was writing mine.] I agree that it is better not to change the standard algorithm, as I indicated in my first comment. The fix which I'm proposing is not an algorithm change, it is an implementation detail similar to the many hundreds checks performed in CM. Just it is not a precondition test. It adequately indicates that something went wrong and can help the user figure out what it was. It makes the implementation more robust.
          Hide
          Gilles added a comment -

          The original implementation, for the "problem instance being examined here", would find the root with absolute accuracy lower than 10e-12 after 3560 evaluations (note: using the default value of 1e-6).
          In fact, the root was found, at the required accuracy, after around 2200 evaluations.

          That does not sound like correct behavior.
          The problem is that, "x0" never being updated, the convergence test always fails... until we reach the limitation of double precision, which entails an infinite loop.

          In fact my fix should not be necessary, as things have gone awry before it would apply, but there is a bug to fix nonetheless.

          Show
          Gilles added a comment - The original implementation, for the "problem instance being examined here", would find the root with absolute accuracy lower than 10e-12 after 3560 evaluations (note: using the default value of 1e-6 ). In fact, the root was found, at the required accuracy, after around 2200 evaluations. That does not sound like correct behavior. The problem is that, "x0" never being updated, the convergence test always fails... until we reach the limitation of double precision, which entails an infinite loop. In fact my fix should not be necessary, as things have gone awry before it would apply, but there is a bug to fix nonetheless.
          Hide
          Phil Steitz added a comment - - edited

          Is there actually a possibility of an infinite loop in the code? Looks to me like the max evaluations bound will stop the while loop, so there is no potential for an infinite loop. Apologies if I am misreading the code and the loop can fail to terminate, in which case I agree this is a problem. (As a side note, from a style perspective, I prefer to explicitly bound loops to avoid this kind of uncertainty. The natural hard bound here is the evaluation count.)

          Trying to detect when a sequence of iterates has gotten "stuck" and is destined to hit max iterations without converging is walking down a path that I think is unwise for us and users. I see no reason not to stick with the standard impl here, which is nicely documented in the original submission. Trying to workaround numerical problems in simple algorithms and change contracts to include these workarounds is asking for trouble - both for us and users. In a simple case like this, it is much better to just stick with the documented algorithm, which should in this case (again unless I am missing something) end with max evaluations exceeded, which is the right exception to report.

          Show
          Phil Steitz added a comment - - edited Is there actually a possibility of an infinite loop in the code? Looks to me like the max evaluations bound will stop the while loop, so there is no potential for an infinite loop. Apologies if I am misreading the code and the loop can fail to terminate, in which case I agree this is a problem. (As a side note, from a style perspective, I prefer to explicitly bound loops to avoid this kind of uncertainty. The natural hard bound here is the evaluation count.) Trying to detect when a sequence of iterates has gotten "stuck" and is destined to hit max iterations without converging is walking down a path that I think is unwise for us and users. I see no reason not to stick with the standard impl here, which is nicely documented in the original submission. Trying to workaround numerical problems in simple algorithms and change contracts to include these workarounds is asking for trouble - both for us and users. In a simple case like this, it is much better to just stick with the documented algorithm, which should in this case (again unless I am missing something) end with max evaluations exceeded, which is the right exception to report.
          Hide
          Gilles added a comment -

          I surely hope that your last post is not an answer to mine from 23:46.

          I'll try to answer here in case it was in reply to my previous one (23:06).
          Of course, the code will not run forever because of the "maxeval" bound.
          But it will run for a time that depends on the value of "maxeval" with no added benefit! From a certain point, the loop is like

          while (true) {
            // Do nothing useful, just count!
            ++count;
            if (count > maxeval) {
              throw new TooManyEvalutationsException(maxeval);
            }
          }
          

          from a style perspective, I prefer to explicitly bound loops

          From an OO style perspective, the reuse of the "Incrementor" is better, and you don't have to rewrite the same "test and throw exception if failed" boiler plate code each time there is such a loop.

          Trying to detect when a sequence of iterates has gotten "stuck" and is destined to hit max iterations without converging is walking down a path that I think is unwise for us and users.

          Why?

          I see no reason not to stick with the standard impl here

          A busy idle loop is a compelling reason IMO.

          Trying to workaround numerical problems in simple algorithms and change contracts to include these workarounds is asking for trouble

          The trouble is there with the current implementation. I'm not criticizing the contribution but this issue shows that it should be made more robust.
          Also, the documentation about "convergence is guaranteed" can lead to a false sense of security.
          Moreover, is the "regula falsi" a mathematical algorithm (with a guaranteed converge property if computed with infinite precision) or a numerical one, which this issue proves that it cannot guarantee convergence? In the former case, CM's (numerical) implementation is not strictly "regula falsi" and there would be no such thing as respect for an original/standard implementation if we can make it more robust.

          I've already indicated that the fix does not change the contract; it stops the busy idle loop as soon as it is detected and reports that it won't do any good to increase the number of iterations. That's obviously more robust.

          Now, if you were answering to my 23:46 post, I'd be glad to read an explanation of why the first paragraph describes expected behaviour.

          Show
          Gilles added a comment - I surely hope that your last post is not an answer to mine from 23:46. I'll try to answer here in case it was in reply to my previous one (23:06). Of course, the code will not run forever because of the "maxeval" bound. But it will run for a time that depends on the value of "maxeval" with no added benefit ! From a certain point, the loop is like while ( true ) { // Do nothing useful, just count! ++count; if (count > maxeval) { throw new TooManyEvalutationsException(maxeval); } } from a style perspective, I prefer to explicitly bound loops From an OO style perspective, the reuse of the "Incrementor" is better, and you don't have to rewrite the same "test and throw exception if failed" boiler plate code each time there is such a loop. Trying to detect when a sequence of iterates has gotten "stuck" and is destined to hit max iterations without converging is walking down a path that I think is unwise for us and users. Why? I see no reason not to stick with the standard impl here A busy idle loop is a compelling reason IMO. Trying to workaround numerical problems in simple algorithms and change contracts to include these workarounds is asking for trouble The trouble is there with the current implementation. I'm not criticizing the contribution but this issue shows that it should be made more robust. Also, the documentation about "convergence is guaranteed" can lead to a false sense of security. Moreover, is the "regula falsi" a mathematical algorithm (with a guaranteed converge property if computed with infinite precision) or a numerical one, which this issue proves that it cannot guarantee convergence? In the former case, CM's (numerical) implementation is not strictly "regula falsi" and there would be no such thing as respect for an original/standard implementation if we can make it more robust. I've already indicated that the fix does not change the contract; it stops the busy idle loop as soon as it is detected and reports that it won't do any good to increase the number of iterations. That's obviously more robust. Now, if you were answering to my 23:46 post, I'd be glad to read an explanation of why the first paragraph describes expected behaviour.
          Hide
          Luc Maisonobe added a comment -

          I don't understand.

          When it was created, the maxIteration threshold was exactly designed for this purpose: get out of infinite loops. It was later renamed maxEvaluation but the purpose is still the same: don't get stuck. The reason why we get stuck is irrelevant. This limit is simply a safety limit, not a tuning parameter that user are expected to raise once they hit it hoping they will converge later on. If they could raise it later, then they should set it to an appropriate value at once. Hitting it implies computation failed. Regula falsi just like any algorithm can fail if applied with the wrong parameters or to the wrong function (in fact, even with a good setting of function accuracy, it fails to converge if we require a bracket selection on the side that does not move).

          Also detecting one bound is not updated is what Illinois and Pegasus are designed to do.

          So I think we should completely get rid of regula falsi and only keep the better algorithms.

          Show
          Luc Maisonobe added a comment - I don't understand. When it was created, the maxIteration threshold was exactly designed for this purpose: get out of infinite loops. It was later renamed maxEvaluation but the purpose is still the same: don't get stuck. The reason why we get stuck is irrelevant. This limit is simply a safety limit, not a tuning parameter that user are expected to raise once they hit it hoping they will converge later on. If they could raise it later, then they should set it to an appropriate value at once. Hitting it implies computation failed. Regula falsi just like any algorithm can fail if applied with the wrong parameters or to the wrong function (in fact, even with a good setting of function accuracy, it fails to converge if we require a bracket selection on the side that does not move). Also detecting one bound is not updated is what Illinois and Pegasus are designed to do. So I think we should completely get rid of regula falsi and only keep the better algorithms.
          Hide
          Gilles added a comment -

          I think we should completely get rid of regula falsi and only keep the better algorithms.

          That was my first idea. And that would be the simplest one, the safest one, and the only viable one as I can't seem to state clearly enough that

          • Problem 1: When the doc says "guaranteed convergence", the algorithm should provide the answer.
          • Problem 2: When the (absolute) accuracy threshold is set to 1e-6, and the correct root is found (after 2200 iterations) within the requirements, it should be returned, instead running idle and finish with an exception

          The reason why we get stuck is irrelevant.

          But why? If we can be more precise on the cause of failure, why not do it?

          This limit is simply a safety limit, not a tuning parameter that user are expected to raise once they hit it hoping they will converge later on.

          In principle, some possible use would be to compare the efficiency of different methods where the main criterion would be a time limitation (assuming that the function evaluation time overwhelms the of the root solver algorithm time). Thus with the function that triggered this issue:

          • If you set maxeval to "3000", then both "Pegasus" (17 evals) and (a fixed) "RegulaFalsi" (2200 evals) would fill the bill.
          • If you set maxeval to "1000", then "Pegasus" will be the only winner.

          Anyways:
          +1 for removing it altogether, and include somewhere the reason for it not being implemented in CM.

          Show
          Gilles added a comment - I think we should completely get rid of regula falsi and only keep the better algorithms. That was my first idea. And that would be the simplest one, the safest one, and the only viable one as I can't seem to state clearly enough that Problem 1: When the doc says "guaranteed convergence", the algorithm should provide the answer. Problem 2: When the (absolute) accuracy threshold is set to 1e-6, and the correct root is found (after 2200 iterations) within the requirements, it should be returned, instead running idle and finish with an exception The reason why we get stuck is irrelevant. But why? If we can be more precise on the cause of failure, why not do it? This limit is simply a safety limit, not a tuning parameter that user are expected to raise once they hit it hoping they will converge later on. In principle, some possible use would be to compare the efficiency of different methods where the main criterion would be a time limitation (assuming that the function evaluation time overwhelms the of the root solver algorithm time). Thus with the function that triggered this issue: If you set maxeval to "3000", then both "Pegasus" (17 evals) and (a fixed) "RegulaFalsi" (2200 evals) would fill the bill. If you set maxeval to "1000", then "Pegasus" will be the only winner. Anyways: +1 for removing it altogether, and include somewhere the reason for it not being implemented in CM.
          Hide
          Phil Steitz added a comment -

          I am OK removing Reg Falsi, but stand by comments above that it is a very bad idea to hack standard algorithms and agree with Luc that maxing iterations is the correct behavior in the case we have been discussing. It is kind of pathetic that the compromise is to drop the impl; but in this case I don't see it as a real loss, since I can't think of any examples where Reg Falsi would be preferable to one of the other solvers - other than for educational purposes.

          Show
          Phil Steitz added a comment - I am OK removing Reg Falsi, but stand by comments above that it is a very bad idea to hack standard algorithms and agree with Luc that maxing iterations is the correct behavior in the case we have been discussing. It is kind of pathetic that the compromise is to drop the impl; but in this case I don't see it as a real loss, since I can't think of any examples where Reg Falsi would be preferable to one of the other solvers - other than for educational purposes.
          Hide
          Gilles added a comment -

          May I please know why it is OK that a bit of code does loop counting and repeatedly computes the same thing!

          You insist that I'd be "hacking" whereas I've indicated 3 or 4 times that there is no hack: just a test that will exit the loop as soon as it detects that the algorithm has failed. Why is it not understandable that the busy loop could last for a long time? The function is potentially evaluated millions of times at the same point. What if the evaluation is costly? Imagine the computation running for days, only to discover that it could have been be stopped after a few seconds. Is that robust code and good advertising for a library? It is one thing to expect that there are unknown bugs in CM, but refusing to fix a known one is so obviously wrong...

          And may I please know why it is OK that an algorithm that finds the right result does not return it.

          I had been trying to provide alternatives to the removal, but I can't do much more if nobody answers the above two questions.
          You just have to run the code and print "x" and "x1" to see what is going on!

          Show
          Gilles added a comment - May I please know why it is OK that a bit of code does loop counting and repeatedly computes the same thing ! You insist that I'd be "hacking" whereas I've indicated 3 or 4 times that there is no hack: just a test that will exit the loop as soon as it detects that the algorithm has failed. Why is it not understandable that the busy loop could last for a long time? The function is potentially evaluated millions of times at the same point. What if the evaluation is costly? Imagine the computation running for days, only to discover that it could have been be stopped after a few seconds. Is that robust code and good advertising for a library? It is one thing to expect that there are unknown bugs in CM, but refusing to fix a known one is so obviously wrong... And may I please know why it is OK that an algorithm that finds the right result does not return it . I had been trying to provide alternatives to the removal, but I can't do much more if nobody answers the above two questions. You just have to run the code and print "x" and "x1" to see what is going on!
          Hide
          Luc Maisonobe added a comment -
          May I please know *why it is OK that a bit of code does loop counting and repeatedly computes the same thing!*
          

          We didn't say that. We said that regula falsi is a standard bad algorithm. We said that very smart people have enhanced it 40 years ago and the enhanced versions are known and already implemented in Commons Math. These algorithms are not blind loop counters and they insert smart target shifts that prevent the behavior we observe here. These algorithms not only detect the problem, they fix it! They allow convergence along x. They allow selection of the side of the root.

          The function is potentially evaluated millions of times at the same point.
          

          The maxEvaluations is already here to prevent this, and in fact now this max number is even mandatory in the solve method (you placed it if I remember correctly). So the function is called millions of time only if the users wishes so by setting the maxEvaluations to a number in the range of millions.

          And may I please know *why it is OK that an algorithm that finds the right result does not return it.*
          

          If the user asked for a convergence in x or for a convergence on y on the side that is stuck, then no, the algorithm did not find the right result. One of its bounds converged but the users asked for something else.

          You just have to run the code and print "x" and "x1" to see what is going on!
          

          We know exactly what is going on! We know the algorithm is stuck. We know why it is stuck. We know why it did not detect it is stuck. We know it will finally hit the safety maxEvaluation threshold that is just waiting for that. And we know that removing all these problems is done by using other algorithms which are already there.

          Regula falsi is doomed. It is an algorithm used for educational purposes, or for comparison purposes, not something suited for production use. It is just like Euler for ODE (and by the way we did implement Euler for ODE and we don't recommend users to use it as we also did implement better algorithms that were also designed by smart mathematicians decades ago).

          Show
          Luc Maisonobe added a comment - May I please know *why it is OK that a bit of code does loop counting and repeatedly computes the same thing!* We didn't say that. We said that regula falsi is a standard bad algorithm. We said that very smart people have enhanced it 40 years ago and the enhanced versions are known and already implemented in Commons Math. These algorithms are not blind loop counters and they insert smart target shifts that prevent the behavior we observe here. These algorithms not only detect the problem, they fix it! They allow convergence along x. They allow selection of the side of the root. The function is potentially evaluated millions of times at the same point. The maxEvaluations is already here to prevent this, and in fact now this max number is even mandatory in the solve method (you placed it if I remember correctly). So the function is called millions of time only if the users wishes so by setting the maxEvaluations to a number in the range of millions. And may I please know *why it is OK that an algorithm that finds the right result does not return it.* If the user asked for a convergence in x or for a convergence on y on the side that is stuck, then no, the algorithm did not find the right result. One of its bounds converged but the users asked for something else. You just have to run the code and print "x" and "x1" to see what is going on! We know exactly what is going on! We know the algorithm is stuck. We know why it is stuck. We know why it did not detect it is stuck. We know it will finally hit the safety maxEvaluation threshold that is just waiting for that. And we know that removing all these problems is done by using other algorithms which are already there. Regula falsi is doomed. It is an algorithm used for educational purposes, or for comparison purposes, not something suited for production use. It is just like Euler for ODE (and by the way we did implement Euler for ODE and we don't recommend users to use it as we also did implement better algorithms that were also designed by smart mathematicians decades ago).
          Hide
          Gilles added a comment -

          So the function is called millions of time only if the users wishes so by setting the maxEvaluations to
          a number in the range of millions.

          No, the user should not expect that any algorithm will go on a single iteration more than necessary.
          This is a plain bug.

          Why do you see that a test such as I proposed (exit the loop early) is wrong while CM (and any good program) is full of tests to ensure that you don't do useless computations?
          This has nothing to do with "regula falsi", it is robustness in the face of limited precision.

          However, if you insist that the bug (failing to detect that it is stuck) is really an integral part of the algorithm, then removing it is not a "pathetic compromise", it is the only right thing to do!

          Show
          Gilles added a comment - So the function is called millions of time only if the users wishes so by setting the maxEvaluations to a number in the range of millions. No, the user should not expect that any algorithm will go on a single iteration more than necessary. This is a plain bug. Why do you see that a test such as I proposed (exit the loop early) is wrong while CM (and any good program) is full of tests to ensure that you don't do useless computations? This has nothing to do with "regula falsi", it is robustness in the face of limited precision. However, if you insist that the bug (failing to detect that it is stuck) is really an integral part of the algorithm, then removing it is not a "pathetic compromise", it is the only right thing to do!
          Hide
          Phil Steitz added a comment -

          This is a pointless discussion. Gilles, you obviously don't share the views that Luc and I have on implementing standard algorithms or even what the meaning of a numerical algorithm is. Some algorithms perform well for some classes of problems and not others. There is an art to choosing the right algorithm for the problem instance at hand. If we modify our implementations to try to work around shortcomings of the algorithms we implement, then we are not implementing the standard algorithms, and we need to document exactly what it is that we are implementing, because in this case we are actually making it harder for users to choose (because we are not longer advertising standard numerics). This is what I meant when I said it is both harder for us (because we have to document the hacks and non-standard contracts) and users (because the standard numerical analysis theory that they may be using to choose among implementations will no longer apply). It is, IMO, a "pathetic compromise" to drop the implementation because we can't agree on what it means to implement the algorithm. So be it. Lets drop it and resolve this issue as "fixed."

          Show
          Phil Steitz added a comment - This is a pointless discussion. Gilles, you obviously don't share the views that Luc and I have on implementing standard algorithms or even what the meaning of a numerical algorithm is. Some algorithms perform well for some classes of problems and not others. There is an art to choosing the right algorithm for the problem instance at hand. If we modify our implementations to try to work around shortcomings of the algorithms we implement, then we are not implementing the standard algorithms, and we need to document exactly what it is that we are implementing, because in this case we are actually making it harder for users to choose (because we are not longer advertising standard numerics). This is what I meant when I said it is both harder for us (because we have to document the hacks and non-standard contracts) and users (because the standard numerical analysis theory that they may be using to choose among implementations will no longer apply). It is, IMO, a "pathetic compromise" to drop the implementation because we can't agree on what it means to implement the algorithm. So be it. Lets drop it and resolve this issue as "fixed."
          Hide
          Gilles added a comment -

          Gilles, you obviously don't share the views that Luc and I have on implementing standard algorithms

          That's simply not true.
          I was the one pointing out that standard algorithms should have precedence: Please recall that it was considered fine that "Levenberg-Marquardt" and "Brent" would be, unknowingly to the user, "twisted" to perform non-standard convergences check.
          In those cases, there was the risk that the result of the algorithm would not be the same as the reference implementation.

          In this case, there is no such thing as deviating from standard numerics! It was just a matter of throwing the right exception. So: "The algorithm fails? Let's tell it sooner rather than later."

          Very interesting question that you ask: "what it means to implement the algorithm". But please note that I asked it several posts ago[1], and an answer would have helped sort out this discussion. What is your definition?

          [1] 08/Aug/11 07:24

          Show
          Gilles added a comment - Gilles, you obviously don't share the views that Luc and I have on implementing standard algorithms That's simply not true . I was the one pointing out that standard algorithms should have precedence: Please recall that it was considered fine that "Levenberg-Marquardt" and "Brent" would be, unknowingly to the user, "twisted" to perform non-standard convergences check. In those cases, there was the risk that the result of the algorithm would not be the same as the reference implementation. In this case, there is no such thing as deviating from standard numerics! It was just a matter of throwing the right exception. So: "The algorithm fails? Let's tell it sooner rather than later." Very interesting question that you ask: "what it means to implement the algorithm". But please note that I asked it several posts ago [1] , and an answer would have helped sort out this discussion. What is your definition? [1] 08/Aug/11 07:24
          Hide
          Gilles added a comment -

          Also:

          Phil,

          Could you please leave out dismissive qualifiers such as "pointless" and "pathetic" (and, elsewhere, "silly") and stick to more or less objective arguments?
          That will certainly help keep the conversation tone to a courteous level.

          Luc,

          Thanks for stating in full details what you meant by "convergence" in this case. However, it is still a "post-mortem" description.
          Do you really expect that the average user of the CM library (a.o. me and the original reporter of the issue) to be able to figure out that "obvious" explanation just by getting a "TooManyEvalutationsException", setting the along-x accuracy threshold to a ridiculously high value and still getting the same exception?
          If just for educational purposes, don't you think that it is more instructive to get a specific hint that the algorithm is stuck, rather than hit the ultimate fail-safe barrier much much later, and then download the source code and sprinkle the code with "println" statements to do forensic analysis?

          Phil,

          I tried to handle this issue out of respect for a real user who reported an issue that would have looked suspicious to many CM users. [How many of them would be experts in numerical analysis?]
          You do not do me a favour by removing this algorithm; I don't want it to be a compromise (pathetic or not). If you prefer to keep it, I don't care anymore. But, in that case, you should have answered to Axel Kramer to go and read some books on numerical analysis.

          Show
          Gilles added a comment - Also: Phil, Could you please leave out dismissive qualifiers such as "pointless" and "pathetic" (and, elsewhere, "silly") and stick to more or less objective arguments? That will certainly help keep the conversation tone to a courteous level. Luc, Thanks for stating in full details what you meant by "convergence" in this case. However, it is still a "post-mortem" description. Do you really expect that the average user of the CM library (a.o. me and the original reporter of the issue) to be able to figure out that "obvious" explanation just by getting a "TooManyEvalutationsException", setting the along-x accuracy threshold to a ridiculously high value and still getting the same exception? If just for educational purposes, don't you think that it is more instructive to get a specific hint that the algorithm is stuck, rather than hit the ultimate fail-safe barrier much much later, and then download the source code and sprinkle the code with "println" statements to do forensic analysis? Phil, I tried to handle this issue out of respect for a real user who reported an issue that would have looked suspicious to many CM users. [How many of them would be experts in numerical analysis?] You do not do me a favour by removing this algorithm; I don't want it to be a compromise (pathetic or not). If you prefer to keep it, I don't care anymore. But, in that case, you should have answered to Axel Kramer to go and read some books on numerical analysis.
          Hide
          Phil Steitz added a comment -

          Gilles, I apologize for tone of comments.

          Show
          Phil Steitz added a comment - Gilles, I apologize for tone of comments.
          Hide
          Dennis Hendriks added a comment -

          The discussions for this issue have left me with a lack of overview, so I'll (try to) objectively summerize the discussions above:

          The problems are:

          1. Regula Falsi states it always converges, but the implementation doesn't.
          2. The main loop may continue, even when it no longer makes any progress, and subsequently ends with a TooManyEvaluationsException exception.

          The cause of both problems is:

          • The limited/finite precision of the Java double type.

          Proposed solutions:

          1. The patch from revision 1154614, which modifies the Regula Falsi algorithm.
            • Consensus seems to be that this change, which modifies the algorithm, is undesireable. We should keep the original algorithm.
          2. Detect that the algorithm no longer makes progress and throw an exception, instead of continuing the loop which no longer makes progress.
            • This is just earlier detection of the algorithm getting stuck.
            • We could throw the TooManyEvaluationsException exception, that continuing the loop would also get us.
              • The class only states "Exception to be thrown when the maximal number of evaluations is exceeded.".
              • The exception message only states: "illegal state: maximal count (100) exceeded: evaluations"
              • Both may benefit from more extended documentation/messages.
            • We could also throw an other exception that more clearly states this issue (NoMoreProgressException, AlgorithmStuckException, ...?).
              • It could for instance mention that changing the function value accuracy may be a solution, or asking for a different kind of solution?
          3. Add documentation to the Regula Falsi algorithm that it is not intended to be used for actual problems, but only to compare algorithms, for testing, educational purposes, etc.
          4. Add documentation to the Regula Falsi algorithm that users should use Illinois or Pegasus instead, which should outperform the algorithm for most if not all problems.
          5. Add documentation to the Regula Falsi algorithm that it theoretically converges, but the implementation may not, due to the limited/finite precision of Java's double type. This will result in an exception (or 2 if we also do solution number 2).
          6. Remove the Regula Falsi algorithm, and document why it is not included/implemented.
            • This seems to have been accepted as a last resort solution only.

          Other notes:

          • The following problem was also indicated: a solution is found after a certain number of iterations, but the algorithm does not return the solution (it does not terminate)
            • This should only happen if the user asked for a different solution. That is, there are several accuracy parameters, as well as an allowedSolution parameter.
            • If the solution requested by the user is found, it should return the solution immediately, otherwise it is a bug.

          New notes:

          • I think the Regula Falsi algorithm does not state a fixed convergence criteria: it is left to the user to decide on one.
            • When I implemented the algorithm, I think I copied the convergence checks for Brent.
            • I subsequently modified the convergence criteria when I added the allowedSolution parameter.

          My personal opinions on the proposed solutions:

          • (1) Revert part of 1154614, so get the original algorithm back. The other changes of that commit, that don't change the actual algorith, can stay.
          • (2) If we keep the algorithm, earlier detection would be nice. Not sure which exception to throw in these cases.
            • This would result in a single 'if' that detects that the new approximation is the same as the previous one, and we thus no longer make progress, in which case we throw the exception earlier, instead of later.
          • (3-5) If we keep the algorith, all 3 documentation extensions would be a good idea.
          • (6) If possible, keep the algorithm, and don't remove it.

          New issue:

          • TooManyEvaluationsException currently seems to use LocalizedFormats.MAX_COUNT_EXCEEDED("maximal count ( {0}) exceeded"), but maybe should use LocalizedFormats.MAX_EVALUATIONS_EXCEEDED("maximal number of evaluations ({0}

            ) exceeded") instead?

          Show
          Dennis Hendriks added a comment - The discussions for this issue have left me with a lack of overview, so I'll (try to) objectively summerize the discussions above: The problems are: Regula Falsi states it always converges, but the implementation doesn't. The main loop may continue, even when it no longer makes any progress, and subsequently ends with a TooManyEvaluationsException exception. The cause of both problems is: The limited/finite precision of the Java double type. Proposed solutions: The patch from revision 1154614, which modifies the Regula Falsi algorithm. Consensus seems to be that this change, which modifies the algorithm, is undesireable. We should keep the original algorithm. Detect that the algorithm no longer makes progress and throw an exception, instead of continuing the loop which no longer makes progress. This is just earlier detection of the algorithm getting stuck. We could throw the TooManyEvaluationsException exception, that continuing the loop would also get us. The class only states "Exception to be thrown when the maximal number of evaluations is exceeded.". The exception message only states: "illegal state: maximal count (100) exceeded: evaluations" Both may benefit from more extended documentation/messages. We could also throw an other exception that more clearly states this issue (NoMoreProgressException, AlgorithmStuckException, ...?). It could for instance mention that changing the function value accuracy may be a solution, or asking for a different kind of solution? Add documentation to the Regula Falsi algorithm that it is not intended to be used for actual problems, but only to compare algorithms, for testing, educational purposes, etc. Add documentation to the Regula Falsi algorithm that users should use Illinois or Pegasus instead, which should outperform the algorithm for most if not all problems. Add documentation to the Regula Falsi algorithm that it theoretically converges, but the implementation may not, due to the limited/finite precision of Java's double type. This will result in an exception (or 2 if we also do solution number 2). Remove the Regula Falsi algorithm, and document why it is not included/implemented. This seems to have been accepted as a last resort solution only. Other notes: The following problem was also indicated: a solution is found after a certain number of iterations, but the algorithm does not return the solution (it does not terminate) This should only happen if the user asked for a different solution. That is, there are several accuracy parameters, as well as an allowedSolution parameter. If the solution requested by the user is found, it should return the solution immediately, otherwise it is a bug. New notes: I think the Regula Falsi algorithm does not state a fixed convergence criteria: it is left to the user to decide on one. When I implemented the algorithm, I think I copied the convergence checks for Brent. I subsequently modified the convergence criteria when I added the allowedSolution parameter. My personal opinions on the proposed solutions: (1) Revert part of 1154614, so get the original algorithm back. The other changes of that commit, that don't change the actual algorith, can stay. (2) If we keep the algorithm, earlier detection would be nice. Not sure which exception to throw in these cases. This would result in a single 'if' that detects that the new approximation is the same as the previous one, and we thus no longer make progress, in which case we throw the exception earlier, instead of later. (3-5) If we keep the algorith, all 3 documentation extensions would be a good idea. (6) If possible, keep the algorithm, and don't remove it. New issue: TooManyEvaluationsException currently seems to use LocalizedFormats.MAX_COUNT_EXCEEDED("maximal count ( {0}) exceeded"), but maybe should use LocalizedFormats.MAX_EVALUATIONS_EXCEEDED("maximal number of evaluations ({0} ) exceeded") instead?
          Hide
          Gilles added a comment -

          Thanks for the neat summary!

          • (1) Revert part of 1154614, so get the original algorithm back. The other changes of that commit, that don't change the actual algorith, can stay.

          Done in revision 1157185.

          • (2) If we keep the algorithm, earlier detection would be nice. Not sure which exception to throw in these cases.
            • This would result in a single 'if' that detects that the new approximation is the same as the previous one, and we thus no longer make progress, in which case we throw the exception earlier, instead of later.

          +1 (my position in the "07/Aug/11 20:28" post)
          As suggested there, the exception could be "MathIllegalStateException" but with a clear message stating that the algorithm is stuck. Or maybe a new subclass of it which we could call "NumericalPrecisionException" or even a general-purpose "ImplementationException".

          [...] all 3 documentation extensions would be a good idea.

          +1

          About the "new issue", the message string:

          "illegal state: maximal count (100) exceeded: evaluations"

          contains everything:

          1. error type: illegal state
          2. failure description: maximal count (100) exceeded
          3. context: evaluations

          I proposed to use this approach (combining message items with the "addMessage" method of "ExceptionContext") in order to reduce the number of messages in the "LocalizedFormats" enum. Too many of them are just slight variations on a same theme.

          Show
          Gilles added a comment - Thanks for the neat summary! (1) Revert part of 1154614, so get the original algorithm back. The other changes of that commit, that don't change the actual algorith, can stay. Done in revision 1157185. (2) If we keep the algorithm, earlier detection would be nice. Not sure which exception to throw in these cases. This would result in a single 'if' that detects that the new approximation is the same as the previous one, and we thus no longer make progress, in which case we throw the exception earlier, instead of later. +1 (my position in the "07/Aug/11 20:28" post) As suggested there, the exception could be "MathIllegalStateException" but with a clear message stating that the algorithm is stuck. Or maybe a new subclass of it which we could call "NumericalPrecisionException" or even a general-purpose "ImplementationException". [...] all 3 documentation extensions would be a good idea. +1 About the "new issue", the message string: "illegal state: maximal count (100) exceeded: evaluations" contains everything: error type: illegal state failure description: maximal count (100) exceeded context: evaluations I proposed to use this approach (combining message items with the "addMessage" method of "ExceptionContext") in order to reduce the number of messages in the "LocalizedFormats" enum. Too many of them are just slight variations on a same theme.
          Hide
          Dennis Hendriks added a comment -

          contains everything

          I agree. I was just wondering why a message that seems to be exactly the same as the exception was not used, as it kind of looked like it was created just for this purpose...

          I proposed to use this approach (combining message items with the "addMessage" method of "ExceptionContext") in order to reduce the number of messages in the "LocalizedFormats" enum. Too many of them are just slight variations on a same theme.

          Ah, so then the MAX_EVALUATIONS_EXCEEDED is just a remnant of the past that should be eliminated, by replacing it everywhere by the more general MAX_COUNT_EXCEEDED?

          Show
          Dennis Hendriks added a comment - contains everything I agree. I was just wondering why a message that seems to be exactly the same as the exception was not used, as it kind of looked like it was created just for this purpose... I proposed to use this approach (combining message items with the "addMessage" method of "ExceptionContext") in order to reduce the number of messages in the "LocalizedFormats" enum. Too many of them are just slight variations on a same theme. Ah, so then the MAX_EVALUATIONS_EXCEEDED is just a remnant of the past that should be eliminated, by replacing it everywhere by the more general MAX_COUNT_EXCEEDED?
          Hide
          Gilles added a comment -

          Yes. In the file "LocalizedFormats.java", I've started to write

          /* keep */
          

          after each enum that is supposedly to be kept. All the others are still to be examined for redundancy with another one, or the possibility to create something close using the "multi-item" approach.

          Show
          Gilles added a comment - Yes. In the file "LocalizedFormats.java", I've started to write /* keep */ after each enum that is supposedly to be kept. All the others are still to be examined for redundancy with another one, or the possibility to create something close using the "multi-item" approach.
          Hide
          Dennis Hendriks added a comment -

          The 'ticket631.patch' file is my attempt to resolve this issue with a solution (or maybe I should call it a compromise?) that is satisfactory for all people that participated in the discussions for this issue, without having to remove the Regula Falsi algorithm from Commons Math.

          I changed the following:

          • Added early detection of no longer making progress ('getting stuck'), and documented it.
            • I used ConvergenceException for this, as it seems to fit... Do we want a custom error message with it?
          • Extended RegulaFalsiSolver documentation to indicate:
            • that the algorithm should not be used for actual problems.
            • that Illinois and Pegasus are improved versions and should be prefered.
            • that the implementation does not guarantee convergence, while the algorithm theoretically does.
          • Extended IllinoisSolver and PegasusSolver documentation to indicate that they don't suffer from the RegulaFalsiSolver's implementation/convergence issues.

          Please comment on whether this patch is an acceptable solution/compromise, and if not, why it is not.

          Show
          Dennis Hendriks added a comment - The 'ticket631.patch' file is my attempt to resolve this issue with a solution (or maybe I should call it a compromise?) that is satisfactory for all people that participated in the discussions for this issue, without having to remove the Regula Falsi algorithm from Commons Math. I changed the following: Added early detection of no longer making progress ('getting stuck'), and documented it. I used ConvergenceException for this, as it seems to fit... Do we want a custom error message with it? Extended RegulaFalsiSolver documentation to indicate: that the algorithm should not be used for actual problems. that Illinois and Pegasus are improved versions and should be prefered. that the implementation does not guarantee convergence, while the algorithm theoretically does. Extended IllinoisSolver and PegasusSolver documentation to indicate that they don't suffer from the RegulaFalsiSolver's implementation/convergence issues. Please comment on whether this patch is an acceptable solution/compromise, and if not, why it is not.
          Hide
          Gilles added a comment -

          Committed (with minor additional Javadoc fixes) in revision 1164474.

          Leaving open until confirmation that ConvergenceException is the right one to use. I thought that we could make a difference between theoretical and implementation convergence failures. But it might not be worth introducing the distinction just for this one case, especially since it is quite clear clear now that the class should not be used.

          Show
          Gilles added a comment - Committed (with minor additional Javadoc fixes) in revision 1164474. Leaving open until confirmation that ConvergenceException is the right one to use. I thought that we could make a difference between theoretical and implementation convergence failures. But it might not be worth introducing the distinction just for this one case, especially since it is quite clear clear now that the class should not be used.
          Hide
          Gilles added a comment -

          No objection raised; setting to "Resolved".

          Show
          Gilles added a comment - No objection raised; setting to "Resolved".

            People

            • Assignee:
              Unassigned
              Reporter:
              Gilles
            • Votes:
              0 Vote for this issue
              Watchers:
              1 Start watching this issue

              Dates

              • Created:
                Updated:
                Resolved:

                Development