Какой самый быстрый способ получить значение π? - PullRequest
Новая
       176

Какой самый быстрый способ получить значение π?

307 голосов
/ 01 августа 2008

Я ищу самый быстрый способ получить значение π, как личный вызов. Более конкретно, я использую способы, которые не включают использование #define констант, таких как M_PI, или жесткое кодирование числа в.

Программа ниже тестирует различные известные мне способы. Версия inline сборки, теоретически, является самым быстрым вариантом, хотя и явно не переносимым. Я включил его в качестве основы для сравнения с другими версиями. В моих тестах со встроенными модулями версия 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) по-прежнему выходит на первое место каждый раз.

Ответы [ 23 ]

11 голосов
/ 05 августа 2009

Метод Брента, опубликованный Крисом выше, очень хорош; Брент обычно является гигантом в области арифметики произвольной точности.

Если все, что вы хотите, это N-ая цифра, знаменитый формула BBP полезно в шестнадцатеричном формате

1 голос
/ 03 июня 2017

Расчет π по площади круга: -)
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 += " " } 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 = "

Generating circle...

"; setTimeout(function() { var circ = generateCircle(width); e.innerHTML = "
" + "π = " + circ[1].toFixed(2) + "\n" + circ[0] +"
"; }, 200); } calcPi ();
0 голосов
/ 18 июня 2018

лучший подход

Чтобы получить выходные данные стандартных констант, таких как pi или стандартных концепций, мы должны сначала использовать встроенные методы, доступные на используемом вами языке. Он вернет значение самым быстрым и лучшим способом. Я использую python, чтобы получить самый быстрый способ получить значение pi

  • Пи переменная математической библиотеки . В библиотеке Math переменная pi хранится как константа.

math_pi.py 

import math
print math.pi

Запустить скрипт с утилитой времени linux /usr/bin/time -v python math_pi.py

Выход: 

Command being timed: "python math_pi.py"
User time (seconds): 0.01
System time (seconds): 0.01
Percent of CPU this job got: 91%
Elapsed (wall clock) time (h:mm:ss or m:ss): 0:00.03
  • Использовать метод математики arc cos

acos_pi.py 

import math
print math.acos(-1)

Запустить скрипт с утилитой времени linux /usr/bin/time -v python acos_pi.py

Выход: 

Command being timed: "python acos_pi.py"
User time (seconds): 0.02
System time (seconds): 0.01
Percent of CPU this job got: 94%
Elapsed (wall clock) time (h:mm:ss or m:ss): 0:00.03

bbp_pi.py 

from decimal import Decimal, getcontext
getcontext().prec=100
print sum(1/Decimal(16)**k * 
          (Decimal(4)/(8*k+1) - 
           Decimal(2)/(8*k+4) - 
           Decimal(1)/(8*k+5) -
           Decimal(1)/(8*k+6)) for k in range(100))

Запустить скрипт с утилитой времени linux /usr/bin/time -v python bbp_pi.py

Выход: 

Command being timed: "python c.py"
User time (seconds): 0.05
System time (seconds): 0.01
Percent of CPU this job got: 98%
Elapsed (wall clock) time (h:mm:ss or m:ss): 0:00.06

Таким образом, лучший способ - использовать встроенный метод, предоставляемый языком, потому что они самые быстрые и лучшие для получения результата. В питоне используйте math.pi

Страница:
...