Jaký je nejrychlejší způsob, jak získat hodnotu n?

hlasů
275

Dívám se na nejrychlejší způsob, jak získat hodnotu n, jako osobní výzvu. Přesněji řečeno, já jsem s použitím způsobů, které nezahrnují pomocí #definekonstanty podobně M_PI, nebo hard-kódování čísla.

Uvedený program testuje různé způsoby, jak vím. Verze sestavení inline je teoreticky nejrychlejší možnost, i když zjevně není přenosná. Uvedl jsem ji jako základ pro porovnávání proti jiných verzích. V mých testů, s vestavěnými spotřebiči je 4 * atan(1)verze je nejrychlejší na GCC 4.2, protože to auto-sklopit atan(1)do konstantou. S -fno-builtinzadán, atan2(0, -1)verze je nejrychlejší.

Zde je hlavní testovací program ( 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;
}

A montážní inline věci ( fldpi.c), který bude fungovat jen pro x86 a x64 systémů:

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

A build skript, který staví všechny konfigurace Zkouším ( 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

Kromě testování mezi různými kompilátoru praporky (jsem oproti 32-bit proti 64-bit příliš, protože optimalizace se liší), také jsem se snažil přepínání pořadí zkoušek v okolí. Ale přesto je atan2(0, -1)verze ještě vyjde na vrcholu pokaždé.

Položena 01/08/2008 v 06:21
zdroj uživatelem
V jiných jazycích...                            


23 odpovědí

hlasů
180

Metodou Monte Carlo , jak již bylo uvedeno, platí některé velké koncepty, ale to je evidentně není nejrychlejší, ani zdaleka ne jakýmkoli vhodným opatřením. Samozřejmě, že vše závisí na tom, jaký druh přesnosti hledáte. Nejrychlejší π vím, je ten s číslicemi tvrdě kódované. Při pohledu na Pi a Pi [PDF] , existuje mnoho vzorců.

Zde je metoda, která konverguje rychleji - asi 14 číslic na iteraci. PiFast současný nejrychlejší aplikace, používá tento vzorec pomocí FFT . Budu psát vzorec, protože kód je jednoduché. Tento vzorec byl téměř nalezen Ramanujan a objevil Chudnovsky . Ve skutečnosti je to, jak se vypočítá několik miliard číslice čísla - takže to není způsob, jak ignorovat. Vzorec přeteče a rychle, protože jsme dělení faktoriály, by bylo výhodné, potom pro oddálení těchto výpočtů pro odstranění podmínky.

zadejte popis obrázku zde

zadejte popis obrázku zde

kde,

zadejte popis obrázku zde

Níže je algoritmus Brent-Salamin . Wikipedia uvádí, že když a b jsou „dost blízko“, pak (a + b) ² / 4t bude aproximace n. Nejsem si jistý, co „dost blízko“ znamená, ale z mých testů, jeden iterace dostal 2 číslice, dva dostali 7 a tři měli 15, samozřejmě je to s zdvojnásobí, takže to mohlo být chyba na základě své zastoupení a pravda výpočet může být přesnější.

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)

A konečně, jak se o nějakém pi Golf (800 míst)? 160 znaků!

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);}
Odpovězeno 02/08/2008 v 19:22
zdroj uživatelem

hlasů
96

Moc se mi líbí tento program, který přibližuje pi pohledu na vlastním území :-)

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()
{
            _-_-_-_
       _-_-_-_-_-_-_-_-_
    _-_-_-_-_-_-_-_-_-_-_-_
  _-_-_-_-_-_-_-_-_-_-_-_-_-_
 _-_-_-_-_-_-_-_-_-_-_-_-_-_-_
 _-_-_-_-_-_-_-_-_-_-_-_-_-_-_
_-_-_-_-_-_-_-_-_-_-_-_-_-_-_-_
_-_-_-_-_-_-_-_-_-_-_-_-_-_-_-_
_-_-_-_-_-_-_-_-_-_-_-_-_-_-_-_
_-_-_-_-_-_-_-_-_-_-_-_-_-_-_-_
 _-_-_-_-_-_-_-_-_-_-_-_-_-_-_
 _-_-_-_-_-_-_-_-_-_-_-_-_-_-_
  _-_-_-_-_-_-_-_-_-_-_-_-_-_
    _-_-_-_-_-_-_-_-_-_-_-_
        _-_-_-_-_-_-_-_
            _-_-_-_
}
Odpovězeno 02/09/2008 v 14:28
zdroj uživatelem

