我正在寻找最快的方法来获得π的值,作为一个个人挑战。更具体地说,我使用的方法不涉及使用#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)版本在每次测试中仍然名列前茅。


当前回答

BBP公式允许你计算第n位数字-以2为基数(或16)-甚至不需要麻烦之前的n-1位:)

其他回答

双打:

4.0 * (4.0 * Math.Atan(0.2) - Math.Atan(1.0 / 239.0))

这将精确到小数点后14位,足以填充双精度(不准确可能是因为弧切线中的其余小数被截断了)。

还有Seth,是3.141592653589793238463,不是64。

为了完整起见,一个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次迭代,我相信大约有80k次调用value()(在没有内存的情况下)。

下面的内容精确地回答了如何以尽可能快的方式——以最少的计算工作量——完成这一任务。即使你不喜欢这个答案,你也不得不承认,这确实是求圆周率值最快的方法。

求圆周率的最快方法是:

选择你最喜欢的编程语言 加载它的数学库 发现圆周率已经在那里定义了——可以使用了!

以防你手边没有数学图书馆。

第二快的方法(更普遍的解决方案)是:

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

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

或者在这里:

http://3.141592653589793238462643383279502884197169399375105820974944592.com/

或者在这里:

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

它可以非常快速地找到您想要使用的任何精度算术所需要的数字,并且通过定义一个常量,您可以确保不会浪费宝贵的CPU时间。

这不仅是一个有点幽默的回答,而且在现实中,如果有人愿意在实际应用中计算圆周率的值。这将是对CPU时间的巨大浪费,不是吗?至少我没有看到重新计算这个的实际应用。

还要考虑到NASA只使用15位圆周率来计算星际旅行:

TL;博士:https://twitter.com/Rainmaker1973/status/1463477499434835968 喷气推进实验室解释:https://www.jpl.nasa.gov/edu/news/2016/3/16/how-many-decimals-of-pi-do-we-really-need/

亲爱的主持人:请注意,OP问:“最快的方法来获得PI的值”

实际上,有一本书专门介绍了π的快速计算方法:Jonathan和Peter Borwein写的《π和AGM》(在亚马逊上可以买到)。

我对年度股东大会和相关算法进行了相当多的研究:这非常有趣(尽管有时并非微不足道)。

请注意,要实现大多数现代算法来计算\pi,您将需要一个多精度算术库(GMP是一个很好的选择,尽管距离我上次使用它已经有一段时间了)。

最佳算法的时间复杂度为O(M(n)log(n)),其中M(n)是使用基于fft算法对两个n位整数(M(n)=O(n log(n) log(log(n)))相乘的时间复杂度,通常在计算\pi数字时需要fft算法,GMP中实现了该算法。

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

从圆面积计算π:-)

<input id="range" type="range" min="10" max="960" value="10" step="50" oninput="calcPi()"> <br> <div id="cont"></div> <script> function generateCircle(width) { var c = width/2; var delta = 1.0; var str = ""; var xCount = 0; for (var x=0; x <= width; x++) { for (var y = 0; y <= width; y++) { var d = Math.sqrt((x-c)*(x-c) + (y-c)*(y-c)); if (d > (width-1)/2) { str += '.'; } else { xCount++; str += 'o'; } str += "&nbsp;" } str += "\n"; } var pi = (xCount * 4) / (width * width); return [str, pi]; } function calcPi() { var e = document.getElementById("cont"); var width = document.getElementById("range").value; e.innerHTML = "<h4>Generating circle...</h4>"; setTimeout(function() { var circ = generateCircle(width); e.innerHTML = "<pre>" + "π = " + circ[1].toFixed(2) + "\n" + circ[0] +"</pre>"; }, 200); } calcPi(); </script>