найти как можно больше цифр квадратного корня из 2, как это возможно

Question

#include <iostream> 
#include <cmath> 

using namespace std; 

int main() 
{ 
double a = sqrt(2); 
cout << a << endl; 
} 

привет это программа, чтобы найти SQRT 2 печатает только 1,41421 на выходе, как реализовать это в таким образом, что он будет печатать 200000 знаков после десятичной точка

1,41421 .......... дО 200 000 цифр

есть ли подход к печати, как это?

Answer 1

Вот код по вашему вопросу, который использует GNU GMP library. Код будет печатать 1000 цифр sqrt (2), увеличивая число в строках с комментарием, чтобы удовлетворить ваш запрос.

#include <stdio.h> 
#include <gmp.h> 

int main(int argc, char *argv[]) 
{ 
    mpf_t res,two; 
    mpf_set_default_prec(1000000); // Increase this number. 
    mpf_init(res); 
    mpf_init(two); 
    mpf_set_str(two, "2", 10); 
    mpf_sqrt (res, two); 
    gmp_printf("%.1000Ff\n\n", res); // increase this number. 
    return 0; 
} 

Пожалуйста скомпилировать его с помощью следующей команды:

$gcc gmp.c -lgmp -lm -O0 -g3 

Answer 2

Пример, который вы даете, точна, поскольку точность двойной арифметики идет, это самая высокая точность, которую используют большинство компиляторов C++. В общем, компьютеры не предназначены для вычисления более высокой точности. Если это домашнее задание какого-то рода, то я подозреваю, что вам нужно выяснить алгоритм вычисления - вам нужно сохранить собственный массив цифр в некотором роде, чтобы сохранить всю необходимую точность. Если у вас есть приложение реального мира, вам обязательно нужно использовать библиотеку высокой точности, специально созданную для выполнения такой арифметики (GMP - это хорошая возможность с открытым исходным кодом) - это сложное колесо, которое не нуждается в повторном использовании.

Answer 3

It can be shown, что

sqrt(2) = (239/169)*1/sqrt(1-1/57122) 

И 1/SQRT (1-1/57122) может быть вычислена эффективно, используя ряд Тейлора расширение:

1/sqrt(1-x) = 1 + (1/2)x + (1.3)/(2.4)x^2 + (1.3.5)/(2.4.6)x^3 + ... 

There's also a C program available that uses this method (я немного переформатировать и исправил):

/* 
** Pascal Sebah : July 1999 
** 
** Subject: 
** 
** A very easy program to compute sqrt(2) with many digits. 
** No optimisations, no tricks, just a basic program to learn how 
** to compute in multiprecision. 
** 
** Formula: 
** 
** sqrt(2) = (239/169)*1/sqrt(1-1/57122) 
** 
** Data: 
** 
** A big real (or multiprecision real) is defined in base B as: 
**  X = x(0) + x(1)/B^1 + ... + x(n-1)/B^(n-1) 
**  where 0<=x(i)<B 
** 
** Results: (PentiumII, 450Mhz) 
** 
** 1000 decimals : 0.02seconds 
** 10000 decimals : 1.7s 
** 100000 decimals : 176.0s 
** 
** With a little work it's possible to reduce those computation 
** times by a factor of 3 and more. 
*/ 

#include <stdio.h> 
#include <stdlib.h> 

long B = 10000; /* Working base */ 
long LB = 4; /* Log10(base) */ 

/* 
** Set the big real x to the small integer Integer 
*/ 
void SetToInteger(long n, long* x, long Integer) 
{ 
    long i; 
    for (i = 1; i < n; i++) 
    x[i] = 0; 
    x[0] = Integer; 
} 

/* 
** Is the big real x equal to zero ? 
*/ 
long IsZero(long n, long* x) 
{ 
    long i; 
    for (i = 0; i < n; i++) 
    if (x[i]) 
     return 0; 
    return 1; 
} 

/* 
** Addition of big reals : x += y 
** Like school addition with carry management 
*/ 
void Add(long n, long* x, long* y) 
{ 
    long carry = 0, i; 
    for (i = n - 1; i >= 0; i--) 
    { 
    x[i] += y[i] + carry; 
    if (x[i] < B) 
     carry = 0; 
    else 
    { 
     carry = 1; 
     x[i] -= B; 
    } 
    } 
} 

