实现Spigot算法计算π (pi)

Question

实现Spigot算法计算π (pi)

calgorithmmathspigot-algorithm

10

我很难理解在这里找到的π（pi）的Spigot算法，尤其是在第2部分“将A转换为常规形式”的底部，我不确定如何在C（或任何语言）中实现它。

- Devan Buggay

1

你可能对这个问题感兴趣。 - Shafik Yaghmour

3个回答

2

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

- Progo

这似乎只是一个近似值，这是有意为之吗？ - jjxtra

1

当我将上面的 spigot pi 程序的输出数字与 http://www.numberworld.org/misc_runs/pi-10t/details.html 进行比较时，发现存在差异。

Pi 前 50 位正确值为： 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

通过修改长整型变量f=100000000，每次循环将4位数字更改为8位数字，可产生正确结果。

- Hari

1

似乎这是Spigot算法中已知的问题，需要纠正步骤 - 参考haenel的实现来修复此问题并产生正确的结果。请参阅http://www.jjj.de/hfloat/spigot.haenel.txt开头的正确C实现和描述。 - Hari

Haenel的Pi Spigot实现可计算到32372位小数。使用Chudnovsky算法输出正确的数字序列。 2. 这里有一个版本，它在这方面似乎是正确的，并且希望没有新的错误：（它也更快，更短。）"Fast"版本：（大约快25%）

/* 计算pi的32372个小数位 */ /* 程序大小：152个字符 */ /* 来自Dik T. Winter, CWI Amsterdam */ unsigned a=1e4,b,c=113316,d,e,f[113316],g,h,i; main(){for(;b=c,c-=14;i=printf("%04d",e+d/a),e=d%a) while(g=--b*2)d=h*b+a*(i?f[b]:a/5),h=d/--g,f[b]=d-g*h;}

- Hari

网页内容由stack overflow 提供, 点击上面的

可以查看英文原文，
原文链接

- Pedro Silva · Accepted Answer

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