500 Primes
Source Code
% Algorithm P: Print table of 500 primes
L IS 500 % The number of primes to find
t IS $255 % Temporary storage
n GREG 0 % Prime candidate
q GREG 0 % Quotient
r GREG 0 % Remainder
jj GREG 0 % Index for PRIME[j]
kk GREG 0 % Index for PRIME[k]
pk GREG 0 % Value of PRIME[k]
mm IS kk % Index for output lines
LOC Data_Segment
PRIME1 WYDE 2 % PRIME[1] = 2
LOC PRIME1+2*L
ptop GREG @ % Address of PRIME[501]
j0 GREG PRIME1+2-@ % Initial value of jj
BUF OCTA 0 % Place to form decimal string
LOC #100
Main SET n,3 % P1. Start table. n <- 3
SET jj,j0 % j <- 1
2H STWU n,ptop,jj % P2. n is prime. PRIME[j+1] <- n
INCL jj,2 % j <- j + 1
3H BZ jj,2F % P3. 500 found?
4H INCL n,2 % P4. Advance n
5H SET kk,j0 % P5. k <- 2 / k = ptop - kk
6H LDWU pk,ptop,kk % P6. n / PRIME[k] ?
DIV q,n,pk % q <- floor(n / PRIME[k])
GET r,rR % r <- n mod PRIME[k]
BZ r,4B % To P4 if r = 0 for checking the next n
7H CMP t,q,pk % P7. PRIME[k] large?
BNP t,2B % To P4 if q <= PRIME[k]
8H INCL kk,2 % P8. Advance k. k <- k + 1
JMP 6B % To P6.
GREG @ % Base address
Title BYTE "First Five Hundred Primes"
NewLn BYTE #a,0
Blanks BYTE " ",0 % String of three blanks
2H LDA t,Title % P9. Print Title
TRAP 0,Fputs,StdOut
NEG mm,2
3H ADD mm,mm,j0 % P10. Print line
LDA t,Blanks % Output " ".
TRAP 0,Fputs,StdOut
2H LDWU pk,ptop,mm % pk <- prime to be printed
0H GREG #2030303030000000 % " 0000",0,0,0
STOU 0B,BUF % Prepare buffer for decimal conversion
LDA t,BUF+4 % t <- position of units digit
1H DIV pk,pk,10 % pk <- floor(pk/10)
GET r,rR % r <- next digit
INCL r,'0' % r <- ASCII digit r
STBU r,t,0 % Store r in the buffer
SUB t,t,1 % Move one byte to the left
PBNZ pk,1B % Repeat on remaining digits
LDA t,BUF % Output " " and four digits
TRAP 0,Fputs,StdOut
INCL mm,2*L/10 % Advance by 50 wydes
PBN mm,2B
LDA t,NewLn % Output a newline
TRAP 0,Fputs,StdOut
CMP t,mm,2*(L/10-1) % P11. 500 printed?
PBNZ t,3B % To P10 if not done
TRAP 0,Halt,0시작에 앞서armasm
코드의 각 필드는 다음을 의미한다.
| line number | LABEL | OP | EXPR | Comments |
|---|---|---|---|---|
| 02 | L | IS | 500 | % The number of primes to find |
Line 01
01 % Algorithm P: Print table of 500 primes%로 시작하는 01은 주석으로 어셈블리 코드에 영향을 주지 않는다.
전역 레지스터 선언과 초기화
Line 02 ~ 03
02 L IS 500 % The number of primes to find
03 t IS $255 % Temporary storage..., the pseudo-operation
ISsets the equivalent of a symbol.
Pseudo-operation IS는 심볼의 값을 설정한다.
02에서 L은 500으로 설정된다. 이 값은 우리가 찾을 소수의 갯수이다.
03에서 t의 값은 $255 레지스터이다.
심볼들은 255 범위의 레지스터 값을 갖거나, 8바이트의 숫자값을 가질 수 있다.
일반적으로 레지스터를 나타내는 심볼은 소문자로 시작하고, 순수한 값을 나태내는 심볼은 대문자를 사용한다.
Line 04 ~ 09
04 n GREG 0 % Prime candidate
05 q GREG 0 % Quotient
06 r GREG 0 % Remainder
07 jj GREG 0 % Index for PRIME[j]
08 kk GREG 0 % Index for PRIME[k]
09 pk GREG 0 % Value of PRIME[k]The pseudo-op
GREGon line 04 allocates a global register.
Pseudo-operation GREG는 전역 레지스터를 할당한다.
$255 레지스터는 항상 전역 레지스터이다.
04의 GREG는 253에 대해서 그러하다. 따라서 04에서 09까지 총 6개의 전역 레지스터가 할당된다. 그리고 n, q, r, jj, kk, pk는 각 레지스터와 동일하다.
| Symbol | Global Register | Value |
|---|---|---|
| n | $254 | 0 |
| q | $253 | 0 |
| r | $252 | 0 |
| jj | $251 | 0 |
| kk | $250 | 0 |
| pk | $249 | 0 |
GREG 정의의 EXPR 필드가 0이면, 해당 전역 레지스터는 프로그램이 실행될 때 동적으로 변하는 값을 갖는다고 가정한다.
14, 15, 34, 45와 같이 0이 아닌 식이 주어지면, 해당 전역 레지스터는 프로그램이 실행되는 동안 상수값을 갖는다.
Line 10
10 mm IS kk % Index for output lines08줄에 따라 mm은 $250와 동일하다.
Line 11
11 LOC Data_Segment
Location LOC Expression: Continue to assemble instructions or data at the position in memory given by Expression. Often used Expressions are: #100 (where programs start) or Data_Segment. -- MMIX Quick Reference Card "Assembler Directives"
Pseudo-operation LOC는 EXPR에 의해 주어진 메모리의 위치에서 어셈블리 명령 또는 데이터가 계속됨을 의미한다.
Data_Segment는 MMIXAL에서 편의상 #2000 0000 0000 0000 (보기 편의상 4자리 마다 공백 문자를 넣었음. 실제로는 붙여써야 함)로 미리 정의되어 있다.
Line 12
12 PRIME1 WYDE 2 % PRIME[1] = 2WYDE는 2바이트 메모리를 할당하고 EXPR의 결과로 로 초기화 한다. 그리고 LABEL은 할당된 주소의 이름이 된다. 그리하야 Data_Segment 영역에 소수를 저장할 공간의 시작 주소에 PRIME1 이라는 이름이 붙었고, 거기에 첫번째 소수인 2가 저장되었다.
Line 13 ~ Line 15
13 LOC PRIME1+2*L
14 ptop GREG @ % Address of PRIME[501]
15 j0 GREG PRIME1+2-@ % Initial value of jj전역 레지스터 ptop에 PRIME1으로 부터 1000 bytes 떨어진 메모리의 주소를 저장한다.
그리고 전역 레지스터 ptop, j0에 아래와 같은 값이 초기화 된다.
| Symbol | Global Register | Value | |
|---|---|---|---|
| ptop | $248 | #20000000000003e8 | PRIME1+1000 |
| j0 | $247 | -998 | PRIME1+2-(PRIME1+1000) |
Line 16
16 BUF OCTA 0 % Place to form decimal string이 후 결과 출력을 위해 십진수 숫자를 저장할 문자열 버퍼로 메모리에 8 byte를 할당하고 0으로 초기화 한다. 그리고 그 주소의 이름은 BUF.
소수 구하기
Line 18
18 LOC #100user space address #0000 0000 0000 0100에 아래 코드가 위치한다.
Line 19 ~ 20
19 Main SET n,3 % P1. Start table. n <- 3
20 SET jj,j0 % j <- 1| Symbol | Global Register | Previous Value | Current Value |
|---|---|---|---|
| n | $254 | 0 | 3 |
| jj | $251 | 0 | -998 |
| j0 | $247 | -998 | -998 |
Line 21 ~ 33
소수를 찾는 루프 부분.
21 2H STWU n,ptop,jj % P2. n is prime. PRIME[j+1] <- n
22 INCL jj,2 % j <- j + 1
23 3H BZ jj,2F % P3. 500 found?
24 4H INCL n,2 % P4. Advance n
25 5H SET kk,j0 % P5. k <- 2 / k = ptop + kk
26 6H LDWU pk,ptop,kk % P6. n / PRIME[k] ?
27 DIV q,n,pk % q <- floor(n / PRIME[k])
28 GET r,rR % r <- n mod PRIME[k]
29 BZ r,4B % To P4 if r = 0 for checking the next n
30 7H CMP t,q,pk % P7. PRIME[k] large?
31 BNP t,2B % To P4 if q <= PRIME[k]
32 8H INCL kk,2 % P8. Advance k. k <- k + 1
33 JMP 6B % To P6.21번 줄에서는 n = 3이고, 3이 소수이므로 n을 PRIME[ptop + jj]에 저장한다. 뒤의 31번 줄에서 소수를 찾았을 때 2H로 브랜치하여 n을 저장한다.
22번 줄에서는 jj를 2만큼 증가시켜 다음 소수가 저장될 위치에 대한 인덱스로 사용할 수 있게 한다.
23번 줄에서는 jj가 0이되면 500개의 소수가 모두 구해진 것으로 이 경우에는 "2 Forward"로 2H 라벨이 붙은 44줄로 이동한다.
24번 줄에서는 홀수만 검사하기 위해 n을 2씩 증가 시킨다.
25번 줄에서는 n이 현재까지 찾은 소수로 나눠지는지 검사하기 위해 나눠볼 소수에 대한 인덱스로 kk를 사용한다. k = ptop + kk. n은 홀수이므로 ptop에 있는 2로는 나눠볼 필요가 없기 때문에 kk를 j0로 설정한다.
26번 줄에서는 메모리에 있는 k번째 소수를 로드한다. pk = M[ptop + kk] 값이 설정된다.
27번 줄에서 n을 pk로 나눈 몫을 q에 저장한다.
28번 줄에서는 레지스터 r(g#252)로 rR(remainder register)의 값을 가져온다.
29번 줄에서는 r이 0인지 여부를 검사하는데, r이 0이라는 것은 n이 소수로 나눠진다는 것을 의미하므로 n은 소수가 아니다. 때문에 다음 소수를 검사하기 위해 "4 backward" 하여 24번 줄로 이동한다.
30번 줄에서는 q와 pk의 값을 비교하는데 만약 q <= pk 이면 n은 소수이다. 이에 대한 증명은 연습문제 11번을 참고.
31번 줄에서는 q<= pk인 경우 t <= 0이 되므로 n은 소수로 판정되고 n을 저장하기 위해 "2 backward"인 21번 줄의 2H 라벨로 이동한다.
32번 줄에서는 n이 소수인지 아직 알 수 없으므로 다음 소수로 나눠보기 위해서 kk를 2만큼 증가시킨다.
33번 줄에서는 pk[ptop + kk]로 n을 나눠보기 위해서 "6 backward"인 26번 줄의 6H 라벨로 이동한다.
테이블 출력
결과가 출력되는 형식은 다음과 같다.
First Five Hundred Primes
First Five Hundred Primes
0002 0233 0547 0877 1229 1597 1993 2371 2749 3187
0003 0239 0557 0881 1231 1601 1997 2377 2753 3191
0005 0241 0563 0883 1237 1607 1999 2381 2767 3203
...
0229 0541 0863 1223 1583 1987 2357 2741 3181 3571Line 34 ~ 37
34 GREG @ % Base address
35 Title BYTE "First Five Hundred Primes"
36 NewLn BYTE #a,0
37 Blanks BYTE " ",0 % String of three blanks메모리에 출력에 필요한 문자열들을 위한 메모리를 할당하고 초기화한다.
Line 38 ~ 39
38 2H LDA t,Title % P9. Print Title
39 TRAP 0,Fputs,StdOut타이틀을 출력한다.
Line 40 ~ 61
40 NEG mm,2 % Initialize m.
41 3H ADD mm,mm,j0 % P10. Print line
42 LDA t,Blanks % Output " ".
43 TRAP 0,Fputs,StdOut
44 2H LDWU pk,ptop,mm % pk <- prime to be printed
45 0H GREG #2030303030000000 % " 0000",0,0,0
46 STOU 0B,BUF % Prepare buffer for decimal conversion
47 LDA t,BUF+4 % t <- position of units digit
48 1H DIV pk,pk,10 % pk <- floor(pk/10)
49 GET r,rR % r <- next digit
50 INCL r,'0' % r <- ASCII digit r
51 STBU r,t,0 % Store r in the buffer
52 SUB t,t,1 % Move one byte to the left
53 PBNZ pk,1B % Repeat on remaining digits
54 LDA t,BUF % Output " " and four digits
55 TRAP 0,Fputs,StdOut
56 INCL mm,2*L/10 % Advance by 50 wydes
57 PBN mm,2B
58 LDA t,NewLn % Output a newline
59 TRAP 0,Fputs,StdOut
60 CMP t,mm,2*(L/10-1) % P11. 500 printed?
61 PBNZ t,3B % To P10 if not done40번 줄에서는 mm(g#250)을 -2로 설정.
41번 줄에서는 mm = mm + j0로 설정
42번 ~ 43번 줄에서는 출력 라인의 첫 시작인 공백문자 3개를 출력한다.
44번 줄에서는 출력할 소수를 pk로 가져온다. pk는 PRIMES[ptop + mm].
45번 줄에서는 숫자를 문자열로 변환하기 위한 문자열을 위한 전역 레지스터를 할당한다.
46번 줄에서는 45번에 선언한 문자열을 BUF에 저장한다.
47번 줄에서는 t가 BUF + 4의 위치를 가리키도록 한다.
" 0000"
^
t48번 줄에서는 pk를 10으로 나눈 몫을 pk에 저장한다.
49번 줄에서는 pk의 나머지(digit)가 저장된 rR의 값을 r로 가져온다.
50번 줄에서는 digit를 char로 변환하기 위해 r에 문자 '0'을 더해준다.
51번 줄에서는 이렇게 변환된 digit을 버퍼에 저장한다.
52번 줄에서는 t에서 1을 빼서 앞의 자릿수로 이동시킨다.
" 0002"
^
t53번 줄에서는 pk이가 0이 아닌 경우, 출력할 자릿수가 더 남았다는 의미이므로 "1 backward"인 48번줄의 1H 라벨로 이동한다.
54~55번 줄에서는 BUF에 저장된 소수를 출력한다.
56번 줄에서는 다음에 출력할 소수의 위치를 계산하는데 소수 테이블이 row가 50고, column이 10이라, 현재 숫자에서 다음 50번째 숫자를 출력하기 위해 mm을 2 * L / 10 만큼 증가 시킨다.
57번 줄에서 mm이 음수면 현재 줄에 출력한 소수가 남았다는 의미로 "2 backward"인 44번줄로의 2H 라벨로 이동한다.
58~59번 줄은 10개의 소수를 다 출력하고 난 후, 개행문자를 출력해준다.
60번 줄에서는 mm이 마지막 소수를 가리키는 위치인지 검사한다.
61번 줄에서는 mm과 마지막 소수의 위치가를 비교한 경과가 같지 않은 경우(0이 아닌 경우), "3 backward"인 41번 줄의 3H 라벨로 이동한다.
mm의 값의 변화는 다음과 같다.
| Line | c00 | c01 | c02 | c03 | c04 | c05 | c06 | c07 | c08 | c09 | - |
|---|---|---|---|---|---|---|---|---|---|---|---|
| 1 | -1000 | -900 | -800 | -700 | -600 | -500 | -400 | -300 | -200 | -100 | 0 |
| 2 | -998 | -898 | -798 | -698 | -598 | -498 | -398 | -298 | -198 | -98 | 2 |
| 3 | -996 | -896 | -796 | -696 | -596 | -496 | -396 | -296 | -196 | -96 | 4 |
프로그램 종료
Line 62
62 TRAP 0,Halt,0프로그램을 종료한다.