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

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

1.08.2008 05:21:22
Должен быть способ сделать это в метапрограммировании C ++. Время выполнения будет действительно хорошим, но время компиляции не будет.
David Thornley 9.12.2009 16:27:22
Почему вы считаете, что использование atan (1) отличается от использования M_PI? Я бы понял, почему вы хотите сделать это, если вы используете только арифметические операции, но с atan я не вижу смысла.
erikkallen 23.12.2009 12:09:51
вопрос: почему бы вам не использовать константу? например, определяется библиотекой или вами? Вычисление Pi - это пустая трата циклов ЦП, так как эта проблема решалась снова и снова, причем число значащих цифр намного больше, чем необходимо для ежедневных вычислений
Tilo 28.10.2011 00:58:24
@ HopelessN00b На диалекте английского языка, на котором я говорю, «оптимизация» пишется с «s», а не с «z» (что произносится как «zed», кстати, а не «zee» ;-)). (Это не первый раз, когда мне приходится возвращать этот вид редактирования, если вы посмотрите на историю обзора.)
Chris Jester-Young 10.07.2014 22:52:32
Chris Jester-Young 2.05.2015 15:04:02
21 ОТВЕТ
РЕШЕНИЕ

В методе Монте-Карло , как уже упоминалось, применяются некоторые замечательные концепции, но он, очевидно, не самый быстрый, ни в дальнем плане, ни в какой-либо разумной мере. Кроме того, все зависит от того, какую точность вы ищете. Самый быстрый π, который я знаю, это тот, у которого цифры жестко запрограммированы. Глядя на Pi и Pi [PDF] , есть много формул.

Вот метод, который быстро сходится - около 14 цифр за итерацию. PiFast , текущее самое быстрое приложение, использует эту формулу с БПФ. Я просто напишу формулу, так как код прост. Эта формула была почти найдена Рамануджаном и открыта Чудновским . Это на самом деле, как он рассчитал несколько миллиардов цифр числа, так что это не метод игнорировать. Формула будет быстро переполнена, и, поскольку мы делим факториалы, было бы целесообразно отложить такие вычисления, чтобы удалить термины.

введите описание изображения здесь

введите описание изображения здесь

где,

введите описание изображения здесь

Ниже приведен алгоритм Брента – Саламина . В Википедии упоминается, что когда a и b «достаточно близки», тогда (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);}
202
5.09.2018 11:46:23
Предполагая, что вы пытаетесь реализовать первый самостоятельно, разве sqr (k3) не будет проблемой? Я почти уверен, что в итоге получится иррациональное число, которое вы должны будете оценить (IIRC, все корни, которые не являются целыми числами, иррациональны). Все остальное выглядит довольно просто, если вы используете арифметику с бесконечной точностью, но этот квадратный корень является нарушителем. Второй также включает в себя sqrt.
Bill K 30.08.2010 22:20:27
по моему опыту, «достаточно близко» обычно означает, что используется приближение ряда Тейлора.
Stephen 10.02.2011 19:46:21

Мне очень нравится эта программа, потому что она аппроксимирует π, глядя на свою область.

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()
{
            _-_-_-_
       _-_-_-_-_-_-_-_-_
    _-_-_-_-_-_-_-_-_-_-_-_
  _-_-_-_-_-_-_-_-_-_-_-_-_-_
 _-_-_-_-_-_-_-_-_-_-_-_-_-_-_
 _-_-_-_-_-_-_-_-_-_-_-_-_-_-_
_-_-_-_-_-_-_-_-_-_-_-_-_-_-_-_
_-_-_-_-_-_-_-_-_-_-_-_-_-_-_-_
_-_-_-_-_-_-_-_-_-_-_-_-_-_-_-_
_-_-_-_-_-_-_-_-_-_-_-_-_-_-_-_
 _-_-_-_-_-_-_-_-_-_-_-_-_-_-_
 _-_-_-_-_-_-_-_-_-_-_-_-_-_-_
  _-_-_-_-_-_-_-_-_-_-_-_-_-_
    _-_-_-_-_-_-_-_-_-_-_-_
        _-_-_-_-_-_-_-_
            _-_-_-_
}
115
3.09.2018 05:27:55
Если вы замените _ на -F <00 || --F-OO--, вам будет легче следовать :-)
Pat 24.09.2008 22:01:54
или, если вы замените _ на «if (предыдущий символ - '-') {OO--;} F--;"
FryGuy 12.01.2009 19:00:17
он печатает 0,25 здесь -.-
Johannes Schaub - litb 26.02.2009 19:30:38
Эта программа была великолепна в 1998 году, но была сломана, потому что современные препроцессоры более либеральны, вставляя пробелы вокруг макроподстановок, чтобы такие вещи не работали. Это реликвия, к сожалению.
Chris Lutz 23.12.2009 10:12:29
Перейдите --traditional-cppк cpp, чтобы получить намеченное поведение.
Nietzche-jou 6.01.2010 12:47:19

