Hva er den raskeste måten å få verdien av π?

stemmer
284

Jeg leter etter den raskeste måten å få verdien av π, som en personlig utfordring. Mer spesifikt, jeg bruker metoder som ikke involverer bruker #definekonstanter som M_PI, eller hard-koding nummeret i.

Programmet under tester de ulike måtene jeg vet om. Inline montering versjonen er, i teorien, den raskeste alternativet, men klart ikke bærbar. Jeg har tatt det som en basis for å sammenligne mot de andre versjonene. I mine tester, med innebygde moduler, den 4 * atan(1)er versjon raskest på GCC 4.2, fordi det automatisk bretter atan(1)inn en konstant. Med -fno-builtinspesifisert, det atan2(0, -1)er versjon raskest.

Her er de viktigste testprogram ( 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;
}

Og inline montering ting ( fldpi.c) som bare vil fungere for x86 og x64-systemer:

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

Og en bygge skript som bygger alle konfigurasjonene Jeg tester ( 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

Bortsett fra testing mellom forskjellige kompilator flagg (I har sammenlignet med 32-bit mot 64-bit også, fordi optimeringene er forskjellige), Jeg har også prøvd å bytte rekkefølgen av prøvene rundt. Men likevel, atan2(0, -1)versjonen kommer fortsatt ut på toppen hver gang.

Publisert på 01/08/2008 klokken 05:21
kilden bruker
På andre språk...                            


23 svar

stemmer
186

The Monte Carlo-metoden , som nevnt, gjelder noen gode konsepter, men det er klart, ikke den raskeste, ikke av en lang skudd, ikke av noen rimelig tiltak. Også, alt avhengig av hva slags nøyaktighet du leter etter. Den raskeste π jeg vet om er den med sifrene hard kodet. Ser på Pi og Pi [PDF] , er det en rekke formler.

Her er en metode som konvergerer raskt - ca 14 sifre per iterasjon. PiFast , den nåværende raskeste søknad, bruker denne formel med FFT . Jeg skal bare skrive formelen, siden koden er grei. Denne formelen ble nesten funnet av Ramanujan og oppdaget av Chudnovsky . Det er faktisk hvordan han regnet flere milliarder sifrene i nummeret - så det er ikke en metode for å se bort fra. Formelen vil flomme over raskt og, siden vi dele factorials, ville det være fordelaktig så å utsette slike beregninger for å fjerne betingelser.

skriv bildebeskrivelse her

skriv bildebeskrivelse her

hvor,

skriv bildebeskrivelse her

Nedenfor er Brent-Salamin algoritme . Wikipedia nevner at når en og b er "nær nok" da (a + b) ² / 4t vil være en tilnærming til π. Jeg er ikke sikker på hva "nær nok" betyr, men fra mine tester, en gjentakelse fikk 2 sifre, to fikk 7, og tre hadde 15, dette er selvsagt med dobler, så det kan ha en feil basert på sin representasjon og den virkelige beregning kan være mer nøyaktig.

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)

Til slutt, hva med noen pi golf (800 sifre)? 160 tegn!

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);}
Svarte 02/08/2008 kl. 18:22
kilden bruker

stemmer
98

Jeg liker dette programmet, som tilnærmet pi ved å se på sitt eget område :-)

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()
{
            _-_-_-_
       _-_-_-_-_-_-_-_-_
    _-_-_-_-_-_-_-_-_-_-_-_
  _-_-_-_-_-_-_-_-_-_-_-_-_-_
 _-_-_-_-_-_-_-_-_-_-_-_-_-_-_
 _-_-_-_-_-_-_-_-_-_-_-_-_-_-_
_-_-_-_-_-_-_-_-_-_-_-_-_-_-_-_
_-_-_-_-_-_-_-_-_-_-_-_-_-_-_-_
_-_-_-_-_-_-_-_-_-_-_-_-_-_-_-_
_-_-_-_-_-_-_-_-_-_-_-_-_-_-_-_
 _-_-_-_-_-_-_-_-_-_-_-_-_-_-_
 _-_-_-_-_-_-_-_-_-_-_-_-_-_-_
  _-_-_-_-_-_-_-_-_-_-_-_-_-_
    _-_-_-_-_-_-_-_-_-_-_-_
        _-_-_-_-_-_-_-_
            _-_-_-_
}
Svarte 02/09/2008 kl. 13:28
kilden bruker

