Fibonacci Generators

fibonacci_unabridged.js

////// Fun with ES2015 Generators & Fibonacci Sequence //////
//
// Generators are awesome for lazy calculations, but they're less 
// than ideal for certain use-cases (give me the result of the
// 1000th iteration).
//
// This is an experiment where I try to have my cake and eat it too, 
// by wrapping a generator with a factory function.
//
//// Note: This is the annotated version!
//// Too verbose? The straight dope is available here:
//// https://gist.github.com/joshwcomeau/41d8a8b7682bf1b6c6378c143031d9e8


function* fibonacciGenerator() {
  // Start with the first two numbers in the sequence.
  let previous = 0, current = 1;
  
  // Generators pause at `yield`, so this seemingly monstrous 
  // loop is actually an acceptable practice!
  while (true) {
    // Use nifty array deconstruction to juggle the variables.
    // Our `current` number is reassigned to the `previous` number,
    // and we assign the sum of the two numbers to `current`.
    [previous, current] = [current, previous + current];
    
    // Yield! This terminates this iteration of the generator,
    // but the state is not lost. On the next invocation, we'll
    // restart from the top of the `while` loop.
    yield(current);
  }
}

// If we wanted to, we could use the generator function directly,
// but it's only really good at one thing: getting the next number
// in the sequence. If I want to get a previous number, I need to
// start from the beginning and invoke the generator until I hit it.
//
// Let's create a fibonacci factory - a thin wrapper around the
// generator, with one key improvement: It maintains an internal 
// record of the numbers generated, so it can efficiently return 
// numbers it's already computed.
function fibonacciFactory(n = 1) {
  const generator = fibonacciGenerator();
  
  // This array will hold the fibonacci sequence, as high as it's been
  // computed. Setting the first value to null, because arrays are 0-
  // indexed. If someone asks for the 0th number in the fibonacci
  // sequence, it should return null.
  const sequence = [null];

  // Return the function that will be used to request numbers.
  return (n = 1) => {
    // The body of this function is pretty straightforward.
    //
    // sequence[n] is either our answer, or `undefined` because we
    // haven't generated that high yet.
    // 
    // If it's undefined, keep generating numbers until we hit it!
    while (typeof sequence[n] === 'undefined') {
      sequence.push(generator.next().value);
    }
    
    return sequence[n]
  }
}

// // Wanna test it? Uncomment these lines:
// const fibonacci = fibonacciFactory();
//
// console.log(fibonacci());  // -> 1
// console.log(fibonacci(7)); // -> 21
// console.log(fibonacci(4)); // -> 5
// console.log(fibonacci(9)); // -> 55


////////////////// Test! //////////////////


// I'm curious how much more efficient this actually is.
// Let's grab the 1000th number in the sequence, a few times in a row.

// First, the vanilla generator way
const t1Start = performance.now();
const t1Generator = fibonacciGenerator();

for (let i = 0; i < 25; i++) {
  let sequenceNum = 0;
  while (sequenceNum <= 1000) {
    t1Generator.next();
    sequenceNum++;
  }
}

const t1Time = performance.now() - t1Start;


// Then, the factory way
const t2Start = performance.now();
const t2Factory = fibonacciFactory();

for (let i = 0; i < 25; i++) {
  fibonacciFactory(1000);
}

const t2Time = performance.now() - t2Start;

// Let's log out the (unsurprising) results:
console.log(`Generator took ${t1Time}ms`); // ~10-20ms
console.log(`Factory took ${t2Time}ms`);   // 0.01 - 0.2ms


// Caveats:
// This is a purely academic endeavour. I don't think it's super
// practical to use generators this way (their whole benefit is
// being able to pause execution and evaluate lazily, and I've
// abstracted that benefit away!).