miten on mahdollista koodata c:llä ohjelma joka laskee piin lukuarvoa ja näyttää jokaisen desimaaliosan näytöllä (ohjelmasta pääsee pois painamalla ESC (tai odottamalla, että kone posahtaa)). Yleensähän c ohjelmissa on muutujilla tietty maksimiarvo, niin miten tämän ohjelman toteuttaminen olisi mahdollista?
lainaus:
Yleensähän c ohjelmissa on muutujilla tietty maksimiarvo
öh ... ei?
no esimerkiksi int = -32768-32767
Mitä historiallista kääntäjää oikein käytät? Kyllä se int on nykyään yleensä 32-bittinen...
Tuohon toteutukseen on monia ratkaisuja. Joko keksit algiritmin, jolla voit laskea piin likiarvon seuraavia desimaaleja tietämättä edellisiä. Toinen vaihtoehto on käyttää tavallisten muuttujien sijaan taulukoita, jolloin saadaan jossakin määrin käytettyä ikään kuin suurempia muuttujia. Siinä joutuukin sitten tekemään koko joukon omia funktioita aina yhteenlaskusta alkaen.
Taisi olla jonkin koodivinkin kommentissa, mutta laitetaanpa nyt tähän. Tällä ohjelmalla saa laskettua piin likiarvon jonnekin asti, en nyt muista, minne.
#include <stdio.h>
int main()
{
int a = 0, b, c = 70000, e = 0, f[70001], g = 0, d = 0;
for (b = 0; b < c; b++) f[b] = 2000;
for ( ; d = 0, g = c * 2; e = d % 10000)
{
for ( b = c; d += f[b] * 10000, f[b] = d % --g, d /= g--, --b; d *= b);
c -= 14;
printf("%.1d", e + d / 10000);
}
// Tähän joku pysäytyskomento
return 0;
}Mistä lähtien C-kielessä int on ollut 32-bittinen???
long int on sitten ihan eri juttu...
Kyllä sen monet kääntäjät kääntävät 32-bittisenä.
int on 16 bittinen (- 2^15 .. 2^15 ) ja long int 32 bittinen, (-2^31 ... 2^31)
Ja piitä laskettaessa miljoonia desimaaleja pitkiä lukuja _ei_ tallenneta kerrallaan mihinkään samaan muuttujaan, tai yleensäkään koko litaniaa muuttujiin.
Esimerkiksi lukuja voidaan tulostaa suoraan stdouttiin tai sitten striimata tiedostoon desimaalien laskennan ohessa.
Eihän tuossa Metabolixin esimerkissäkään koko lukujono ole tallennettu kertaakaan samaanaikaan mihinkään muuttujaan, vaan (e+d/10000) sisältää käsittääkseni kerrallaan neljä piin desimaalia jotka sitten tulostetaan näytölle jonka jälkeen lasketaan muuttujiin uudet arvot joiden perusteella tulostetaan seuraavat neljä desimaalia.
Eikö int tarkoitat ihan vain, että muuttuja on kokonaisluku? Sitten voi erikseen määritellä, onko se short, eli 16-bittinen, vai long, eli 32-bittinen. Minun tietääkseni jos pistää pelkän int, niin se riippuu kääntäjästä, tuleeko siitä 16- vai 32-bittinen.
Pikaisella googletuksella (n. 10s) löytyi kaava piin n. desimaalin laskemiseen. ;)
Tällaiset kaksi:
http://numbers.computation.free.fr/Constants/
http://www.lacim.uqam.ca/~plouffe/Simon/
Edit: Erittäin mielenkiintoisia kaavoja muuten.. ..harmi vaan, että menevät joiltakin osin nykyisten taitojeni yli. :P
coaster, tomaattigeeni: short ja int ovat vähintään 16-bittisiä, long on vähintään 32-bittinen. x86:lla 32-bittisessä suojatussa tilassa pyörivät kääntäjät yleensä tarjoavat 32-bittistä int:ä.
Ja se arvoalue on 16-bittiselle signedille [-2^15, 2^15 - 1] ja 32-bittiselle [-2^31, 2^31 - 1] ;-)
coaster kirjoitti:
Mistä lähtien C-kielessä int on ollut 32-bittinen???
long int on sitten ihan eri juttu...
int on ollut 32-bittinen siitä lähtien kun koneiden arkkitehtuurit ovat muuttuneet 32-bittisiksi ja käyttöjärjestelmät ja kääntäjä ovat alkaneet tukea sitä. Alunperinhän int on ollut tietokoneen sanan mittainen kokonaisluku ja long kahden sanan mittainen. Aikojen saatossa kuitenkin monet ohjelmat ovat olettaneet int:n tai long:n olevan tietyn kokoiset ja kääntäjät ovat tarjonneet tukea näille ohjelmille, joten nykyään asia ei olekaan avain niin selvä kuin ennen. Monessa tapauksessa sekä int ja long ovat 32-bittisiä. Asiaa voi testata yksinkertaisella ohjelmalla:
#include <stdio.h>
#include <limits.h>
int main() {
printf("min int: %d max int: %d\n", INT_MIN, INT_MAX);
printf("min char: %d max char: %d\n", CHAR_MIN, CHAR_MAX);
printf("size of long double %d, double %d, float %d, longlong %d, \n",
sizeof (long double), sizeof (double),
sizeof (float), sizeof (long long));
printf("long %d, int %d, short %d, char %d\n",
sizeof (long), sizeof (int),
sizeof (short int), sizeof (char));
return 0;
}Metabolix: taulukon käyttö mielivaltaisen tarkkuuden aritmetiikkaan on kömpelö ratkaisu koska taulukon koko on muuttumaton. Käytä mieluummin linkitettyä listaa.
Minähän esitin sen olevan vain yksi vaihtoehto, en väittänyt sitä hyväksi. Itse käytänkin lähes aina vain linkitettyjä listoja.
dungeon86 kirjoitti:
miten on mahdollista koodata c:llä ohjelma joka laskee piin lukuarvoa ja näyttää jokaisen desimaaliosan näytöllä
Alanpa rakentamaan ihan alusta alkaen ajan kanssa projektinomaisesti sellaista ohjelmaa. Vinkkejä ja neuvoja otetaan vastaa. Kyseeseen tulevat dynaamiset muuttujat, jotka varaavat muistia sitä mukaa kuin tarvitsevat.
Tutkin ja pohdin aluksi hieman dynaamista tilanvarausta.
http://koti.welho.com/pkeckman/temp/lista.c (kopioitu oppikirjasta C-kieli, Oy Edita Ab, Kari Silpiö)
http://koti.welho.com/pkeckman/temp/Project1.exe
Jos käytössä olisi vaikka 200 MB muistia ja piin desimaaleja tallennettaisiin listaan, joka olisi tyyppiä:
typedef struct S
{
struct S *link;
unsigned char tieto;
} SOLMU;Veisi yksi tuollainen listan alkio tilaa 8 tavua...
tyyppi: koko tavuina: =======-------============ SOLMU 8 struct S 8 unsigned char 1 long 4 long double 12
...eli 8*8 bittiä eli 64 bittiä! Periaatteessahan yhden digitaalin 0..9 voisi tallettaa tietokoneen muistiin neljään bittiin eli kauheeta tilan tuhlausta tehdä tällaisella tavalla, mutta aloitetaan nyt tällä.
Siis 200 MB (=2000000 * 1024 tavua) johon mahtuisi (2000000*1024)/8 = 256000000 solmua ja siis vain 256 miljoonaa piin desimaalia mahtuisi tietokoneen muistiin kerralla vaikka tilaa olisi 2000000 * 1024 * 2 = 4 miljardille 96 miljoonalle (kun yksi desimaali vie 4 bittiä eli puoli tavua).
Ihmetyttää hieman miksi muuten SOLMU vie tilaa 8 tavua? Siinähän on siis tieto- ja linkkiosa. Tietoosa vie tilaa yhden tavun - kuinka paljon vie linnkiosa? 8 tavua? Eli onko tuo sizeof(SOLMU) function antama arvo nimenomaan sen linkin koon tarvitsema tila ja itse tietorakenne veisi siis 8+1 tavua ja piin desimaaleja mahtuisikin vain 2000000 * 1024 / 9 = 227 miljoonaa 555 tuhatta 555,555556 eli 227555555 alaspäin pyöristettynä?
Ja jos tuon tietorakenteen linkkiosa eli osoitin seuraavaan alkioon on 8 tavua, niin periaatteessahan sillä pystyy osoittamaan "vain" 2^(8*8) eli 18446744073709552000 muistipaikkaa. Eli tällä tarkastelulla on periaatteelinen raja piin desimaaleille hieman päälle 18 miljoonaa miljardia. Tyydytäänkö tähän vai tehdääkö tuosta osoittimesta jotenkin suhteellinen, niin että se ei osoita absoluuttista osoitetta vaan suhteellista? Silloinhan ei kai mitään periaattellista rajaa ole.
Projekti jatkuu huomenna?
Suosittelen, että rakennat ohjelman niin, että laskuissa tosiaan hyödynnetään koko muuttuja, eli käytetään kuusitoistajärjestelmää. Tuo outo tilanvaraus johtuu siitä, että monet kääntäjät asettelevat datan sen mukaan, paljonko suurin jäsen vie tilaa. Tuossa tapauksessa siis "struct S *" vie 4 tavua, joten myös yhden tavun kokoinen char vie saman verran. Jos tavuja olisi kaksi, koko tietueen koko olisi yhä sama.
Oli muuttujatyyppi mikä tahansa, tuossa tulee käytettyä ainakin puolet (tai __int64:ää käyttäen 2/3) muistista ihan vain tuohon seuraavan luvun osoittimeen, joten kannattaa varmaankin käyttää toteutukseen osoitinta suurempaan datasegmenttiin, vaikkapa kilotavuun kerralla. Taidanpa tehdä tästä koodivinkin, kunhan kerkiän.
Pystyyköhän tota kiertämään mitenkään, että joutuu (parhaimmassa tapauksessa) tuhlaamaan 4 bittiä yhteen desimaaliin. Periaatteessahan siihen mahtuisivat luvut 0..16 ($0..$f). Matemaattisesti laskettuna desimaalit 0..9 veisivät tallenuskapasiteettiä x kpl, jossa 2^x=10 eli x=2kantainenlog(10) eli x=log(10)/log(2)=3.321928095 bittiä.
----
Sinänsähän muistin tarve n:n desimaalin laskemiseksi ei ole O(n) vaan O(sqrt(n))
Tuolla artikkelissa
http://numbers.computation.free.fr/Constants/
mainttiin:
For example, it is possible to obtain the n-th decimal digit of p in time O(n3/2logn loglogn) and memory O(n1/2).
Muistin tarve kasvaa siis samassa suhteessa sqrt(n):n kanssa, mutta mikä lie kerroin? kerroin*sqrt(n).
Jos tuo kerran on ongelmasi, niin auttaisiko yhtään, jos käyttäisit 10 bittiä lukuihin 0..999, jolloin olisit jo lähempänä? 2^10 = 1024. Ja neljään bittiin mahtuvat luvut 0..15 eikä 0..16.
petterik kirjoitti:
Siis 200 MB (=2000000 * 1024 tavua) johon mahtuisi (2000000*1024)/8 = 256000000 solmua ja siis vain 256 miljoonaa piin desimaalia mahtuisi tietokoneen muistiin kerralla
Ei riittäisi alkuunkaan :( Sivun http://www.cecm.sfu.ca/personal/jborwein/
---
Näköjään systeemi ei päästä kirjoittamaan uutta viestiä, jos vika on oma "Jos haluat kirjoittaa lisää, voit vielä muokata edellistä viestiäsi." Luki mulla. No, tarkoitus oli tulla vastaamaan Metabolixin edelliseen.
Ei se ole sen kummempi ongelma ikuisuus projektissa. Järkevintä olisi kai laskea piitä 2-järjestelmän lukuna, en tiedä. silloin tulisi ainakin joka bitti käytetyksi, tai tutkia mille luvulle b 2^b on mahdollisimman lähellä jotain luku 10^x. No joo. Taidan jättää projektin sikseen.
http://www.geocities.com/SiliconValley/Pines/
"Pi calculated to 1.24 trillion digits"
Tulosta ei ole kylläkään vielä varmistettu.
Ja kuka sen tarkistaa, että ne kaikki desimaalit ovat oikeita? Siis tietysti todistetaan matemaattisesti, että algoritmi laskee oikein, mutta koneissahan on voinut tapahtua jokin yhden bitin häiriö - ja se riittää: kaikki sen jälkeiset desimaalit ovat väärin. Herääkin kysymys, että riittäisikö ennätyksen tekoon teoreettinen tarkastelu. Että jos annan tämän tai tämän algoritmin pyöriä 1/2 vuotta niin se todistettavasti laskisi oikeat 1.25 triljoonaa (=1250 miljardia?) desimaalia.
Aihe on jo aika vanha, joten et voi enää vastata siihen.