Program for seems to freeze up despite functioning on earlier iterations

Question

I am writing a program to calculate Feigenbaum's constant using the Logistics equation by finding superstable values and then using the ratio of these superstable values to calculate the constant.

I use BigDecimals for almost all of my values so that I can maintain the necessary level of precision during the calculation of the constant.

I am adapting my code from the C++ code on pages 30-35 of the following file: http://webcache.googleusercontent.com/search?q=cache:xabTioRiF0IJ:home.simula.no/~logg/pub/reports/chaos_hw1.ps.gz+&cd=21&hl=en&ct=clnk&gl=us

I doubt what the program does even matters to my question. I run the program, and it seems to be working. The output i get for the first 4 superstable values and the first 2 d's is what is expected, but then after displaying these 4 rows, the program seems to just halt. I don't get an exception, but even after waiting for 30 minutes no more calculations are outputted. I can't figure out what exactly is causing it, because the calculation time should be about the same for each row, yet it obviously is not. Here is my output:

Feigenbaum constant calculation (using superstable points):
j       a           d
-----------------------------------------------------
1       2.0         N/A
2   3.23606797749979        N/A
4   3.4985616993277016  4.708943013540503
8   3.554640862768825   4.680770998010695

And here is my code:

import java.math.*;


// If there is a stable cycle, the iterates of 1/2 converge to the cycle. 
// This was proved by Fatou and Julia. 
// (What's special about x = 1/2 is that it is the critical point, the point at which the logistic map's derivative is 0.)
// Source: http://classes.yale.edu/fractals/chaos/Cycles/LogisticCycles/CycleGeneology.html