Вот общее описание методики расчета пи, которую я выучил в старшей школе.

Я делюсь этим только потому, что думаю, что это достаточно просто, чтобы каждый мог помнить об этом на неопределенный срок, плюс он учит вас концепции методов "Монте-Карло" - статистических методов получения ответов, которые не сразу кажутся выводимые через случайные процессы.

Нарисуйте квадрат и нарисуйте квадрант (одну четверть полукруга) внутри этого квадрата (квадрант с радиусом, равным стороне квадрата, чтобы он заполнил как можно большую часть квадрата)

Теперь бросьте дротик в квадрат и запишите, где он приземлится, то есть выберите случайную точку в любом месте квадрата. Конечно, он приземлился внутри квадрата, но внутри полукруга? Запишите этот факт.

Повторите этот процесс много раз - и вы обнаружите, что есть отношение количества точек внутри полукруга к общему количеству брошенных, назовите это отношение x.

Так как площадь квадрата r раз r, вы можете сделать вывод, что площадь полукруга равна x раз r раз r (то есть x умножено на квадрат). Следовательно, х раз 4 даст вам пи.

Это не быстрый метод для использования. Но это хороший пример метода Монте-Карло. И если вы посмотрите вокруг, вы можете обнаружить, что с помощью этих методов можно решить многие проблемы, не относящиеся к вашим вычислительным навыкам.

78
25.05.2012 21:09:03
Это метод, который мы использовали для вычисления Пи в проекте Java в школе. Просто использовал рандомизатор, чтобы придумать координаты x, y и чем больше «дротиков» мы бросили, тем ближе к Пи мы подошли.
Jeff Keslinke 2.02.2009 21:01:27

В интересах полноты, версия шаблона 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 итераций существует около 80 тыс. Вызовов value () (при отсутствии запоминания).

55
26.12.2018 21:38:13
Я запускаю это и получаю «пи ~ 3.14159265383»
maxwellb 29.06.2010 20:56:00
Ну, это точно с 9dp. Вы возражаете против чего-то или просто делаете наблюдение?
jon-hanson 30.06.2010 05:17:50
как называется алгоритм, используемый здесь для вычисления PI?
Sebastião Miranda 3.04.2016 17:37:30
Формула @ Sebastião-Миранда Лейбница , с усреднением ускорения улучшить сходимость. pi_calc<0, J>вычисляет каждый последующий член по формуле, а неспециалист - pi_calc<I, J>по среднему.
jon-hanson 3.04.2016 18:51:49

На самом деле есть целая книга, посвященная (среди прочего) быстрым методам вычисления \ pi: 'Pi и AGM' Джонатаном и Питером Боровейном ( доступно на Amazon ).

Я немного изучил AGM и связанные с ним алгоритмы: это довольно интересно (хотя иногда нетривиально).

Обратите внимание, что для реализации большинства современных алгоритмов для вычисления \ pi вам понадобится многоточная арифметическая библиотека ( GMP - неплохой выбор, хотя я давно его использовал).

Временная сложность лучших алгоритмов находится в O (M (n) log (n)), где M (n) - временная сложность для умножения двух n-битных целых чисел (M (n) = O (n). log (n) log (log (n))) с использованием алгоритмов на основе FFT, которые обычно необходимы при вычислении цифр \ pi, и такой алгоритм реализован в GMP).

Обратите внимание, что хотя математика, лежащая в основе алгоритмов, может и не быть тривиальной, сами алгоритмы обычно представляют собой несколько строк псевдокода, и их реализация обычно очень проста (если вы решили не писать свою собственную арифметику множественности точности :-)).

43
6.01.2012 00:48:57

Ниже приведен точный ответ, как сделать это максимально быстрым способом - с наименьшими вычислительными затратами . Даже если вам не нравится ответ, вы должны признать, что это действительно самый быстрый способ получить значение PI.

Самый быстрый способ получить значение Pi:

1) выберите свой любимый язык программирования 2) загрузите его библиотеку математики 3) и обнаружите, что Pi там уже определен - готов к использованию!

