Vă mulțumim pentru susținere

Care este cel mai rapid mod de a obține valoarea?

Soluțiile sunt binevenite în orice limbă. :-) Caut cel mai rapid mod de a obtine valoarea?, Ca o provocare personala. Mai precis, folosesc metode care nu implică utilizarea constantelor #define d precum M_PI sau codarea greu a numărului în.

Programul de mai jos testează diferitele moduri de care știu. Versiunea de asamblare inline este, în teorie, cea mai rapidă opțiune, deși nu este în mod evident portabilă; Am inclus-o ca o linie de bază pentru a compara celelalte versiuni împotriva. În testele mele, cu built-in, versiunea 4 * atan (1) este cea mai rapidă pe GCC 4.2, deoarece ea folosește automat atan (1) . Cu -fno-builtin specificat, versiunea atan2 (0, -1) este cea mai rapidă.

Iată programul principal de testare ( pitimes.c ):

#include 
#include 
#include 

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

Și chestii de asamblare inline ( fldpi.c ), observând că va funcționa numai pentru sistemele x86 și x64:

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

Și un script de construire care construiește toate configurațiile pe care le testez ( 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

În afară de testarea între diferitele steaguri de compilatoare (am comparat 32 de biți și pe 64 de biți prea, pentru că optimizările sunt diferite), am încercat, de asemenea, să schimb ordinea testelor în jur. Versiunea atan2 (0, -1) iese totuși la început de fiecare dată.

0
adăugat editat
@Zeus În acest caz specific, întrebarea mea a fost de fapt destinată să fie o întrebare "amuzantă" de micro-optimizare (care, în aceste zile, ar fi probabil o potrivire mai bună pentru Programarea puzzle-urilor și a codului de golf ), dar premisa generală a" celui mai rapid mod de a calcula pi "părea să fie suficient de utilă pentru a păstra această întrebare aici. Deci, într-o anumită etapă, probabil voi reevalua dacă ar trebui să accept doar cel mai bun răspuns algoritmic (probabil cel al lui nlucaroni), indiferent dacă este vorba de micro
adăugat autor Chris Jester-Young
@ HopelessN00b În dialectul limbii engleze vorbesc, "optimizarea" este scris cu un " s ", nu un" z "(pronunțat ca" zed ", BTW, nu" zee ";-)). (Nu este prima dată când trebuia să revin acest tip de editare, dacă te uiți la istoricul recenziilor.)
adăugat autor Chris Jester-Young
Răspunsul lui nlucaroni a ajuns la 100 de creșteri (felicitări), deci este probabil un punct bun pentru a-l bifa verde. Bucurați-vă! (Deși, din moment ce este wiki comunitară, nu generează nici un rep, deci nici măcar sigur dacă nlucaroni va observa acest lucru.)
adăugat autor Chris Jester-Young
adăugat autor Chris Jester-Young
@erik: Nu toate limbile au o constantă încorporată, ca M_PI . Încercam să găsesc o modalitate "autoritară" de a obține o valoare (floating-point) a lui pi care (teoretic) funcționează într-o varietate de limbi (și / sau bibliotecile încorporate). Metoda curentă preferată este folosirea atan2 (0, -1) , dar probabil că există mai multe modalități.
adăugat autor Chris Jester-Young
@signonsridhar Nu, vorbim doar despre metode de calcul care dau exact acelasi rezultat ca si M_PI atunci cand sunt reduse la dubla precizie.
adăugat autor Chris Jester-Young
Trebuie să fie o modalitate de ao face în metaprogramarea C ++. Timpul de rulare va fi foarte bun, dar timpul de compilare nu va fi.
adăugat autor David Thornley
Există o singură soluție care este mai rapidă decât calcularea constantă a PI constantă: calculați toate valorile în formule, de ex. când circumferința este necesară, puteți calcula 2 * PI în loc să se înmulțească de fiecare dată când PI cu 2 în timpul de execuție.
adăugat autor ern0
întrebarea este: de ce nu doriți să utilizați o constantă? de exemplu. fie definite de o bibliotecă, fie de dvs.? Computing Pi este o risipă de cicluri CPU, deoarece această problemă a fost rezolvată din nou și din nou la un număr de cifre semnificative mult mai mare decât este necesar pentru calculele zilnice
adăugat autor Tilo
De ce credeți că folosiți atan (1) diferit de utilizarea lui M_PI? Aș înțelege de ce vrei să faci asta dacă ai folosit doar operații aritmetice, dar cu atan nu văd punctul.
adăugat autor erikkallen
Aceasta ar trebui să primească în mod ideal atenția lui Mysticial, deoarece el este titularul recordului mondial de computerizare la cel mai mare număr de cifre.
adăugat autor Team Upvote
@ ChrisJester-Young Nope. Aceasta nu este intenția .. Recent am început să citesc mai mult în regulile .. și am crezut că mi-aș face partea mea pe firele pe care le vizitez pentru a reaminti utilizatorilor care ar fi putut uita coz de mult timp. În nici un caz nu încerc să fiu poliție aici. Îmi cer scuze dacă m-am întâlnit nepoliticos.
adăugat autor Zeus
9801 / (1103? 8) .. da șase zecimale .. aceasta este cea mai rapidă modalitate de a calcula PI? = 3,14159273
adăugat autor signonsridhar
@Chris Jester-Young Ei bine, tocmai am văzut un videoclip despre Ramanujan care a dat acest mod pentru a calcula PI. Deci tocmai l-am împărtășit:>
adăugat autor signonsridhar

