Fibonacci (iterative, recursive, memoized)

fib.c

#include <stdlib.h>
#include <stdio.h>
#include <time.h>

int fibI(int n) {
  int result = 0;
  int a = 0;
  int b = 1;
  for (int i = 2; i <= n; i++) {
    result = a + b;
    a = b;
    b = result;
  }
  return result;
}

int *memo;

int fibM(int n) {
  if (n < 2) {
    return n;
  }
  if (memo[n - 1] != 0) {
    return memo[n - 1];
  }
  int result = fibM(n - 1) + fibM(n - 2);
  memo[n - 1] = result;
  return result;
}

int fibR(int n) {
  if (n < 2) {
    return n;
  }
  return fibR(n - 1) + fibR(n - 2);
}

int main(int argc, char **argv) {
  int result = 0;
  int num = atoi(argv[1]);
  char opt = argv[2][0];

  clock_t begin = clock();
  switch (opt) {
    case 'r':
      printf("recursive fib:\n");
      result = fibR(num);
      break;
    case 'm':
      printf("memoized recursive fib:\n");
      memo = (int*)malloc(num*sizeof(int));
      result = fibM(num);
      free(memo);
      break;
    case 'i':
      printf("iterative fib:\n");
      result = fibI(num);
      break;
    default:
      printf("invalid Arg: use r, m, i\n");
  }
  clock_t end = clock();

  if (result != 0) {
    printf("Result: %d\n", result);
  }

  double time_spent = (double)(end - begin) / CLOCKS_PER_SEC;
  printf("%f\n", time_spent);

  return 0;
}

fib.go

package main

import (
	"fmt"
	"time"
)

// 0, 1, 1, 2, 3, 5 ...
// fib iterative
func fibI(n int) int {
	result, a, b := 0, 0, 1
	for i := 2; i <= n; i++ {
		result = a + b
		a, b = b, result
	}
	return result
}

// fib recursive
func fibR(n int) int {
	if n < 2 {
		return n
	}
	return fibR(n-1) + fibR(n-2)
}

// memoed
var memo map[int]int = make(map[int]int)

func fibM(n int) int {
	if n < 2 {
		memo[n] = n
	}
	num, prs := memo[n]
	if !prs {
		num = fibM(n-1) + fibM(n-2)
		memo[n] = num
	}
	return num
}

func timer(start time.Time, name string) {
	elapsed := time.Since(start)
	fmt.Printf("%s took %s\n", name, elapsed)
}

func timeFunc(fn func(int) int, arg int, name string) {
	defer timer(time.Now(), name)
	fn(arg)
}

func main() {
	// println("iterative fib: ", fibI(20))
	// println("recursive fib: ", fibR(20))
	// println("recursive memoized fib: ", fibM(20))
	num := 60
	timeFunc(fibI, num, "iterative fib")
	// timeFunc(fibR, 40, "recursive fib")
	timeFunc(fibM, num, "recursive memoized fib")
}

fib.js

/**
 * Generate the nth number in the fibonacci sequence
 * write recursive, memoized, and iterative implementations
 * and a time the implementations
 * 
 * The Fibonacci sequence 0 1 1 2 3 5 8 13...
 */

function timeFn(fn, msg = 'function') {
  const start = process.hrtime()
  return function (...fnArgs) {
    const returnValue = fn.apply(null, fnArgs)
    const [seconds, nanoseconds] = process.hrtime(start)
    const diff = seconds * 1_000_000 + nanoseconds / 1000
    console.log(`${msg} took ${diff}µs`)
    return returnValue
  }
}

// base case fib(0) => 0 & fib(1) => 1
// fib(2) => fib(2 - 1) + fib(2 - 2)
function fibR(n) {
  if (n < 2) {
    return n
  }
  return fibR(n - 1) + fibR(n - 2)
}

const memo = new Map()

function fibM(n) {
  if (n < 2) {
    return n
  }
  if (memo.has(n)) {
    return memo.get(n)
  }
  const result = fibM(n - 1) + fibM(n - 2)
  memo.set(n, result)
  return result
}

// 0 => a, 1 => b, 2 => tmp = a + b, a = b, b = tmp
function fibI(n) {
  let [a, b] = [0, 1]
  let tmp = 0
  for (let i = 0; i <= n; i++) {
    if (i === 0) {
      tmp = a
      continue
    }
    if (i === 1) {
      tmp = b
      continue
    }
    tmp = a + b, a = b, b = tmp
  }
  return tmp
}

function main() {
  const n = 60
  // let result = timeFn(fibR, 'recursive fib')(n)
  // console.log(`fib of ${n} is ${result}`)
  // result = timeFn(fibM, 'recursive (memoized) fib')(n)
  let result = timeFn(fibM, 'recursive (memoized) fib')(n)
  console.log(`fib of ${n} is ${result}`)
  result = timeFn(fibI, 'iterative fib')(n)
  console.log(`fib of ${n} is ${result}`)
}

main()

fib_v2.c

#include <stdlib.h>
#include <stdio.h>
#include <time.h>

