Collection of Fibonacci Sequence implementations

Calculating the Fibonacci Sequence is a common interview question and good exercise. Presenting: The wildest ways to calculate numbers of the Fibonacci Sequence on the web!

Jannes Mingram Jannes Mingram Jan 2, 2022 • 6 min read

You can try all the examples on this page directly in the development console of this page (F12).

Recursive Stairs. — Photo by Mario Mesaglio / Unsplash

JavaScript

Easy loop

let target = 10;
let c, a = 0, b = 1;
for(let i = 0; i < target; i++) {
  c = a, a = a + b, b = c;
}
console.log(a);

Easy loop using `BigInt`

let target = 10;
let a = 0n, b = 1n;
for(let i = 0; i < target; i++) {
  b = [a, a = a + b][0];
}
console.log(a);

Easy recursive

const fib = (x) => x < 3 ? 1 : fib(x - 1) + fib(x - 2);
console.log(fib(10));

With caching and `BigInt`

const cacheFn = fn => {
  const cache = {};
  return (cacheKey, ...rest) => {
    if(cache[cacheKey]) return cache[cacheKey];
    const result = fn(cacheKey, ...rest);
    cache[cacheKey] = result;
    return result;
  }
}

const fib = (x, fn) => x < 3 ? 1n : fn(x - 1, fn) + fn(x - 2, fn);
const cachedFib = cacheFn(fib);
console.log(cachedFib(10, cachedFib));

Tail-recursive

const fib = (t, a = 0n, b = 1n) => t < 0 ? b : fib(t - 1, a + b, a);
console.log(fib(10));

Tail-recursive using `BigInt`

const fib = (t, a = 0n, b = 1n) => t < 0 ? b : fib(t - 1, a + b, a);
console.log(fib(10));

Fast doubling

✔️

Really fast
Use this method for big n

function fib(q) {
    if(q == 0) return [0n, 1n];
    const [a, b] = fib(Math.floor(n / 2));
    const c = a * (b * 2n - a);
    const d = a * a + b * b;
    if(q % 2 == 0) return [c, d];
    return [d, c + d];
}
console.log(fib(10)[0]);

Tuple based

const [a, b] = Array.from({ length: 10 }).reduce(([a, b]) => [a + b, a], [1n, 0n]);
console.log(b)

List-based

Get all Fibonacci numbers in a list.

Array.from({ length: 10 }).reduce(([b, a, ...rest]) => [b + a, b, a, ...rest], [1n, 0n]);

Fills the initial array with Fibonacci numbers

Generator

Get the next Fibonacci number.

function* fibgen() {
  let n = [0n, 1n];
  while(true) {
    n = [n[0] + n [1], n[0]];
    yield n[0];
  }
}
const gen = fibgen();
gen.next().value;
gen.next().value;
// ... generates a new fib-number

Call gen.next().value 10 times to get the 10th value

Tail-recursive generator

Get the next Fibonacci number.

function* fibgen(a = 0, b = 1) {
  yield b;
  yield* fibgen(b, a+b);
}
const gen = fibgen();
gen.next().value;
gen.next().value;
// ... generates a new fib-number

Call gen.next().value 10 times to get the 10th value

Fast doubling generator

✔️

Suitable for large n

function* fib(q, depth=0) {
    if(q == 0) return [0n, 1n];
    const [a, b] = yield* fib(Math.floor(q / 2), depth+1);
    const c = a * (b * 2n - a);
    const d = a * a + b * b;
    yield depth;
    if(q % 2 == 0) return [c, d];
    return [d, c + d];
}
const n = 10;
const gen = fib(n);
const fn = () => {
    const {done, value} = gen.next();
    if(done) { clearTimeout(timeout); return console.log(n < 1000000 ? value[0] : "Yay"); }
    console.log("Depth", value)
    timeout = setTimeout(fn, 1)
};
let timeout = setTimeout(fn, 1)

⚠️

For larger n, do not log the return value to console
Printing the value to the console takes longer than the entire calculation of it!

A needle acting as a prism. — Photo by John Anvik / Unsplash

Multithreaded

Simple web worker

const script = "self.onmessage=function(e){postMessage({ a: e.data.a + e.data.b, b: e.data.a });}";
const blob = new Blob([script], {type: 'application/javascript'});
const worker = new Worker(URL.createObjectURL(blob));
const calculatestep = ({ a, b }) => new Promise(res => {
	worker.onmessage = function(e) {
    	worker.onmessage = null;
    	res({ a: e.data.a, b: e.data.b });
	};
	worker.postMessage({ a, b });
});

let target = 10;
let a = 0, b = 1;
for(let i = 0; i < target; i++) {
  const r = await calculatestep({ a, b })
  a = r.a, b = r.b;
}
console.log(a);