20 răspunsuri

Iată o descriere generală a unei tehnici de calcul pentru pI pe care am învățat-o în liceu.

Îmi împărtășesc acest lucru doar pentru că cred că este suficient de simplu ca oricine să-și poată aminti, pe termen nedefinit, plus vă învață conceptul de metode "Monte-Carlo" - metode statistice de a ajunge la răspunsuri care nu par imediat să fie deducibil prin procese aleatorii.

Desenați un pătrat și inscriptați un cadran (un sfert dintr-un semicerc) în interiorul acelui pătrat (un cvadrant cu o rază egală cu latura pătratului, astfel încât să se umple cât mai mult de pătrat posibil)

Acum, aruncați o dart la pătrat și înregistrați unde se îndreaptă - adică alegeți un punct aleator oriunde în interiorul pieței. Desigur, a aterizat în interiorul pieței, dar este în semicerc? Înregistrați acest fapt.

Repetați acest proces de mai multe ori - și veți găsi că există un raport al numărului de puncte din semicerc în raport cu numărul total aruncat, numiți acest raport x.

Deoarece aria pătratului este r ori r, puteți deduce că aria semicercului este de x ori r ori r (adică x de ori r pătrat). Prin urmare, x ori 4 vă va da pi.

Aceasta nu este o metodă rapidă de utilizat. Dar este un exemplu frumos de metoda Monte Carlo. Iar dacă te uiți în jur, s-ar putea să afli că multe alte probleme, în afară de abilitățile dumneavoastră computaționale, pot fi rezolvate prin astfel de metode.

0
adăugat
Aceasta este metoda pe care am folosit-o pentru a calcula Pi într-un proiect de java în școală. Am folosit doar un randomizator pentru a veni cu coordonatele x, y și mai multe "darts" pe care le-am aruncat mai aproape de Pi am venit.
adăugat autor Jeff Keslinke

Dacă vă grăbiți cel mai rapid să tastați codul, iată soluția golfscript :

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

Metoda Metoda Monte Carlo , așa cum am menționat, aplică câteva concepte minunate, însă este, evident, nu cea mai rapidă - nu printr-o lovitură lungă, nu printr-o utilitate rezonabilă. De asemenea, totul depinde de ce precizie căutați. Cea mai rapidă cifră pe care o cunosc este codurile greu codate. Privind la Pi și Pi [PDF] , există o mulțime de formule.

Iată o metodă care converge rapid (~ 14digiți pe iterație). Cea mai rapidă aplicație actuală, PiFast utilizează această formulă cu FFT . Voi scrie formula, deoarece codul este drept. Această formulă a fost aproape găsită de Ramanujan și descoperită de Chudnovsky . De fapt, el a calculat câteva miliarde de cifre ale numărului - deci nu este o metodă de ignorare. Formula se va depăși rapid de când împărțim factoriali, ar fi avantajos să întârziem această calculare pentru a elimina termenii.

introduceți descrierea imaginii aici

introduceți descrierea imaginii aici

Unde,

introduceți descrierea imaginii aici