public class Feigenbaum4
{
public static BigDecimal r[] = new BigDecimal[19];
public static int iter = 0;
public static int iter1 = 20; // Iterations for tolerance level 1
public static int iter2 = 10; // Iterations for tolerance level 2
public static BigDecimal tol1 = new BigDecimal("2E-31"); // Tolerance for convergence level 1
public static BigDecimal tol2 = new BigDecimal("2E-27"); // Tolerance for convergence level 2
public static BigDecimal step = new BigDecimal("0.01"); // step when looking for second superstable a
public static BigDecimal x0 = new BigDecimal(".5");
public static BigDecimal aZero = new BigDecimal("2.0");

public static void main(String [] args)
{
    System.out.println("Feigenbaum constant calculation (using superstable points):");
    System.out.println("j\t\ta\t\t\td");
    System.out.println("-----------------------------------------------------");

    int n = 20;
    if (FindFirstTwo())
    {
        FindRoots(n);
    }

}

public static BigDecimal F(BigDecimal a, BigDecimal x)
{
    BigDecimal temp = new BigDecimal("1");
    temp = temp.subtract(x);
    BigDecimal ans = (a.multiply(x.multiply(temp)));
    return ans;
}

public static BigDecimal Dfdx(BigDecimal a, BigDecimal x)
{
    BigDecimal ans = (a.subtract(x.multiply(a.multiply(new BigDecimal("2")))));
    return ans;
}

public static BigDecimal Dfda(BigDecimal x)
{
    BigDecimal temp = new BigDecimal("1");
    temp = temp.subtract(x);
    BigDecimal ans = (x.multiply(temp));
    return ans;
}

public static BigDecimal NewtonStep(BigDecimal a, BigDecimal x, int n)
{
    // This function returns the Newton step for finding the root, a,
    // of fn(x,a) - x = 0 for a fixed x = X

    BigDecimal fval = F(a, x);
    BigDecimal dval = Dfda(x);

    for (int i = 1; i < n; i++)
    {
        dval = Dfda(fval).add(Dfdx(a, fval).multiply(dval));
        fval = F(a, fval);
    }

    BigDecimal ans = fval.subtract(x);
    ans = ans.divide(dval, MathContext.DECIMAL64);
    ans = ans.negate();
    return ans;

}

public static BigDecimal Root(BigDecimal a0, int n)
{
    // Find the root a of fn(x,a) - x = 0 for fixed x = X
    // with Newton’s method. The initial guess is a0.
    //
    // On return iter is the number of iterations if
    // the root was found. If not, iter is -1.

    BigDecimal a = a0;
    BigDecimal a_old = a0;
    BigDecimal ans;

    // First iter1 iterations with a stricter criterion,
    // tol1 < tol2

    for (iter = 0; iter < iter1; iter++)
    {
        a = a.add(NewtonStep(a, x0, n));

        // check for convergence
        BigDecimal temp = a.subtract(a_old);
        temp = temp.divide(a_old, MathContext.DECIMAL64);
        ans = temp.abs();

        if (ans.compareTo(tol1) < 0)
        {
            return a;
        }

        a_old = a;
    }

    // If this doesn't work, do another iter2 iterations 
    // with the larger tolerance tol2
    for (; iter < (iter1 + iter2); iter++)
    {
        a = a.add(NewtonStep(a, x0, n));

        // check for convergence
        BigDecimal temp = a.subtract(a_old);
        temp = temp.divide(a_old, MathContext.DECIMAL64);
        ans = temp.abs();

        if (ans.compareTo(tol2) < 0)
        {
            return a;
        }

        a_old = a;
    }

    BigDecimal temp2 = a.subtract(a_old);
    temp2 = temp2.divide(a_old, MathContext.DECIMAL64);
    ans = temp2.abs();

    // If not out at this point, iterations did not converge
    System.out.println("Error: Iterations did not converge,");
    System.out.println("residual = " + ans.toString());

    iter = -1;

    return a;
}

public static boolean FindFirstTwo()
{
    BigDecimal guess = aZero;
    BigDecimal r0;
    BigDecimal r1;

    while (true)
    {
        r0 = Root(guess, 1);
        r1 = Root(guess, 2);

        if (iter == -1)
        {
            System.out.println("Error: Unable to find first two superstable orbits");
            return false;
        }

        BigDecimal temp = r0.add(tol1.multiply(new BigDecimal ("2")));
        if (temp.compareTo(r1) < 0)
        {
            System.out.println("1\t\t" + r0.doubleValue() + "\t\t\tN/A");
            System.out.println("2\t" + r1.doubleValue() + "\t\tN/A");

            r[0] = r0;
            r[1] = r1;

            return true;
        }

        guess = guess.add(step);

    }


}

public static void FindRoots(int n)
{
    int n1 = 4;
    BigDecimal delta = new BigDecimal(4.0);
    BigDecimal guess;

    for (int i = 2; i < n; i++)
    {
        // Computation

        BigDecimal temp = (r[i-1].subtract(r[i-2])).divide(delta, MathContext.DECIMAL64);
        guess = r[i-1].add(temp);
        r[i] = Root(guess, n1);
        BigDecimal temp2 = r[i-1].subtract(r[i-2]);
        BigDecimal temp3 = r[i].subtract(r[i-1]);
        delta = temp2.divide(temp3, MathContext.DECIMAL64);

        // Output

        System.out.println(n1 + "\t" + r[i].doubleValue() + "\t" + delta.doubleValue());

        // Step to next superstable orbit

        n1 = n1 * 2;
    }
}

}

EDIT: Phil Steitz's Answer essentially solved my problem. I looked at some thread dumps, and after doing a bit of research to try and understand them, and compiling my program with debugging info, I was able to find that the main thread was stalling at the line:

dval = Dfda(fval).add(Dfdx(a, fval).multiply(dval));

as Phil Steit's said, by using

MathContext.DECIMAL128

in not only this line:

 dval = Dfda(fval).add(Dfdx(a, fval).multiply(dval));

but also in my multiplication operations in the methods F, Dfda, and Dfdx, I was able to get my code to work properly.

I used DECIMAL128 because the smaller precision made the calculation non-functional, because I compare them to such low numbers for the tolerance check.

Answer 1

I think that what is going on here is that when n is larger than about 10, your NewtonStep method becomes very slow because none of your multiply invocations limit the scale by providing a MathContext. When no MathContext is provided, the result of a multiply gets the sum of the scales of the multiplicands. With the code above, the scales of dval and fval inside the for loop in NewtonStep get very large for large n, resulting in very slow multiplications in this method and the methods that it calls. Try specifying MathContext.DECIMAL64 (or something else) in the multiply activations as you do for the divides.