Skip to content

📌 Fibonacci Project

The project

This project involves translating an algorithm into different programming languages to perform certain tasks, such as generating Fibonacci sequence items, detecting prime numbers, and computing the golden ratio. Disclaimer: this project was done quickly, for pedagogical purposes, and it’s not a good example of state-of-the-art coding.

Project Overview

This project involves creating and comparing algorithms in different programming languages for scientific computing tasks. The main objectives are to: - Generate the first n items of the Fibonacci sequence. - Detect prime numbers up to a user-defined limit. - Compute the golden ratio and calculate its error against \(\frac{1+\sqrt{5}}{2}\).

Cross-Platform Compatibility

  • The program should be compatible with both Linux 🐧 and Windows 🪟 operating systems.

Packaging and Language Requirements

  • Compile into DLL for Windows and SO for Linux.
  • Callable via Python, with Python handling time tracking.
  • Implementations in various languages:
  • Assembly: MASM x64 for DLL and NASM for DLL/SO (no SIMD AVX2 instructions).
  • C++: Using MSVC x64 and GCC compilers with -O3 or /Ox optimizations.
  • C#: Using .NET Core 8 for DLL.
  • Python: Version 3.12.1. In our example, it’s forbidden to use extra C-backed libraries like NumPy or pandas.
  • PyPy 7.3.14
  • JavaScript/TypeScript: Node.js (version 21.5.0) and in Firefox.

Performance Metrics

  • Time to Code: Measure the development and debugging time in each language using JetBrains IDEs and GitHub Copilot.
  • Execution Time: Record the time for single and multiple executions, including computing the uncertainty.
\[ u(\Delta T) = \frac{\sigma_{n-1}}{\sqrt{n}} \]
\[ \sigma_{n-1} = \sqrt{ \frac{1}{n-1} \sum_{i=1}^{n} (\Delta t_i - \mu)^2 } \]
\[ \mu = \sum^n_{i=1} \frac{\Delta t_i}{n} \]

Optimization Constraints

  • Focus on straightforward algorithms without excessive optimization.

Goal

This structured approach allows for an in-depth comparison of different programming languages and environments in handling typical scientific computing tasks.

Return

enum fbReturn {
    OK,      // 0
    TMT,     // Too many terms
    TB,      // Too big
    PRM_ERR, // Parameter error
};

Signature

extern "C" fbReturn FibonacciInterop(
    unsigned long long fbStart,
    unsigned char maxTerms, // Number of terms to compute (1 byte)
    unsigned long long maxFibo,  // Maximum Fibonacci value (8 bytes)
    unsigned long long maxFactor, // Maximum factorization value (8 bytes)
    unsigned char nbrOfLoops, // Number of loops of the algorithm (1 byte max)
    unsigned long long* arTerms, // Pointer to an array of `maxTerms` * 50 unsigned long long integers (quad words) to store the Fibonacci terms (flattened multidimensional array)
    bool* arPrimes, // Pointer to an array of `maxTerms` * 50 booleans, true if it is prime and false if it is not (flattened multidimensional array)
    double* arErrors, // Pointer to a `maxTerms` array of double-precision floats to store the error on the golden ratio
    double& fldGoldNumber // Reference to a double-precision float to store the final approximation of the golden ratio
);