Реализация алгоритма SPIGOT для π (PI)
-
28-09-2019 - |
Вопрос
Мне трудно понять Алгоритм Spigot Для π (PI) найдено здесь внизу страницы.
Я теряюсь в нижней части части 2 «поставить в обычную форму», я не точно уверен, как реализовать это в Слияние (или любой язык действительно)
Решение
#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);
Другие советы
// 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("%d",e+d/f);//print prev 4 digits
d = e = d % f; //save currently 4 digits
//assure a small enough d
}
getchar();
return 0;
}
Я вижу разницу в цифрах O / P вышеуказанного SPIGOT PI Program по сравнению с http://www.numberworld.org/misc_runs/pi-10t/details.html.
Правильное значение 50 цифр PI:http://www.numberworld.org/misc_runs/pi-10t/details.html.
3.
1415926535 8979323846 2643383279 5028841971 6939937510
Выше SPIGOT PI:
3.
1415926535 8979323846 2643383279 5**(0)**28841971 6939937510
^^^ zero missing
Изменил 4 цифры на петлю до 8 цифр путем модификации длинного f = 100000000;
произвел правильный результат.
Не связан с StackOverflow