Skip to content

Instantly share code, notes, and snippets.

@martinsson
Last active February 9, 2018 22:19
Show Gist options
  • Save martinsson/fff10fdbc05966b8d919b96791ca5fdc to your computer and use it in GitHub Desktop.
Save martinsson/fff10fdbc05966b8d919b96791ca5fdc to your computer and use it in GitHub Desktop.
Algorithm for generating fibonacci numbers, javascript is not that slow after all
import * as _ from 'lodash'
function sumPreviousTwo(numbers: number[]) {
let [n2, n1] = _.takeRight(numbers, 2);
return n2 + n1;
}
export function fibonacci(length: number): number {
let firstTwoNumbers = [0, 1];
let numbers = firstTwoNumbers;
let remainingLength = length - firstTwoNumbers.length;
_.times(remainingLength, () => numbers.push(sumPreviousTwo(numbers)));
return numbers[length-1];
}
import {assert} from "chai";
import {fibonacci} from "../src/Fibonacci";
describe('Fibonacci', () => {
it('first number is 0', () => {
assert.deepEqual(fibonacci(1), 0);
});
it('the second number is 1', () => {
assert.deepEqual(fibonacci(2), 1);
});
it('the third number is 1', () => {
assert.deepEqual(fibonacci(3), 1);
});
it('acceptance test', () => {
assert.deepEqual(fibonacci(9), 21);
});
it('scales, it takes a few ms to calculate the 1477th, which is ~ 1.3e+308!', () => {
assert.equal(fibonacci(1477), 1.3069892237633987e+308)
});
});
Fibonacci
✓ first number is 0 (1ms)
✓ the second number is 1
✓ the third number is 1
✓ acceptance test
✓ scales, it takes a few ms to calculate the 1477th, which is ~ 1.3e+308! (2ms)
5 passing (4ms)
the perf test varies between 1-2 milliseconds measured with hrtime. Seems suspiciously fast.
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment