※ Fibonacci Sequence using Mips
- Tool
http://spimsimulator.sourceforge.net/
- Instruction Set
- Result Screen
- Source Explanation
main:
li $v0, 5
syscall
add $t0, $zero, $v0
add $a0, $zero, $t0
$v0에 5를 저장하여 콘솔창을 통해 입력받는 시스템콜을 이용한다. 입력 받은 값을 $t0에 저장한다. 그 값을 앞으로 사용할 함수의 인자로 사용하기 때문에 $a0에 저장한다. (가독성 때문에 이렇게 하였습니다.)
addi $sp, $sp, -4
sw $ra, 0($sp)
jal Fibonacci_Sequence
lw $ra, 0($sp)
addi $sp, $sp, 4
Fibonacci_Sequence 함수를 호출하기 위해 스택에 공간을 할당하고 $ra레지스터에 main함수를 호출했던 주소를 저장한다. jal명령어는 바로 다음 명령어의 주소를 $ra에 저장하고 해당 레이블로 이동하는 명령어이다.
함수 호출 후 사용한 스택공간은 원래대로 돌려준다.
jr $ra
main함수를 호출했던 곳의 바로 다음 명령어로 돌아간 후 프로그램은 종료된다.
Fibonacci_Sequence:
add $s0, $zero, $a0
li $t0, 0 # 반복문을 돌기위한 레지스터
li $t2, 0 # a=0
li $t3, 1 # b=1
li $t4, 0 # c=0
피보나치 수열에 사용할 레지스터들을 정의 하였다. $a0에는 main문에서 입력받은 값을 파라미터로 사용하여 그 값을 $s0에 저장한다. 피보나치 함수에서는 받아온 $s0으로 몇 개의 수를 나열할지 정할 것이다.
피보나치에 주로 사용되는 알고리즘은
c=a+b;
a=b;
b=c;
이 방식을 이용할 것이다. $t2는 a의 역할, $t3는 b의 역할, $t4는 c의 역할이다.
첫 번째값은 1로 고정 시킬 것이고 두 번째 값부터 시작하므로 두 번째 값이 1이 나오기 위해서는 a는 0, b는 1이여야 한다. $t0은 입력한 값만큼 반복하기 위한 레지스터이다.
Loop:
beq $t0, $s0, EndLoop
$t0(반복횟수)와 $s0(입력한 반복해야할 숫자)를 비교하여 같으면(반복문이 끝나게 된다.) EndLoop 레이블로 이동하고 그렇지 않으면 다음 명령어를 실행한다.
li $t1, 0 # 첫번째 수를 1로 두기 위해서
bne $t1, $t0, OneCondition
위에서 말한 것처럼 피보나치는 ‘1 1 2 3 5’ 이 방식으로 진행되므로 올바른 값이 나오기 위해서는 첫 번째 값은 1로 고정해야한다.
bne를 이용하여 $t0(반복하는 I같은 역할)이 0일 때 ((0~4) 5번 반복하므로) 즉 0=0일 때 첫 번째 수인 것이 true이므로 바로 밑의 명령문을 실행하면 된다. 같지 않다면 두 번째 수 이후의 숫자 이므로 OneCondition레이블로 이동한다.
li $v0, 1
li $a0, 1
syscall
첫 번째 수이므로 콘솔창에 출력하기 위한 시스템 콜($v0=0)을 이용하여 $a0 레지스터에 1을 저장하여 출력화면에 보이도록 한다.
li $v0, 11
li $a0, ' '
syscall
출력되는 숫자들을 구분하기 위해 ‘ ’ 공백을 사용하여 시스템콜(character출력을 위한 $v0=11)을 이용한다.
addi $t0, $t0, 1
5번의 반복중 한번을 사용한 것이므로 $t0에 1을 더해준다.
OneCondition:
여기서는 $t2는 a의 역할, $t3는 b의 역할, $t4는 c의 역할을 a, b, c로 표현하겠다.
add $t4, $t2, $t3 # c=a+b;
c에 a와 b를 더하여 저장한다.
(a와 b는 전과 바로 전의 값을 의미한다. 그대신 재귀로 짤 경우 $t0이 1일 때와 2일 때는 1만 나오도록 해야한다. 여기서는 간단한 알고리즘을 이용하였으므로 1인 경우만 1이 나오게하고 2부터는 a,b,c를 이용하여 결과를 나오게 하였다)
f(n)=f(n-1)+f(n-2)
li $v0, 1
add $a0, $zero, $t4
syscall
시스템 콜 출력을 통해 c를 출력한다.
li $v0, 11
li $a0, ' '
syscall
시스템 콜 출력을 통해 ‘ ’ 공백을 출력하여 출력 값들을 구분한다.
add $t2, $zero, $t3 # a=b;
add $t3, $zero, $t4 # b=c;
a(전 전의 값, 재귀로 본다면 f(n-2))에 b(전의 값)을 저장한다.
b(전의 값, 재귀로 본다면 f(n-1))에 c를 저장한다.
addi $t0, $t0, 1
j Loop
반복 횟수를 1 증가한고 Loop레이블로 이동한다. (반복문이므로)
EndLoop:
jr $ra
반복문이 모두 끝나게 되어 이 레이블로 이동하거나 오게 된다.
main함수를 호출했던 곳의 바로 다음 명령어로 돌아간 후 프로그램은 종료된다.
댓글 없음:
댓글 쓰기