stemmer
76

Her er en generell beskrivelse av en teknikk for å beregne pi som jeg lærte på high school.

Jeg bare dele dette fordi jeg tror det er enkelt nok til at alle kan huske det, på ubestemt tid, pluss at det lærer deg begrepet "Monte-Carlo" metoder - som er statistiske metoder for å komme fram til svar som ikke umiddelbart synes å være avledes gjennom hjelp av tilfeldige prosesser.

Tegne en firkant, og dedisere en kvadrant (en fjerdedel av en halvsirkel) inne i denne firkanten (en kvadrant med radius lik den siden av plassen, slik at det fyller så mye av plassen som mulig)

Nå kaster en dart på torget, og registrere hvor det lander - det er, velger et tilfeldig tidspunkt hvor som helst inne i firkanten. Selvfølgelig, den landet inne på torget, men det er inne i halvsirkelen? Spill dette faktum.

Gjenta denne prosessen mange ganger - og du vil finne det er et forhold mellom antall poeng inne i halvsirkelen mot det totale antall kastet, kaller dette forholdet x.

Siden området av plassen er r ganger r, kan du utlede at arealet av halvsirkelen er x ganger r ganger r (som er x ganger r squared). Derfor x ganger 4 vil gi deg pi.

Dette er ikke en rask metode å bruke. Men det er et fint eksempel på en Monte Carlo-metoden. Og hvis du ser deg rundt, kan du oppleve at mange problemer ellers utenfor dine regneferdigheter kan løses ved hjelp av slike metoder.

Svarte 01/08/2008 kl. 13:37
kilden bruker

stemmer
51

Av hensyn til fullstendighet, en C ++ mal versjonen, som for en optimalisert build vil beregne PI ved kompilering og vil inline til en enkelt verdi.

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

Legg merke til I> 10, optimalisert bygger kan være langsom, likeledes for ikke-optimalisert kjøringer. For 12 gjentakelser tror jeg det er rundt 80k samtaler til verdi () (i fravær av memoisation).

Svarte 22/12/2009 kl. 15:40
kilden bruker

stemmer
40

Det er faktisk en hel bok dedikert (blant annet) til raske metoder for beregning av \ pi: 'Pi og generalforsamlingen', Jonathan og Peter Borwein ( tilgjengelig på Amazon ).

Jeg studerte generalforsamlingen og relaterte algoritmer ganske mye: det er ganske interessant (men noen ganger ikke-triviell).

Merk at for å gjennomføre mest moderne algoritmer for å beregne \ pi, trenger du en multiprecision aritmetisk bibliotek ( GMP er ganske godt valg, selv om det er en stund siden sist jeg brukte det).

Tids kompleksiteten av de beste algoritmer er i O (M (n) log (n)), hvor M (n) er den tids kompleksitet for multiplikasjon av to n-bit heltall (M (n) = O (n log (n) log (log (n))) ved anvendelse av FFT-baserte algoritmer, som vanligvis er nødvendig ved beregning av sifrene i \ pi, og en slik algoritme er implementert i GMP).

Merk at selv om matematikken bak algoritmer kanskje ikke trivielt, algoritmer selv er vanligvis noen få linjer med pseudo-kode, og gjennomføringen er vanligvis veldig grei (hvis du ikke valgte å skrive din egen multiprecision aritmetikk :-)).

Svarte 24/08/2008 kl. 17:14
kilden bruker

stemmer
37

Følgende svar nøyaktig hvordan du gjør dette på raskest mulig måte - med minst databehandling innsats . Selv om du ikke liker svaret, må du innrømme at det er faktisk den raskeste måten å verdien av PI.

