uni/inf2440/hw2/rapport.txt

Kompilering: `javac *.java`
Kjøring: `java Main <tall>`

# Eksempelutskrift

I filen output.txt finner du et eksempel på å kjøre `java Main 2000000000`.

# Hvordan jeg har parallellisert

## Sil

Silen har jeg parallellisert ved å først generere de sqrt(n) første
primtallene sekvensielt, og så lager jeg n tråder som hver får en kopi av
det arrayet som har løst de sqrt(n) første tallene. Hver tråd krysser av
en del av tallene som ikke primtall. Når alle trådene er ferdige, slår jeg
sammen arrayene til de forskjellige trådene ved å ORe hver byte i hvert array,
slik at bare de tallene som ingen har markert som ikke primtall blir igjen.
Jeg bruker OR istedenfor AND fordi jeg lar 0 bety at tallet er primtall og
1 bety at det ikke er primtall, fordi det gjør at jeg slipper å gå igjennom
hele arrayet og sette hver byte til 11111111 når jeg oppretter silen,
siden et array av tall i Java starter som et array av 0.

## Faktorisering

Hver tråd får en del av primtallene opp til sqrt(n). Tråden går igjennom disse
primtallene, og når den finner et primtall som n kan deles på, gir den det
tallet til en monitor, som legger det til i en liste over faktorer og deler n
på primtallet. Alle trådene må deretter oppdatere hvilket tall de jobber med
og begynne på nytt. Når trådene har kommet til et tall som er større enn
sqrt(n) uten å finne faktorer, stopper tråden. Når alle trådene har stoppet,
vet monitoren at den er ferdig. Hvis tallet monitoren har kommet frem til så
langt etter å ha latt trådene faktorisere, er større enn sqrt(n), legges dette
tallet til listen faktorer, siden vi da vet at det er en faktor.

Måten primtallene fordeles på, er at hver tråd tar hvert n-te primtall, hvor n
er antall tråder, og hver tråd gis en unik startposisjon. Hvis det for eksempel
er 2 tråder, vil tråd 1 ta primtall 1(3), 3(7), 5(13), etc, og tråd 2 vil ta
primtall 2(5), 4(11), 6(17), etc. (Monitoren tar seg av de første 4
primtallene, fordi det tar så kort tid å finne dem at det ikke gir mening
å ha tråder som leter etter dem)

# Tider

CPU: quad core Intel Xeon E31225 @ 3.1 GHz (ingen hyperthreading)

2 000 000 000:
	* Erastothenes' Sil sekvensielt: 9.82s
	* Erastothenes' Sil parallelt: 6.77s (1.45x speedup)
	* Faktorisering sekvensielt: 19.46s (294.60ms per)
	* Faktorisering parallelt: 11.66s (1.67x speedup) (116.55ms per)

200 000 000:
	* Erastothenes' Sil sekvensielt: 829.98ms
	* Erastothenes' Sil parallelt: 618.72ms (1.34x speedup)
	* Faktorisering sekvensielt: 4.82s (48.25 per)
	* Faktorisering parallelt: 1.46s (3.30x speedup) (14.64ms per)

20 000 000:
	* Erastothenes' Sil sekvensielt: 68.11ms
	* Erastothenes' Sil parallelt: 41.41ms (1.64x speedup)
	* Faktorisering sekvensielt: 508.17ms (5.08ms per)
	* Faktorisering parallelt: 213.90ms (2.38x speedup) (2.14ms per)

2 000 000:
	* Erastothenes' Sil sekvensielt: 15.67ms
	* Erastothenes' Sil parallelt: 9.58ms (1.64x speedup)
	* Faktorisering sekvensielt: 93.61ms (936.07μs per)
	* Faktorisering parallelt: 73.76ms (1.27x speedup) (737.58μs per)

## Analyse:

* Erastothenes' sil sekvensielt:
	Tidene øker tilnærmet lineært mellom 20m, 200m, og 2 milliarder;
	10x større tall betyr 10x lengre tid.
	Mellom 2m og 20m øker tiden av en eller annen grunn bare 4.5x, men det
	er nærme nok 10x at jeg ikke vet om det betyr noe.
* Erastothenes' sil parallelt:
	Igjen øker tidene tilnærmet lineært mellom 20m, 200m, og 2 milliarder,
	og forskjellen på 2m og 20m er igjen bare rundt 4x.
	Både parallelt og sekvensielt kan det se ut som at
	jo større tallene er, jo nærmere kommer vi lineær økning.

* Faktorisering sekvensielt:
	Økningen her ligner mer på eksponensiell økning.
* Faktorisering parallelt:
	Igjen ser økningen eksponensiell ut.