hlasů
72

Zde je obecný popis techniky pro výpočet pi, které jsem se naučil na střední škole.

Sdílím jen to, protože si myslím, že je dost jednoduché, že někdo může pamatovat, na dobu neurčitou, a to vás naučí pojem „Monte-Carlo“ metody - které jsou statistické metody přicházení u odpovědi, které nejsou bezprostředně jeví jako odvoditelný prostřednictvím náhodných procesů.

Nakreslit čtverec, a vepsat kvadrantu (čtvrtinu polokruhu) uvnitř tohoto čtverce (čtvrtkruhu s poloměrem rovným straně náměstí, tak, aby vyplnil tolik náměstí jak je to možné)

Nyní hodit šipku na náměstí, a zaznamenat, kde se pozemky - to znamená, že si vybrat náhodný bod kdekoliv uvnitř čtverce. Samozřejmě, to přistálo uvnitř čtverce, ale je to uvnitř půlkruhu? Zaznamená tuto skutečnost.

Tento postup opakujte několikrát - a najdete tam je poměr počtu bodů uvnitř půlkruhu proti celkovému počtu hozený, nazývají tento poměr x.

Vzhledem k tomu, oblast čtverce je doba R R, můžete odvodit, že plocha semifinále kruhu x x r x r (to znamená, že x x r kvadrát). Z tohoto důvodu x krát 4 dám vám pi.

Nejedná se o rychlý způsob, jak používat. Ale je to pěkný příklad metody Monte Carlo. A když se podíváte kolem sebe, možná zjistíte, že mnoho problémů, jinak mimo své početní dovednosti lze řešit pomocí těchto metod.

Odpovězeno 01/08/2008 v 14:37
zdroj uživatelem

hlasů
51

V zájmu úplnosti, C ++ šablony verze, která pro optimální sestavení spočítá PI v době kompilace a bude vložené do jediné hodnoty.

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

Poznámka k I> 10, optimalizovaná sestavení může být pomalé, podobně pro neoptimalizovanými běhů. 12 iterací Věřím, že existuje asi 80K volání hodnoty () (v nepřítomnosti memoisation).

Odpovězeno 22/12/2009 v 16:40
zdroj uživatelem

hlasů
40

Je tu vlastně celá kniha věnovaná (mimo jiné) na rychlé metody pro výpočet \ pi: ‚Pi a AGM‘, Jonathan a Peter Borwein ( k dispozici na Amazonu ).

Studoval jsem na valné hromadě as tím spojené algoritmy docela dost: je to docela zajímavé (i když někdy non-triviální).

Všimněte si, že implementovat nejmodernější algoritmy pro výpočet \ pi, budete potřebovat multiprecision aritmetické knihovny ( GMP je docela dobrá volba, i když je to už dlouho, co jsem naposledy použil).

Časový složitost nejlepších algoritmů je O (M (n) log (n)), kde je M (n) časově složitost pro násobení dvou n-bitová celá čísla (M (n) = O (n log (n) log (log (n))) za použití FFT založené algoritmy, které jsou obvykle potřebné při výpočtu číslic \ pi, a takový algoritmus je realizován v GMP).

Všimněte si, že i přesto, že matematika za algoritmy nemusí být triviální, samotné algoritmy jsou obvykle několik řádků pseudo-kódu, a jejich implementace je obvykle velmi jednoduché (pokud jste se rozhodli napsat vlastní multiprecision aritmetiku :-)).

Odpovězeno 24/08/2008 v 18:14
zdroj uživatelem

hlasů
36

Následující odpovědi přesně, jak to udělat v nejrychlejším možným způsobem - s co nejmenším úsilím výpočetní . Dokonce i když se vám nelíbí odpověď, musíte uznat, že to je opravdu nejrychlejší způsob, jak získat hodnotu PI.

