CS 218 MIPS ASSEMBLY #4 Fibonacci and Perrin CS 218 Homework, MIPS Asst. #4 Purp
ID: 3915691 • Letter: C
Question
CS 218 MIPS ASSEMBLY #4 Fibonacci and Perrin
CS 218 Homework, MIPS Asst. #4 Purpose Become familiar with the MIPS Instruction Set, and the MIPS procedure calling Due: convention, and basic recursion. Thursday (7/05) 70 Points: rite a recursive assembly language program to compute the Fibonacci and Perrin sequences. HUT 3! HUT S! HUT 8 HUT 3! HUT o! S IT THE WE'RE SICK OF HUT o! HUT 1 HUT 1 HUT 2! FIBONACCI HoO! SERIES?ToUCHDOWN FoOTBALL HUT 2 T13 SERESPCORRECr,WoO. MARCUS FAVOR- HUT 3 ING THE HUT 2 BRAWNY. HUT S! The provided main program will call the following functions Function, fibonacci0, that recursively computes the Fibonacci number. Must be recursive for credit. The Fibonacci Sequence is defined as follows: e n0 or n1 fibonacci(n) = n fibonacci(n-2)fibonacci(n-1)if n22 Function, perrin, that recursively computes the Perrin number. Must be recursive for credit. The Perrin sequence is defined as follows: nE n= n= perrin(n) perrin(n-2) + perrin(n-3) if n>2 Function, getNumber0, that prompts for and reads the N value from the user. The program must verify that N is between 3 and 45 (inclusive o IfN25, display This is going to take a while (n> 25)". o If N 30, display "This is going to take a long time (n>30). o IfN>35, display "This going to take a really long time (n>35)" o If N >40, display "This is going to take a very long time (>30 minutes)" o If NExplanation / Answer
a) MIPS for Fibonacci() is given below:-
fibonacci:
pushq %rbp
movq %rsp, %rbp
pushq %rbx
subq $24, %rsp
movl %edi, -20(%rbp)
cmpl $0, -20(%rbp)
je .L2
cmpl $1, -20(%rbp)
jne .L3
.L2:
movl -20(%rbp), %eax
jmp .L4
.L3:
movl -20(%rbp), %eax
subl $1, %eax
movl %eax, %edi
call fibonacci
movl %eax, %ebx
movl -20(%rbp), %eax
subl $2, %eax
movl %eax, %edi
call fibonacci
addl %ebx, %eax
.L4:
addq $24, %rsp
popq %rbx
popq %rbp
ret
.LC0:
.string "10th Fibonacci number: %d"
main:
pushq %rbp
movq %rsp, %rbp
subq $16, %rsp
movl $10, -4(%rbp)
movl $10, %edi
call fibonacci
movl %eax, %esi
movl $.LC0, %edi
movl $0, %eax
call printf
movl $0, %eax
leave
ret
b) Perrin Number code in MIPS is given below:-
.LC0:
.string " Enter a Number: "
.LC1:
.string "%d"
.LC2:
.string "Error value of range. Please re enter"
.LC3:
.string "This should be quick"
.LC4:
.string "This is going to take a while (N > 25)"
.LC5:
.string "This is going to take a long time (N > 30)"
.LC6:
.string "This going to take a really long time (N > 35)"
.LC7:
.string "This is going to take a very long time (> 30 minutes)"
getNumber:
pushq %rbp
movq %rsp, %rbp
subq $16, %rsp
movl $.LC0, %edi
movl $0, %eax
call printf
leaq -4(%rbp), %rax
movq %rax, %rsi
movl $.LC1, %edi
movl $0, %eax
call __isoc99_scanf
movl -4(%rbp), %eax
cmpl $2, %eax
jle .L2
movl -4(%rbp), %eax
cmpl $45, %eax
jle .L3
.L2:
movl $.LC2, %edi
movl $0, %eax
call printf
movl $-1, %eax
jmp .L10
.L3:
movl -4(%rbp), %eax
cmpl $25, %eax
jg .L5
movl $.LC3, %edi
movl $0, %eax
call printf
jmp .L6
.L5:
movl -4(%rbp), %eax
cmpl $25, %eax
jle .L7
movl $.LC4, %edi
movl $0, %eax
call printf
jmp .L6
.L7:
movl -4(%rbp), %eax
cmpl $30, %eax
jle .L8
movl $.LC5, %edi
movl $0, %eax
call printf
jmp .L6
.L8:
movl -4(%rbp), %eax
cmpl $35, %eax
jle .L9
movl $.LC6, %edi
movl $0, %eax
call printf
jmp .L6
.L9:
movl -4(%rbp), %eax
cmpl $40, %eax
jle .L6
movl $.LC7, %edi
movl $0, %eax
call printf
.L6:
movl -4(%rbp), %eax
.L10:
leave
ret
perrin:
pushq %rbp
movq %rsp, %rbp
pushq %rbx
subq $24, %rsp
movl %edi, -20(%rbp)
cmpl $0, -20(%rbp)
jne .L12
movl $3, %eax
jmp .L13
.L12:
cmpl $1, -20(%rbp)
jne .L14
movl $0, %eax
jmp .L13
.L14:
cmpl $2, -20(%rbp)
jne .L15
movl $2, %eax
jmp .L13
.L15:
movl -20(%rbp), %eax
subl $2, %eax
movl %eax, %edi
call perrin
movl %eax, %ebx
movl -20(%rbp), %eax
subl $3, %eax
movl %eax, %edi
call perrin
addl %ebx, %eax
.L13:
addq $24, %rsp
popq %rbx
popq %rbp
ret
.LC8:
.string "Perrin Number: %d"
main:
pushq %rbp
movq %rsp, %rbp
subq $16, %rsp
movl $0, -4(%rbp)
.L17:
movl $0, %eax
call getNumber
movl %eax, -4(%rbp)
cmpl $-1, -4(%rbp)
je .L17
movl -4(%rbp), %eax
movl %eax, %edi
call perrin
movl %eax, -8(%rbp)
movl -8(%rbp), %eax
movl %eax, %esi
movl $.LC8, %edi
movl $0, %eax
call printf
movl $0, %eax
leave
ret
Please let me know in case of any clarifications required. Thanks!