C ja laitteistoläheinen ohjelmointi -kurssi 2010: Kolmas tentti 11.3.2011

Tehtäviä oli kolme, maksimipistemäärä 8 kustakin, hyväksytyn suorituksen raja 12 pistettä.

Tehtävä 1

Ensimmäisessä tehtävässä piti muuttaa vanha 16-bittiselle koneelle K&R C:llä tehty short-muuttujia käyttävä piin desimaaleja laskeva ohjelma pi.c käyttämään isompia lukutyyppejä ja pakkaamaan niihin enemmän desimaaleja per luku niin, että samasta tiedostosta saa käännettyä sekä alkuperäisen että uuden version sopivalla optiolla (-D...).

Tässä olisi pitänyt huomata miten DIGITSIZE, BASE, Digit ja LongDigit riippuvat toisistaan; niiden määrittelyjen kohdalla olevat kommentit kertoivat periaatteessa kaiken olennaisen: pelkän DIGITSIZEn muuttaminen ei vaikuta laskentaan mitenkään (varaa vain turhaan muistia), ellei BASEa muuteta vastaavasti, ja Digit ja LongDigit pitää määritellä niille riittävän suuriksi. Optimaaliset arvot voi laskea niiden kohdalla olevista kommenteista selviävillä kaavoilla, esim. long ja long long -tyypeillä 9 desimaalia; tässä olisi kuitenkin kelvannut mikä vain toimiva 4:ää suurempi arvo. Tyypeille Digit ja LongDigit on useita periaatteessa järkeviä yhdistelmiä, tehokkain 64-bittisessä koneessa olisi unsigned long long molempiin.

Lisäksi PrintBig -funktiossa oli taulukon s kokona vakio 5, joka toimii vain kun DIGITSIZE on enintään 4; se olisi pitänyt korjata DIGITSIZE+1:ksi, ja tulostusformaatti parissa paikassa riippuu Digit-tyypistä.

Ohessa malliratkaisut newpi.c, joka on käännettävissä optioilla -DDIGITSIZE=4 (vanha, short + long) tai -DDIGITSIZE=14 (long long + long long), ja newpi2.c, joka ymmärtää kaikki DIGITSIZE:n arvot 1-14 ja jossa on muutettu funktioiden määrittelyt modernin C:n mukaisiksi (mitä ei vaadittu) ja sille sopiva Makefile.

Ratkaisusta, jossa muutetaan vain Digit-tyyppiä muuttamatta siihen pakattavien desimaalien määrää, sai 5 pistettä.

Tehtävä 2

Toisessa tehtävässä piti korjata piin desimaaleja Monte Carlo -menetelmällä laskeva ohjelma, joka alusti satunnaislukugeneraattoreita toistuvasti samalla siemenluvulla, siten, että satunnaislukugeneraattorin tila säilytettäisiin samannumeroisen lapsiprosessin seuraavaan käynnistykseen.

Kuten "man random" kertoo, satunnaislukugeneraattorin tilan alustamiseen ja säilyttämiseen on funktiot initstate() ja setstate(), joita siis olisi pitänyt käyttää srandom()in asemesta. Lisävaikeus tulee siitä, että tilataulukoistakin pitää tehdä jaettua muistia, muuten niiden arvo katoaa lapsiprosessin päättyessä, ja jokainen lapsiprosessi tarvitsee omansa, joten niistäkin pitää tehdä taulukko.

Malliratkaisu tässä.

Luovasta ideasta käyttää pääohjelman random()-arvoa lapsiprosessien srandom()-kutsussa sai kaksi pistettä. (Sillä saa aikaan erilaisia tuloksia lapsiprosessien eri kutsukerroilla, mutta ei riippumattomia, tilastollisesti tulos ei ole sen parempi kuin alkuperäinenkään, eikä se myöskään vastaa tehtävänantoa - ja kiertää sen molemmat vaikeudet, initstate()/setstate() -funktiot ja jaetun muistin käytön.)

Tehtävä 3

Kolmannessa tehtävässä piti muuttaa kokonaislukuja tiedostoon pakkaavaa ohjelmaa niin, että bittimäärää ja lukujen määrää ei tarvitse antaa argumentteina vaan se pakatessa laskee ne itse ja tallettaa ne tiedoston alkuun ja purettaessa vastaavasti lukee ne tiedoston alusta.

Olennaisesti siis piti osata lukea ennestään tuntemattoman kokoinen taulukko muistiin, etsiä siitä suurin luku ja laskea montako bittiä sen tallentamiseen tarvitaan, ja tallettaa nämä tiedot tiedoston alkuun kirjoitetettaessa ja löytää ne sieltä luettaessa.

Malliratkaisu tässä.

Syöttötietojen lukemisesta dynaamisesti kasvatettavaan taulukkoon sai kaksi pistettä, bittien laskemisesta oikein olisi saanut kolme pistettä, lukujen ja bittien määrän kirjoittamisesta tiedoston alkuun kaksi lisää ja lukemisesta vielä yhden.