алгоритм квадратного корня переполнения стека
Я не могу понять, почему этот алгоритм входит в бесконечный цикл, если введенное число превышает 12 цифр. Кто-нибудь может понять, почему это никогда не закончится? Благодарю. Я только что обновил алгоритм, чтобы использовать функцию fabs () и получить бесконечный цикл.
double squareroot(double x)
{ /* computes the square root of x */
/* make sure x is not negative .. no math crimes allowed! */
assert( x >= 0 );
if (x==0) return 0;
/* the sqrt must be between xhi and xlo */
double xhi = x;
double xlo = 0;
double guess = x/2;
/* We stop when guess*guess-x is very small */
while (abs(guess*guess-x) > 0.00001 )
{
if (guess*guess > x){
xhi = guess;
}
else {
xlo = guess;
}
guess = (xhi + xlo)/2;
}
return guess;
}
Решение
Я считаю, что вы должны использовать относительную ошибку для завершения, а не абсолютную ошибку.
while (abs((guess*guess-x) / guess) > 0.00001)
В противном случае это займет очень много времени (это не бесконечный цикл), чтобы вычислить квадратный корень из очень длинных значений.
http://en.wikipedia.org/wiki/Approximation_error
Ура!
РЕДАКТИРОВАТЬ: Кроме того, как указано ниже в комментариях, стоит проверить, guess было уже угадано, чтобы избежать бесконечного цикла с некоторыми конкретными угловыми случаями.
Другие решения
Я предлагаю подождать, пока вы не получите стабильный ответ, а не возиться со значениями epsilon:
double squareroot(double x)
{
double xhi = x;
double xlo = 0;
double guess = x/2;
while (guess * guess != x)
{
if (guess * guess > x)
xhi = guess;
else
xlo = guess;
double new_guess = (xhi + xlo) / 2;
if (new_guess == guess)
break; // not getting closer
guess = new_guess;
}
return guess;
}
Это не прямой ответ на ваш вопрос, а альтернативное решение.
Ты можешь использовать Метод Ньютона для нахождения корней:
assert(x >= 0);
if (x == 0)
return 0;
double guess = x;
for (int i=0; i<NUM_OF_ITERATIONS; i++)
guess -= (guess*guess-x)/(2*guess);
return guess;
24 итерации должны дать вам достаточно хорошее приближение, но вы также можете проверить абсолютную разницу.
http://floating-point-gui.de/errors/comparison/
Хех, похоже, вы не должны использовать abs (), как это. Есть некоторые случаи, когда это должно прекратиться, но я не буду, потому что это ограниченная точность.
Вместо этого используйте fabs ()
http://www.cygnus-software.com/papers/comparingfloats/comparingfloats.htm
Я бы сказал, что когда числа достаточно велики, вы не можете использовать абсолютное значение эпсилона, потому что оно не соответствует точности.
Попробуйте вместо этого использовать относительное сравнение. Рассмотрим следующую функцию, чтобы проверить, равны ли 2 числа:
bool are_eql(double n1, double n2, double abs_e, double rel_e)
{
// also add check that n1 and n2 are not NaN
double diff = abs(n1 - n2);
if (diff < abs_e)
return true;
double largest = max(abs(n1), abs(n2));
if (diff < largest * rel_e)
return true;
return false;
}