## Instructions

**Objective**

Write a program to calculate fibonacci in ARM Raspberry PI ARM assembly language .

## Requirements and Specifications

Implement the following two programs in ARM assembly. I suggest that you implement them first in some high level language (C/C++, Java, Python, etc), and translate the logic into assembly. Unless you clearly understand the problem and program structure for assembly language recursion, even translating the programs requires some thought. In particular, be sure to handle the stack values correctly.

As always, follow proper style as defined in the style guide.

- Implement a program to calculate multiplication using successive addition with recursion. For example, 5x4 is 5+5+5+5. This can be defined recursively as:
- Implement a program to calculate a Fibonacci number recursively. A Fibonacci number is defined recursively as:

Mult(m, n) = if n is 1, return m

Fib(n) = if (n == 0 or n == 1) return 1

else return Fib(n-1) + Fib(n-2)

**Screenshots of output**

**Source Code**

**Fibonacci**

```
.data
prompt: .asciz "Please enter fibonacci number to calculate: "
result: .asciz "Fibonacci(%d) = %d\n"
format: .asciz "%d"
number: .word 0
.text
.global main
@ Registers used:
@ R0 = used as first argument to functions and to hold return values
@ R1 = used as second argument to functions and to save variable address
@ R2 = used as third argument for printf
@ LR = return address
main:
sub sp, sp, #4 @ save return address
str lr, [sp]
ldr r0, =prompt @ load adress of prompt
bl printf @ print the prompt
ldr r0, =format @ format to read an integer
ldr r1, =number @ read in variable
bl scanf @ read the number
ldr r1, =number @ load variable address
ldr r4, [r1] @ load number value in r4
mov r0, r4 @ pass number to function
bl Fib @ calculate fibonacci of number
mov r2, r0 @ copy result to r2 for printing it
ldr r0, =result @ load adress of result message
mov r1, r4 @ copy number
bl printf @ print the result
ldr lr, [sp] @ restore return address
add sp, sp, #4
bx lr @ return to os
@ Function that calculates a Fibonacci number using recursion
@ Receives: r0 = number
@ Returns: r0 = fibonacci of number
@ Registers used:
@ R0 = function argument n and return value
@ R4 = saves the initial value of n
@ R5 = saves the result of Fib(n-1)
@ LR = return address
Fib:
sub sp, sp, #12 @ allocate space in stack to save registers
str lr, [sp, #0] @ save registers
str r4, [sp, #4]
str r5, [sp, #8]
if0:
cmp r0, #0 @ if number is 0
bne if1
mov r0, #1 @ return 1
b fib_ret
if1:
cmp r0, #1 @ if number is 1
beq fib_ret @ return 1
else:
mov r4, r0 @ copy number n to r4
sub r0, r0, #1 @ calculate n-1
bl Fib @ calculate Fib(n-1)
mov r5, r0 @ save result in r5
sub r0, r4, #2 @ calculate n-2
bl Fib @ calculate Fib(n-2)
add r0, r0, r5 @ add result of Fib(n-1) to Fib(n-2)
fib_ret:
ldr lr, [sp, #0] @ restore registers
ldr r4, [sp, #4]
ldr r5, [sp, #8]
add sp, sp, #12 @ remove allocated space from stack
bx lr @ return to calling function
```

**Multiply**

```
.data
prompt1: .asciz "Please enter first number to multiply: "
prompt2: .asciz "Please enter second number to multiply: "
result: .asciz "%d * %d = %d\n"
format: .asciz "%d"
number: .word 0
.text
.global main
@ Registers used:
@ R0 = used as first argument to functions and to hold return values
@ R1 = used as second argument to functions and to save variable address
@ R2 = used as third argument for printf
@ R3 = used as fourth argument for printf
@ R4 = first number to multiply
@ R5 = second number to multiply
@ LR = return address
main:
sub sp, sp, #4 @ save return address
str lr, [sp]
ldr r0, =prompt1 @ load adress of first prompt
bl printf @ print the prompt
ldr r0, =format @ format to read an integer
ldr r1, =number @ read in variable
bl scanf @ read the number
ldr r1, =number @ load variable address
ldr r4, [r1] @ load first number value in r4
ldr r0, =prompt2 @ load adress of second prompt
bl printf @ print the prompt
ldr r0, =format @ format to read an integer
ldr r1, =number @ read in variable
bl scanf @ read the number
ldr r1, =number @ load variable address
ldr r5, [r1] @ load second number value in r5
mov r0, r4 @ pass first number to function
mov r1, r5 @ pass second number to function
bl Mult @ multiply numbers
mov r3, r0 @ copy result to r3 for printing it
ldr r0, =result @ load adress of result message
mov r1, r4 @ copy first number
mov r2, r5 @ copy second number
bl printf @ print the result
ldr lr, [sp] @ restore return address
add sp, sp, #4
bx lr @ return to os
@ Function that multiplies two numbers using recursion
@ Receives: r0 = first number, r1 = second number
@ Returns: r0 = multiplication
@ Registers used:
@ R0 = function argument m and return value
@ R1 = function argument n
@ R4 = saves the initial value of m
@ LR = return address
Mult:
sub sp, sp, #8 @ allocate space in stack to save registers
str lr, [sp, #0] @ save registers
str r4, [sp, #4]
cmp r1, #1 @ if second number is 1
beq mult_ret @ return m (first number)
mov r4, r0 @ copy m to r4
sub r1, r1, #1 @ calculate n-1
bl Mult @ multiply m * (n-1)
add r0, r0, r4 @ add result of m * (n-1) to m
mult_ret:
ldr lr, [sp, #0] @ restore registers
ldr r4, [sp, #4]
add sp, sp, #8 @ remove allocated space from stack
bx lr @ return to calling function
```