trouver autant de chiffres de la racine carrée de 2 que possible

Question

#include <iostream> 
#include <cmath> 

using namespace std; 

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

salut c'est le programme pour trouver sqrt de 2 il imprime juste 1.41421 dans la sortie comment l'implémenter de manière à ce qu'il imprime 200000 chiffres après la virgule Point

1,41421 .......... jusqu'à 200 000 chiffres

y at-il approche d'imprimer comme ça?

Answer 1

Voici le code pour votre question qui utilise la bibliothèque GNU GMP. Le code imprimera 1000 chiffres de sqrt (2), augmenter le nombre dans les lignes avec un commentaire pour satisfaire votre demande.

#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; 
} 

S'il vous plaît le compiler avec la commande suivante:

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

Answer 2

L'exemple que vous donnez est précis dans la mesure où la précision de l'arithmétique double est la plus précise que la plupart des compilateurs C++ utilisent. En général, les ordinateurs ne sont pas équipés pour effectuer des calculs de plus grande précision. Si c'est un devoir de quelque sorte alors je suppose que vous devez trouver un algorithme de calcul - vous devez garder votre propre tableau de chiffres d'une certaine manière pour garder toute la précision dont vous avez besoin. Si vous avez une application réelle, vous devez absolument utiliser une bibliothèque de haute précision spécialement conçue pour faire ce genre d'arithmétique (GMP est une bonne possibilité open-source) - c'est une roue compliquée qui n'a pas besoin d'être réinventée.

Answer 3

It can be shown que

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

Et 1/sqrt (1-1/57122) peut être calculé en utilisant efficacement la série Taylor expansion:

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 (je l'ai légèrement reformaté et corrigé):

/* 
** 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; 
} 

Il faut environ une minute pour calculer 200.000 chiffres de sqrt (2). Notez toutefois qu'à 200 000 chiffres, les 11 derniers chiffres produits sont incorrects en raison des erreurs d'arrondi accumulées et que vous devez l'exécuter pour 200 012 chiffres si vous voulez 200 000 chiffres corrects.

Answer 4

Voici une solution qui calcule 1 million de chiffres de sqrt (2) en moins d'une minute dans le bon vieux langage de programmation Prolog. Il est basé sur la résolution de l'équation de Pell, voir également here:

p*p+1 = 2*q*q 

La relation recurence p '= 3P + 4q et q' = 2p + 3q peuvent être coulés en une multiplication matricielle. A savoir, nous voyons que si l'on multiplie le vecteur [p, q] par la matrice des coefficients, nous obtenons le vecteur [p «q »]:

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

Pour matrice A, nous pouvons utiliser une récursivité binaire de telle sorte que on peut calculer A^n en O (log n). Nous aurons besoin de gros nums.J'utilise ce code expérimental here dans lequel le programme principal est alors simplement:

/** 
    * 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]. 

La capture d'écran ci-dessous montre le calendrier et des résultats. J'utilisais 10 fois un million d'itérations. On peut comparer le résultat avec cette page here.

Ce qui est manquant est toujours un critère de calcul et coupe claire qui dit combien de chiffres sont stables. Nous aurons besoin de plus de temps pour le faire.

Modifier 20/12/2016:
Nous avons amélioré le code un peu par une borne supérieure de l'erreur relative, et plus calculer les chiffres stables en poussant le résultat. Le temps de calcul pour 1 million de chiffres est maintenant inférieur à 2 secondes:

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