Perform calculations in a web worker

Recursive web workers

⚠️

Bigger n will crash your browser tab!
This is due to the high number of threads spawned.

const script = `self.onmessage=async function(e){
    const { n, a, b, blob } = e.data;
    if(n < 0) return postMessage(b);
    
    const worker = new Worker(URL.createObjectURL(blob));
    worker.onmessage = function(e) {
        worker.onmessage = null;
        postMessage(e.data);
    };
    worker.postMessage({ n: n - 1, a: a+b, b: a, blob });
}`;

const n = 10, a = 0, b = 1;
const blob = new Blob([script], {type: 'application/javascript'});
const worker = new Worker(URL.createObjectURL(blob));
worker.onmessage = function(e) {
	worker.onmessage = null;
	console.log(e.data)
};
worker.postMessage({ n, a, b, blob });

This method creates one web worker per recursion level.

Having a seat on the swing of life —
Start to see the world
in the colors you choose. — Photo by Simon Berger / Unsplash

CSS

html {
    --fiba: 1;
    --fibb: 1;
}
.fib {
    --na: calc(var(--fiba) + var(--fibb));
    --nb: var(--fiba);
    counter-increment: listCounter;
}
.fibn {
    --fiba: var(--na);
    --fibb: var(--nb);
}
.fib.result::before {
    counter-reset: fib var(--fibb);
    content: counter(listCounter) 'th Fibonacci number:' counter(fib);
    font-size: smaller;
}

Note: The counter-reset is a 'hack' to display the value of the CSS custom property

<div class="fib"><div class="fibn"><div class="fib"><div class="fibn"><div class="fib"><div class="fibn"><div class="fib"><div class="fibn"><div class="fib"><div class="fibn"><div class="fib"><div class="fibn"><div class="fib"><div class="fibn"><div class="fib"><div class="fibn"><div class="fib"><div class="fibn"><div class="fib result"><div class="fibn"></div></div></div></div></div></div></div></div></div></div></div></div></div></div></div></div></div></div></div></div>

Note: There are 10 div.fib to calculate the 10th number

Web Assembly

Rust

❔

This method will overflow without warning for large n!

use wasm_bindgen::prelude::*;

#[wasm_bindgen]
pub fn fibonacci(n: u64, a: u64, b: u64) -> u64 {
    match n {
        1 => a,
        _ => fibonacci(n - 1, a + b, a),
    }
}

Compile with wasm-pack build --target web

const fibmod = await import("https://jannes.mingram.net/content/files/2022/01/fib_wasm.js");
fibmod.default().then(() => console.log(fibmod.fibonacci(10n, 1n, 0n)) );

Download the compiled files and source below

Rust with BigInt

use num_bigint::BigUint;
use num_traits::{Zero, One};
use std::mem::replace;
use wasm_bindgen::prelude::*;


#[wasm_bindgen]
pub fn bigfib(n: u64) -> String {
    let mut f0: BigUint = Zero::zero();
    let mut f1: BigUint = One::one();
    for _ in 0..n {
        let f2 = f0 + &f1;
        f0 = replace(&mut f1, f2);
    }
    f0.to_str_radix(10)
}

Compile with wasm-pack build --target web

const fibmod = await import("https://jannes.mingram.net/content/files/2022/01/fib_wasm.js");
fibmod.default().then(() => console.log(fibmod.bigfib(10n)) );

Download the compiled files and source above

Papers. Writer. Businessman. manege and manager. Student.
It would be nice if you can support my Instagram https://www.instagram.com/tanywu4ka/
@tanywu4ka — Photo by Tetiana Shyshkina / Unsplash

Collection of Fibonacci Sequence implementations

JavaScript

Easy loop

Easy loop using `BigInt`

Easy recursive

With caching and `BigInt`

Tail-recursive

Tail-recursive using `BigInt`

Fast doubling

Tuple based

List-based

Generator

Tail-recursive generator

Fast doubling generator

Multithreaded

Simple web worker

Recursive web workers

CSS

Web Assembly

Rust

Rust with BigInt

Self-referencing 1-1 rel. integrity in PostgreSQL

Multi-tenant nginx server

Integrating React into any existing system

Theme demo

JavaScript

Easy loop

Easy loop using BigInt

Easy recursive

With caching and BigInt

Tail-recursive

Tail-recursive using BigInt

Fast doubling

Tuple based

List-based

Generator

Tail-recursive generator

Fast doubling generator

Multithreaded

Simple web worker

Recursive web workers

CSS

Web Assembly

Rust

Rust with BigInt

Subscribe!

Easy loop using `BigInt`

With caching and `BigInt`

Tail-recursive using `BigInt`