Nejrychlejší způsob, jak se dostat na hodnotu Pi je:

  1. zvolil svůj oblíbený programovací jazyk
  2. načíst Je knihovnu Math
  3. a zjistili, že Pi je již definováno tam !! připraven k použití ..

V případě, že nemáte k dispozici knihovna na dosah ruky Math ..

druhý nejrychlejší způsob (více univerzální řešení) je:

vzhlížet Pi na internetu, např zde:

http://www.eveandersson.com/pi/digits/1000000 (1 milion míst .. jaký je váš plovoucí přesný bod?)

nebo zde:

http://3.141592653589793238462643383279502884197169399375105820974944592.com/

nebo zde:

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

Je to opravdu rychle najít číslic, které potřebujete pro cokoliv přesné aritmetický byste chtěli použít, a tím, že definuje konstantní, můžete se ujistit, že nemusíte ztrácet drahocenný čas procesoru.

Nejen, že je to částečně vtipná odpověď, ale ve skutečnosti, jestli někdo bude pokračovat a vypočítat hodnotu Pi v reálné aplikaci .. to by bylo dost velké plýtvání času CPU, nebo ne? Alespoň Nevidím skutečnou žádost o snaží znovu spočítat to.

Vážený Moderátor: upozorňujeme, že OP zeptal: „Nejrychlejší způsob, jak získat hodnotu PI“

Odpovězeno 28/10/2011 v 02:02
zdroj uživatelem

hlasů
25

BBP vzorec umožňuje vypočítat n-té číslice - v základu 2 (nebo 16) -, aniž by museli neobtěžoval s předchozími n-1 číslice první :)

Odpovězeno 29/08/2008 v 10:22
zdroj uživatelem

hlasů
21

Namísto definování pí jako konstantu, jsem vždy používat acos(-1).

Odpovězeno 08/03/2009 v 04:02
zdroj uživatelem

hlasů
20

Pokud tento článek je to pravda, pak je algoritmus, který Bellard vytvořil by mohlo být jedním z nejrychlejší dostupné. On vytvořil pí na 2,7 bilionu číslice pomocí stolního počítače!

... a on vydával jeho práci zde

Dobrá práce Bellard, Jste průkopníkem!

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

Odpovězeno 06/01/2010 v 13:41
zdroj uživatelem

hlasů
20

Právě narazil na tento jeden, který by měl být pro úplnost:

výpočet PI v Piet

Má poměrně příjemnou vlastnost, že přesnost lze zlepšit provádění programu větší.

Tady to trochu vhled do jazyka samotného

Odpovězeno 12/01/2009 v 19:46
zdroj uživatelem

hlasů
19

Jedná se o „klasickou“ metodou, velmi snadno implementovat. Tato implementace v pythonu (ne tak rychle jazyk) to dělá:

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)

Můžete si najít více informací zde .

Každopádně nejrychlejší způsob, jak získat přesný as-e-as-you-nouzi hodnotu pí v python je:

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

Zde je kousek zdroje pro gmpy metodou pi, nemyslím si, že kód je stejně užitečné jako komentář v tomto případě:

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: jsem měl nějaký problém s vyjmout a vložit a identation, přesto můžete najít zdroj zde .

Odpovězeno 02/10/2008 v 22:27
zdroj uživatelem

hlasů
17

Pokud by nejrychlejší myslíš nejrychleji zadat kód, tady je golfscript řešení:

