Fibonacci (15p)¶
In Autumn 2024, the y86-assembly language project involves creating a program that checks whether all numbers in a given sequence are Fibonacci numbers. Fibonacci sequences have applications in various fields such as nature, art, and general technical applications. For this course, our focus lies in its use in computer science, such as in efficient search algorithms and other computational processes.
Examples of Fibonacci sequences as referred to in this project:
1,1,2,3,5,8,13,21,34,55 233,377,610,987,1597,2584 1346269,2178309,3524578,5702887,9227465,14930352,24157817 160500643816367088,259695496911122585,420196140727489673,679891637638612258
The project involves implementing a formula to determine if a number is a Fibonacci number. Below is an example implementation in C:
bool isPerfectSquare(int x) { int s = sqrt(x); return (s*s == x); } // Returns true if n is a Fibonacci Number, else false bool isFibonacci(int x) { return isPerfectSquare(5*x*x + 4) || isPerfectSquare(5*x*x - 4); }
It should be noted that the project requires efficient algorithms for multiplication and square roots, which are also explored in the exercises.
Note!!! While there are simpler solutions to compute Fibonacci numbers, these will not be accepted for this project. The required algorithm is designed to handle larger numbers effectively and is significantly more efficient than brute-force approaches.
Requirements¶
The project involves creating a Fibonacci checker that verifies whether all numbers in a memory-stored sequence are Fibonacci numbers.
- The project does not require checking whether the entire sequence forms a Fibonacci series. That is, you do not need to verify the relationship between consecutive numbers.
- The implementation must follow the algorithm described above. Other solutions will not be accepted, although you may discuss alternative solutions found online in the project’s reflection section.
- While the y86 architecture is 64-bit, the largest number to be handled is 1000, meaning the full range is not used.
- You may reuse assembly code from the exercises for implementing the algorithm.
The program must have the following features:
- The program starts at the
main:
block without any prior initializations. - The program reads the sequence starting at memory location
0x700
. - The sequence always begins with at least the number 1, i.e., it does not start with zero.
- The sequence ends with the number zero.
- The program stops execution when it encounters the first number that is not a Fibonacci number. This number should be returned in the
%rax
register. - If all numbers are Fibonacci numbers, the program returns the value 0 in the
%rax
register. - The goal is for the program to execute in approximately
20,000–30,000
machine instructions for the provided test cases. This is not an absolute requirement; see the guidelines below.
Here is an example initialization:
# Start by writing the sequence 3,5,8 to memory # Note! Lovelace checker does this automatically .pos 0 irmovq array,%r11 # memory address 0x700 irmovq $3,%r12 # 3 rmmovq %r12,(%r11) irmovq $5,%r12 # 5 rmmovq %r12,8(%r11) irmovq $8,%r12 # 8 rmmovq %r12,16(%r11) irmovq $0,%r12 # terminating zero rmmovq %r12,24(%r11) # Code to be submitted starts here main: # Your code # ... .pos 0x700 array:
Guidelines for the Project¶
- The project must be completed independently.
- While discussions with others are allowed, the code must be written individually.
- The project may be submitted incomplete.
- Bugs are acceptable, and the project does not need to pass all test cases completely.
- For the project to be accepted, the submitted code must show genuine effort and should work at least partially. Code that is still in its initial stages will not be accepted.
- During evaluation, missing features and bugs will be identified, and points will be deducted accordingly.
- The submitted assembly code must be well-documented with comments.
- Plagiarism rules are the same as for the Introduction course.
- In the comments, list others with whom you discussed the project to avoid suspicions of plagiarism due to similar solutions.
- You are not allowed to submit another student's code as your own.
Implementation¶
The project can be implemented by reusing your own code from the exercises. However, this might result in an inefficient solution since large numbers will lead to a quick increase in instruction count due to multiplication, division, and square root operations. Optimization opportunities can be explored here.
A good approach is to first create a working version of the program without worrying about the number of instructions. Once this version works, optimization can be considered.
The instruction count can be estimated by reviewing the code and manually calculating the number of instructions executed during runtime. For example:
- Loops and conditional branches should be taken into account.
- The code can also be run in a simulator, which provides an exact count of instructions executed. Instructions for installing a simulator are available in the assembly exercise section.
- There are several y86 simulators available online, such as this 32-bit y86 simulator. Note: In this simulator, the instruction suffix q must be replaced with l (e.g., irmovq -> irmovl).
- This year, Lovelace would provide the number of instructions. But please, do not use Lovelace just to check the number of instructions.
In the reflection section of the project, consider how the program could be made more efficient. For instance:
- Try to estimate the amount of instructions executed by each one of your subroutines or significant amount of code. Provide a justification for your estimate.
- If the program exceeds 59,000 instructions, reflect on this issue. Note that instruction count does not affect the points awarded for the project, but reflection is required.
- Identify any clear bottlenecks in your implementation.
- Consider if Peasant multiplication is helpful or improves instruction count.
- Could division be optimized? Would the remainder help?
- Is there an elegant single-instruction solution for bit shifting left (towards MSB)?
- Could loops/subroutine calls be optimized?
- What optimization choices did you make, and what was their impact (e.g., on instruction count)?
- etc.
Grading¶
The project is worth a maximum of
15 points
, distributed as follows:- A functioning y86-assembly program meeting the specifications:
0–9 points
- Submissions exceeding 300,000 instructions will be accepted, and the program may include bugs. Instruction count influences points, and optimization options should be discussed in the reflection section.
- The submitted code must demonstrate genuine effort to solve the problem.
- Bugs will result in
1–2 point
deductions depending on severity: - For example, whether it’s a small calculation error in some test cases or the program stops working entirely.
- Evaluators will manually review the submitted code, identify bugs, and assign points accordingly.
- Well-documented and readable assembly code with subroutine calls and consistent register usage:
0–3 points
- Reflection on your implementation:
0–3 points
- Address the reflection questions above. Runtime instruction count (or an estimate) must be included.
- Note: Reflection alone is not sufficient for passing the project!
- The reflection section should be 10–15 lines in the comments of your code file. Example:
# TKJ Project 2024 Fibonacci # Olli Student, student number, email # # Reflection: # - Runtime instruction count: xxxx # - I optimized the program using method x.. # - ... # Code starts here main:
Assembly Programming Guidelines¶
Programming in assembly is more challenging than high-level languages, so a few general tips:
- Plan your program thoroughly, just as you would for a high-level language.
- A "try and error" approach doesn’t work for more complex assembly programs.
- Using concepts from "structured programming" is beneficial. Divide the program into functional sections that can be implemented as subroutines and combined into a working program.
- What subroutines are needed? How should they be placed in memory to minimize jumps/branches? How are parameters passed?
- Could any code from the exercises be reused?
- Assign consistent purposes to registers in advance (and stick to them):
- Some registers are only for "global variables."
- Some registers are for "temporary variables."
- Some registers are for subroutine "parameters" (should the stack be used?).
- Using the stack:
- The stack grows "downwards" in memory, so ensure it doesn’t overwrite the code...
- Extra data can remain on the stack at the end of the program, as long as the required result is at the bottom (or topmost in memory).
- Test your algorithm on paper or implement it in C to understand the intermediate results assembly code should produce.
- In the C code, you could name variables after registers.
- Test your code in a simulator.
- Test subroutines as standalone programs.
- Test conditional statements similarly. Use all possible result types (e.g.,
<0, ==0, >0
). - For jumps, it’s often sufficient to examine the
ZF
flag (is the result zero or not zero?). - If your program exceeds 10,000 instructions, you can increase the maximum instruction limit using a simulator flag.
- For example, run the simulator with the command
ssim fibonacci.yo -l 50000
for a 50,000-instruction limit. - The code must be well-documented with comments.
- Test this by stepping away from the code for a few days, then returning to it.
- Debugging/testing your program can be done by inserting
halt
instructions at appropriate locations, then checking the intermediate results/state in the simulator. For example, after implementing part of the algorithm, stop execution with ahalt
command and inspect registers/memory. You can also usebrk
instructions to create breakpoints if you use the recommended online simulator. However, be sure that they are removed before sending the file to Lovelace. Lovelace do not recognize those. - It's definitely worth asking for help from the exercises or the Discord chat if needed. The staff is hired to assist you.
Submission¶
The project deadline is 2024-12-22 23:59
Project Grading¶
Assessment guidelines are provided in the return box. In this course, there is no feedback meeting. Total points is 15 points.
Grading takes into consideration, among other things, the number of instructions used, the number of test that succeed and other aspects such as code structure, comments and reflection.
We have estimated the amount of steps that each number check might take, with a non super-optimized code:
- Low numbers (<20) ~ 8000 - 8500 steps
- Medium numbers (20<x<100) ~ 17000 - 18000 steps
- Large numbers (100<x<1000) ~18000 - 20000 steps.
Each test contains a different list of numbers, but are designed that with some optimization number of iterations is < 59000. If you do not have good optimizations it could go to 120000 easily. If no optimization at all number of steps might be up to 300k (this is the maximum number of steps allowed. Grade takes this into account (see assessment criteria in the return box)
Minimum requirements¶
- Program must compile and not have runtime errors
- There should be clear proof that students tried to implement the provided algorithm. If it is not working add comments indicating what each subroutine is doing, what is failing and which are the possible causes.
- Students must get at least 5 points in the project, so it can be considered accepted.