Нахождение квадратного корня от 2 до более чем десятичных знаков

Question

Я пытался получить эту работу, используя метод Ньютона, как описано здесь: wiki , используя следующий код, но проблема в том, что он дает точный результат только до 16 десятичных знаков. Я пытался увеличить количество итераций, но результат тот же. Я начал с первоначального предположения 1. Так как я могу улучшить точность ответа (до 100 или более десятичных знаков)? Благодарю. Код:

double x0,x1;
#define n 2
double f(double x0)
{
    return ((x0*x0)-n);
}
double firstDerv(double x0)
{
    return 2.0*x0;
}
int main()
{
    x0 = n/2.0;
    int i;
    for(i=0;i<40000;i++)
    {
        x1=x0-(f(x0)/((firstDerv(x0))));
        x0=x1;
    }
    printf("%.100lf\n",x1);
    return 0;
}

Answer 1

Чтобы обойти проблему с плавающей запятой ограниченной точности, вы также можете использовать метод Ньютона, чтобы найти в каждой итерации рациональное (a / b, с целыми числами a и b), которое является лучшим приближением к sqr (2).

Если x = a / b является значением, возвращенным из вашей последней итерации, то метод Ньютона утверждает, что новая оценка y = c / d равна:

y = x / 2 + 1 /x = a / 2b + b / a = (a ^ 2 + 2b ^ 2) (2ab)

так:

c = a ^ 2 + 2b ^ 2

d = 2ab

Точность удваивает каждую итерацию.Вы все еще ограничены в точности, которую можете достичь, потому что знаменатель и знаменатель быстро увеличиваются, но, возможно, найти реализацию больших целых чисел (или сочинить их самостоятельно) проще, чем найти реализацию с плавающей запятой произвольной точности.Кроме того, если вы действительно заинтересованы в десятичных дробях, то этот ответ вам не поможет.Это дает вам очень точную оценку sqr (2).

Всего несколько итераций a / b для алгоритма:

1/1, 3/2, 17/12, 577/ 408, 665857 / 470832.

665857/470832 приближает sqr (2) с ошибкой 1,59e-12.Ошибка останется порядка 1 / a ^ 2, поэтому реализация длинных a и b даст вам точность 1e-37 -ish.

Answer 2

Вы просто не можете сделать это с таким подходом; у двойников недостаточно битов, чтобы получить 100 знаков точности. Рассмотрите возможность использования библиотеки для произвольной точности, такой как GMP .

Answer 3

Числа с плавающей точкой на современных машинах IEEE754 и имеют ограниченную точность (около 15 цифр).

Если вам нужна большая точность, вам понадобятся bignums , которые (медленно) предоставляются библиотеками программного обеспечения, такими как GMP

Вы также можете кодировать свою программу на языках и реализациях, используя bignums.

Answer 4

возможно, это потому, что числа с плавающей запятой аппроксимируются компьютерами через форму m * 10 ^ e.так как m и e состоят из конечного числа цифр, вы не можете аппроксимировать все числа с абсолютной точностью.

думать о 1/3, что составляет 0,333333333333333 ...