Fibonacci functions. You will write three functions, each of which computes Fibonacci numbers.

Question

Fibonacci functions. You will write three functions, each of which computes Fibonacci numbers.

Write the assembly code for the functions fibonacci_recursive.s, fibonacci_iterative.s, fibonacci_closed.s. Provide the assembly code as the answers for all three functions separately.

main.c code

#include <stdio.h>

#include <inttypes.h>

#include <math.h>

uint64_t fibonacci_recursive(uint64_t n);

uint64_t fibonacci_iterative(uint64_t n);

uint64_t fibonacci_closed(uint64_t n);

double phi;

int main() {

uint64_t n;

scanf("%" SCNu64, &n);

phi = (1.0 + sqrt(5.0)) / 2.0;

printf("Recursive: %" PRIu64 "\n", fibonacci_recursive(n));

printf("Iterative: %" PRIu64 "\n", fibonacci_iterative(n));

printf("Closed: %" PRIu64 "\n", fibonacci_closed(n));

return 0;

}

Code for the functions:



#include <stdio.h>

#include <inttypes.h>

#include <math.h>

uint64_t fibonacci_recursive(uint64_t n);

uint64_t fibonacci_iterative(uint64_t n);

uint64_t fibonacci_closed(uint64_t n);

double phi;

int main() {

    uint64_t n;

    scanf("%" SCNu64, &n);

    phi = (1.0 + sqrt(5.0)) / 2.0;

    

    printf("Recursive: %" PRIu64 "\n", fibonacci_recursive(n));

    printf("Iterative: %" PRIu64 "\n", fibonacci_iterative(n));

    printf("Closed: %" PRIu64 "\n", fibonacci_closed(n));

    

    return 0;

}

uint64_t fibonacci_recursive(uint64_t n)

{

    if(n == 0)

        return 0;

    else if (n == 1)

        return  1;

    return (fibonacci_recursive(n - 1) + fibonacci_recursive(n - 2));

}

uint64_t fibonacci_iterative(uint64_t n)

{

    uint64_t fn = 1, fn_1 = 0;

    for(int i = 2; i <= n; i++)

    {

        uint64_t temp = fn + fn_1;

        fn_1 = fn;

        fn = temp;

    }

    return fn;

}

uint64_t fibonacci_closed(uint64_t n)

{

    return (pow(phi,n) - pow(-1,n)/pow(phi,n))/sqrt(5);

}

Answer 1

Assembly code for fibonacci_recursive.s:

fibonacci_recursive:

PUSH {LR}

CMP R0, #0

BEQ recursive_base_case

CMP R0, #1

BEQ recursive_base_case

SUB SP, SP, #16

MOV R1, R0

SUB R1, R1, #1

BL fibonacci_recursive

MOV R2, R0

SUB R0, R0, #1

BL fibonacci_recursive

ADD R0, R0, R2

ADD SP, SP, #16

POP {PC}

recursive_base_case:

MOV R0, R0

POP {PC}

Assembly code for fibonacci_iterative.s:

fibonacci_iterative:

PUSH {LR}

CMP R0, #0

BEQ iterative_base_case

CMP R0, #1

BEQ iterative_base_case

MOV R1, #1

MOV R2, #0

MOV R3, #2

iterative_loop:

CMP R3, R0

BEQ iterative_loop_end

ADD R4, R1, R2

MOV R2, R1

MOV R1, R4

ADD R3, R3, #1

B iterative_loop

iterative_loop_end:

MOV R0, R1

POP {PC}

iterative_base_case:

MOV R0, R0

POP {PC}

Assembly code for fibonacci_closed.s:

fibonacci_closed:

PUSH {LR}

CMP R0, #0

BEQ closed_base_case

MOV R1, #1

MOV R2, #5

BL sqrt

MOV R3, #1

ADD R4, R3, R2

BL sqrt

ADD R5, R1, R4

MOV R6, #2

BL pow

SUB R7, #1

MOV R8, #2

BL pow

ADD R9, R6, R7

MOV R10, #5

BL sqrt

MUL R11, R10, R9

DIV R12, R11, R6

MOV R0, R12

POP {PC}

closed_base_case:

MOV R0, R0

POP {PC}