Если у вас нет математической библиотеки под рукой ..

ВТОРОЙ БЫСТРЫЙ способ (более универсальное решение) является:

найдите Пи в Интернете, например, здесь:

http://www.eveandersson.com/pi/digits/1000000 (1 миллион цифр .. какова ваша точность с плавающей запятой?)

или здесь:

http://3.141592653589793238462643383279502884197169399375105820974944592.com/

или здесь:

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

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

Это не только отчасти юмористический ответ, но на самом деле, если бы кто-нибудь пошел дальше и вычислил значение Pi в реальном приложении ... это было бы довольно большой тратой процессорного времени, не так ли? По крайней мере, я не вижу реального приложения для попытки пересчитать это.

Уважаемый Модератор: обратите внимание, что ОП спросил: «Самый быстрый способ получить значение ПИ»

42
15.01.2019 18:31:05

Формула BBP позволяет вычислять n-ую цифру - в базе 2 (или 16) - без необходимости сначала беспокоиться о предыдущих n-1 цифрах :)

27
29.08.2008 09:22:16

Вместо того, чтобы определять пи как константу, я всегда использую acos(-1).

23
25.05.2012 21:11:11
cos (-1) или acos (-1)? :-P Это (последний) является одним из тестовых примеров в моем исходном коде. Это один из моих предпочтений (наряду с atan2 (0, -1), который на самом деле такой же, как acos (-1), за исключением того, что acos обычно реализуется в терминах atan2), но некоторые компиляторы оптимизируют для 4 * atan (1) !
Chris Jester-Young 2.04.2009 20:27:46

Это «классический» метод, очень простой в реализации. Эта реализация в 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 "Costant 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;
}

РЕДАКТИРОВАТЬ: У меня были некоторые проблемы с вырезать и вставить и идентификации, в любом случае вы можете найти источник здесь .

21
31.01.2019 02:00:09

Если под самым быстрым вы подразумеваете самый быстрый ввод кода, вот решение для гольфа :

