Программа, кажется, замерзает, несмотря на работу на более ранних итерациях.

Question

Я пишу программу для вычисления константы Фейгенбаума с использованием уравнения логистики путем нахождения сверхстабильных значений, а затем используя соотношение этих сверхстабильных значений для вычисления константы.

Я использую BigDecimals для почти всех моих значений, чтобы я мог поддерживать необходимый уровень точности во время вычисления константы.

Я адаптируя свой код из кода C++ на страницах 30-35 следующего файла: 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

Я сомневаюсь, что программа делает даже вопросы, на мой вопрос. Я запускаю программу и, похоже, работает. Результат, который я получаю для первых 4 суперстабильных значений, и первые 2 д'а - это то, что ожидается, но после отображения этих 4 строк программа, похоже, просто остановилась. Я не получаю исключения, но даже после ожидания в течение 30 минут больше вычислений не выводится. Я не могу понять, что именно вызывает его, потому что время вычисления должно быть примерно одинаковым для каждой строки, но, очевидно, это не так. Вот мой результат:

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 

И вот мой код:

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: Ответ Фил Steitz по существу решить мою проблему. Я посмотрел на некоторых резьбовых свалках, и после того, как делать немного исследований, чтобы попытаться понять их и компиляции моей программы с отладочной информации, я был в состоянии найти, что основной поток тянул на линии:

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

а Фил Steit сказал, используя

MathContext.DECIMAL128 

не только этой линии:

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

, но и в моих операций умножения в методах F, DFDA и Dfdx, я смог мой код работает нормально.

Я использовал DECIMAL128, потому что меньшая точность сделала вычисление нефункциональным, потому что я сравниваю их с такими низкими номерами для проверки допуска.

Answer 1

Я думаю, что здесь происходит то, что, когда n больше, чем около 10, ваш метод NewtonStep становится очень медленным, потому что ни одна из ваших multiply invocations не ограничивает масштаб, предоставляя MathContext. Когда MathContext не предоставляется, результат умножения получает сумму шкал мультипликаций. С помощью приведенного выше кода шкалы dval и fval внутри цикла for в NewtonStep становятся очень большими для больших n, что приводит к очень медленным умножениям в этом методе и методам, которые он вызывает. Попробуйте указать MathContext.DECIMAL64 (или что-то еще) в многократных активациях, как и для делений.