Najkraći C program za računajje broja pi

[ Nedeljko @ 20.04.2004. 23:43 ] @

Čisto da se zna.

Na adresi http://numbers.computation.fre...ts/TinyPrograms/tinycodes.html nalaze se najkraći poznati programi na jeziku C za računanje broja pi na veliki broj decimalnih mesta. Takođe, traže da im se obrati svako ko ima kraći kod. Njihov najkraći kod glasi

Code:

long k=4e3,p,a[337],q,t=1e3;
main(j){for(;a[j=q=0]+=2,--k;)
for(p=1+2*k;j<337;q=a[j]*k+q%p*t,a[j++]=q/p)
k!=j>2?:printf("%.3d",a[j-2]%t+q/p/t);}

i ja sam uspeo da ga skratim za jedan znak zamenjujući izraz k!=j>2 izrazom j>2<k koji je sa njim ekvivalentan pod uslovom da k nije manje od 1, a taj uslov je u ovom programu uvek ispunjen, jer se vrednost promenljive k smanjuje od 4000 do 0 za po jedan pri čemu program završava rad kada k postane 0, tako da se izraz k!=j>2 izračunava samo kada je k>=1. No, bez obzira na sve to, kao i na činjenicu da oba koda proizvode isti rezultat (programi su testirani), i pored toga što sam im poslao poboljšani kod, oni se i dalje prave ludi! Tek toliko da se zna.

[ blaza @ 10.07.2004. 10:43 ] @

Nedeljko, prevideo si da se

Code:
for(;a[j=q=0]+=2,--k;)

moze zameniti sa

Code:
for(;--k;a[j=q=0]=2)

cime se program skracuje za dodatna dva karaktera. Verujem da postoje i dodatna poboljsanja.

[ -zombie- @ 13.07.2004. 01:42 ] @

nešto slično na http://www1.physik.tu-muenchen...tpack/html/Mathematics/Pi.html

Code:
/* Calculation of pi to 16276 decimal digits */
/* Size of program: 143 characters */
/* After Dik T. Winter, CWI Amsterdam */
int a=1e4,b,c=56980,d,e,f[56980],g,h,i;
main(){for(;b=c,c-=14;i=printf("%04d",e+d/a),e=d%a)
while(g=--b*2)d=h*b+a*(i?f[b]:a/5),h=d/--g,f[b]=d%g;}

i još kraći za e:

Code:
/*[email protected]*/int a[3302],b=3301,*c=a,d,e,f;main(){for(e=b;--e;*c++=1);*c
=2;for(d=2001;d--;printf("%05d",f))for(c=a,e=b;e;f/=e--){f+=*c*1e5;*c++=f%e;}}

[ Nedeljko @ 17.08.2004. 16:27 ] @

Inače nisam napisao da programi koje sam priložio imaju jednu sitnu anomaliju koja se može pojaviti kod serija od šest i više uzastopnih devetki, ali koja se ne ispoljava među prvih hiljadu decimala. Blažina, kao i moja korekcija nemaju nikakvog uticaja na to. Sve verzije tog koda imaju isti nedostatak. Inače, analizom programa se može utvrditi da je zasnovan na Ojlerovoj transformaciji Lajbnicovig reda (razvoja za arctg u tački 1).

[ byTer @ 18.08.2004. 12:48 ] @

nije li najkrace 22/7 ?

[ chupcko @ 18.08.2004. 13:37 ] @

Puf, eto sale...

greska je samo oko 0.04 % dovoljno za recimo stari egipat, ali ne i za savremeno doba :).

[ blaza @ 18.08.2004. 14:35 ] @

Jedan od kracih progama za izracunavanje broja Pi moze se naci u attachment-u (kompajlirana vezija i sors kod). Program je pisan u x86 asembleru, i izracunava 9300+ tacnih decimala broja Pi. Duzina kompajliranog programa (DOS .COM fajl) iznosi 110 bajtova.

[ Nedeljko @ 18.08.2004. 17:36 ] @

Da, samo to nije C program. To rešenje spada u kategoriju asemblerskih rešenja i u njoj je izuzetno optimalno. Svuda gde se prilažu takvi programi, oni se razvrstavaju u zasebne kategorije prema jezicima u kojima su pisani.

