什么是获取π值最快的方法?

353
我正在寻找最快的方法来获取π的值,这是一个个人挑战。更具体地说,我正在使用不涉及使用#define常量,如M_PI或硬编码数字的方式。
下面的程序测试了我所知道的各种方式。理论上,内联汇编版本是最快的选择,尽管显然不可移植。我将其包含在内作为与其他版本进行比较的基线。在我的测试中,使用内置函数,4 * atan(1)版本在GCC 4.2上最快,因为它自动折叠atan(1)成一个常数。指定-fno-builtin后,atan2(0,-1)版本最快。
以下是主要测试程序(pitimes.c):
#include <math.h>
#include <stdio.h>
#include <time.h>

#define ITERS 10000000
#define TESTWITH(x) {                                                       \
    diff = 0.0;                                                             \
    time1 = clock();                                                        \
    for (i = 0; i < ITERS; ++i)                                             \
        diff += (x) - M_PI;                                                 \
    time2 = clock();                                                        \
    printf("%s\t=> %e, time => %f\n", #x, diff, diffclock(time2, time1));   \
}

static inline double
diffclock(clock_t time1, clock_t time0)
{
    return (double) (time1 - time0) / CLOCKS_PER_SEC;
}

int
main()
{
    int i;
    clock_t time1, time2;
    double diff;

    /* Warmup. The atan2 case catches GCC's atan folding (which would
     * optimise the ``4 * atan(1) - M_PI'' to a no-op), if -fno-builtin
     * is not used. */
    TESTWITH(4 * atan(1))
    TESTWITH(4 * atan2(1, 1))

#if defined(__GNUC__) && (defined(__i386__) || defined(__amd64__))
    extern double fldpi();
    TESTWITH(fldpi())
#endif

    /* Actual tests start here. */
    TESTWITH(atan2(0, -1))
    TESTWITH(acos(-1))
    TESTWITH(2 * asin(1))
    TESTWITH(4 * atan2(1, 1))
    TESTWITH(4 * atan(1))

    return 0;
}

而内联汇编的东西(fldpi.c)只适用于x86和x64系统:

double
fldpi()
{
    double pi;
    asm("fldpi" : "=t" (pi));
    return pi;
}

还有一个构建脚本,用于构建我正在测试的所有配置(build.sh):

#!/bin/sh
gcc -O3 -Wall -c           -m32 -o fldpi-32.o fldpi.c
gcc -O3 -Wall -c           -m64 -o fldpi-64.o fldpi.c

gcc -O3 -Wall -ffast-math  -m32 -o pitimes1-32 pitimes.c fldpi-32.o
gcc -O3 -Wall              -m32 -o pitimes2-32 pitimes.c fldpi-32.o -lm
gcc -O3 -Wall -fno-builtin -m32 -o pitimes3-32 pitimes.c fldpi-32.o -lm
gcc -O3 -Wall -ffast-math  -m64 -o pitimes1-64 pitimes.c fldpi-64.o -lm
gcc -O3 -Wall              -m64 -o pitimes2-64 pitimes.c fldpi-64.o -lm
gcc -O3 -Wall -fno-builtin -m64 -o pitimes3-64 pitimes.c fldpi-64.o -lm

除了在各种编译器标志之间进行测试(我也比较了32位和64位,因为优化不同),我还尝试过改变测试顺序。但是,每次都是atan2(0, -1)版本最优。


2
你为什么认为使用atan(1)与使用M_PI不同?如果你只使用算术运算,我可以理解你为什么这样做,但是对于atan,我看不出有什么意义。 - erikkallen
11
为什么你不想使用常量?比如由库定义或自己定义的常量?计算圆周率是浪费CPU周期,因为该问题已经被反复解决,并得出了比日常计算所需更多的有效数字。 - Tilo
1
除了预先计算常数π之外,只有一种解决方案更快:预先计算公式中出现的所有值,例如当需要周长时,您可以预先计算2*PI而不是在运行时每次将PI乘以2。 - ern0
5
在我所说的英语方言中,“optimisation”的拼写是带有“s”而不是“z”的(顺便提一下,“z”读作“zed”,而不是“zee” ;-))。如果您查看审查历史记录,您会发现这并不是我第一次撤销这种编辑。 - C. K. Young
3
@Pacerier 请见http://en.wiktionary.org/wiki/boggle 和 http://en.wiktionary.org/wiki/mindboggling。 - C. K. Young
显示剩余12条评论
24个回答

