4.4 Summing Addends with Different Signs

The previous example involved addends that were all of the same sign. What happens when we sum both positive and negative numbers?

Our next two programs experiment with the following series:

which has alternating signs. ^[2]

^[2] This equation is due to the Indian mathematician Ramanujan. We'll see more of his formulas in Chapter 13.

Program 4-7 performs a simple straight summation of the series. See Listing 4-7. The summation stops as soon as the fractions are too small to change the value of the running sum.

Listing 4-7 Summing numbers with mixed signs.

package numbercruncher.program4_7;

import numbercruncher.mathutils.AlignRight;

/**
 * Program 4-7: Sum Numbers with Mixed Signs
 *
 * Sum a sequence numbers with alternating signs.  The sum should be 0.
 */
public class SumMixedSigns
{
    private static AlignRight ar = new AlignRight();

    public static void main(String args[])
    {
        int     k          = 0;
        int     odd        = 1;      // odd number
        float   kFactorial = 1;      // k!
        boolean subtract   = false;  // true if subtract, false if add

        float   sum        = 0;      // running sum
        float   prevSum    = -1;     // previous value of running sum
        ar.print("k", 2);
        ar.print("Numerator", 11);
        ar.print("Factorial", 16);
        ar.print("Fraction", 16);
        ar.print("Running sum", 16);
        ar.underline();

        // Loop until the running sum stops changing.
        do {
            float numerator = odd*odd;
            numerator += odd*numerator;

            float fraction = numerator/kFactorial;
            prevSum = sum;

            // Add or subtract the next fraction.
            if (subtract) fraction = -fraction;
            sum += fraction;

            ar.print(k, 2);
            ar.print(numerator, 11);
            ar.print(kFactorial, 16);
            ar.print(fraction, 16);
            ar.print(sum, 16);
            ar.println();

            ++k;
            kFactorial *= k;
            odd += 2;
            subtract = !subtract;
        } while (sum != prevSum);
    }
}

Output:

k  Numerator       Factorial        Fraction     Running sum
-------------------------------------------------------------
 0        2.0             1.0             2.0             2.0
 1       36.0             1.0           -36.0           -34.0
 2      150.0             2.0            75.0            41.0
 3      392.0             6.0      -65.333336      -24.333336
 4      810.0            24.0           33.75        9.416664
 5     1452.0           120.0           -12.1      -2.6833363
 6     2366.0           720.0        3.286111      0.60277486
 7     3600.0          5040.0     -0.71428573     -0.11151087
 8     5202.0         40320.0      0.12901786     0.017506987
 9     7220.0        362880.0    -0.019896384   -0.0023893975
10     9702.0       3628800.0     0.002673611    2.8421357E-4
11    12696.0       3.99168E7   -3.1806156E-4   -3.3847988E-5
12    16250.0      4.790016E8     3.392473E-5     7.674316E-8
13    20412.0     6.2270208E9    -3.277972E-6   -3.2012288E-6
14    25230.0    8.7178289E10    2.8940693E-7   -2.9118219E-6
15    30752.0   1.30767428E12    -2.351656E-8   -2.9353384E-6
16    37026.0   2.09227885E13    1.7696494E-9   -2.9335688E-6
17    44100.0   3.55687415E14  -1.2398527E-10   -2.9336927E-6
18    52022.0    6.4023735E15    8.125424E-12   -2.9336845E-6
19    60840.0   1.21645096E17   -5.001435E-13    -2.933685E-6
20    70602.0   2.43290202E18   2.9019664E-14    -2.933685E-6

The values of the running sum are supposed to oscillate about 0, alternating between positive and negative in step with the signs of the fractions. After the first couple of values, the running sum values should steadily decrease in magnitude. However, the pattern breaks when k = 12. The running sum's value seems smaller than expected, the next value has a greater magnitude, and all subsequent values are negative.

The pattern breaks when the exponents of the fraction and of the running sum are the same. Because the fraction and the running sum have opposite signs, cancellation error is the culprit. When k = 12, we subtract

