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

я попытался получить эту работу, используя метод Ньютона, как описано здесь: вики, используя следующий код, но проблема в том, что он дает точный результат только до 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;
}

math newtons-method square-root
person pranay    schedule 14.12.2011    source источник
comment
Вы искали, какова точность используемого вами типа данных double? Прочитайте это: cplusplus.com/doc/tutorial/variables   -  person ypercubeᵀᴹ    schedule 14.12.2011
comment
Со стандартом IEEE double вы не сможете получить такую ​​высокую точность. Вам понадобится больший тип с плавающей запятой.   -  person Fred Foo    schedule 14.12.2011
comment
en.wikipedia.org/wiki/Arbitrary-precision_arithmetic#Libraries содержит список библиотек произвольных значений. Проверьте один из них, чтобы получить более 16 цифр точности.   -  person tafoo85    schedule 14.12.2011

Ответы (4)


arrow_upward
4
arrow_downward

Чтобы обойти проблему ограниченной точности с плавающей запятой, вы также можете использовать метод Ньютона, чтобы найти в каждой итерации рациональное число (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)

so:

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 как longs даст вам точность 1e-37 -ish.

person willem    schedule 14.12.2011
comment
+1 за предложение рационального арифметического подхода. Я могу представить себе написание длинной процедуры деления, которая выдает десятичные цифры по одной за раз, если кто-то хочет избежать библиотеки произвольной точности с плавающей запятой. Конечно, в какой-то момент даже 64-битные целые числа окажутся недостаточными для этой цели; они дадут точность примерно 1e-37 (как рациональную пару), которую вы предлагаете, и ОП хочет выйти далеко за рамки этого. Так что, возможно, использование GMP исключительно для его целых чисел с множественной точностью — это золотая середина. - person hardmath; 14.12.2011

arrow_upward
2
arrow_downward

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

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

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

person Basile Starynkevitch    schedule 14.12.2011
comment
спасибо, пробовал на питоне, но и там такой точности не получилось, хоть и больше, чем в с - person pranay; 14.12.2011
comment
По крайней мере, для целочисленных бигнумов они должны быть у SBCL и SciLab. (Я не знаю для плавающих бигнумов). - person Basile Starynkevitch; 14.12.2011

arrow_upward
2
arrow_downward

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

person Michael J. Barber    schedule 14.12.2011

arrow_upward
0
arrow_downward

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

подумайте о 1/3, что равно 0,333333333333333...

person zuloo    schedule 14.12.2011
comment
Большинство представлений с плавающей запятой находятся в двоичном формате, поэтому в форме m*2^e используется ваша запись (т.е. база 2, а не база 10) - person Basile Starynkevitch; 14.12.2011