223
作为提及的蒙特卡罗方法,应用了一些伟大的概念,但显然不是最快的,无论如何都不是通过任何合理的措施。此外,这完全取决于您要寻找哪种准确性。我知道最快的π是硬编码的那个。看看PiPi[PDF],有很多公式。
这是一种快速收敛的方法-每次迭代约为14位数字。PiFast,当前最快的应用程序,使用FFT使用此公式。我将只写公式,因为代码很简单。这个公式几乎是由拉马努金(Ramanujan)发现并由Chudnovsky发现的。实际上,这就是他计算数十亿位数字的方法-所以它不是一个可以忽略的方法。该公式会很快溢出,并且由于我们正在除以阶乘,因此推迟这些计算以消除术语将是有利的。

enter image description here

enter image description here

在哪里,

enter image description here

以下是Brent-Salamin算法。维基百科提到,当ab足够接近时,(a + b)² / 4t将近似于π。我不确定"足够接近"是什么意思,但从我的测试来看,一次迭代得到2位数字,两次得到7位,三次得到15位,当然这是使用双精度浮点数,所以它可能存在表示误差,而真实的计算可能更准确。
let pi_2 iters =
    let rec loop_ a b t p i =
        if i = 0 then a,b,t,p
        else
            let a_n = (a +. b) /. 2.0 
            and b_n = sqrt (a*.b)
            and p_n = 2.0 *. p in
            let t_n = t -. (p *. (a -. a_n) *. (a -. a_n)) in
            loop_ a_n b_n t_n p_n (i - 1)
    in 
    let a,b,t,p = loop_ (1.0) (1.0 /. (sqrt 2.0)) (1.0/.4.0) (1.0) iters in
    (a +. b) *. (a +. b) /. (4.0 *. t)

最后,来一局派高尔夫(800位小数点)怎么样?只需 160 个字符!
int a=10000,b,c=2800,d,e,f[2801],g;main(){for(;b-c;)f[b++]=a/5;for(;d=0,g=c*2;c-=14,printf("%.4d",e+d/a),e=d%a)for(b=c;d+=f[b]*a,f[b]=d%--g,d/=g--,--b;d*=b);}

1
假设您正在尝试自己实现第一个,那么sqr(k3)会成为一个问题吗?我非常确定它最终会变成一个您必须估计的无理数(如果我没记错,所有不是整数的根都是无理数)。如果您使用无限精度算术,其他一切看起来都很简单,但是这个平方根是一个难以克服的问题。第二个也包括一个sqrt。 - Bill K
3
根据我的经验,“足够接近”通常意味着涉及到泰勒级数展开的近似。 - Stephen

127

我非常喜欢这个程序,因为它通过观察自己的面积来近似π。

IOCCC 1988:westley.c

#define _ -F<00||--F-OO--;
int F=00,OO=00;main(){F_OO();printf("%1.3f\n",4.*-F/OO/OO);}F_OO()
{
            _-_-_-_
       _-_-_-_-_-_-_-_-_
    _-_-_-_-_-_-_-_-_-_-_-_
  _-_-_-_-_-_-_-_-_-_-_-_-_-_
 _-_-_-_-_-_-_-_-_-_-_-_-_-_-_
 _-_-_-_-_-_-_-_-_-_-_-_-_-_-_
_-_-_-_-_-_-_-_-_-_-_-_-_-_-_-_
_-_-_-_-_-_-_-_-_-_-_-_-_-_-_-_
_-_-_-_-_-_-_-_-_-_-_-_-_-_-_-_
_-_-_-_-_-_-_-_-_-_-_-_-_-_-_-_
 _-_-_-_-_-_-_-_-_-_-_-_-_-_-_
 _-_-_-_-_-_-_-_-_-_-_-_-_-_-_
  _-_-_-_-_-_-_-_-_-_-_-_-_-_
    _-_-_-_-_-_-_-_-_-_-_-_
        _-_-_-_-_-_-_-_
            _-_-_-_
}

