Dark: Primtall
I denne oppgaven skal det implementeres en algoritme som avgjør om et heltall er et primtall eller ikke. Bruk Darks Load/Store-arkitektur.
Heltallet som skal avgjøres legges i register 5. Dersom tallet er et primtall, skal register 6 settes til 1, ellers skal register 6 settes til 0.
«The problem of distinguishing prime numbers from composite numbers and of resolving the latter into their prime factors is known to be one of the most important and useful in arithmetic. It has engaged the industry and wisdom of ancient and modern geometers to such an extent that it would be superfluous to discuss the problem at length... Further, the dignity of the science itself seems to require that every possible means be explored for the solution of a problem so elegant and so celebrated.» - Karl Friedrich Gauss, Disquisitiones Arithmeticae, 1801.
Det er ikke noe krav at algoritmen dere implementerer skal være effektiv. Faktisk var man inntil svært nylig usikker på om det i det hele tatt var mulig å løse dette problemet effektivt med en deterministisk algoritme. Forskere innenfor informatikk og matematikk har jobbet med dette problemet i årtier uten å finne en løsning. Men for litt over et år siden oppdaget noen studenter og deres veilleder en algoritme for å løse problemet effektivt med en deterministisk algoritme. (Med effektivt mener vi en algoritme som har polynomiell kjøretid.) Dette resultatet beskrives som sensasjonelt.
Har gitt:
start
; nop
;Skriv inn din kode her.
;push 4 ; b = 4
;push 2 ; a = 2
; gcd skal bli 2
data x
data y
data r
dup
pop x ; x = a
swap
dup
pop y ; y = b
swap
check
push y
jfalse slutt
push x
push y
mod ; x mod y
pop r ; r = x mod y
push y
pop x ; x = y
push r
pop y ; y = r
jmp check
slutt
drop
drop
push x
end start