int fibI(int n) {
  int result = 0;
  int a = 0;
  int b = 1;
  for (int i = 2; i <= n; i++) {
    result = a + b;
    a = b;
    b = result;
  }
  return result;
}

int fibM(int n, int *memo) {
  if (n < 2) {
    return n;
  }
  if (memo[n - 1] != 0) {
    return memo[n - 1];
  }
  int result = fibM(n - 1, memo) + fibM(n - 2, memo);
  memo[n - 1] = result;
  return result;
}

int fibR(int n) {
  if (n < 2) {
    return n;
  }
  return fibR(n - 1) + fibR(n - 2);
}

void bench(int n, char *desc, int (*fn)(int), int arg) {
  printf("Benchmarking %s\n", desc);
  
  int64_t *results = (int64_t*)malloc(n*sizeof(int64_t));
  struct timespec start, end;
  u_int64_t before_ns, after_ns;

  for (int i = 0; i < n; i++) {
    clock_gettime(CLOCK_MONOTONIC, &start);
    fn(arg);
    clock_gettime(CLOCK_MONOTONIC, &end);

    before_ns = (start.tv_sec * 1000000000LL) + start.tv_nsec;
    after_ns = (end.tv_sec * 1000000000LL) + end.tv_nsec;
    results[i] = after_ns - before_ns;
  }

  int64_t sum = 0;
  for (int i = 0; i < n; i++) {
    sum += results[i];
  }
  double avg = sum / n;
  printf("Average time: %.2fns\n", avg);
  free(results);
}

int fib_memo(int n) {
  int *memo = (int*)calloc(n, sizeof(int));
  int result = fibM(n, memo);
  free(memo);
  return result;
}

int main(int argc, char **argv) {
  int n = 1000000;
  int num = 40;

  // bench(n, "recursive fib", fibR, num);
  bench(n, "iterative fib", fibI, num);
  bench(n, "memoized fib", fib_memo, num);

  return 0;
}

fib_v2.go

package main

import (
	"fmt"
	"time"
)

// 0, 1, 1, 2, 3, 5 ...
// fib iterative
func fibI(n int) int {
	next, prev, curr := 0, 0, 1

	for i := 2; i <= n; i++ {
		next = prev + curr
		prev, curr = curr, next
	}

	return next
}

// fib recursive
func fibR(n int) int {
	if n < 2 {
		return n
	}

	return fibR(n-1) + fibR(n-2)
}

// fib memoized
func fibM(n int, cache []int) int {
	if n < 2 {
		return n
	}

	if cache[n-1] != 0 {
		return cache[n-1]
	}

	num := fibM(n-1, cache) + fibM(n-2, cache)
	cache[n-1] = num
	return num
}

func fibMemo(n int) int {
	cache := make([]int, n)
	return fibM(n, cache)
}

func bench(n int, desc string, fn func(int) int, arg int) {
	fmt.Printf("Benchmarking %s\n", desc)
	results := make([]time.Duration, n)

	for i := 0; i < n; i++ {
		start := time.Now()
		fn(arg)
		results = append(results, time.Since(start))
	}

	var sum time.Duration = 0
	for _, v := range results {
		sum += v
	}

	var mean time.Duration = sum / time.Duration(n)
	fmt.Printf("Average time: %s\n", mean)
}

func main() {
	num := 40
	n := 10_000_000

	// bench(n, "recursive fib", fibR, num)
	bench(n, "iterative", fibI, num)
	bench(n, "recursive memoized", fibMemo, num)

}

main.rs

use std::time::Instant;

fn fib_iter(n: u64) -> u64 {
    let (mut next, mut prev, mut curr) = (0, 0, 1);

    for _ in 2..=n {
        next = prev + curr;
        prev = curr;
        curr = next;
    }

    next
}

fn fib_recur(n: u64) -> u64 {
    if n < 2 {
        return n;
    }

    fib_recur(n - 1) + fib_recur(n - 2)
}

fn fib_memo(n: u64, cache: &mut Vec<u64>) -> u64 {
    if n < 2 {
        return n;
    }

    if let Some(&result) = cache.get(n as usize) {
        return result;
    }
    
    let result = fib_memo(n - 1, cache) + fib_memo(n - 2, cache);
    cache.push(result);
    result
}

fn memo(n: u64) -> u64 {
    let mut cache = Vec::with_capacity(n as usize);
    cache.push(0);
    cache.push(1);
    fib_memo(n, &mut cache)
}

fn bench(n: u32, desc: &str, f: fn(u64) -> u64, arg: u64) {
    println!("Benchmarking {}", desc);
    let mut results = Vec::with_capacity(n as usize);
    for _ in 0..n {
        let t = Instant::now();
        f(arg);
        let d = t.elapsed().as_nanos();
        results.push(d);
    }
    let sum: u128 = results.iter().sum();
    let avg = sum / n as u128;
    println!("Average time: {} ns", avg);
}

fn main() {
    let num = 40;
    let n = 10_000_000;
    // bench(10, "recursive", fib_recur, num);
    bench(n, "iterative", fib_iter, num);
    bench(n, "memoized", memo, num);
}