1
如果你用-F<00||--F-OO--替换_,那么就更容易理解了 :-) - Pat
1
或者,如果您将 _ 替换为 "if (前一个字符是 '-') { OO--; } F--;" - FryGuy
9
这个程序在1998年很棒,但由于现代预处理器在宏扩展周围插入空格以防止类似情况的发生时更加自由,所以已经失效了。遗憾的是,这是一件陈旧的事物。 - Chris Lutz
41
在运行 cpp 时添加 --traditional-cpp 参数即可获得预期的行为。 - Nietzche-jou
@Pat 如果你想知道我为什么编辑了它,那是因为我在LQP队列https://stackoverflow.com/review/low-quality-posts/16750528中看到了这个答案,因此为了避免删除,我将链接中的代码添加到了答案中。 - Petter Friberg

81

下面是我在高中学习时学到的计算π的一般方法。

我分享这个方法只是因为我认为它足够简单,任何人都可以永远记住它,而且它教会了你“蒙特卡罗”方法的概念——这是一种通过统计方法得出答案的方法,这些答案不是立即通过随机过程推导出来的。

画一个正方形,在正方形内画一个象限(半圆的四分之一)(半径等于正方形边长的象限,使其尽可能地填满正方形)

现在在正方形上扔一个飞镖,并记录它落在哪里——也就是说,在正方形内随机选择一个点。当然,它落在正方形内,但它是否在半圆内呢?记录这个事实。

重复这个过程很多次——你会发现有一个比率是半圆内部点数与总点数的比值,称这个比值为x。

由于正方形的面积是r乘以r,所以你可以推出半圆的面积是x乘以r乘以r(也就是x乘以r的平方)。因此x乘以4将给你π。

这不是一个快速的计算方法。但它是一个很好的蒙特卡罗方法的例子。如果你四处寻找,你可能会发现许多本来超出你的计算能力的问题可以通过这种方法解决。


2
这是我们在学校的Java项目中用来计算圆周率的方法。只需使用随机化程序生成x、y坐标,投掷的“飞镖”数量越多,我们就越接近圆周率。 - Jeff Keslinke

62

为了完整性,这里提供一个 C++ 模板版本。对于优化编译,它会在编译时计算 PI 的近似值,并且内联到单个值。

#include <iostream>

template<int I>
struct sign
{
    enum {value = (I % 2) == 0 ? 1 : -1};
};

template<int I, int J>
struct pi_calc
{
    inline static double value ()
    {
        return (pi_calc<I-1, J>::value () + pi_calc<I-1, J+1>::value ()) / 2.0;
    }
};

template<int J>
struct pi_calc<0, J>
{
    inline static double value ()
    {
        return (sign<J>::value * 4.0) / (2.0 * J + 1.0) + pi_calc<0, J-1>::value ();
    }
};


template<>
struct pi_calc<0, 0>
{
    inline static double value ()
    {
        return 4.0;
    }
};

template<int I>
struct pi
{
    inline static double value ()
    {
        return pi_calc<I, I>::value ();
    }
};

int main ()
{
    std::cout.precision (12);

    const double pi_value = pi<10>::value ();

    std::cout << "pi ~ " << pi_value << std::endl;

    return 0;
}

注意:当I > 10时,优化后的构建可能会变慢,非优化运行也是如此。对于12次迭代,我认为在没有备忘录的情况下调用value()大约有80k次。