[ blaza @ 26.12.2004. 18:14 ] @

What's the big deal?
Dik T. Winter se nije narocito potrudio da skrati kod.
Skratio sam njegov program za 9 znakova (143 -> 134).

Code:
int a=1e4,c=56980,d,e,f[56980],g,h;
main(b){for(;b=c-=14;printf("%04d",e+d/a))for(e=d%a;g=2*--b;h=d/--g,f[b]=d%g)d=h*b+a*(e?f[b]:2e3);}

[ sallle @ 04.01.2005. 02:54 ] @

printf nije sluzbena rec...

[ Nedeljko @ 04.01.2005. 12:18 ] @

A ko je tvrdio da je službena? Dobro de, svuda fali jedno #include <stdio.h>

[ sallle @ 05.01.2005. 03:06 ] @

onda treba optimizovati i taj heder, i izbaciti nepotrebne stvari...

[ s1cK @ 24.10.2007. 21:30 ] @

Citat:

sallle: onda treba optimizovati i taj heder, i izbaciti nepotrebne stvari...

u prevodu , minimalizam C-a ;)

[ Shadowed @ 24.10.2007. 21:48 ] @

Citat:

blaza: What's the big deal?
Dik T. Winter se nije narocito potrudio da skrati kod.
Skratio sam njegov program za 9 znakova (143 -> 134).

Code:
int a=1e4,c=56980,d,e,f[56980],g,h;
main(b){for(;b=c-=14;printf("d",e+d/a))for(e=d%a;g=2*--b;h=d/--g,f[b]=d%g)d=h*b+a*(e?f[b]:2e3);}

Hm, ako se ne varam, na poslednjoj liniji nije potrebno ; na kraju, ako vec ide }. Eto jos jednog znaka ;]

[ X Files @ 24.10.2007. 22:01 ] @

Citat:

Hm, ako se ne varam, na poslednjoj liniji nije potrebno ; na kraju, ako vec ide }

Mora ;) Pomesao si sa Pascal-om, gde nesto slicno moze...
C/C++ su rigorozni po tom pitanju.
Čak mora i iza prazne "default:" konstrukcije unutar switch, neposredno pre }.

Dalje, u izrazima:
if ( nesto )
x=1;
else
x=2;
... opet mora ; cak i iza x=1, za razliku od Pascala.

EDIT / Off Topic

Jedino se ; ne stavlja iz kraja bloka } sem u posebnim slucajevima (koji doduse i nisu tako retki) kada sintaksa konstrukcije nalaze. Na primer:
class NekaKlasa {};
Ovde treba ; jer moze da postoji i izraz:
class NekaKlasa {} Objekat;
... kojim se odmah kreira i objekat.

To je inace jedna od gresaka koju pocetnici tesko uspevaju da lociraju i otklone, jer se greska obicno prijavi u DRUGOM izvornom fajlu projekta, zbog strukture C/C++ programa (zaglavlje/izvorni kod):

--- fajl.H ---
class Klasa {}
--- fajl.CPP ---
#include "fajl.H"
int i=10;

... gore u H nedostaje ; iza } a greska se obicno javi u CPP fajlu :)

_{[Ovu poruku je menjao X Files dana 24.10.2007. u 23:26 GMT+1]}

[ blaza @ 15.01.2009. 19:44 ] @

Idemo dalje: 134 -> 127.

Code:
a=1e4,c=56980,d,e,f[56980],g;main(b){for(;b=c-=14;printf("%04d",e+d/a))for(e=d%a;g=2*--b;d+=e?f[b]*a:2e7,f[b]=d%--g,d/=g)d*=b;}

_{[Ovu poruku je menjao blaza dana 16.01.2009. u 00:18 GMT+1]}

[ blaza @ 18.01.2009. 12:02 ] @

Ne moze krace?

Moze ;)

Nova skracenja:

123 karaktera, 16275 tacnih decimala

Code:
a=1e4,c=113932,d,e,f[113960];main(g){for(;g=c-=28;printf("%04d",e%a+d/a))for(e=d;g;d/=g--)d*=g--/2,f[g]=d+=e?f[g]%g*a:2e7;}

121 karakter, 9999 tacnih decimala

