Last active
February 9, 2018 22:19
-
-
Save martinsson/fff10fdbc05966b8d919b96791ca5fdc to your computer and use it in GitHub Desktop.
Algorithm for generating fibonacci numbers, javascript is not that slow after all
This file contains hidden or bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
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]; | |
} | |
This file contains hidden or bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
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) | |
}); | |
}); |
This file contains hidden or bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
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