Den raskeste måten å få verdien av Pi er:

  1. velge din favoritt programmeringsspråk
  2. legger det er Math bibliotek
  3. og finner ut at Pi er allerede definert der !! klar til å bruke det ..

Hvis du ikke har en Math biblioteket for hånden ..

den nest raskeste måte (mer universell løsning) er:

se opp Pi på Internett, for eksempel her:

http://www.eveandersson.com/pi/digits/1000000 (1 million sifre .. hva er din flytende punktet presisjon?)

eller her:

http://3.141592653589793238462643383279502884197169399375105820974944592.com/

eller her:

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

Det er veldig fort å finne de tallene du trenger uansett presisjon aritmetikk du ønsker å bruke, og ved å definere en konstant, kan du være sikker på at du ikke kaster bort dyrebar CPU tid.

Ikke bare er dette en delvis humoristisk svar, men i virkeligheten, hvis noen ville gå videre og beregne verdien av Pi i en reell søknad .. det ville være en ganske stor sløsing med CPU tid, ville det ikke? Minst jeg ikke ser en reell søknad for å prøve å re-beregne dette.

Kjære Moderator: vær oppmerksom på at OP spurte: "raskeste måten å få verdien av PI"

Svarte 28/10/2011 kl. 01:02
kilden bruker

stemmer
25

Den BBP formel gjør det mulig å beregne den nte sifret - i basisen 2 (eller 16) - uten å måtte bry med de foregående n-1 første siffer :)

Svarte 29/08/2008 kl. 09:22
kilden bruker

stemmer
21

I stedet for å definere pi som en konstant, jeg alltid bruke acos(-1).

Svarte 08/03/2009 kl. 03:02
kilden bruker

stemmer
20

Hvis denne artikkelen er sant, så den algoritmen som Bellard har skapt kan være en av de raskeste tilgjengelige. Han har skapt pi til 2,7 billioner sifre bruker en stasjonær PC!

... og han har publisert sitt arbeid her

Godt arbeid Bellard, Du er en pioner!

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

Svarte 06/01/2010 kl. 12:41
kilden bruker

stemmer
20

Bare kom over dette som skal være her for fullstendighet:

beregne PI i Piet

Den har ganske fin egenskap at presisjonen kan forbedres gjøre programmet større.

Her finnes en viss innsikt i språket selv

Svarte 12/01/2009 kl. 18:46
kilden bruker

stemmer
19

Dette er en "klassisk" metoden, svært enkelt å implementere. Denne implementeringen, i python (ikke så fort språket) gjør det:

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)

Du finner mer informasjon her .

Uansett den raskeste måten å få en presis som-mye-som-du-vil verdien av pi i python er:

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

her er stykke kilde for gmpy pi metoden, tror jeg ikke koden er så mye nyttig som kommentar i dette tilfellet:

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: Jeg hadde noen problemer med klipp og lim og identation, likevel kan du finne kilden her .

Svarte 02/10/2008 kl. 21:27
kilden bruker

stemmer
17

Hvis av raskeste du mener raskeste til å skrive inn koden, her er golfscript løsning:

