Wat is die vinnigste manier om die waarde van π te kry?
https://stackoverflow.com/questions/19
-
08-06-2019 - |
italiano
english
français
española
中国
日本の
العربية
Deutsch
한국어
Português
RussianVra
Ek is op soek na die vinnigste manier om die waarde van π te verkry, as 'n persoonlike uitdaging.Meer spesifiek, ek gebruik maniere wat nie gebruik behels nie #define konstantes soos M_PI, of hardkodeer die nommer in.
Die program hieronder toets die verskillende maniere waarvan ek weet.Die inlynsamestellingweergawe is in teorie die vinnigste opsie, hoewel dit duidelik nie draagbaar is nie.Ek het dit ingesluit as 'n basislyn om met die ander weergawes te vergelyk.In my toetse, met ingeboude, die 4 * atan(1) weergawe is die vinnigste op GCC 4.2, want dit outomaties vou die atan(1) in 'n konstante.Met -fno-builtin gespesifiseer, die atan2(0, -1) weergawe is die vinnigste.
Hier is die hooftoetsprogram (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;
}
En die inlyn-samestelling goed (fldpi.c) wat net vir x86- en x64-stelsels sal werk:
double
fldpi()
{
double pi;
asm("fldpi" : "=t" (pi));
return pi;
}
En 'n bouskrif wat al die konfigurasies bou wat ek toets (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
Behalwe om tussen verskeie samestellervlae te toets (ek het 32-bis met 64-bis ook vergelyk omdat die optimalisering verskil), het ek ook probeer om die volgorde van die toetse om te skakel.Maar tog, die atan2(0, -1) weergawe kom steeds elke keer bo uit.
Oplossing
Die Monte Carlo metode, soos genoem, pas 'n paar wonderlike konsepte toe, maar dit is duidelik nie die vinnigste nie, nie met 'n lang skoot nie, nie volgens enige redelike maatstaf nie.Dit hang ook alles af van watter soort akkuraatheid jy soek.Die vinnigste π waarvan ek weet is die een met die syfers hard gekodeer.Kyk na PI en Pi[PDF], daar is baie formules.
Hier is 'n metode wat vinnig konvergeer - ongeveer 14 syfers per iterasie. PiFast, die huidige vinnigste toepassing, gebruik hierdie formule met die FFT.Ek sal net die formule skryf, aangesien die kode eenvoudig is.Hierdie formule is amper gevind deur Ramanujan en ontdek deur Chudnovsky.Dit is eintlik hoe hy 'n paar miljard syfers van die getal bereken het - so dit is nie 'n metode om te verontagsaam nie.Die formule sal vinnig oorloop en aangesien ons faktoriale deel, sal dit voordelig wees om sulke berekeninge te vertraag om terme te verwyder.
waar,
Hieronder is die Brent-Salamin-algoritme.Wikipedia noem dat wanneer a en b is dan "naby genoeg". (a + b)² / 4t sal 'n benadering van π wees.Ek is nie seker wat "naby genoeg" beteken nie, maar uit my toetse het een iterasie 2 syfers gekry, twee het 7, en drie het 15 gehad, natuurlik is dit met dubbels, so dit kan 'n fout hê gebaseer op sy voorstelling en die waar berekening kan meer akkuraat wees.
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)
Laastens, wat van 'n paar pi-gholf (800 syfers)?160 karakters!
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);}
Ander wenke
Ek hou baie van hierdie program, want dit benader π deur na sy eie area te kyk.
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() { _-_-_-_ _-_-_-_-_-_-_-_-_ _-_-_-_-_-_-_-_-_-_-_-_ _-_-_-_-_-_-_-_-_-_-_-_-_-_ _-_-_-_-_-_-_-_-_-_-_-_-_-_-_ _-_-_-_-_-_-_-_-_-_-_-_-_-_-_ _-_-_-_-_-_-_-_-_-_-_-_-_-_-_-_ _-_-_-_-_-_-_-_-_-_-_-_-_-_-_-_ _-_-_-_-_-_-_-_-_-_-_-_-_-_-_-_ _-_-_-_-_-_-_-_-_-_-_-_-_-_-_-_ _-_-_-_-_-_-_-_-_-_-_-_-_-_-_ _-_-_-_-_-_-_-_-_-_-_-_-_-_-_ _-_-_-_-_-_-_-_-_-_-_-_-_-_ _-_-_-_-_-_-_-_-_-_-_-_ _-_-_-_-_-_-_-_ _-_-_-_ }
Hier is 'n algemene beskrywing van 'n tegniek vir die berekening van pi wat ek op hoërskool geleer het.
Ek deel dit net omdat ek dink dit is eenvoudig genoeg dat enigiemand dit onbepaald kan onthou, plus dit leer jou die konsep van "Monte-Carlo" metodes -- wat statistiese metodes is om by antwoorde uit te kom wat nie dadelik blyk te wees nie afleibaar deur lukrake prosesse.
Teken 'n vierkant en skryf 'n kwadrant (een kwart van 'n halfsirkel) binne daardie vierkant in ('n kwadrant met radius gelyk aan die sy van die vierkant, sodat dit soveel as moontlik van die vierkant vul)
Gooi nou 'n pyl na die vierkant, en teken aan waar dit land -- dit wil sê, kies 'n ewekansige punt enige plek binne die vierkant.Natuurlik het dit binne die vierkant beland, maar is dit binne die halfsirkel?Teken hierdie feit aan.
Herhaal hierdie proses baie keer -- en jy sal vind daar is 'n verhouding van die aantal punte binne die halfsirkel teenoor die totale getal gegooi, noem hierdie verhouding x.
Aangesien die oppervlakte van die vierkant r maal r is, kan jy aflei dat die oppervlakte van die halfsirkel x maal r maal r is (dit is x maal r kwadraat).Dus sal x maal 4 jou pi gee.
Dit is nie 'n vinnige metode om te gebruik nie.Maar dit is 'n goeie voorbeeld van 'n Monte Carlo-metode.En as jy rondkyk, sal jy dalk vind dat baie probleme andersins buite jou rekenaarvaardighede deur sulke metodes opgelos kan word.
In die belang van volledigheid, 'n C++-sjabloonweergawe, wat, vir 'n geoptimaliseerde bou, 'n benadering van PI sal bereken op die samestellingstyd, en sal inlyn tot 'n enkele waarde.
#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;
}
Let wel vir I > 10, geoptimaliseerde bouwerk kan stadig wees, net so vir nie-geoptimaliseerde lopies.Vir 12 iterasies glo ek daar is ongeveer 80 000 oproepe na waarde() (in die afwesigheid van memorisering).
Daar is eintlik 'n hele boek wat (onder andere) aan vinnig metodes vir die berekening van \pi:'Pi and the AGM', deur Jonathan en Peter Borwein (beskikbaar op Amazon).
Ek het die AJV en verwante algoritmes nogal bestudeer:dit is nogal interessant (hoewel soms nie-triviaal).
Let daarop dat om die meeste moderne algoritmes te implementeer om \pi te bereken, sal jy 'n veelpresisie rekenkundige biblioteek nodig hê (GMP is nogal 'n goeie keuse, al is dit 'n rukkie sedert ek dit laas gebruik het).
Die tyd-kompleksiteit van die beste algoritmes is in O(M(n)log(n)), waar M(n) die tyd-kompleksiteit is vir die vermenigvuldiging van twee n-bis heelgetalle (M(n)=O(n) log(n) log(log(n))) met behulp van FFT-gebaseerde algoritmes, wat gewoonlik nodig is wanneer syfers van \pi bereken word, en so 'n algoritme word in GMP geïmplementeer).
Let daarop dat alhoewel die wiskunde agter die algoritmes dalk nie triviaal is nie, die algoritmes self gewoonlik 'n paar reëls pseudo-kode is, en die implementering daarvan is gewoonlik baie eenvoudig (as jy verkies om nie jou eie veelpresisie-rekenkunde te skryf nie :-) ).
Die volgende antwoorde presies hoe om dit op die vinnigste moontlike manier te doen -- met die minste rekenaarinspanning.Selfs as jy nie van die antwoord hou nie, moet jy erken dat dit inderdaad die vinnigste manier is om die waarde van PI te kry.
Die VINNIGSTE manier om die waarde van Pi te kry is:
1) Kies u gunsteling programmeringstaal 2) Laai sy wiskundebiblioteek 3) en vind dat PI reeds daar gedefinieër is - gereed vir gebruik!
As jy nie 'n Wiskunde-biblioteek byderhand het nie.
Die TWEEDE VINNIGSTE manier (meer universele oplossing) is:
soek Pi op die internet, bv.hier:
http://www.eveandersson.com/pi/digits/1000000 (1 miljoen syfers ..wat is jou drywende punt akkuraatheid?)
of hier:
http://3.141592653589793238462643383279502884197169399375105820974944592.com/
of hier:
http://en.wikipedia.org/wiki/Pi
Dit is baie vinnig om die syfers te vind wat jy nodig het vir watter presiese rekenkunde jy ook al wil gebruik, en deur 'n konstante te definieer, kan jy seker maak dat jy nie kosbare SVE-tyd mors nie.
Nie net is dit 'n gedeeltelik humoristiese antwoord nie, maar in werklikheid, as iemand sou voortgaan en die waarde van Pi in 'n regte toepassing bereken ..dit sal 'n redelike groot vermorsing van SVE-tyd wees, nie waar nie?Ten minste sien ek nie 'n werklike toepassing om dit te probeer herbereken nie.
Geagte Moderator:neem asseblief kennis dat die OP gevra het:"Vinnigste manier om die waarde van PI te kry"
Die BBP formule laat jou toe om die nde syfer te bereken - in basis 2 (of 16) - sonder om eers met die vorige n-1 syfers te hoef te steur :)
In plaas daarvan om pi as 'n konstante te definieer, gebruik ek altyd acos(-1).
Sopas afgekom op hierdie een wat vir volledigheid hier behoort te wees:
Dit het die nogal mooi eienskap dat die akkuraatheid verbeter kan word om die program groter te maak.
Hier'n bietjie insig in die taal self
As Hierdie artikel waar is, dan is die algoritme wat Bellard geskep het, kan een van die vinnigste beskikbaar wees.Hy het pi tot 2.7 TRILJOEN syfers geskep met 'n REKENAARKANT!
...en hy het syne gepubliseer werk hier
Goeie werk Bellard, jy is 'n pionier!
Dit is 'n "klassieke" metode, baie maklik om te implementeer.Hierdie implementering, in python (nie so vinnige taal nie) doen dit:
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)
Jy kan meer inligting vind hier.
In elk geval is die vinnigste manier om 'n presiese soveel-as-wat-jy-wil-waarde van pi in luislang te kry:
from gmpy import pi
print pi(3000) # the rule is the same as
# the precision on the previous code
hier is die stukkie bron vir die gmpy pi-metode, ek dink nie die kode is so nuttig soos die opmerking in hierdie geval nie:
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: Ek het 'n probleem gehad met knip en plak en identifikasie, in elk geval kan jy die bron vind hier.
As jy met vinnigste bedoel die vinnigste om die kode in te tik, hier is die gholfskrif oplossing:
;''6666,-2%{2+.2/@*\/10.3??2*+}*`1000<~\;
Gebruik die Machin-agtige formule
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.
Geïmplementeer in Skema, byvoorbeeld:
(+ (- (+ (* 176 (atan (/ 1 57))) (* 28 (atan (/ 1 239)))) (* 48 (atan (/ 1 682)))) (* 96 (atan (/ 1 12943))))
As jy bereid is om 'n benadering te gebruik, 355 / 113 is goed vir 6 desimale syfers, en het die bykomende voordeel dat dit bruikbaar is met heelgetaluitdrukkings.Dit is deesdae nie so belangrik nie, aangesien "sweefpunt-wiskunde-medeverwerker" opgehou het om enige betekenis te hê, maar dit was een keer nogal belangrik.
Met dubbels:
4.0 * (4.0 * Math.Atan(0.2) - Math.Atan(1.0 / 239.0))
Dit sal akkuraat wees tot 14 desimale plekke, genoeg om 'n dubbel te vul (die onakkuraatheid is waarskynlik omdat die res van die desimale in die boogtangens afgekap is).
Ook Seth, dit is 3.141592653589793238463, nie 64 nie.
Bereken PI tydens samestelling met D.
(Gekopieer van 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))) );
Pi is presies 3![Prof.Frink (Simpsons)]
Grap, maar hier is een in C# (.NET-Framework vereis).
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;
}
}
}
Hierdie weergawe (in Delphi) is niks besonders nie, maar dit is ten minste vinniger as die weergawe wat Nick Hodge op sy blog geplaas het :).Op my masjien neem dit ongeveer 16 sekondes om 'n miljard iterasies te doen, wat 'n waarde van 3.1415926525879 (die akkurate deel is vetgedruk).
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.
In die ou dae, met klein woordgroottes en stadige of nie-bestaande drywende-punt-bewerkings, het ons dinge soos hierdie gedoen:
/* Return approximation of n * PI; n is integer */
#define pi_times(n) (((n) * 22) / 7)
Vir toepassings wat nie baie akkuraatheid vereis nie (videospeletjies, byvoorbeeld), is dit baie vinnig en akkuraat genoeg.
As jy wil bereken 'n benadering van die waarde van π (om een of ander rede), moet jy 'n binêre ekstraksie-algoritme probeer. Die van Bellard verbetering van BBP gee doen PI in O(N^2).
As jy wil verkry 'n benadering van die waarde van π om berekeninge te doen, dan:
PI = 3.141592654
Toegegee, dit is slegs 'n benadering, en nie heeltemal akkuraat nie.Dit is af met 'n bietjie meer as 0,00000000004102.(vier tien triljoenstes, ongeveer 4/10,000,000,000).
As jy wil doen wiskunde met π, kry dan vir jou 'n potlood en papier of 'n rekenaaralgebra-pakket, en gebruik π se presiese waarde, π.
As jy regtig 'n formule wil hê, is hierdie een pret:
π = -i ln(-1)
Brent se metode wat Chris hierbo geplaas het, is baie goed;Brent is oor die algemeen 'n reus op die gebied van arbitrêre-presisie-rekenkunde.
As al wat jy wil hê, is die Nde syfer, die beroemdeBBP formuleis nuttig in hex
Bereken π vanaf sirkeloppervlakte :-)
<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 += " "
}
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>Beter benadering
Om die uitset van standaardkonstantes soos PI of die standaardkonsepte, moet ons eers gaan met die ingeboude metodes wat beskikbaar is in die taal wat jy gebruik.Dit sal waarde op die vinnigste manier en ook die beste manier teruggee.Ek gebruik python om die vinnigste manier te kry om die waarde pi te kry
- pi veranderlike van die wiskunde biblioteek.Wiskunde biblioteek stoor die veranderlike pi as konstant.
math_pi.py
import math
print math.pi
Begin die skrip met die tydnuts van linux /usr/bin/time -v python math_pi.py
Uitset:
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
- Gebruik arc cos-metode van wiskunde
acos_pi.py
import math
print math.acos(-1)
Begin die skrip met die tydnuts van linux /usr/bin/time -v python acos_pi.py
Uitset:
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
- gebruik BBP formule
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))
Begin die skrip met die tydnuts van linux /usr/bin/time -v python bbp_pi.py
Uitset:
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
Die beste manier is dus om ingeboude metodes te gebruik wat deur die taal verskaf word, want hulle is die vinnigste en beste om die uitset te kry.In luislang gebruik math.pi