Mai jos este Brent? Salamin algoritm . Wikipedia menționează că atunci când a și b sunt "destul de apropiate" atunci (a + b) ^ 2 / 4t va fi o aproximare a lui pi. Nu sunt sigur ce înseamnă "destul de aproape", dar din testele mele, o repetare a obținut 2 cifre, două au 7 și trei au 15, bineînțeles că este vorba de dubluri, deci ar putea avea erori pe baza reprezentării sale și a " adevărat "ar putea fi mai precis.

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)

În cele din urmă, ce zici de unele golfuri (800 de cifre)? 160 caractere!

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);}
0
adăugat
Presupunând că încercați să implementați primul singur, nu ar fi sqr (k3) o problemă? Sunt sigur că va ajunge la un număr irațional pe care va trebui să-l estimați (IIRC, toate rădăcinile care nu sunt numere întregi sunt iraționale). Totul altceva arată destul de direct înainte dacă utilizați o aritmetică de precizie infinită dar această rădăcină pătrată este o întrerupere a afacerii. Cel de-al doilea include un sqrt, de asemenea.
adăugat autor Bill K
din experiența mea, "destul de aproape" înseamnă de obicei că există o aproximare a seriei Taylor.
adăugat autor Stephen

Îmi place foarte mult acest program, care aproximează pi privindu-și zona proprie :-)

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()
{
            _-_-_-_
       _-_-_-_-_-_-_-_-_
    _-_-_-_-_-_-_-_-_-_-_-_
  _-_-_-_-_-_-_-_-_-_-_-_-_-_
 _-_-_-_-_-_-_-_-_-_-_-_-_-_-_
 _-_-_-_-_-_-_-_-_-_-_-_-_-_-_
_-_-_-_-_-_-_-_-_-_-_-_-_-_-_-_
_-_-_-_-_-_-_-_-_-_-_-_-_-_-_-_
_-_-_-_-_-_-_-_-_-_-_-_-_-_-_-_
_-_-_-_-_-_-_-_-_-_-_-_-_-_-_-_
 _-_-_-_-_-_-_-_-_-_-_-_-_-_-_
 _-_-_-_-_-_-_-_-_-_-_-_-_-_-_
  _-_-_-_-_-_-_-_-_-_-_-_-_-_
    _-_-_-_-_-_-_-_-_-_-_-_
        _-_-_-_-_-_-_-_
            _-_-_-_
}
0
adăugat
Dacă înlocuiți _ cu -F <00 || - F-OO - ar fi mai ușor să urmăriți :-)
adăugat autor Pat
Acest program a fost grozav în 1998, dar a fost rupt deoarece preprocesorii moderni sunt mai liberali, introducând spații în jurul expansiunilor macro, pentru a împiedica astfel de lucruri să funcționeze. Este o relicvă, din păcate.
adăugat autor Chris Lutz
aceasta imprimă 0.25 aici -.-
adăugat autor Johannes Schaub - litb
@Pat dacă ați rănit de ce l-am editat a fost pentru că am văzut acest răspuns în coada LQP stackoverflow.com/review/low -calitate-posts / 16750528 , prin urmare, pentru a evita ștergerea am adăugat codul în link-ul la răspuns.
adăugat autor Petter Friberg
Treceți - tradițional-cpp la cpp pentru a obține comportamentul dorit.
adăugat autor Nietzche-jou
sau, dacă înlocuiți _ cu "dacă (caracterul anterior este '-') {OO--;} F--;"
adăugat autor FryGuy

În trecut, cu mici dimensiuni de cuvinte și cu operațiuni cu virgulă inactivă sau inexistentă, obișnuiaam să facem chestii de genul:

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

Pentru aplicațiile care nu necesită multă precizie (jocuri video, de exemplu), acest lucru este foarte rapid și este suficient de precis.

0
adăugat
Pentru o mai mare acuratețe, folosiți 355/113 . Foarte precisă pentru dimensiunea numărului implicat.
adăugat autor David Thornley
Doar din curiozitate: 22/7 este 3 + 1/7
adăugat autor Agnius Vasiliauskas

formula BBP vă permite să calculați a cincea cifră - în baza 2 (sau 16 ) - fără a mai deranja cu n-1 cifre anterioare mai întâi :)

0
adăugat

Această versiune (în Delphi) nu este nimic special, dar este cel puțin mai rapid decât versiunea Nick Hodge postat pe blogul său :). Pe mașina mea, este nevoie de aproximativ 16 secunde pentru a face un miliard de iterații, oferind o valoare 3.14159265 25879 (partea exactă este îngroșată).

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.
0
adăugat