Code:
a=1e4,c=70028,d,e,f[70000];main(g){for(;g=c-=28;printf("%04d",e%a+d/a))for(e=d;g;d/=g--)d*=g--/2,f[g]=d+=e?f[g]%g*a:2e7;}

119 karaktera, 999 tacnih decimala

Code:
a=1e4,c=7028,d,e,f[7000];main(g){for(;g=c-=28;printf("%04d",e%a+d/a))for(e=d;g;d/=g--)d*=g--/2,f[g]=d+=e?f[g]%g*a:2e7;}

_{[Ovu poruku je menjao blaza dana 18.01.2009. u 19:41 GMT+1]}

[ Nedeljko @ 27.03.2010. 22:47 ] @

Citat:

Nedeljko: Inače nisam napisao da programi koje sam priložio imaju jednu sitnu anomaliju koja se može pojaviti kod serija od šest i više uzastopnih devetki, ali koja se ne ispoljava među prvih hiljadu decimala.

Kolega, niste dobro naučili matematiku. Ovde nema nikakve anomalije, program je potpuno čist.

Kod u čitljivijoj varijanti izgleda ovako:

Code:
#include <stdio.h>

int main()
{
    int a[337], t = 1000, k;

    printf("3.");

    for (k = 4000; k > 0; k--) {
        int p = 2*k + 1;
        int q = 0;
        int j;

        a[0] += 2;

        for (j=0; j<337; j++) {
            if (k == 1 && j > 2) {
                printf("%.3d", a[j-2]%t + q/p/t);
            }

            q = a[j]*k + q%p*t;
            a[j] = q/p;
        }
    }

    printf("\n");

    return 0;
}

[ X Files @ 28.03.2010. 09:00 ] @

^
Je l' to kolega Nedeljko pre i posle spavanja? ;)

[ Nedeljko @ 29.03.2010. 09:17 ] @

Citat:

Nedeljko: Kolega, niste dobro naučili matematiku. Ovde nema nikakve anomalije, program je potpuno čist.

Kolega, Vi niste dobro naučili matematiku! Program ima anomaliju o kojoj ću nešto napisati kasnije.

[ Goran Rakić @ 29.03.2010. 09:28 ] @

Nedeljko, da li ti je dobro?

[ mmix @ 29.03.2010. 22:05 ] @

Hoces i ti da odbijes milion dolara kad ti ponude

pa nas spremas polako

[ Nedeljko @ 29.03.2010. 23:11 ] @

je osnova sistema. Problem je što može biti

(konkretno, može biti jednako

, ali ne i više od toga), pa to što se ispisuje ne mora biti cifra tog sistema. To se najlakše vidi tako što se osnova smanji na 10, pa se generiše dosta cifara. No, program je napisan da ispisuje oko 1000 cifara broja pi i u tom opsegu se greška ne ispoljava, pa je izlaz dobar.

[ Nedeljko @ 30.03.2010. 09:26 ] @

Citat:

Goran Rakić: Nedeljko, da li ti je dobro?

Ma, dobro sam ja, nego ispravljam ovog kolegu što lupeta.

Citat:

mmix: Hoces i ti da odbijes milion dolara kad ti ponude :D pa nas spremas polako ;)

Pa, ne bi mi bilo loše sa miliončetom u džepu. Ko mi to nudi? Mogu li ja da preuzmem Grišinu nagradu umesto njega?

[ Nedeljko @ 31.03.2010. 16:17 ] @

Svi navedeni programi su "nategnuti" da ispale odredjen broj tačnih cifara. Kada bismo zamislili apstraktnu mašinu sa neograničenim intovima ili zamenili int sa nekom bigint klasom, na njima priloženi algoritmi ne bi ispaljivali bilo koji broj cifara broja pi tačno, već bi se dešavalo da ponegde omanu neku cifru (pa da opet iza nje imaju dugu seriju tačnih cifara).

[ Nedeljko @ 06.04.2010. 02:41 ] @

Evo jednog čitljivog programa bez anomalija.

Code:
#include <stdio.h>
#include <stdlib.h>

#define EXPONENT 5
#define DIGITS 1000