;''6666,-2%{2+.2/@*\/10.3??2*+}*`1000<~\;
Odpovězeno 06/08/2008 v 23:54
zdroj uživatelem

hlasů
15

Pomocí Machin-jako vzorec

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.

Provedeno ve schématu, například:

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

Odpovězeno 05/02/2011 v 06:26
zdroj uživatelem

hlasů
15

Se zdvojnásobí:

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

To bude přesné až 14 desetinných míst, stačí vyplnit double (nepřesnost je pravděpodobně proto, že zbytek desetinných míst v obloukových tangent jsou zkráceny).

Také Seth je to 3,14159265358979323846 3 , ne 64.

Odpovězeno 28/02/2010 v 04:52
zdroj uživatelem

hlasů
15

Pokud jste ochotni používat aproximaci, 355 / 113je dobré pro 6 desetinných míst, a má navíc tu výhodu, že jsou použitelné s celočíselnými výrazy. To není tak důležité v těchto dnech, jako „plovoucí desetinnou čárkou matematický koprocesor“ přestala mít nějaký význam, ale bylo to docela důležité jednou.

Odpovězeno 17/09/2009 v 17:30
zdroj uživatelem

hlasů
15

Pi je přesně 3! [Prof. Frink (Simpsons)]

Vtip, ale tady je jedna v jazyce C # (.NET Framework povinné).

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;
        }
    }
}
Odpovězeno 26/02/2009 v 20:22
zdroj uživatelem

hlasů
15

Vypočtěte PI na kompilaci s D.

(Zkopírováno z 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))) );
Odpovězeno 17/09/2008 v 18:49
zdroj uživatelem

hlasů
13

Tato verze (v Delphi) není nic zvláštního, ale je to alespoň rychlejší než verze Nick Hodge vyslán na svém blogu :). Na mém stroji, to trvá asi 16 sekund, než dělat miliardy iterací, což představuje hodnotu 3,14159265 25879 (přesný část je tučně).

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.
Odpovězeno 12/01/2009 v 19:24
zdroj uživatelem

hlasů
12

Chcete-li vypočítat přibližnou hodnotu n (z nějakého důvodu), měli byste se pokusit algoritmus binární extrakce. Bellard je zlepšení BBP dává dělá PI v O (n ^ 2).


Chcete-li získat aproximaci hodnoty n provádět výpočty, pak:

PI = 3.141592654

Je pravda, že je to jen přibližný, a ne zcela přesné. Je to pryč o něco více než 0,00000000004102. (čtyři deset-trillionths, asi 4 / 10000000000 ).


Chcete-li dělat matematiku s n, pak si sami tužku a papír nebo balíček počítačové algebry, a používat přesnou hodnotu n je, π.

Pokud opravdu chcete vzorec, tohle je zábava:

π = - i ln (-1)

Odpovězeno 22/12/2009 v 22:13
zdroj uživatelem

hlasů
12

Po návratu do starých časů, s malými rozměry slovo a pomalými či neexistujících operací s plovoucí desetinnou čárkou, jsme byli zvyklí dělat věci, jako je toto:

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

Pro aplikace, které nevyžadují mnoho přesných (video hry, například), to je velmi rychlé a dostatečně přesné.

Odpovězeno 20/02/2009 v 22:21
zdroj uživatelem

hlasů
11

Brentova metoda vykázala nad Chris je velmi dobrá; Brent obecně je obří v oblasti výpočty s libovolnou přesností.

Pokud vše, co chcete, je N-tá číslice, známý BBP vzorec je užitečná v hex

Odpovězeno 04/08/2009 v 22:39
zdroj uživatelem

hlasů
1

Výpočet n z kruhového prostoru :-)

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

Odpovězeno 03/06/2017 v 17:13
zdroj uživatelem

hlasů
0

lepší přístup

Chcete-li získat výstup standardní konstanty jako nebo standardních pojmů, měli bychom nejprve jít s dostupnými jazyk, který používáte vestavěných příkazů metod. Vrátí hodnotu v nejrychlejším způsobem, a nejlepší způsob, jak také. Já používám Python získat nejrychlejší způsob, jak získat hodnotu pí

  • pi proměnná matematické knihovny . Matematická knihovna ukládat proměnné pi konstantní.

math_pi.py

import math
print math.pi

Spusťte skript s časovým využitelností linux /usr/bin/time -v python math_pi.py

Výstup:

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
  • Použijte oblouk cos způsobu matematiky

acos_pi.py

import math
print math.acos(-1)

Spusťte skript s časovým využitelností linux /usr/bin/time -v python acos_pi.py

Výstup:

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

Spusťte skript s časovým využitelností linux /usr/bin/time -v python bbp_pi.py

Výstup:

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

Takže nejlepší způsob, jak je použít vestavěných příkazů metody poskytované jazykové příčiny, které jsou nejrychlejší a nejlépe dostat výstup. V python použití math.pi

Odpovězeno 18/06/2018 v 10:07
zdroj uživatelem

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