Kevyt alkuluku (10p)¶
Tietokonejärjestelmät-kurssin harjoitustyö 2018 on Kevyt alkuluku. Kevyellä tässä tarkoitetaan laskennallisesti kevyttä tapaa etsiä alkulukuja muinaisten kreikkalaisten kehittämällä Eratostheneen seula:lla. Tämän algoritmin käyttäminen on perusteltua muistaen y86-suorittimien varsin pieniä laskenta- ja muistiresursseja.
Seula toimii seuraavasti:
- Kirjoitetaan lista kaikista luonnollisista luvuista alkaen kakkosesta ja päättyen johonkin valittuun suurimpaan lukuun n.
- Lähdetään liikkeelle ensimmäisestä luvusta ja poistetaan listasta kaikki sen monikerrat
- Kun luku on 2, poistetaan 4, 6, 8, jne..
- Listassa seuraava jäljellä oleva luku on alkuluku, eli se jää listaan.
- Nyt lukua 2 seuraava listassa jäljelläoleva luku on 3.
- Poistetaan listasta kaikki tämän alkuluvun moninkerrat.
- Nyt luku on 3, poistetaan moninkerrat 6,9,12, jne..
- Toistetaan vaiheita 3 ja 4, kunnes listassa seuraava jäljellä oleva luku on suurempi kuin listan suurimman luvun n neliöjuuri.
- Jos suurin luku 100, sen neliöjuuri 10 ja listassa seuraavana jäljellä on 11.
Alla referenssiesitys vastaavan seulan toteuttamiseksi C-kielellä. Koodi on mukailtu täältä.
#include <stdbool.h>
#include <stdio.h>
#define MAX 200
// Prints all primes less than MAX using the Sieve of Eratosthenes.
int main(void) {
bool sieve[MAX];
int i, j;
// initialize numbers to array
for (i = 0; i < MAX; i++) {
sieve[i] = true;
}
sieve[0] = sieve[1] = false;
// prime number or not? Note no square root
for (i = 2; i * i <= MAX; i++) {
if (!sieve[i]) {
continue;
}
for (j = i * i; j < MAX; j += i) {
sieve[j] = false;
}
}
// print prime numbers
for (i = 0; i < MAX; i++) {
if (sieve[i]) {
printf("%d\n",i);
}
}
}
Työn vaatimukset¶
Yleisesti:
- Harjoitustyö tehdään y86-assembly-kielellä y86-64-suorittimelle.
- Simulaattori verkossa täällä, mutta suosittelemme työasemasimulaattorin asentamista monipuolisempien ominaisuuksien vuoksi.
- Harjoitustyö tehdään yksin.
- Työstä saa toki keskustella muiden kanssa, mutta oma koodi on kirjoitettava itse.
- Plagiointia koskevat yliopiston säännöt ja samat säännöt kuin Johdatus-kurssin harjoitustyötä.
- Palautuksessa listatkaa henkilöt, joiden kanssa olette keskustelleet tehtävästä, ettei tule plagiointiepäilyksiä samankaltaisten ratkaisujen johdosta.
- Toisen opiskelijan koodia ei saa palauttaa omanaan.
Tekniset vaatimukset:
- Maksimiluku, eli mihin asti alkuluvut etsitään, annetaan
%rax
-rekisterissä. - Annettu luku voi olla mikä tahansa väliltä
2-200
- Ohjelmalla luvut pitää kirjoittaa pinoon (=taulukkoon) alkaen maksimiluvusta, jossa päällä on siis luku 2.
- Pinon alkuosoite on oltava
0x1800
- Ohjelman pitää tyhjentää pinossa ne luvut, mitkä eivät ole alkulukuja. Tyhjentäminen tehdään kirjoittamalla muistipaikkaan luku 0.
- Alkulukujen etsintä tehdään Eratostheneen seulalla, muita menetelmiä ei hyväksytä
- Lopputuloksena pinoon jää ne luvut välillä 2-maksimiluku, jotka ovat alkulukuja.
Esimerkki pinosta.
Ohjelman alussa: Ohjelman lopussa: 0x02 0x02 // alkuluku 0x03 0x03 // alkuluku 0x04 0x00 // poistui 0x05 0x05 // alkuluku 0x06 0x00 // poistui 0x07 0x07 // alkuluku 0x08 0x00 // poistui
Ohjeita työhön¶
Assembly-kielellä koodaaminen on astetta vaativampaa kuin korkean tason kielillä joten muutama yleisohje on paikallaan. Harjoitustyön tekemiseksi on kaksi tapaa: Oikea ja Väärä.
Väärä tapa tehdä harjoitustyö on seuraava:
- Koodataan jotain
- Testataan lähettämällä koodi Lovelacen tarkistimelle
- Yritetään miettiä mikä meni pieleen ja päädytään muuttamaan jotain arvauksen perusteella
- Palataan kohtaan 1.
Oikea tapa tehdä harjoitustyö on seuraava:
- Selvitetään miten C-kielinen seula toimii ja toteutetaan se vaihe vaiheelta assykoodina.
- Tässä ehdottomasti kannattaa palastella koodi pienempiin osasiin ja toteuttaa ne yksi kerrallaan. Kun pala saadaan tehtyä, testataan se irrallisena simulaattorissa viemällä itse rekistereihin sopivat arvot.
- Omaa aiempaa koodia harjoitustehtävistä voi toki hyödyntää.
- Seulaa voi myös laskea paperilla ja selvittää mitä välituloksia (eri muuttujat jne) koodin pitäisi saada.
- Voi olla jopa hyödyllistä toteuttaa C-kielinen algoritmi, niin että käyttää rekistereitä muuttujannimissä ja tekee ohjelman ikäänkuin se olisi assya.
- y86-simulaattori on kullankallis väline seurata mitä ohjelma oikein tekee.
- Simulaattoria voi ajaa komentoriviltä
ssim__
, jolloin saa tulostuksen ohjelman etenemisestä tai graffisessä käyttöliittymässässim
. - Assy-ohjelmoinnin periaatteita
- Mietitään C-kielen toteutuksista, mitä muuttujia algoritmi tarvitsee ja määritellään niille rekisterit. Näistä käyttötarkoituksista EI poiketa.
- Tietyt rekisterit vain globaaleille muuttujille
- Tietyt rekisterit vain apumuuttujille
- Tietyt rekisterit ovat vain aliohjelmakutsujen parametreille, jos tarvitaan aliohjelmakutsuja.
- Ehdollisissa hyppykäskyissä riittää usein pelkästään ZF-tilabitin tarkastelu, siis onko operaation tulos nolla tai erisuuri kuin nolla.
- Simulaattorissa näkee omasta koodista miten tilaliput asettuu ja tämän perusteella voi valita sopivan hyppykäskyn
- Eksoottisimpia ehtoja harvoin tarvitsee kun ei olla optimoimassa koodia..
- Koska algoritmi käyttää pinoa, mieti onko syytä kutsua aliohjelmia?
- Tehtävä voi olla kätevämpi toteuttaa epäsuorilla muistiosoituksilla pinoon, kuin että hakisi ja kirjoittaisi sinne arvoja..
- Ohjelman lopussa pinossa ei saisi olla ylimääräistä tavaraa, ts. ei muuta kuin alkuluvut
Deadline ja työn palautus¶
Takaraja sekä harjoitustehtäville ja harjoitustyölle on 31. Joulukuuta 2018 klo 23:59.
Työ palautetaan Lovelaceen, jossa se ajetaan tarkistimen läpi. Ohjelman ei tarvitse läpäistä tarkistinta, jotta työ hyväksyttäisiin. Tarkistimessa testien läpäisy ei myöskään takaa täysiä pisteitä, kts. arvosteluperusteet.
Palautettu koodi katselmoidaan myös henkilökunnan toimesta. Jotta työ hyväksytään, palautetusta koodista tulisi näkyä (riippumatta siitä menikö se tarkistimesta läpi) että ratkaisua on oikeasti yritetty. Koodia, joka on ihan alkutekijöissään, ei kannata palauttaa suorituksena.
Arvostelu¶
Max 10p, joka koostuu seuraavasti:
- Toimiva ohjelma, jossa on noudatettu ohjeita: max 8p
- Tarkastuksessa löydetyt bugit: -1 / -2p per bugi
- Koodi hyvin kommentoitu: 1-2p
- Kommenteista pystyy seuraamaan mitä koodissa tapahtuu. Voi olla esim jokaisen rivin lopussa lyhyt kommentti.
Kurssiarvosana¶
Seuraava koskee tätä 3op:n TKJ-osuutta.
- Harjoitustehtävistä saa max 20p.
- Harjoitustyöstä saa max 10p.
- Hyväksyttyyn kurssisuoritukseen pisteitä vaaditaan 50% harjoitustehtävien ja harjoitustyön maksimista eli 15 / 30p.
- Suorituksia tulee olla molemmista: sekä harjoitustehtäviä että lopputyö.
Koko kurssin Tietokonejärjestelmät (8op) arvosana tulee etusivulla kerrotun mukaisesti, eli molemmista kurssin osista tulee 50% arvosanaan.
Kurssipalaute¶
Pyydämme virallista palautetta palaute.oulu.fi:n kautta. Epävirallisempaa palautetta voi antaa ao. boksiin.
Anna palautetta
Kommentteja materiaalista?