int main(int argc, char *argv[])
{
    int t = 1;
    int n = (DIGITS + EXPONENT - 1) / EXPONENT;
    char format[] = "%.0d ";
    int summand[n+2];
    int sum[n+2];
    int i;
    int k = 0;
    int p;
    int q;

    for (i=0; i < EXPONENT; ++i) {
        t *= 10;
    }

    n++;
    format[2] = '0' + EXPONENT;

    for (i = 0; i <= n; ++i) {
        summand[i] = sum[i] = 0;
    }

    summand[0] = 2;

    do {
        int carrier = 0;

        for (i = n; i >= 0; --i) {
            sum[i] += summand[i] + carrier;
            carrier = sum[i]/t;
            sum[i] -= carrier*t;
        }

        k++;
        p = 2*k + 1;
        q = 0;

        for (i = 0; i <= n; ++i) {
            q = summand[i]*k + q%p*t;
            summand[i] = q/p;
        }

        for (i = 0; i <= n; ++i) {
            if (summand[i] != 0) {
                break;
            }
        }
    } while(i <= n);

    printf("3.");

    for (i=1; i < n; ++i) {
        printf(format, sum[i]);

        if (i % (2*EXPONENT) == 0) {
            printf("\n  ");
        } else if ((i & 1) == 0) {
            printf(" ");
        }
    }

    if ((n - 1) % (2*EXPONENT) != 0) {
        printf("\n");
    }

    printf("\n");
    system("pause");

    return EXIT_SUCCESS;
}

[ 3okc @ 22.05.2012. 19:19 ] @

Nije C ali jeste 'kraći', 'najkraći': računanje broja pi iz singl-Excel-formule. :D

66 karaktera i samo 5 tačnih decimala (od milion iteracija -vrlo sporo konvergira!) ali je zato ultra kratko.

(J. Sondow 1997.)

http://mathworld.wolfram.com/PiFormulas.html (70)

Code:

{=PRODUCT(1+1/(4*ROW(1:1000000)^2-1))/SUM(1/(4*ROW(1:1000000)^2-1))}

[ Nedeljko @ 22.05.2012. 20:25 ] @

Program ti jednostavno ne valja zato što koristi standardan realni tip ograničene tačnosti, pa ne možeš dobiti proizvoljan broj cifara..

[ 3okc @ 22.05.2012. 20:50 ] @

Šta je ovde "moj program"? Excel? Ja lepo potpisah autora algoritma a sad što se formule tiče, to je što je.

Inače, Excel u računanju koristi samo 15 značajnih cifara i to je obogaljujuće u ovom proračunu ali zato sam i postavio linkove i integralnu formulu, pošto Excel nije tema.

[ Nedeljko @ 22.05.2012. 22:03 ] @

Ovde se prilažu programi koji mogu da izračunaju mnogo više cifara broja pi, nego što to podržavaju standardni realni tipovi koji su mašinski podržani. Dakle, ovde tema nisu programi koji npr. ne mogu da izračunaju 100 decimala broja pi kako treba.

[ 3okc @ 23.05.2012. 06:20 ] @

Auu koliko sujete, nemam reči. Zašto je problem napisati program u C-u tako da se podrže svi neophodni "mašinski tipovi"? A broj decimala usko je vezan za broj iteracija i dakle ne može nikako biti propisan. Kao što i nije bio. Do malopre.

[ Nedeljko @ 23.05.2012. 12:34 ] @

Nije nikakav problem napisati program u bilo kom jeziku koji se oslanja na ugrađene tipove. Evo ti jednog

Code:
#include <iostream>
#include <cmath>
#include <iomanip>

using namespace std;

int main()
{
cout << setprecision(50) << 4*atanl(1); << endl;
}

Broj iteracija o kome govoriš je samo jedno od ograničenja tačnosti koju ćeš dobiti. Izvršavanjem gornjeg C++ programa ćeš doboti tačnost koja odgovara long double tipu. Recimo,

3.1415926535897932385128089594061862044327426701784

Zacrnjene su dobre cifre (umesto pslednje petice treba 46..., što se zaokrugljuje na 5). Dakle, korišćeni tip ima svoja ograničenja. Možeš praviti kakve god hoćeš programe po kakvim god hoćeš formulama, izvršiti koliko god hoćeš iteracija, ali ako se osloniš na standardne tipove, nežeš dobiti veću tačnost od one koju oni podržavaju. Poenta je upravo u pisanju koji nemaju ograničenja za broj cifara koje se mogu dobiti.