是什么让π值的最快方法？ [英] What is the fastest way to get the value of π?

问题描述

解决方案欢迎任何语言。 :-)我在寻找获得π的值，以最快的方式，作为一种个人的挑战。更具体地说，我使用的方法不涉及使用的#define D常数如 M_PI ，或硬编码在数

Solutions are welcome in any language. :-) I'm looking for the fastest way to obtain the value of π, as a personal challenge. More specifically I'm using ways that don't involve using #defined constants like M_PI, or hard-coding the number in.

下面的程序测试的各种方法，我知道的。内联汇编的版本，在理论上，最快的选项，但显然不便于携带;我已经包含它作为基线，比较其它版本。在我的测试，内置插件，在 4 * ATAN（1）版本是最快的GCC 4.2，因为它自动折叠 ATAN（ 1）成一个常数。随着 -fno-内建指定， ATAN2（0，-1）版本是最快的。

The program below tests the various ways I know of. The inline assembly version is, in theory, the fastest option, though clearly not portable; I've included it as a baseline to compare the other versions against. In my tests, with built-ins, the 4 * atan(1) version is fastest on GCC 4.2, because it auto-folds the atan(1) into a constant. With -fno-builtin specified, the atan2(0, -1) version is fastest.

下面是主要的测试计划（ pitimes.c ）：

Here's the main testing program (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系统：

And the inline assembly stuff (fldpi.c), noting that it will only work for x86 and x64 systems:

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

和构建脚本生成的所有配置我测试（<$ C C $> build.sh ）：

And a build script that builds all the configurations I'm testing (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

除了各种编译器标志之间的测试（我比较反对的64位过32位，因为最佳化是不同的），我也试着开关周围的测试顺序。该 ATAN2（0，-1）版本仍然名列前茅每一次，虽然。

Apart from testing between various compiler flags (I've compared 32-bit against 64-bit too, because the optimisations are different), I've also tried switching the order of the tests around. The atan2(0, -1) version still comes out top every time, though.

推荐答案

在蒙特卡罗方法，如前所述，适用一些伟大的概念，但它是，显然，并不是最快的 - 不是由一个长镜头，没有任何合理的效用。而且，这一切都取决于你在寻找什么样的精度。最快PI我所知道的是数字硬盘codeD。看着皮和的批[PDF] ，有很多公式。

The Monte Carlo method, as mentioned, applies some great concepts but it is, clearly, not the fastest --not by a long shot, not by any reasonable usefulness. Also, it all depends on what kind of accuracy you are looking for. The fastest pi I know of is the digits hard coded. Looking at Pi and Pi[PDF], there are a lot of formulas.

下面是快速收敛的方法（每次迭代〜14digits）。目前最快的应用， PiFast ，使用这个公式用的FFT 。我就写公式，因为code是直线前进。这个公式几乎被拉马努金发现并Chudnovsky 发现。这其实是他是如何计算数十亿的数量的数字 - 因此它不是一个方法忽视。式会溢出很快，因为我们正在分裂阶乘，这将是有利的，然后延迟处理该计算以除去术语

Here is a method that converges quickly (~14digits per iteration). The current fastest application, PiFast, uses this formula with the FFT. I'll just write the formula, since the code is straight forward. This formula was almost found by Ramanujan and discovered by Chudnovsky. It is actually how he calculated several billion digits of the number --so it isn't a method to disregard. The formula will overflow quickly since we are dividing factorials, it would be advantageous then to delay such calculating to remove terms.

其中，

下面是布伦特 - Salamin算法。维基提到当a和b是'足够接近则（A + B）^ 2 /4吨将是圆周率的近似值。我不知道'足够接近'的手段，但是从我的测试中，一个迭代得到2digits，两人得到了7，和三个有15个，当然这与双打，因此它可能在此基础上有错误的重presentation和真的计算可以更准确

Below is the Brent–Salamin algorithm. Wikipedia mentions that when a and b are 'close enough' then (a+b)^2/4t will be an approximation of pi. I'm not sure what 'close enough' means, but from my tests, one iteration got 2digits, two got 7, and three had 15, of course this is with doubles, so it might have error based on it's representation and the 'true' calculation could be more accurate.

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)

最后，如何对一些PI高尔夫球（800位）？ 160个字符！

Lastly, how about some pi golf (800 digits)? 160 characters!

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

这篇关于是什么让π值的最快方法？的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！