Results.md

JS vs Go vs C fib

Running on MacBook Air (M1, 2020) with 16 GB of RAM.

gcc fib.c -O2

n = 40

result = 102334155

Language	recursive	memoized	iterative
Javascript	1389.67ms	26.33µs	23.54µs
Go	532.82ms	20.92µs	21.17µs
C	340.91ms	60.00µs	26.00µs
Go v2	339.71ms	192ns	20ns
C v2	340.91ms	118ns	31ns
Rust	309 ms	234ns	20ns

n = 60

result = 1548008755920

Language	recursive	memoized	iterative
Javascript	n/a	43.79µs	29.21µs
Go	n/a	31.54µs	20.58µs
C	n/a	45.00µs	24.00µs

better impl in Go:

package main

import (
	"fmt"
	"time"
)

// 0, 1, 1, 2, 3, 5 ...
// fib iterative
func fibI(n int) int {
	result, a, b := 0, 0, 1
	for i := 2; i <= n; i++ {
		result = a + b
		a, b = b, result
	}
	return result
}

// fib recursive
func fibR(n int) int {
	if n < 2 {
		return n
	}
	return fibR(n-1) + fibR(n-2)
}

// memoed
func fibM(n int, memo map[int]int) int {
	if n < 2 {
		memo[n] = n
	}
	num, prs := memo[n]
	if !prs {
		num = fibM(n-1, memo) + fibM(n-2, memo)
		memo[n] = num
	}
	return num
}

func fibMemoV2(n int, cache []int) int {
	if n < 2 {
		return n
	}
	if i := cache[n]; n != 0 && i != 0 {
		return cache[n]
	}
	num := fibMemoV2(n-1, cache) + fibMemoV2(n-2, cache)
	cache[n] = num
	return num
}

func timer(start time.Time, name string) {
	elapsed := time.Since(start)
	fmt.Printf("%s took %s\n", name, elapsed)
}

func timeFunc(fn func(int) int, arg int, name string) {
	defer timer(time.Now(), name)
	fn(arg)
}

func memoV2(n int) int {
	cache := make([]int, n)
	cache = append(cache, 0, 1)
	return fibMemoV2(n, cache)
}

func memoV1(n int) int {
	var memo map[int]int = make(map[int]int, n)
	return fibM(n, memo)
}

func bench(n int, desc string, fn func(int) int, arg int) {
	fmt.Printf("Benchmarking %s\n", desc)
	results := make([]time.Duration, n)
	for i := 0; i < n; i++ {
		start := time.Now()
		fn(arg)
		results = append(results, time.Since(start))
	}
	var sum time.Duration = 0
	for _, v := range results {
		sum += v
	}
	var mean time.Duration = sum / time.Duration(n)
	fmt.Printf("Average time: %s\n", mean)
}

func main() {
	num := 40
	n := 1_000_000

	// bench(n, "recursive fib", fibR, num)
	bench(n, "recursive memoized fib", memoV1, num)
	bench(n, "iterative fib", fibI, num)
	bench(n, "recursive memoized fib v2", memoV2, num)
}

Better C:

#include <stdlib.h>
#include <stdio.h>
#include <time.h>

int fibI(int n) {
  int result = 0;
  int a = 0;
  int b = 1;
  for (int i = 2; i <= n; i++) {
    result = a + b;
    a = b;
    b = result;
  }
  return result;
}

int fibM(int n, int *memo) {
  if (n < 2) {
    return n;
  }
  if (memo[n - 1] != 0) {
    return memo[n - 1];
  }
  int result = fibM(n - 1, memo) + fibM(n - 2, memo);
  memo[n - 1] = result;
  return result;
}

int fibR(int n) {
  if (n < 2) {
    return n;
  }
  return fibR(n - 1) + fibR(n - 2);
}

void bench(int n, char *desc, int (*fn)(int), int arg) {
  printf("Benchmarking %s\n", desc);
  
  int64_t *results = (int64_t*)malloc(n*sizeof(int64_t));
  struct timespec start, end;
  u_int64_t before_ns, after_ns;

  for (int i = 0; i < n; i++) {
    clock_gettime(CLOCK_MONOTONIC, &start);
    fn(arg);
    clock_gettime(CLOCK_MONOTONIC, &end);

    before_ns = (start.tv_sec * 1000000000LL) + start.tv_nsec;
    after_ns = (end.tv_sec * 1000000000LL) + end.tv_nsec;
    results[i] = after_ns - before_ns;
  }

  int64_t sum = 0;
  for (int i = 0; i < n; i++) {
    sum += results[i];
  }
  double avg = sum / n;
  printf("Average time: %.2fns\n", avg);
  free(results);
}

int fib_memo(int n) {
  int *memo = (int*)calloc(n, sizeof(int));
  int result = fibM(n, memo);
  free(memo);
  return result;
}

int main(int argc, char **argv) {
  int n = 1000000;
  int num = 40;

  // bench(n, "recursive fib", fibR, num);
  bench(n, "iterative fib", fibI, num);
  bench(n, "memoized fib", fib_memo, num);

  return 0;
}