J'ai du mal à comprendre l'algorithme SpiGot pour π (PI) trouvé ici au bas de la page.
Je me perds au bas de la partie 2 "Mettez une forme régulière", je ne sais pas exactement comment implémenter cela dans C (ou toute langue vraiment)
3 Réponses :
#include <math.h>
#include <stdio.h>
#define N 100
int len = floor(10 * N/3) + 1;
int A[len];
for(int i = 0; i < len; ++i) {
A[i] = 2;
}
int nines = 0;
int predigit = 0;
for(int j = 1; j < N + 1; ++j) {
int q = 0;
for(int i = len; i > 0; --i) {
int x = 10 * A[i-1] + q*i;
A[i-1] = x % (2*i - 1);
q = x / (2*i - 1);
}
A[0] = q%10;
q = q/10;
if (9 == q) {
++nines;
}
else if (10 == q) {
printf("%d", predigit + 1);
for (int k = 0; k < nines; ++k) {
printf("%d", 0);
}
predigit, nines = 0;
}
else {
printf("%d", predigit);
predigit = q;
if (0 != nines) {
for (int k = 0; k < nines; ++k) {
printf("%d", 9);
}
nines = 0;
}
}
}
printf("%d", predigit);
Pourquoi s'initialisez-vous dans des boucles? Et pourquoi vos déclarations si inversées sont-elles inversées?
Que voulez-vous dire «initialiser pour les boucles»? Les instructions si sont inversées car cela vous aide à attraper des affectations par inadvertance (par exemple, si (q = 0) au lieu de si (q == 0) ). Le compilateur attrapera ma version ( si (0 = q) ) mais pas si (q = 0) .
Oh, vous voulez dire faire pour (int i = 0 ...) ? Effacer l'encombrement, je suppose. Aucune initialisation temporaire en dehors de la portée réelle des boucles. En théorie, cela devrait s'assurer que les variables d'index sont sensibles lexiquement à l'intérieur de la boucle, mais je pense que j'ai lu quelque part qu'ils restent liés à l'extérieur de la boucle.
// Spigot program for pi to NDIGITS decimals.
// 4 digits per loop.
// Thanks to Dik T. Winter and Achim Flammenkamp who originally made a compressed version of this.
#include "stdafx.h"
#include <stdio.h>
#include <stdlib.h>
#define NDIGITS 15536 //max digits to compute
#define LEN (NDIGITS/4+1)*14 //nec. array length
long a[LEN]; //array of 4-digit-decimals
long b; //nominator prev. base
long c = LEN; //index
long d; //accumulator and carry
long e = 0; //save previous 4 digits
long f = 10000; //new base, 4 decimal digits
long g; //denom previous base
long h = 0; //init switch
int main(void) {
for(; (b=c-=14) > 0 ;){ //outer loop: 4 digits per loop
for(; --b > 0 ;){ //inner loop: radix conv
d *= b; //acc *= nom prev base
if( h == 0 )
d += 2000*f; //first outer loop
else
d += a[b]*f; //non-first outer loop
g=b+b-1; //denom prev base
a[b] = d % g;
d /= g; //save carry
}
h = printf("%.4d",e+d/f);//print prev 4 digits
// %.4d to add leading zeros
d = e = d % f; //save currently 4 digits
//assure a small enough d
}
getchar();
return 0;
}
Je vois une différence dans les chiffres O / P du programme SPIGOT PI ci-dessus par rapport à http://www.numberworld.org/misc_runs/pi-10t/details.html
valeur correcte de 50 chiffres de PI: http://www.numberworld.org/misc_runs/pi-10t/details.html p>
3. P>
1415926535 8979323846 2643383279 5028841971 6939937971 6939937971 6939937510 P>
SpiGot PI: P>
3. P> 1415926535 8979323846 2643383279 5 ** 2399383271 6939937510 P>
^^^ zero missing
On dirait que ceci est un problème connu dans l'algorithme de Spigot, qui nécessite une étape corrective - reportez-vous à la mise en œuvre de Haenel qui corrige ce problème et produisent un résultat correct. Voir la bonne implémentation et la description du CORRECT au début de jjj.de/hfloat/spigot.haenel .txt
La mise en œuvre de Haenel de PI SpiGOT pour 32372 chiffres. Vérifié pour une séquence de chiffre correcte avec l'algorithme de Chudnovsky O / P. 2. Voici une version qui semble être correcte à cet égard et qui espérons-le, sans de nouveaux bugs: (il est également plus rapide et plus court.) Version "rapide": (environ 25% plus rapide) / * Calcul de PI à 32372 chiffres décimaux * / / * Taille du programme: 152 caractères * / / * Après DIK T. hiver, CWI Amsterdam * / non signé A = 1E4, B, C = 113316, D, E, F [113316], G ,salut; Main () {pour (; b = c, c- = 14; i = printf ("% 04d", E + D / A), E = D% A) tandis que (g = - B * 2) D = H * B + A * (i? F [B]: A / 5), H = D / - G, F [B] = DG * H;}
Vous êtes peut-être intéressé par ce Question .