Lab 2: Hosoya's Triangle (Fibonacci Triangle)

Introduction

This lab generates the N-th row of Hosoya's Triangle. The solution will include code that uses multiple arrays.

Background

A Hosoya's Triangle, also known as the Fibonacci Triangle, is a 2D version of the Fibonacci sequence. In a Fibonacci sequence, each number is calculated by adding the previous 2 numbers.

\[\Large 0,\ 1,\ 1,\ 2,\ 3,\ 5,\ 8,\ 13 \]

i.e \[\large \begin{align*} 0+1 &= 1 \\ 1+1 &= 2 \\ 1+2 &= 3 \\ 2+3 &= 5 \\ \dots \end{align*}\]

The first two diagonals of Hosoya's Triangle (from top to left) are the Fibonacci sequence (without \(F[0] = 0\)), and each subsequent diagonal is created by adding the elements of the previous two diagonals.

Assignment

Write a RISC-V program for the function hosoyaTriangle that writes the N-th row of Hosoya's Triangle to a preallocated array according to the following specifications:

hosoyaTriangle:
Writes N-th level of Hosoya's Triangle in array provided in a2

Arguments:
a0: N
a1: Pointer to empty array used for storing Fibonacci Sequence
a2: Pointer to empty array used for storing N-th row of Hosoya's Triangle

Side Effect:
Array provided in a2 contains the N-th row of Hosoya's Triangle

The solution may contain helper functions as long as they do not share a name with any labels already used in the common.s file.

Hosoya's Triangle Generator in RISC-V

The provided file hosoyaTriangle.s contains the label for the hosoyaTriangle function. The solution must be written using this file. Do not modify the hosoyaTriangle label, because this label is required by the common.s file to properly call your hosoyaTriangle function.

The directive .include "common.s" in hosoyaTriangle.s causes RARS to insert the code from the file common.s before the start of any code in the solution. The code in common.s allocates space in memory, parses the numbers from the test file into a 2D array of integers, and then calls the hosoyaTriangle function written as a solution to the lab. You are encouraged to read the code in the common.s file to understand how the whole program works.

0-Based Indexing

This lab uses 0-based indexing:
The 0-th row of Hosoya's Triangle is \(H[0] = [1]\).
The 0-th Fibbonacci number is \(F[0] = 0\).

Computing Hosoya's Triangle:

Fibonacci Sequence:

The pseudo-code below describes the easiest way to do this.

F[0] = 0
F[1] = 1
// For n >= 2, compute:
F[n] = F[n-1] + F[n-2]

\(F[n]\) represents the n-th number of the Fibonacci sequence because of the 0-based indexing.

These values can then be used in the formula for Hosoya's Triangle below, where each element is calculated by multiplying appropriate Fibonacci numbers.

Hosoya Triangle rows:

\( H[n] \) is the notation used to represent the \( n \)-th row of Hosoya's Triangle for Hosoya's Triangle, which contains \((n+1)\) elements, as we are using 0-based indexing.

\( H[n][k] \) corresponds to the \( k \)-th element in the \( n \)-th row of Hosoya's Triangle, again, using 0-based indexing.

Example: \(H[2] = [3, 2, 2, 3]\)

• \(H[2][0] = 3\)
• \(H[2][1] = 2\)
• \(H[2][2] = 2\)
• \(H[2][3] = 3\)

To calculate \( H[n][k] \), you can use the formula

\[ H[n][k] = F[k+1] \times F[n-k+1] \]

\( F[k] \) represents the \( k \)-th Fibonacci number and \( F[n-k+1] \) represents the \( (n-k+1) \)-th Fibonacci number. Each element in Hosoya's Triangle is derived by adding two consecutive numbers.

Multiplication Extension:

The core RISC-V ISA (RV32I) does not contain any multiplication instructions. However, there is a standard extension (M) that contains integer multiplication and division instructions. RARS supports these instructions natively.

Loops:

There are many different ways to implement loops in RISC-V. Several examples can be found here: Do-While, While, For

Testing Your Lab

When debugging, it can be very helpful to step through the assembly code instruction by instruction. You can use ebreak statements to pause the execution program execution at a specified instruction and examine the state of the registers and memory. From that point you can then execute instructions one by one.

The folder Code/Tests/ contains sample test cases. The *.txt files contain test inputs. The corresponding *.out file contains the correct output. The provided test cases are not extensive. Additional testing is required to ensure that the solution is correct.

To perfom a test, enter the complete file path of the corresponding test input into the Program Arguments box in RARS. The file path cannot have any spaces. Do not put quotations areound the filename. Provide a full path to the file. For example /home/user/cmput229/test.txt is a valid path, while /home/user/cmput 229/this is a test.txt is not. Once you have entered the path to the test case, you can run the program. If the program arguments field does not appear in your RARS, you need to change your settings. Go to Settings -> Program Arguments Provided To Program (second option) and make sure that this opiton is checked.

You can test your lab from a terminal with rars LABFILE pa TESTFILE where LABFILE is the path to hosoyaTriangle.s and TESTFILE is the path to the file that contains the test case you want to test. Depending on the version of RARS and your operating system RARS may print extra copyright lines. Ignore these lines.

CheckMyLab

Link to CheckMyLab

This lab is supported by CheckMyLab. To get started, navigate to the Hosoya's Triangle lab in CheckMyLab found in the dashboard. From there, you can upload test cases in the Test cases table (see below). Your test cases will be shared with the entire class. You can upload your hosoyaTriangle.s file in the My solutions table, which will then be tested against all other valid test cases.

Test Case Format

Test cases are plain text files ending with .txt that must be in the following format:

(NOTE! The stuff between the square brackets is not part of the input file)

N [Where N is the row you are to return] 

For example:

5

5 3 4 3 5

Resources

• Slides used for in-class introduction of the lab (.pptx) (.pdf)
• Marksheet used to mark the lab (.txt)