Losing the leading significant digits throws off the remaining values of the running sum. It is also at this point that the factorial values (and hence the fraction values) begin to lose accuracy due to insufficient digits of precision.

Program 4-8 uses double arithmetic to show one solution to the cancellation problem. See Listing 4-8. It computes separate subtotals for the positive fractions and for the negative fractions, thus removing the cancellation problem. Then, it computes the correct final sum by adding together the two subtotals. So we see that, when summing numbers with mixed signs, it is better to sum the positive numbers and the negative numbers separately.

Listing 4-8 Summing numbers with mixed signs using separate positive and negative subtotals.

package numbercruncher.program4_8;

import numbercruncher.mathutils.AlignRight;

/**
 * Program 4-8: Sum Numbers with Mixed Signs,
 *              Positive and Negative Subtotals
 *
 * Sum a sequence of double numbers with alternating signs.
 * Compute separate positive and negative subtotals.  The final sum
 * should be 0.
 */
public class SumMixedSignsPosNeg
{
    public static void main(String args[])
    {
        AlignRight ar = new AlignRight();
        int    k          = 0;
        int    odd        = 1;   // odd number
        double kFactorial = 1;   // k!
        double posSum     = 0;   // running subtotal of pos fractions
        double negSum     = 0;   // running subtotal of neg fractions
        double prevPosSum = -1;  // previous value of positive sum
        double prevNegSum = 1;   // previous value of negative sum

        ar.print("k", 2);
        ar.print("Fraction", 25);
        ar.print("Positive subtotal", 20);
        ar.print("Negative subtotal", 21);
        ar.underline();

        // Loop until the positive and negative subtotals
        // no longer change.
        do {
            // Positive fraction and subtotal.
            double posNumerator = odd*odd;
            posNumerator += odd*posNumerator;
            double posFraction = posNumerator/kFactorial;
            prevPosSum = posSum;
            posSum += posFraction;

            ar.print(k, 2);
            ar.print(posFraction, 25);
            ar.print(posSum, 20);
            ar.println();

            ++k;
            kFactorial *= k;
            odd += 2;

            // Negative fraction and subtotal.
            double negNumerator = odd*odd;
            negNumerator += odd*negNumerator;
            double negFraction = -negNumerator/kFactorial;
            prevNegSum = negSum;
            negSum += negFraction;

            ar.print(k, 2);
            ar.print(negFraction, 25);
            ar.print(" ", 20);
            ar.print(negSum, 21);
            ar.println();

            ++k;
            kFactorial *= k;
            odd += 2;
        } while ((posSum != prevPosSum)  (negSum != prevNegSum));

        System.out.println("\nFinal sum = " + (posSum + negSum));
    }
}

Output:

k                 Fraction   Positive subtotal    Negative subtotal
--------------------------------------------------------------------
 0                      2.0                 2.0
 1                    -36.0                                    -36.0
 2                     75.0                77.0
 3       -65.33333333333333                      -101.33333333333333
 4                    33.75              110.75
 5                    -12.1                      -113.43333333333332
 6        3.286111111111111  114.03611111111111
 7      -0.7142857142857143                      -114.14761904761903
 8      0.12901785714285716  114.16512896825397
 9    -0.019896384479717814                      -114.16751543209875
10     0.002673611111111111  114.16780257936507
11   -3.1806156806156807E-4                      -114.16783349366682
12     3.392473010528566E-5  114.16783650409518
13    -3.277972027972028E-6                      -114.16783677163885
14      2.89406911430721E-7  114.16783679350209
15     -2.35165579080923E-8                      -114.16783679515541
16    1.7696492770897533E-9  114.16783679527174
17  -1.2398526491663746E-10                       -114.1678367952794
18    8.125423849197927E-12  114.16783679527987
19   -5.001434484046243E-13                       -114.1678367952799
20    2.901966448410855E-14   114.1678367952799
21  -1.5923761931532594E-15                       -114.1678367952799
22    8.287361182067708E-17   114.1678367952799
23   -4.101498195323127E-18                       -114.1678367952799

Final sum = 0.0