Commons Math
  1. Commons Math
  2. MATH-375

Elementary functions in JDK are slower than necessary and not as accurate as they could be.

    Details

    • Type: New Feature New Feature
    • Status: Closed
    • Priority: Major Major
    • Resolution: Fixed
    • Affects Version/s: None
    • Fix Version/s: 2.2
    • Labels:
      None
    • Environment:

      JDK 1.4 - 1.6

      Description

      I would like to contribute improved versions on exp(), log(), pow(), etc. to the project. Please refer to this discussion thread http://markmail.org/message/zyeoguw6gwtofm62.

      I have developed over the past year a set of elementary functions similar to those in java.lang.Math, but with the following characteristics:

      • Higher performance.
      • Better accuracy. Results are accurate to slightly more that +/- 0.5 ULP.
      • Pure Java. The standard Math class is impleneted via JNI, and thus takes a performance hit.

      Note that some functions such as exp are nearly twice as fast in my implementation.   I've seen it 3 times faster on different processors.   The preformance varies by the relative speed of calculation vs memory lookups.

      The functions are implemented as tables of values in extra precision (approx 70 bits), and then interpolated with a minimax polynomial.

      1. cosh-patch.txt.gz
        2 kB
        William Rossi
      2. cbrt-patch.txt.gz
        2 kB
        William Rossi
      3. asinacos-patch.txt.gz
        3 kB
        William Rossi
      4. test_fastmath_wr.zip
        13 kB
        Jeff Hain
      5. atanpatch.txt.gz
        0.6 kB
        William Rossi
      6. FastMath.tar.gz
        44 kB
        William Rossi

        Activity

        Hide
        William Rossi added a comment -

        Description of files in the archive:

        FastMath.java The software itself
        FastMathTest.java TestNG test case
        remez/ Utilities for generating coefficients of the polynomials used in the software

        remez/lib/dfp10.jar High precision fp lib used for testing, from dfp.sourceforge.net

        Show
        William Rossi added a comment - Description of files in the archive: FastMath.java The software itself FastMathTest.java TestNG test case remez/ Utilities for generating coefficients of the polynomials used in the software remez/lib/dfp10.jar High precision fp lib used for testing, from dfp.sourceforge.net
        Hide
        Roman Werpachowski added a comment -

        Hi Bill,

        this is a very nice piece of work which I would be happy to use in my project. Did you publish it anywhere under an Open Source license? The archive attached doesn't have any license information.

        Show
        Roman Werpachowski added a comment - Hi Bill, this is a very nice piece of work which I would be happy to use in my project. Did you publish it anywhere under an Open Source license? The archive attached doesn't have any license information.
        Hide
        William Rossi added a comment -

        It hasn't yet been published, I was hoping to get it incorportated into
        larger project such as Commons Math. With that in mind, I'm willing to
        issue an Apache License for it.

        I'm not very familiar with all the procedures of licensing yet, it was
        suggested to me that I post it here and submit a license grant to the
        Apache Foundation separtely. If that doesn't meet you needs, let me know
        what needs to be done.

        Show
        William Rossi added a comment - It hasn't yet been published, I was hoping to get it incorportated into larger project such as Commons Math. With that in mind, I'm willing to issue an Apache License for it. I'm not very familiar with all the procedures of licensing yet, it was suggested to me that I post it here and submit a license grant to the Apache Foundation separtely. If that doesn't meet you needs, let me know what needs to be done.
        Hide
        Roman Werpachowski added a comment -

        I would feel more comfortable if the source attached attributed copyright to ASF and included the license (Apache License).

        Show
        Roman Werpachowski added a comment - I would feel more comfortable if the source attached attributed copyright to ASF and included the license (Apache License).
        Hide
        Sebb added a comment -

        Note that the dfp library is released under LGPL, so cannot be included in any ASF releases.

        However it can be used as an optional dependency - which may well be sufficient here.

        Show
        Sebb added a comment - Note that the dfp library is released under LGPL, so cannot be included in any ASF releases. However it can be used as an optional dependency - which may well be sufficient here.
        Hide
        William Rossi added a comment -

        I'm not as well versed in these copyright issues I as I should be, but my
        understanding is that as the copyright holder of the dfp library, I could
        dual license it. In any event, dfp is not required by the software, its
        only used in the supporting test cases.

        Which also why I whould be hesitant to assign copyright to ASF, if I were
        to do that and ASF decides not to persue the project then I'm left with
        nothing. By maintaining the copyright, I can issue licenses to other
        parties as I see fit.

        The ASF software grant agreement doesn't ask me to assign copyright to
        ASF, but to mearly agree to specific license terms.

        Show
        William Rossi added a comment - I'm not as well versed in these copyright issues I as I should be, but my understanding is that as the copyright holder of the dfp library, I could dual license it. In any event, dfp is not required by the software, its only used in the supporting test cases. Which also why I whould be hesitant to assign copyright to ASF, if I were to do that and ASF decides not to persue the project then I'm left with nothing. By maintaining the copyright, I can issue licenses to other parties as I see fit. The ASF software grant agreement doesn't ask me to assign copyright to ASF, but to mearly agree to specific license terms.
        Hide
        Roman Werpachowski added a comment -

        Thanks for the clarification. Could the archive file, then, contain the license information under which it is published?

        Show
        Roman Werpachowski added a comment - Thanks for the clarification. Could the archive file, then, contain the license information under which it is published?
        Hide
        William Rossi added a comment -

        Certainly, I'll do then when I get a chance.

        Show
        William Rossi added a comment - Certainly, I'll do then when I get a chance.
        Hide
        Roman Werpachowski added a comment -

        Thanks a lot.

        Show
        Roman Werpachowski added a comment - Thanks a lot.
        Hide
        William Rossi added a comment -

        Added license file

        Show
        William Rossi added a comment - Added license file
        Hide
        Luc Maisonobe added a comment -

        I finally found some time to look at this proposal.
        It is very impressive and I really want to include it.
        As the code is rather long and has been developed outside of the Apache Software Foundation, could you send a signed Software Grant to the foundation (see http://www.apache.org/licenses/#grants) ? As you will see, the softaware grant is simply a license you grant, the intellectual property remains yours.
        The best way would be to have it sent by fax or by mail with a detached gpg signature. Please refer to this Jira issue and the attached patch you already submitted.
        Thanks a lot for this contribution.

        Show
        Luc Maisonobe added a comment - I finally found some time to look at this proposal. It is very impressive and I really want to include it. As the code is rather long and has been developed outside of the Apache Software Foundation, could you send a signed Software Grant to the foundation (see http://www.apache.org/licenses/#grants ) ? As you will see, the softaware grant is simply a license you grant, the intellectual property remains yours. The best way would be to have it sent by fax or by mail with a detached gpg signature. Please refer to this Jira issue and the attached patch you already submitted. Thanks a lot for this contribution.
        Hide
        Luc Maisonobe added a comment -

        Adding one technical comment now.
        It seems to me the atan2 function does not behave as expected for some special inputs with one tiny (or zero) parameter and the other very large (or infinite). For example the following codes:

        double y1 = 1.2713504628280707e10;
        double x1 = -5.674940885228782e-10;
        System.out.println("Math: " + Math.atan2(y1, x1) + ", FastMath: " + FastMath.atan2(y1, x1));
        double y2 = 0.0;
        double x2 = Double.POSITIVE_INFINITY;
        System.out.println("Math: " + Math.atan2(y2, x2) + ", FastMath: " + FastMath.atan2(y2, x2));
        

        prints these results:

        Math: 1.5707963267948968, FastMath: -1.5707963267948966
        Math: 0.0, FastMath: Infinity
        

        It would also be very useful to have a few more functions, the main missing one being sqrt. However, thes functions can be added later on.

        Show
        Luc Maisonobe added a comment - Adding one technical comment now. It seems to me the atan2 function does not behave as expected for some special inputs with one tiny (or zero) parameter and the other very large (or infinite). For example the following codes: double y1 = 1.2713504628280707e10; double x1 = -5.674940885228782e-10; System .out.println( " Math : " + Math .atan2(y1, x1) + ", FastMath: " + FastMath.atan2(y1, x1)); double y2 = 0.0; double x2 = Double .POSITIVE_INFINITY; System .out.println( " Math : " + Math .atan2(y2, x2) + ", FastMath: " + FastMath.atan2(y2, x2)); prints these results: Math : 1.5707963267948968, FastMath: -1.5707963267948966 Math : 0.0, FastMath: Infinity It would also be very useful to have a few more functions, the main missing one being sqrt. However, thes functions can be added later on.
        Hide
        Luc Maisonobe added a comment -

        We need to add this as soon as possible
        A patch is available and it includes tests
        Setting target version for fix to 2.2

        Show
        Luc Maisonobe added a comment - We need to add this as soon as possible A patch is available and it includes tests Setting target version for fix to 2.2
        Hide
        William Rossi added a comment -

        The attached patch fixes the bugs you reported in atan2(). I didn't implement sqrt() because I can't really improve upon Math.sqrt(). The implementation in Math seems to get compiled into a single machine instruction and I can't really compete against that. It might be reasonable to have FastMath.sqrt() simply call Math.sqrt() though.

        As far as other functions go, if there are some that are higher priority than others, please let me know.

        Show
        William Rossi added a comment - The attached patch fixes the bugs you reported in atan2(). I didn't implement sqrt() because I can't really improve upon Math.sqrt(). The implementation in Math seems to get compiled into a single machine instruction and I can't really compete against that. It might be reasonable to have FastMath.sqrt() simply call Math.sqrt() though. As far as other functions go, if there are some that are higher priority than others, please let me know.
        Hide
        Luc Maisonobe added a comment -

        Thanks for the fix.
        I think we will probably start with all missing functions implemented with a call to the corresponding Math function, This would allow people to simply do global search and replace for Math to FastMath and have a working setup.
        From my personal use, the higher priorities functions to be implemented with fast and accurate versions would be first asin, acos, then cbrt and later sinh, cosh, tanh.
        For functions like nextUp, signum and the likes, we could use our own bit twiddling (we should also probably move MathUtil.nextAfter in the FastMath class too).
        I still did not see the grant registered in Apache foundation files, did you sent it already ?

        Show
        Luc Maisonobe added a comment - Thanks for the fix. I think we will probably start with all missing functions implemented with a call to the corresponding Math function, This would allow people to simply do global search and replace for Math to FastMath and have a working setup. From my personal use, the higher priorities functions to be implemented with fast and accurate versions would be first asin, acos, then cbrt and later sinh, cosh, tanh. For functions like nextUp, signum and the likes, we could use our own bit twiddling (we should also probably move MathUtil.nextAfter in the FastMath class too). I still did not see the grant registered in Apache foundation files, did you sent it already ?
        Hide
        William Rossi added a comment -

        I can focus on new functions in that order. I did send the grant by fax last week.

        Show
        William Rossi added a comment - I can focus on new functions in that order. I did send the grant by fax last week.
        Hide
        Luc Maisonobe added a comment -

        We finally get the grant, thanks.
        I have started integrating the patch in our current code base (not committed yet).
        I added all missing functions with default implementations (either simple delegates to java.util.Math or basic implementations).
        The code has also been edited to comply to our standard code style (indentation, braces, trailing spaces, variables naming, this kind of stuff).

        Concerning the unit tests, I cannot commit them due to the external libraries and their license. I will start a discussion on the dev list about it.
        Using the existing tests with all their dependencies on my machine, I had to slightly increase the threshold from 0.502 ULP to 0.504 ULP as the initial value lead to random failures. The tests were done on a 64 bits linux computer with Java 6. Are suche random failure expected ?

        Show
        Luc Maisonobe added a comment - We finally get the grant, thanks. I have started integrating the patch in our current code base (not committed yet). I added all missing functions with default implementations (either simple delegates to java.util.Math or basic implementations). The code has also been edited to comply to our standard code style (indentation, braces, trailing spaces, variables naming, this kind of stuff). Concerning the unit tests, I cannot commit them due to the external libraries and their license. I will start a discussion on the dev list about it. Using the existing tests with all their dependencies on my machine, I had to slightly increase the threshold from 0.502 ULP to 0.504 ULP as the initial value lead to random failures. The tests were done on a 64 bits linux computer with Java 6. Are suche random failure expected ?
        Hide
        William Rossi added a comment -

        Yes, that can happen on occasion.

        I'm the author and copyright holder on the dependant library (dfp) as
        well. Would it help the project if I were to offer it under a dual
        license? I'm concerned that it would take considerable effort to port
        the tests to another library.

        Show
        William Rossi added a comment - Yes, that can happen on occasion. I'm the author and copyright holder on the dependant library (dfp) as well. Would it help the project if I were to offer it under a dual license? I'm concerned that it would take considerable effort to port the tests to another library.
        Hide
        Luc Maisonobe added a comment -

        OK, then I'll simply raise the threshold a bit.

        Offering dfp under a compatible license would help the project. The answer from our legal team concerning this toic can be found here: http://www.apache.org/legal/resolved.html#category-a. Here is the appropriate quote concerning LGPL from the previous link,:

        The LGPL is ineligible primarily due to the restrictions it places on larger works, violating the third license criterion. Therefore, LGPL-licensed works must not be included in Apache products.

        If you consider offering dfp on a dual license, would you also consider integrating it into commons-math too ? It would be a very nice addition I think.

        Show
        Luc Maisonobe added a comment - OK, then I'll simply raise the threshold a bit. Offering dfp under a compatible license would help the project. The answer from our legal team concerning this toic can be found here: http://www.apache.org/legal/resolved.html#category-a . Here is the appropriate quote concerning LGPL from the previous link,: The LGPL is ineligible primarily due to the restrictions it places on larger works, violating the third license criterion. Therefore, LGPL-licensed works must not be included in Apache products. If you consider offering dfp on a dual license, would you also consider integrating it into commons-math too ? It would be a very nice addition I think.
        Hide
        William Rossi added a comment -

        We can do that. How do we proceed, do I write up another software grant?
        Its 6K lines of code not counting the example application which is another
        1K lines.

        Show
        William Rossi added a comment - We can do that. How do we proceed, do I write up another software grant? Its 6K lines of code not counting the example application which is another 1K lines.
        Hide
        Luc Maisonobe added a comment -

        Yes, we would need another grant for that because grants are really specific to one piece of code.
        It would also be better to open a new Jira issue for this and put a reference to this new issue number in the grant.

        Show
        Luc Maisonobe added a comment - Yes, we would need another grant for that because grants are really specific to one piece of code. It would also be better to open a new Jira issue for this and put a reference to this new issue number in the grant.
        Hide
        Luc Maisonobe added a comment -

        The FastMath class has been added to the subversion repository, as of r990655 for branch 2.X and as r990658 for trunk.
        It is now used everywhere in the library (including in tests), in replacement of java.util.Math.
        The contributed patch has been edited to match commons-math coding style which is enforced by checkstyle. The corresponding changes are mainly basic formatting (spaces, braces ...), naming conventions, variables declarations on separate lines, javadoc everywhere ... Some javadoc have been marked as "To Be Confirmed" (exp and log), please have a llook at it and check if they are correct.
        In order to let users do global search and replace of java.util.Math by the new class, several new methods have been added. For the new functions (sinh, cosh ...) basic implementations have been set up. These implementations should be about 3 ULP accurate and may be slow for now. For consistency, the inverse hyperbolic functions (asinh, acosh and atanh) have been added too, depite they are not present in java.util.Math.
        The unit tests have not been committed to the subversion repository yet, we are waiting for the dfp library to be available and integrated too (otherwise the continuous integration process would be broken by the missing dependency). This issue will be marked as resolved when the tests will be committed.

        Thanks again for this contribution.

        Show
        Luc Maisonobe added a comment - The FastMath class has been added to the subversion repository, as of r990655 for branch 2.X and as r990658 for trunk. It is now used everywhere in the library (including in tests), in replacement of java.util.Math. The contributed patch has been edited to match commons-math coding style which is enforced by checkstyle. The corresponding changes are mainly basic formatting (spaces, braces ...), naming conventions, variables declarations on separate lines, javadoc everywhere ... Some javadoc have been marked as "To Be Confirmed" (exp and log), please have a llook at it and check if they are correct. In order to let users do global search and replace of java.util.Math by the new class, several new methods have been added. For the new functions (sinh, cosh ...) basic implementations have been set up. These implementations should be about 3 ULP accurate and may be slow for now. For consistency, the inverse hyperbolic functions (asinh, acosh and atanh) have been added too, depite they are not present in java.util.Math. The unit tests have not been committed to the subversion repository yet, we are waiting for the dfp library to be available and integrated too (otherwise the continuous integration process would be broken by the missing dependency). This issue will be marked as resolved when the tests will be committed. Thanks again for this contribution.
        Hide
        William Rossi added a comment -

        The parameter "extra" to exp() is extra input percision such that x+extra
        is the input parameter.

        The hiPrec[] inputs to exp and log are to return a higher precision output
        such that hiPrec[0] + hiPrec[1] is the desired result.

        I'm currently working on implementations of asin and acos.

        Show
        William Rossi added a comment - The parameter "extra" to exp() is extra input percision such that x+extra is the input parameter. The hiPrec[] inputs to exp and log are to return a higher precision output such that hiPrec [0] + hiPrec [1] is the desired result. I'm currently working on implementations of asin and acos.
        Hide
        Jeff Hain added a comment - - edited

        Hello.

        William, I checked your treatments (with the patch) using tests of another FastMath class I did some time ago (http://sourceforge.net/projects/jafama), and found some troubles with special cases, especially +-Infinity, NaN, or huge values: see "test_fastmath_wr.zip" attachment, which contains test code, and a log of their run.

        Also, running your tests, I had this exception:
        -19.731458173549257 2.696103718050787E-9 2.6961037180507868E-9 1.534029657343928E-16 0.5025524399680612
        Exception in thread "main" java.lang.RuntimeException: exp() had errors in excess of 0.502 ULP
        at FastMathWRTest.testExpAccuracy(FastMathWRTest.java:458)
        at FastMathWRTest.main(FastMathWRTest.java:18)

        Regards,

        Jeff

        Show
        Jeff Hain added a comment - - edited Hello. William, I checked your treatments (with the patch) using tests of another FastMath class I did some time ago ( http://sourceforge.net/projects/jafama ), and found some troubles with special cases, especially +-Infinity, NaN, or huge values: see "test_fastmath_wr.zip" attachment, which contains test code, and a log of their run. Also, running your tests, I had this exception: -19.731458173549257 2.696103718050787E-9 2.6961037180507868E-9 1.534029657343928E-16 0.5025524399680612 Exception in thread "main" java.lang.RuntimeException: exp() had errors in excess of 0.502 ULP at FastMathWRTest.testExpAccuracy(FastMathWRTest.java:458) at FastMathWRTest.main(FastMathWRTest.java:18) Regards, Jeff
        Hide
        William Rossi added a comment -

        Thanks Jeff. I will take a look at your tests. As for my test, the last number on the line shows the error in ULPs, so its just outside the threshold. I may have set the tolerance a bit too tight.

        Show
        William Rossi added a comment - Thanks Jeff. I will take a look at your tests. As for my test, the last number on the line shows the error in ULPs, so its just outside the threshold. I may have set the tolerance a bit too tight.
        Hide
        William Rossi added a comment -

        This patch fixes the issues found in Jeff's tests, and implements the asin() and acos() functions.

        Show
        William Rossi added a comment - This patch fixes the issues found in Jeff's tests, and implements the asin() and acos() functions.
        Hide
        Luc Maisonobe added a comment -

        The asinacos patch fixing the errors identified by Jeff and adding the asin and acos functions has been committed in the subversion repository as of r992872.
        The tests for FastMath depending on the dfp library have also been added as dfp in now a package in commons-math

        Thanks for this contribution and the various fixes.

        Show
        Luc Maisonobe added a comment - The asinacos patch fixing the errors identified by Jeff and adding the asin and acos functions has been committed in the subversion repository as of r992872. The tests for FastMath depending on the dfp library have also been added as dfp in now a package in commons-math Thanks for this contribution and the various fixes.
        Hide
        William Rossi added a comment -

        The attached patch implements the cbrt() function.

        Show
        William Rossi added a comment - The attached patch implements the cbrt() function.
        Hide
        Luc Maisonobe added a comment -

        Thanks Bill!
        You're last patch for cubic root and for asin/acos tests has been checked in both trunk and branch 2.X.
        It works fine and the cubic root function is pretty fast (about 30% faster than java.util.Math on my computer)

        Show
        Luc Maisonobe added a comment - Thanks Bill! You're last patch for cubic root and for asin/acos tests has been checked in both trunk and branch 2.X. It works fine and the cubic root function is pretty fast (about 30% faster than java.util.Math on my computer)
        Hide
        William Rossi added a comment -

        Thanks Luc,
        Glad to hear it is working well for you. I'll work on the hyperbolic functions next.

        Show
        William Rossi added a comment - Thanks Luc, Glad to hear it is working well for you. I'll work on the hyperbolic functions next.
        Hide
        William Rossi added a comment -

        Hyperbolic functions, cosh, sinh, tanh

        Show
        William Rossi added a comment - Hyperbolic functions, cosh, sinh, tanh
        Hide
        Luc Maisonobe added a comment -

        Thanks Bill,

        Your latest patch for sinh, cosh and tanh has been applied to trunk (r1004044) and to branch 2.X (r1004045).
        On my computer the improvement is about 35% faster than java.util.Math and 45% for sinh and tanh.

        Show
        Luc Maisonobe added a comment - Thanks Bill, Your latest patch for sinh, cosh and tanh has been applied to trunk (r1004044) and to branch 2.X (r1004045). On my computer the improvement is about 35% faster than java.util.Math and 45% for sinh and tanh.
        Hide
        Luc Maisonobe added a comment -

        Closing issue as it was included in version 2.2, which has been released

        Show
        Luc Maisonobe added a comment - Closing issue as it was included in version 2.2, which has been released

          People

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

            Dates

            • Created:
              Updated:
              Resolved:

              Development