Dacă acest articol este adevărat, atunci algoritmul pe care Bellard l-a creat ar putea fi unul dintre cele mai rapide disponibile. El a creat pic la 2,7 TRILLION cifre folosind un DESKTOP PC!

...and he has published his work here

Bună treabă Bellard, ești un pionier!

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

0
adăugat
Bellard pionier în multe, multe moduri ... mai întâi a fost LZEXE, destul de probabil primul compresor executabil (cred ce UPX are, flip apoi înapoi în timp la anii '80), și, desigur, acum, atât QEMU și FFMPEG sunt utilizate pe scară largă . Oh, și intrarea sa la IOCCC .... :-P
adăugat autor Chris Jester-Young

Dacă sunteți dispus să utilizați o aproximație, 355/113 este bun pentru 6 cifre zecimale și are avantajul suplimentar de a fi utilizabil cu expresii întregi. Aceasta nu este la fel de importantă în zilele noastre, deoarece "co-procesorul matematic cu matematică" a încetat să mai aibă vreun sens, dar a fost destul de important o dată.

0
adăugat

În interesul exhaustivității, o versiune de șablon C ++, care pentru o construcție optimizată va calcula PI la momentul compilării și va intra pe o singură valoare.

#include 

template
struct sign
{
    enum {value = (I % 2) == 0 ? 1 : -1};
};

template
struct pi_calc
{
    inline static double value ()
    {
        return (pi_calc::value () + pi_calc::value ()) / 2.0;
    }
};

template
struct pi_calc<0, J>
{
    inline static double value ()
    {
        return (sign::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
struct pi
{
    inline static double value ()
    {
        return pi_calc::value ();
    }
};

int main ()
{
    std::cout.precision (12);

    const double pi_value = pi<10>::value ();

    std::cout << "pi ~ " << pi_value << std::endl;

    return 0;
}

Note for I > 10, optimised builds can be slow, likewise for non-optimised runs. For 12 iterations I believe there are around 80k calls to value() (in the absence of memoisation).

0
adăugat
@ sebastião-miranda Formula lui Leibniz , cu o accelerare medie care îmbunătățește convergența. pi_calc <0, J> calculează fiecare termen succesiv din formula și pi_calc necalificat calculează media.
adăugat autor jon-hanson
Ei bine, asta este exact la 9dp. Obiectați de ceva sau faceți doar o observație?
adăugat autor jon-hanson
Am rula acest lucru și a obține "pi ~ 3.14159265383"
adăugat autor maxwellb
care este numele algoritmului folosit aici pentru a calcula PI?
adăugat autor Sebastião Miranda

Calculul? din cerc :-)




0
adăugat

Următoarele răspunsuri exact cum să faceți acest lucru în cel mai rapid mod posibil - cu cel mai mic efort de calcul . Chiar dacă nu vă place răspunsul, trebuie să recunoașteți că este într-adevăr cea mai rapidă modalitate de a obține valoarea PI.

Cea mai rapidă cale pentru a obține valoarea lui Pi este:

  1. alege limba dvs. de programare preferată
  2. încărcați biblioteca matematică
  3. și găsiți că Pi este deja definit acolo! gata de utilizare ..

în cazul în care nu aveți o bibliotecă de matematică la îndemână ..

calea SECOND FASTEST (soluția mai universală) este:

căutați Pi pe Internet, de ex. aici:

http://www.eveandersson.com/pi/digits/1000000 (1 million digits .. what's your floating point precision? )

sau aici:

http://3.141592653589793238462643383279502884197169399375105820974944592.com/

sau aici:

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

Este foarte rapid să găsiți cifrele de care aveți nevoie pentru orice aritmetică de precizie pe care doriți să o utilizați și definind o constantă, puteți să vă asigurați că nu pierdeți timp CPU prețios.

Nu numai că acest lucru este un răspuns plin de umor, dar în realitate, dacă cineva ar merge mai departe și va calcula valoarea lui Pi într-o aplicație reală ... ar fi o pierdere destul de mare de timp CPU, nu-i așa? Cel puțin nu văd o aplicație reală pentru încercarea de a recalcula acest lucru.

Stimate Moderator: vă rugăm să rețineți că OP a întrebat: "Cea mai rapidă cale pentru a obține valoarea PI"

0
adăugat

Dacă doriți să calculați o aproximare a valorii? (din anumite motive), ar trebui să încercați un algoritm de extragere binar. îmbunătățirea lui Bellard de BBP da PI în O (N ^ 2).


Dacă doriți să obțineți o aproximare a valorii? pentru a face calcule, atunci:

PI = 3.141592654

Acordată, este doar o aproximare și nu este în întregime precisă. Este oprit cu puțin mai mult de 0.00000000004102. (patru zeci-trilioane, aproximativ 4 / 10.000.000.000 ).


Dacă doriți să faceți matematică cu?, Atunci obțineți-vă un creion și hârtie sau un pachet de calcul algebră și folosiți valoarea exactă?

Dacă doriți cu adevărat o formulă, aceasta este distractivă:

? = - i ln (-1)

0
adăugat
Formula ta depinde de modul în care definești ln în planul complex. Trebuie să fie necontins de-a lungul unei linii în planul complex și este destul de comun pentru acea linie să fie axa reală negativă.
adăugat autor erikkallen

Tocmai am dat peste acest lucru care ar trebui să fie aici pentru completitudine:

calculați PI în Piet

Are proprietatea destul de drăguță că precizia poate fi îmbunătățită făcând programul mai mare.

Here's some insight into the language itself

0
adăugat

Calculați PI la momentul compilării cu D.

(Copiat de la 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))) );
0
adăugat
Din păcate, tangentele sunt arctangente bazate pe pi, invalidând oarecum acest calcul.
adăugat autor Grant Johnson