/* 
** Multiplication of the big real x by the integer q 
*/ 
void Mul(long n, long* x, long q) 
{ 
    long carry = 0, xi, i; 
    for (i = n - 1; i >= 0; i--) 
    { 
    xi = x[i] * q; 
    xi += carry; 
    if (xi >= B) 
    { 
     carry = xi/B; 
     xi -= carry * B; 
    } 
    else 
     carry = 0; 
    x[i] = xi; 
    } 
} 

/* 
** Division of the big real x by the integer d 
** Like school division with carry management 
*/ 
void Div(long n, long* x, long d) 
{ 
    long carry = 0, xi, q, i; 
    for (i = 0; i < n; i++) 
    { 
    xi = x[i] + carry * B; 
    q  = xi/d; 
    carry = xi - q * d; 
    x[i] = q; 
    } 
} 

/* 
** Print the big real x 
*/ 
void Print(long n, long* x) 
{ 
    long i; 
    printf("%ld.", x[0]); 
    for (i = 1; i < n; i++) 
    printf("%04ld", x[i]); 
    printf("\n"); 
} 

/* 
** Computation of the constant sqrt(2) 
*/ 
int main(void) 
{ 
    long NbDigits = 200000, size = 1 + NbDigits/LB; 
    long* r2 = malloc(size * sizeof(long)); 
    long* uk = malloc(size * sizeof(long)); 
    long k = 1; 
    /* 
    ** Formula used: 
    ** sqrt(2) = (239/169)*1/sqrt(1-1/57122) 
    ** and 
    ** 1/sqrt(1-x) = 1+(1/2)x+(1.3)/(2.4)x^2+(1.3.5)/(2.4.6)x^3+... 
    */ 
    SetToInteger(size, r2, 1); /* r2 = 1 */ 
    SetToInteger(size, uk, 1); /* uk = 1 */ 
    while (!IsZero(size, uk)) 
    { 
    Div(size, uk, 57122); /* uk = u(k-1)/57122 * (2k-1)/(2k) */ 
    Div(size, uk, 2 * k); 
    Mul(size, uk, 2 * k - 1); 
    Add(size, r2, uk); /* r2 = r2+uk */ 
    k++; 
    } 
    Mul(size, r2, 239); 
    Div(size, r2, 169); /* r2 = (239/169)*r2 */ 

    Print(size, r2);  /* Print out of sqrt(2) */ 

    free(r2); 
    free(uk); 

    return 0; 
} 

Она занимает около одной минуты, чтобы вычислить 200000 цифр SQRT (2).

Обратите внимание, что при наличии 200 000 цифр последние 11 цифр были неправильными из-за скопированных ошибок округления, и вам нужно запустить их на 200,012 цифры, если вы хотите 200 000 правильных цифр.

Answer 4

Это решение, которое вычисляет 1 миллион цифр sqrt (2) менее чем за минуту на старом старом языке программирования Prolog. Он основан на решении уравнения Пелла см также here:

p*p+1 = 2*q*q 

В recurence отношение р '= 3p + 4q и Q' = 2p + 3q могут быть отлиты в виде матричного умножения. А именно мы видим, что если умножить вектор [р, д] матрицей коэффициентов получают вектор [р «д»]:

| p' | | 3 4 | | p | 
| | = |  | * | | 
| q' | | 2 3 | | q | 

Для матрицы А мы можем использовать двоичные рекурсии так, чтобы мы можем вычислить A^n в операциях O (log n). Нам понадобятся большие числа.Я использую этот экспериментальный код here посредством основной программы, то просто:

/** 
    * pell(N, R): 
    * Compute the N-the solution to p*p+1=2*q*q via matrices and return 
    * p/q in decimal format in R. 
    */ 
pell(N, R) :- 
    X is [[3,4],[2,3]], 
    Y is X^N, 
    Z is Y*[[1],[1]], 
    R is Z[1,1]*10^N//Z[2,1]. 

Следующий скриншот показывает время и некоторые результаты. Я использовал 10-миллионные итерации. Можно сравнить результат с этой страницей here.

Что не хватает по-прежнему ясно, четкие критерии и расчет, что говорит, сколько цифр стабильны. Нам понадобится еще немного времени.

Редактировать 20.12.2016:
Мы улучшили Кодекс немного по верхней границе относительной погрешности, а в дальнейшем вычислить стабильные цифры, подталкивая результат. Время вычисления на 1 миллион цифр составляет менее 2 секунд:

?- time(pell(653124, _, S)). 
% Uptime 1,646 ms, GC Time 30 ms, Thread Cpu Time 1,640 ms 
S = -1000000