我运行此代码并得到了“pi ~ 3.14159265383”的输出。 - maxwellb
5
这很准确,保留了9位小数。你是在反对什么还是只是做出观察? - jon hanson
这里使用的算法计算PI的名称是什么? - Sebastião Miranda
1
@sebastião-miranda 莱布尼茨公式 通过平均加速改善收敛性。 pi_calc<0, J> 从公式中计算每个连续的项,而非专门化的 pi_calc<I, J> 则计算平均值。 - jon hanson

45

实际上有一整本书专门讲述了计算\pi的快速方法,其中就包括 'Pi and the AGM',作者是Jonathan和Peter Borwein(在亚马逊上有售)。

我研究过AGM及其相关算法:它非常有趣(虽然有时候非常不易懂)。

请注意,要实现大多数现代计算\pi的算法,您需要使用多精度算术库(GMP是一个不错的选择,虽然我已经有一段时间没有使用它了)。

最佳算法的时间复杂度为O(M(n)log(n)),其中M(n)是两个n位整数相乘的时间复杂度(M(n)=O(n log(n) log(log(n)))使用FFT-based算法,通常在计算\pi的数字时需要此类算法,并且这种算法已经在GMP中实现)。

请注意,即使算法背后的数学可能不是那么容易理解,但算法本身通常只需几行伪代码,它们的实现通常非常简单(如果您选择不编写自己的多精度算术 :-))。


44

以下内容将精确地告诉你如何以最快的方式——用最少的计算量来获取圆周率的值。即使你不喜欢这个答案,你也必须承认这是最快的获取圆周率的方法。

获取圆周率的最快方法是:

  1. 选择你喜欢的编程语言
  2. 加载其数学库
  3. 找到已经定义好的圆周率——可以直接使用!

如果你手头没有数学库..

第二快的方法(更通用的解决方案)是:

在互联网上查找圆周率,例如在这里:

http://www.eveandersson.com/pi/digits/1000000(一百万位小数..你的浮点精度是多少?)

或者在这里:

http://3.141592653589793238462643383279502884197169399375105820974944592.com/

或者在这里:

http://en.wikipedia.org/wiki/Pi

找到你需要的数字以进行任何精度算术非常快速,通过定义一个常量,您可以确保不浪费宝贵的 CPU 时间。

这不仅是一个有趣的答案,而且在现实中,如果有人要在真正的应用程序中计算 Pi 的值...那将是相当大的 CPU 时间浪费,不是吗?至少我没有看到尝试重新计算这个值的真正应用。

还要考虑,NASA 仅使用 15 位数字来计算星际旅行:


1
亲爱的Tilo:请注意,原帖中提到:“我正在寻找获取π值的最快方法,作为个人挑战。更具体地说,我使用的方法不涉及使用#define常量(如M_PI)或在代码中硬编码该数字。” - Max
4
亲爱的@Max:请注意,原帖在我回答后被 编辑 了 - 那显然不是我的错 ;)我的解决方案仍然是最快的方式,可以使用任何所需的浮点精度解决问题,并且优雅地不消耗CPU循环 :) - Tilo
1
哦,抱歉,我没有意识到。 只是想,硬编码的常量是否比计算π精度低?我猜这取决于使用的编程语言以及创建者愿意放入多少位数 :-) - Max
我意识到你以最诚实和有趣的方式回答了这个问题,但我也意识到有很多人认真对待并将其作为一种生活方式 - 这个问题上的赞数证明了这一点:不要做任何需要动脑筋的事情,因为其他人已经、正在或将会替你完成。毕竟,人们已经可以通过手机向朋友发送预先制作好的生日祝福,因为他们无法想出几句原创的话来表达... - Yin Cognyto
https://vm.tiktok.com/ZTdsuAWQK/?k=1 - Tilo

28

使用BBP公式,您可以计算基数为2(或16)的第n位数字,而无需先关心前面的n-1位数字:)


24
这是一个“经典”的方法,非常容易实现。 Python语言的实现方式(不是最快的语言)如下:
from math import pi
from time import time


precision = 10**6 # higher value -> higher precision
                  # lower  value -> higher speed

t = time()

calc = 0
for k in xrange(0, precision):
    calc += ((-1)**k) / (2*k+1.)