;''6666,-2%{2+.2/@*\/10.3??2*+}*`1000<~\;
Svarte 06/08/2008 kl. 22:54
kilden bruker

stemmer
16

Bruk Machin lignende formel

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.

Implementert i skjema, for eksempel:

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

Svarte 05/02/2011 kl. 05:26
kilden bruker

stemmer
15

Med dobler:

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

Dette vil være nøyaktig opp til 14 desimaler, nok til å fylle en dobbel (unøyaktighet er sannsynligvis fordi resten av desimalene i ARC tangentene er avkortet).

Også Seth, det 3,14159265358979323846 3 , ikke 64.

Svarte 28/02/2010 kl. 03:52
kilden bruker

stemmer
15

Hvis du er villig til å bruke en tilnærming, 355 / 113er bra for 6 desimaler, og har den ekstra fordelen av å være brukbart med heltall uttrykk. Det er ikke så viktig i disse dager, som "flyttall matte co-prosessor" sluttet å ha noen mening, men det var ganske viktig når.

Svarte 17/09/2009 kl. 16:30
kilden bruker

stemmer
15

Pi er nøyaktig tre! [Prof. Frink (Simpson)]

Spøk, men her er en i C # (.NET-rammeverket nødvendig).

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;
        }
    }
}
Svarte 26/02/2009 kl. 19:22
kilden bruker

stemmer
15

Beregne PI ved kompilering-tid med D.

(Kopiert fra 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))) );
Svarte 17/09/2008 kl. 17:49
kilden bruker

stemmer
13

Denne versjonen (i Delphi) er ikke noe spesielt, men det er i hvert fall raskere enn den versjonen Nick Hodge postet på sin blogg :). På min maskin, det tar ca 16 sekunder å gjøre en milliard gjentakelser, noe som gir en verdi på 3,14159265 25879 (nøyaktig delen er i fet skrift).

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.
Svarte 12/01/2009 kl. 18:24
kilden bruker

stemmer
12

Hvis du ønsker å beregne en tilnærming av verdien av π (for noen grunn), bør du prøve en binær utvinning algoritmen. Bellard 's forbedring av BBP gir gjør PI in O (N ^ 2).


Hvis du ønsker å et overslag over verdien av π å gjøre beregninger, deretter:

PI = 3.141592654

Riktignok er det bare en tilnærming, og ikke helt nøyaktig. Det er av ved litt mer enn ,00000000004102. (fire ti-trillionths, omtrent 4 / 10000000000 ).


Hvis du ønsker å gjøre matte med π, så få deg en blyant og papir eller en datamaskin algebra pakken, og bruke π eksakte verdi, π.

Hvis du virkelig vil ha en formel, er dette en morsom:

π = - i ln (-1)

Svarte 22/12/2009 kl. 21:13
kilden bruker

stemmer
12

Tilbake i gamle dager, med små ord størrelser og treg eller ikke-eksisterende flyttallsoperasjoner, vi pleide å gjøre ting som dette:

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

For applikasjoner som ikke krever mye presisjon (video spill, for eksempel), er dette veldig fort og er nøyaktig nok.

Svarte 20/02/2009 kl. 21:21
kilden bruker

stemmer
11

Brent metode postet ovenfor av Chris er veldig bra; Brent generelt er en gigant innen vilkårlig presisjon aritmetikk.

Hvis alt du ønsker er Nth sifret, den berømte BBP formelen er nyttig i hex

Svarte 04/08/2009 kl. 21:39
kilden bruker

stemmer
1

Beregning av π fra sirkel området :-)

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

Svarte 03/06/2017 kl. 17:13
kilden bruker

stemmer
0

bedre Approach

For å få effekt av standard konstanter som pi eller standardkonsepter, bør vi først gå med builtins metoder tilgjengelig på språket du bruker. Det vil returnere verdien i den raskeste måten og beste måten også. Jeg bruker python å få den raskeste måten å få verdien pi

  • pi variabel av regnestykket bibliotek . Math bibliotek lagre variabelen pi som konstant.

math_pi.py

import math
print math.pi

Kjør skriptet med tiden nytten av linux /usr/bin/time -v python math_pi.py

Produksjon:

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
  • Bruk arc cos metode for matematikk

acos_pi.py

import math
print math.acos(-1)

Kjør skriptet med tiden nytten av linux /usr/bin/time -v python acos_pi.py

Produksjon:

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

Kjør skriptet med tiden nytten av linux /usr/bin/time -v python bbp_pi.py

Produksjon:

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

Så beste måten er å bruke builtins metode gitt av språket fordi de er den raskeste og beste for å få produksjonen. I python bruk math.pi

Svarte 18/06/2018 kl. 10:07
kilden bruker

Cookies help us deliver our services. By using our services, you agree to our use of cookies. Learn more