This is an automated email from the ASF dual-hosted git repository.

aherbert pushed a commit to branch master
in repository https://gitbox.apache.org/repos/asf/commons-numbers.git


The following commit(s) were added to refs/heads/master by this push:
     new 434fe48  Explicit grow expansion of -1 into x^2.
434fe48 is described below

commit 434fe48e101e70c47f561a2060659d29dc6f50ad
Author: aherbert <[email protected]>
AuthorDate: Wed Jan 22 16:03:21 2020 +0000

    Explicit grow expansion of -1 into x^2.
    
    This generates the intermediate expansion for (x^2 - 1) which is further
    away from 1 and closer to the next term y^2.
    
    The formula for sumLow has been rewritten to match Shewchuk's paper.
    
    fastSumLow was added for the grow expansion of -1 which assumes -1 is
    greater in magnitude than the other terms.
---
 .../apache/commons/numbers/complex/Complex.java    | 66 +++++++++++++++-------
 1 file changed, 46 insertions(+), 20 deletions(-)

diff --git 
a/commons-numbers-complex/src/main/java/org/apache/commons/numbers/complex/Complex.java
 
b/commons-numbers-complex/src/main/java/org/apache/commons/numbers/complex/Complex.java
index d5a2ca7..7c08c18 100644
--- 
a/commons-numbers-complex/src/main/java/org/apache/commons/numbers/complex/Complex.java
+++ 
b/commons-numbers-complex/src/main/java/org/apache/commons/numbers/complex/Complex.java
@@ -2489,19 +2489,43 @@ public final class Complex implements Serializable  {
 
     /**
      * Compute the round-off from the sum of two numbers {@code a} and {@code 
b} using
+     * Dekker's two-sum algorithm. The values are required to be ordered by 
magnitude:
+     * {@code |a| >= |b|}.
+     *
+     * @param a First part of sum.
+     * @param b Second part of sum.
+     * @param x Sum.
+     * @return <code>b - (x - a)</code>
+     * @see <a 
href="http://www-2.cs.cmu.edu/afs/cs/project/quake/public/papers/robust-arithmetic.ps";>
+     * Shewchuk (1997) Theorum 6</a>
+     */
+    private static double fastSumLow(double a, double b, double x) {
+        // x = a + b
+        // bVirtual = x - a
+        // y = b - bVirtual
+        return b - (x - a);
+    }
+
+    /**
+     * Compute the round-off from the sum of two numbers {@code a} and {@code 
b} using
      * Knuth's two-sum algorithm. The values are not required to be ordered by 
magnitude.
      *
      * @param a First part of sum.
      * @param b Second part of sum.
-     * @param sum Sum.
-     * @return <code>(b - (sum - (sum - b))) + (a - (sum - b))</code>
+     * @param x Sum.
+     * @return <code>(a - (x - (x - a))) + (b - (x - a))</code>
+     * @see <a 
href="http://www-2.cs.cmu.edu/afs/cs/project/quake/public/papers/robust-arithmetic.ps";>
+     * Shewchuk (1997) Theorum 7</a>
      */
-    private static double sumLow(double a, double b, double sum) {
-        final double aPrime = sum - b;
-        // sum - aPrime == bPrime.
-        // a - aPrime == a round-off
-        // b - bPrime == b round-off
-        return (a - aPrime) + (b - (sum - aPrime));
+    private static double sumLow(double a, double b, double x) {
+        // x = a + b
+        // bVirtual = x - a
+        // aVirtual = x - bVirtual
+        // bRoundoff = b - bVirtual
+        // aRoundoff = a - aVirtual
+        // y = aRoundoff + bRoundoff
+        final double bVirtual = x - a;
+        return (a - (x - bVirtual)) + (b - bVirtual);
     }
 
     /**
@@ -2531,25 +2555,27 @@ public final class Complex implements Serializable  {
         // Variables numbered from 1 as per Figure 7 (p.12). The output 
expansion h is placed
         // into e increasing its length for each grow expansion.
 
-        double e1 = x2Low;
-        double e2 = x2High;
-        double e3 = -1;
-        double e4;
-        double e5;
+        // We have two expansions for x^2 and y^2 and the whole number -1.
+        // Expecting (x^2 + y^2) close to 1 we generate first the intermediate 
expansion
+        // (x^2 - 1) moving the result away from 1 where there are sparse 
floating point
+        // representations. This is then added to a similar magnitude y^2.
+
+        // q=running sum
+        double q = x2Low - 1;
+        double e1 = fastSumLow(-1, x2Low, q);
+        double e3 = q + x2High;
+        double e2 = sumLow(q, x2High, e3);
+
         final double f1 = y2Low;
         final double f2 = y2High;
 
-        // q=running sum, p=previous sum
-        double q;
-        double p;
-
         // Grow expansion of f1 into e
         q = f1 + e1;
         e1 = sumLow(f1, e1, q);
-        p = q;
+        double p = q;
         q += e2;
         e2 = sumLow(p, e2, q);
-        e4 = q + e3;
+        double e4 = q + e3;
         e3 = sumLow(q, e3, e4);
 
         // Grow expansion of f2 into e (only required to start at e2)
@@ -2558,7 +2584,7 @@ public final class Complex implements Serializable  {
         p = q;
         q += e3;
         e3 = sumLow(p, e3, q);
-        e5 = q + e4;
+        final double e5 = q + e4;
         e4 = sumLow(q, e4, e5);
 
         // Final summation

Reply via email to