calc *= 4. # this is just a little optimization

t = time()-t

print "Calculated: %.40f" % calc
print "Constant pi: %.40f" % pi
print "Difference: %.40f" % abs(calc-pi)
print "Time elapsed: %s" % repr(t)

您可以在这里找到更多信息。

无论如何,在Python中获取精确的π值的最快方法是:

from gmpy import pi
print pi(3000) # the rule is the same as 
               # the precision on the previous code

这是gmpy pi方法的源代码,我认为在这种情况下代码并没有注释有用:

static char doc_pi[]="\
pi(n): returns pi with n bits of precision in an mpf object\n\
";

/* This function was originally from netlib, package bmp, by
 * Richard P. Brent. Paulo Cesar Pereira de Andrade converted
 * it to C and used it in his LISP interpreter.
 *
 * Original comments:
 * 
 *   sets mp pi = 3.14159... to the available precision.
 *   uses the gauss-legendre algorithm.
 *   this method requires time o(ln(t)m(t)), so it is slower
 *   than mppi if m(t) = o(t**2), but would be faster for
 *   large t if a faster multiplication algorithm were used
 *   (see comments in mpmul).
 *   for a description of the method, see - multiple-precision
 *   zero-finding and the complexity of elementary function
 *   evaluation (by r. p. brent), in analytic computational
 *   complexity (edited by j. f. traub), academic press, 1976, 151-176.
 *   rounding options not implemented, no guard digits used.
*/
static PyObject *
Pygmpy_pi(PyObject *self, PyObject *args)
{
    PympfObject *pi;
    int precision;
    mpf_t r_i2, r_i3, r_i4;
    mpf_t ix;

    ONE_ARG("pi", "i", &precision);
    if(!(pi = Pympf_new(precision))) {
        return NULL;
    }

    mpf_set_si(pi->f, 1);

    mpf_init(ix);
    mpf_set_ui(ix, 1);

    mpf_init2(r_i2, precision);

    mpf_init2(r_i3, precision);
    mpf_set_d(r_i3, 0.25);

    mpf_init2(r_i4, precision);
    mpf_set_d(r_i4, 0.5);
    mpf_sqrt(r_i4, r_i4);

    for (;;) {
        mpf_set(r_i2, pi->f);
        mpf_add(pi->f, pi->f, r_i4);
        mpf_div_ui(pi->f, pi->f, 2);
        mpf_mul(r_i4, r_i2, r_i4);
        mpf_sub(r_i2, pi->f, r_i2);
        mpf_mul(r_i2, r_i2, r_i2);
        mpf_mul(r_i2, r_i2, ix);
        mpf_sub(r_i3, r_i3, r_i2);
        mpf_sqrt(r_i4, r_i4);
        mpf_mul_ui(ix, ix, 2);
        /* Check for convergence */
        if (!(mpf_cmp_si(r_i2, 0) && 
              mpf_get_prec(r_i2) >= (unsigned)precision)) {
            mpf_mul(pi->f, pi->f, r_i4);
            mpf_div(pi->f, pi->f, r_i3);
            break;
        }
    }

    mpf_clear(ix);
    mpf_clear(r_i2);
    mpf_clear(r_i3);
    mpf_clear(r_i4);

    return (PyObject*)pi;
}

编辑:我在复制粘贴和缩进方面遇到了一些问题,你可以在这里找到源代码。


24

我总是使用acos(-1)来代替定义pi常量。


2
cos(-1) 或者是 acos(-1)? :-P 那个(后者)是我原始代码中的一个测试案例。它是我喜欢的案例之一(和 atan2(0, -1) 一样),不过有些编译器针对 4 * atan(1) 进行了优化! - C. K. Young

21

如果你所指的“最快”是指输入代码的速度,那么这里是 golfscript 的解决方案:

;''6666,-2%{2+.2/@*\/10.3??2*+}*`1000<~\;

网页内容由stack overflow 提供, 点击上面的
可以查看英文原文,
原文链接