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

Мне очень нравится эта программа, которая приблизительно равна пи, глядя на своей собственной области :-)

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()
{
            _-_-_-_
       _-_-_-_-_-_-_-_-_
    _-_-_-_-_-_-_-_-_-_-_-_
  _-_-_-_-_-_-_-_-_-_-_-_-_-_
 _-_-_-_-_-_-_-_-_-_-_-_-_-_-_
 _-_-_-_-_-_-_-_-_-_-_-_-_-_-_
_-_-_-_-_-_-_-_-_-_-_-_-_-_-_-_
_-_-_-_-_-_-_-_-_-_-_-_-_-_-_-_
_-_-_-_-_-_-_-_-_-_-_-_-_-_-_-_
_-_-_-_-_-_-_-_-_-_-_-_-_-_-_-_
 _-_-_-_-_-_-_-_-_-_-_-_-_-_-_
 _-_-_-_-_-_-_-_-_-_-_-_-_-_-_
  _-_-_-_-_-_-_-_-_-_-_-_-_-_
    _-_-_-_-_-_-_-_-_-_-_-_
        _-_-_-_-_-_-_-_
            _-_-_-_
}

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

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

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

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

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

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

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

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

Там на самом деле целая книга , посвященная (среди прочего) для быстрых методов для вычисления \ пи: «Pi и AGM», Джонатан и Питер Боруэин ( доступен на Amazon ).

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

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

Времени сложность лучших алгоритмов в O (M (п) журнал (п)), где М (п) является временной сложностью для умножения двух п-разрядных целых чисел (М (п) = О (п войти (п) журнал (журнал (п))) с использованием алгоритмов БПФ на основе, которые обычно необходимы при расчете цифр \ Pi, и такой алгоритм реализован в GMP).

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

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

БЫСТРЫЙ способ , чтобы получить значение Пи:

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

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

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

смотреть Pi в интернете, например, здесь:

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

или здесь:

http://3.141592653589793238462643383279502884197169399375105820974944592.com/

или здесь:

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

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

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

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

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

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

Если эта статья верна, то алгоритм , который Bellard создал может быть один из скорейших доступны. Он создал пи 2.7 TRILLION цифры с помощью настольного компьютера!

... и он опубликовал свою работу здесь

Хорошая работа Bellard, Вы пионер!

http://www.theregister.co.uk/2010/01/06/very_long_pi/

Просто наткнулся на это тот, который должен быть здесь для полноты картины:

рассчитать PI в Пита

Он имеет довольно приятное свойство, что точность может быть улучшена делает программу больше.

Здесь «S некоторое представление о самом языке

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

Вы можете найти более подробную информацию здесь .

Во всяком случае, самый быстрый способ получить точное, как-много-как-вы-хотите значение числа пи в питон:

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

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

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

EDIT: У меня были некоторые проблемы с вырезать и вставить и identation, в любом случае вы можете найти источник здесь .

Если по быстрому вы имеете в виду быстро ввести в коде, вот golfscript решение:

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

Используйте Мачин-подобную формулу

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

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

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

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

Кроме того, Сет, это +3,14159265358979323846 3 , а не 64.

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

Pi именно 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;
        }
    }
}

Расчет 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))) );

Эта версия (в 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.

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

Если вы хотите , чтобы получить приближение значения я к делать вычисления, то:

PI = 3.141592654

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

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

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

π = - я Ln (-1)

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

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

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

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

Если все , что вы хотите это Nth цифра, известная формула ББП полезна в шестнадцатеричном

Расчет тг из круга области :-)

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

Лучше подход

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

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

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

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