;''6666,-2%{2+.2/@*\/10.3??2*+}*`1000<~\;
20
6.08.2008 22:54:12

Используйте формулу, подобную Machin

176 * arctan (1/57) + 28 * arctan (1/239) - 48 * arctan (1/682) + 96 * arctan(1/12943) 

[; \left( 176 \arctan \frac{1}{57} + 28 \arctan \frac{1}{239} - 48 \arctan \frac{1}{682} + 96 \arctan \frac{1}{12943}\right) ;], for you TeX the World people.

Реализовано в схеме, например:

(+ (- (+ (* 176 (atan (/ 1 57))) (* 28 (atan (/ 1 239)))) (* 48 (atan (/ 1 682)))) (* 96 (atan (/ 1 12943))))

18
19.11.2011 22:39:49

Если вы хотите использовать приближение, 355 / 113оно подходит для 6 десятичных цифр и имеет дополнительное преимущество, заключающееся в возможности использования с целочисленными выражениями. Это не так важно в наши дни, так как «математический сопроцессор с плавающей запятой» перестал иметь какое-либо значение, но когда-то это было довольно важно.

17
17.09.2009 16:30:44

С двойниками:

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

Это будет с точностью до 14 знаков после запятой, что достаточно для заполнения двойного числа (неточность, вероятно, связана с тем, что остальные десятичные знаки в арктангенсах усекаются).

Также Сет, это 3,14159265358979323846 3 , а не 64.

16
25.05.2012 21:12:06

Пи ровно 3! [Профессор Фринк (Симпсоны)]

Шутка, но вот один в C # (требуется .NET-Framework).

using System;
using System.Text;

class Program {
    static void Main(string[] args) {
        int Digits = 100;

        BigNumber x = new BigNumber(Digits);
        BigNumber y = new BigNumber(Digits);
        x.ArcTan(16, 5);
        y.ArcTan(4, 239);
        x.Subtract(y);
        string pi = x.ToString();
        Console.WriteLine(pi);
    }
}

public class BigNumber {
    private UInt32[] number;
    private int size;
    private int maxDigits;

    public BigNumber(int maxDigits) {
        this.maxDigits = maxDigits;
        this.size = (int)Math.Ceiling((float)maxDigits * 0.104) + 2;
        number = new UInt32[size];
    }
    public BigNumber(int maxDigits, UInt32 intPart)
        : this(maxDigits) {
        number[0] = intPart;
        for (int i = 1; i < size; i++) {
            number[i] = 0;
        }
    }
    private void VerifySameSize(BigNumber value) {
        if (Object.ReferenceEquals(this, value))
            throw new Exception("BigNumbers cannot operate on themselves");
        if (value.size != this.size)
            throw new Exception("BigNumbers must have the same size");
    }

    public void Add(BigNumber value) {
        VerifySameSize(value);

        int index = size - 1;
        while (index >= 0 && value.number[index] == 0)
            index--;

        UInt32 carry = 0;
        while (index >= 0) {
            UInt64 result = (UInt64)number[index] +
                            value.number[index] + carry;
            number[index] = (UInt32)result;
            if (result >= 0x100000000U)
                carry = 1;
            else
                carry = 0;
            index--;
        }
    }
    public void Subtract(BigNumber value) {
        VerifySameSize(value);

        int index = size - 1;
        while (index >= 0 && value.number[index] == 0)
            index--;

        UInt32 borrow = 0;
        while (index >= 0) {
            UInt64 result = 0x100000000U + (UInt64)number[index] -
                            value.number[index] - borrow;
            number[index] = (UInt32)result;
            if (result >= 0x100000000U)
                borrow = 0;
            else
                borrow = 1;
            index--;
        }
    }
    public void Multiply(UInt32 value) {
        int index = size - 1;
        while (index >= 0 && number[index] == 0)
            index--;

        UInt32 carry = 0;
        while (index >= 0) {
            UInt64 result = (UInt64)number[index] * value + carry;
            number[index] = (UInt32)result;
            carry = (UInt32)(result >> 32);
            index--;
        }
    }
    public void Divide(UInt32 value) {
        int index = 0;
        while (index < size && number[index] == 0)
            index++;

        UInt32 carry = 0;
        while (index < size) {
            UInt64 result = number[index] + ((UInt64)carry << 32);
            number[index] = (UInt32)(result / (UInt64)value);
            carry = (UInt32)(result % (UInt64)value);
            index++;
        }
    }
    public void Assign(BigNumber value) {
        VerifySameSize(value);
        for (int i = 0; i < size; i++) {
            number[i] = value.number[i];
        }
    }

    public override string ToString() {
        BigNumber temp = new BigNumber(maxDigits);
        temp.Assign(this);

        StringBuilder sb = new StringBuilder();
        sb.Append(temp.number[0]);
        sb.Append(System.Globalization.CultureInfo.CurrentCulture.NumberFormat.CurrencyDecimalSeparator);

        int digitCount = 0;
        while (digitCount < maxDigits) {
            temp.number[0] = 0;
            temp.Multiply(100000);
            sb.AppendFormat("{0:D5}", temp.number[0]);
            digitCount += 5;
        }

        return sb.ToString();
    }
    public bool IsZero() {
        foreach (UInt32 item in number) {
            if (item != 0)
                return false;
        }
        return true;
    }

    public void ArcTan(UInt32 multiplicand, UInt32 reciprocal) {
        BigNumber X = new BigNumber(maxDigits, multiplicand);
        X.Divide(reciprocal);
        reciprocal *= reciprocal;

        this.Assign(X);

        BigNumber term = new BigNumber(maxDigits);
        UInt32 divisor = 1;
        bool subtractTerm = true;
        while (true) {
            X.Divide(reciprocal);
            term.Assign(X);
            divisor += 2;
            term.Divide(divisor);
            if (term.IsZero())
                break;

            if (subtractTerm)
                this.Subtract(term);
            else
                this.Add(term);
            subtractTerm = !subtractTerm;
        }
    }
}
16
31.01.2019 01:59:19

Рассчитать PI во время компиляции с D.

(Скопировано с DSource.org )

/** Calculate pi at compile time
 *
 * Compile with dmd -c pi.d
 */
module calcpi;

import meta.math;
import meta.conv;

/** real evaluateSeries!(real x, real metafunction!(real y, int n) term)
 *
 * Evaluate a power series at compile time.
 *
 * Given a metafunction of the form
 *  real term!(real y, int n),
 * which gives the nth term of a convergent series at the point y
 * (where the first term is n==1), and a real number x,
 * this metafunction calculates the infinite sum at the point x
 * by adding terms until the sum doesn't change any more.
 */
template evaluateSeries(real x, alias term, int n=1, real sumsofar=0.0)
{
  static if (n>1 && sumsofar == sumsofar + term!(x, n+1)) {
     const real evaluateSeries = sumsofar;
  } else {
     const real evaluateSeries = evaluateSeries!(x, term, n+1, sumsofar + term!(x, n));
  }
}

/*** Calculate atan(x) at compile time.
 *
 * Uses the Maclaurin formula
 *  atan(z) = z - z^3/3 + Z^5/5 - Z^7/7 + ...
 */
template atan(real z)
{
    const real atan = evaluateSeries!(z, atanTerm);
}

template atanTerm(real x, int n)
{
    const real atanTerm =  (n & 1 ? 1 : -1) * pow!(x, 2*n-1)/(2*n-1);
}

/// Machin's formula for pi
/// pi/4 = 4 atan(1/5) - atan(1/239).
pragma(msg, "PI = " ~ fcvt!(4.0 * (4*atan!(1/5.0) - atan!(1/239.0))) );
15
27.02.2013 15:13:26
К сожалению, касательные арктангенса основаны на пи, что несколько аннулирует этот расчет.
Grant Johnson 26.09.2008 14:42:05

В этой версии (в Delphi) нет ничего особенного, но она, по крайней мере, быстрее, чем версия Ника Ходжа, размещенная в его блоге :). На моей машине, она занимает около 16 секунд , чтобы сделать миллиард итераций, что дает значение 3,14159265 25879 (точная часть выделены жирным шрифтом).

program calcpi;

{$APPTYPE CONSOLE}

uses
  SysUtils;

var
  start, finish: TDateTime;

function CalculatePi(iterations: integer): double;
var
  numerator, denominator, i: integer;
  sum: double;
begin
  {
  PI may be approximated with this formula:
  4 * (1 - 1/3 + 1/5 - 1/7 + 1/9 - 1/11 .......)
  //}
  numerator := 1;
  denominator := 1;
  sum := 0;
  for i := 1 to iterations do begin
    sum := sum + (numerator/denominator);
    denominator := denominator + 2;
    numerator := -numerator;
  end;
  Result := 4 * sum;
end;

begin
  try
    start := Now;
    WriteLn(FloatToStr(CalculatePi(StrToInt(ParamStr(1)))));
    finish := Now;
    WriteLn('Seconds:' + FormatDateTime('hh:mm:ss.zz',finish-start));
  except
    on E:Exception do
      Writeln(E.Classname, ': ', E.Message);
  end;
end.
14
31.01.2019 01:59:01

В прежние времена, с маленькими размерами слов и медленными или несуществующими операциями с плавающей запятой, мы делали что-то вроде этого:

/* Return approximation of n * PI; n is integer */
#define pi_times(n) (((n) * 22) / 7)

Для приложений, которые не требуют большой точности (например, видеоигры), это очень быстро и достаточно точно.

13
20.02.2009 21:26:34
Для большей точности используйте 355 / 113. Очень точный по размеру вовлеченных чисел.
David Thornley 9.12.2009 16:25:38
Просто из любопытства: 22/7 это3 + 1/7
Agnius Vasiliauskas 1.06.2017 10:58:22

Если вы хотите вычислить аппроксимацию значения π (по некоторым причинам), вам следует попробовать алгоритм двоичного извлечения. Беллар в улучшение BBP дает делает PI в O (N ^ 2).


Если вы хотите получить аппроксимацию значения π для выполнения расчетов, то:

PI = 3.141592654

Конечно, это только приблизительное значение, и не совсем точное. Это немного больше, чем 0,00000000004102. (четыре десять-триллионные, около 4 / 10000000000 ).


Если вы хотите заняться математикой с π, возьмите себе карандаш и бумагу или пакет компьютерной алгебры и используйте точное значение π, π.

Если вы действительно хотите формулу, это весело:

π = - i ln (-1)

13
22.12.2009 21:13:49
Ваша формула зависит от того, как вы определяете ln в комплексной плоскости. Он должен быть несмежным вдоль одной линии в комплексной плоскости, и довольно часто эта линия является отрицательной действительной осью.
erikkallen 23.12.2009 12:14:19

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

Если вам нужна только N-ая цифра, известная формула BBP полезна в шестнадцатеричном виде.

12
4.08.2009 21:39:13
Метод Брента не был опубликован мной; он был опубликован Андреа, и я оказался последним, кто редактировал пост. :-) Но я согласен, этот пост заслуживает одобрения.
Chris Jester-Young 7.08.2009 11:44:05

Вычисление π из площади круга :-)

<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>

1
4.06.2017 16:53:53

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

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

  • пи переменная математической библиотеки . В библиотеке 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
  • Используйте метод аркос, потому что математика

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

0
18.06.2018 10:07:01