[9] RFR of 8032027: Add BigInteger square root methods (original) (raw)
Louis Wasserman lowasser at google.com
Fri Oct 2 20:54:28 UTC 2015
- Previous message: [9] RFR of 8032027: Add BigInteger square root methods
- Next message: [9] RFR of 8032027: Add BigInteger square root methods
- Messages sorted by: [ date ] [ thread ] [ subject ] [ author ]
Have you investigated Guava's really quite tightly optimized implementation here? https://github.com/google/guava/blob/master/guava/src/com/google/common/math/BigIntegerMath.java#L242
A few years back I submitted a patch (now applied) to make BigInteger.doubleValue() very fast. If I recall correctly, that patch was originally inspired by my attempt to optimize sqrt on BigIntegers at the time.
Converting the BigInteger to a double, using Math.sqrt(double), and using that as a starting point for Newton's method (converting that floating point value back to a BigInteger) buys you many bits of precision very fast. That result isn't guaranteed to be >= the true result, but one iteration of Newton's method will fix that.
I'm quite certain you could improve on Guava's implementation even further with access to MutableBigInteger.
On Fri, Oct 2, 2015 at 1:42 PM Brian Burkhalter <brian.burkhalter at oracle.com> wrote:
Please review at your convenience.
Issue: https://bugs.openjdk.java.net/browse/JDK-8032027 Patch: http://cr.openjdk.java.net/~bpb/8032027/webrev.00/ Summary: Add sqrt() and sqrtAndRemainder() methods. The square root calculated is the integer square root ’s’ such that for a given integer ’n’ the value of ’s’ is the largest integer such that s*s <= n. In other words it is the floor of the mathematical square root of the value ’n' taken as a mathematical real number. The method of calculation is Newton iteration starting from a value larger than the square root which ensures that the convergence is monotonically decreasing to the result. An effort is made to make the implementation efficient in particular with respect to the amount of memory used. Any suggestions as to the improvement of the approach concerning memory use or any other aspect of the algorithm would be appreciated, as would be suggestions regarding the test. Thanks, Brian
- Previous message: [9] RFR of 8032027: Add BigInteger square root methods
- Next message: [9] RFR of 8032027: Add BigInteger square root methods
- Messages sorted by: [ date ] [ thread ] [ subject ] [ author ]