MIPS Recursive and Non Recursive Fibonacci Implementation
Assembly Languages, MIPS, and MARS
There is not a unique language called “Assembly language”. Each processor family such as Intel, AMD, IBM, VAX, MIPS, etc. has its own machine instructions and a corresponding assembly language. An assembly language program is a sequence of step by step machine instructions (basic operations) to the processor, describing exactly what the hardware should do.The code in this article is in MIPS assembly language which is the corresponding assembly language for MIPS processor family. MIPS stands for Microprocessor without Interlocked Pipelined Stages. The MIPS processor, designed in 1984 by researches at Stanford University. MIPS is based on a simple, scalable RISC (Reduced Instruction Set Computer) architecture. The word size of the specific processor is a important factor when you write assembly programs for that processor. So the word size of MIPS processor is 4 bytes (32 bits). MIPS is very popular among students who learn assembly languages and instructors who teach assembly programming.
Nowadays we don't use MIPS processors in our computers but MIPS programming is very popular in education domain. So we use MARS (MIPS Assembler and Runtime Simulator). Here I'm not going to explain how to write MIPS assembly programs from the beginning because there are a lot of documentations and tutorials to teach you basic stuffs in the internet. So lets learn how to write a recursive function in assembly language step by step.
Non Recursive Fibonacci Implementation in MIPS Assembly Language
We should create a loop to print the number pattern 0, 1, 1, 2, 3, 5, 8, 13, 21, 34, ... and we should have variables to store previous two numbers, the loop count, and the total because this program will ask "how many numbers the user needs to print from Fibonacci series" and will generate and print numbers in Fibonacci series.
In assembly programming, we should have functions to handle the loop (loop and endloop). And we need separate functions for each different returns from a function (return0, return1).
Recursive Fibonacci Implementation in MIPS Assembly Language
In the machine level, recursive functions means going downward and upward in the machine's stack memory. The stack grows downward (as we push items onto the stack, the address decreases). The register $sp can be used to points to the top of the stack in MIPS and it does not provide push and pop operations on its memory stack. So you have to manually increase and decrease the memory address by 4 (because MIPS word size is 4 bytes) in order to go through the stack. In this code, we are handling 2 values at once because recursive Fibonacci function calls itself twice. So we decrease the stack address value by 4 and 8 when we go down in the recursive tree. When we need to go back, we increase it by 12.
When you implementing a recursive function in an assembly language, you should have a separate function to go back (goback) cause after we go down in the recursive tree, we should go up with calculated results to calculate the final result. After going through the below code, you will understand these concepts better. I have put some comments to make the code more understandable.
3 Comments
Great Explanation
ReplyDeleteCould you please explain how to print them out in array. Lets say I want the first n numbers printed out in array. where n is user input
ReplyDeleteAs this implemented code make a recursive tree, you can't print exact Fibonacci series directly. But you can print values in the each tree branch.
DeleteIf you need to print the exact series like 0 1 1 2 3 5, you have to implement a for loop from 0 to given number and run this recursive function inside the loop.
Post a Comment