Кажется, что программа for зависает несмотря на то, что она работает на более ранних итерациях
Я пишу программу для вычисления постоянной Фейгенбаума, используя уравнение логистики, находя суперстабильные значения и затем используя соотношение этих суперстабильных значений для вычисления константы.
Я использую 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;
}
}
}
РЕДАКТИРОВАТЬ: Ответ Phil Steitz по существу решил мою проблему. Я посмотрел на некоторые дампы потоков, и после небольшого исследования, чтобы попытаться понять их, и скомпилировав мою программу с отладочной информацией, я смог обнаружить, что основной поток остановился:
dval = Dfda(fval).add(Dfdx(a, fval).multiply(dval));
как сказал Фил Стейт, используя
MathContext.DECIMAL128
не только в этой строке:
dval = Dfda(fval).add(Dfdx(a, fval).multiply(dval));
но также в моих операциях умножения в методах F, Dfda и Dfdx я смог заставить свой код работать должным образом.
Я использовал DECIMAL128, потому что меньшая точность делала вычисления не функциональными, потому что я сравнивал их с такими низкими числами для проверки допуска.
1 ответ
Я думаю, что здесь происходит то, что, когда n больше, чем около 10, ваш NewtonStep метод становится очень медленным, потому что ни один из ваших multiply вызовы ограничивают масштаб, предоставляя MathContext. Когда MathContext не предоставлен, результат умножения получает сумму масштабов умножения. С кодом выше, весы dval а также fval внутри цикла for в NewtonStep очень большое значение для больших n, что приводит к очень медленному умножению в этом методе и вызываемых им методах. Попробуйте указать MathContext.DECIMAL64 (или что-то еще) в активациях умножения, как и для делений.