Există, de fapt, o carte integrală dedicată (printre altele) metodelor rapide pentru calculul lui \ pi: "Pi și AGM", de Jonathan și Peter Borwein ( disponibil pe Amazon ).

Am studiat destul de mult algoritmii AGM și cei apropiați: este destul de interesant (deși uneori non-trivial).

Rețineți că, pentru a pune în aplicare cele mai moderne algoritmi pentru a calcula \ pi, veți avea nevoie de o bibliotecă aritmetică multiprecision ( GMP este o alegere destul de bun , deși a trecut ceva timp de când am folosit-o ultima oară).

Complexitatea de timp a celor mai buni algoritmi este în O (M (n) log (n)), unde M (n) este complexitatea timpului pentru multiplicarea a două numere întregi de n-biti (M log (n)) folosind algoritmi bazați pe FFT, care sunt de obicei necesari atunci când se calculează cifrele lui \ pi și un astfel de algoritm este implementat în GMP).

Rețineți că, deși matematica din spatele algoritmilor ar putea să nu fie trivială, algoritmii înșiși sunt de obicei câteva linii de pseudo-cod, iar implementarea acestora este de obicei foarte simplă (dacă nu ați ales să scrieți propria aritmetică multiprecisă :-)).

0
adăugat

Aceasta este o metodă "clasică", foarte ușor de implementat. Această implementare, în Python (nu atât de repede) face:

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)

Puteți găsi mai multe informații aici .

Oricum, cea mai rapidă modalitate de a obține o valoare precisă a piesei în Python este:

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

aici este piesa de sursă pentru metoda gmpy pi, nu cred că codul este la fel de util ca și comentariul în acest caz:

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: I had some problem with cut and paste and identation, anyway you can find the source here.

0
adăugat

Metoda lui Brent postată mai sus de Chris este foarte bună; Brent este, în general, un gigant în domeniul aritmeticii arbitrare-de precizie.

Dacă tot ce vrei este N-ul, celebrul Formula BBP este utilă în hex

0
adăugat
Metoda Brent nu a fost postată de mine; a fost postat de Andrea și tocmai am fost ultima persoană care a editat postul. :-) Dar sunt de acord, că acest post merită un upvote.
adăugat autor Chris Jester-Young

Cu duble:

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

Aceasta va fi exactă cu până la 14 zecimale, suficientă pentru a umple un dublu (inexactitatea este probabil că restul zecimalelor din tangentele arcului sunt trunchiate).

De asemenea, Seth, este 3.14159265358979323846 3 , nu 64.

0
adăugat

Utilizați formula asemănătoare 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.

Implementat în schemă, de exemplu:

<*> (+ (- (+ (* 176 (atan (/ 1 57))) * (atan (/ 1 239) (atan (/ 1 12943))))

0
adăugat