var x = 0;
var y = 1;
var z;
fib[0] = 0;
fib[1] = 1;
for (i = 2; i <= 10; i++) {
alert(x + y);
fib[i] = x + y;
x = y;
z = y;
}
I'm trying to get to generate a simple Fibonacci Sequence but there no output.
Can anybody let me know what's wrong?
This question is related to
javascript
fibonacci
I like the fact that there are so many ways to create a fibonacci sequence in JS. I will try to reproduce a few of them. The goal is to output a sequence to console (like {n: 6, fiboNum: 8}
)
// The IIFE form is purposefully omitted. See below._x000D_
_x000D_
const fiboGenClosure = () => {_x000D_
let [a, b] = [0, 1];_x000D_
let n = 0;_x000D_
return (fiboNum = a) => {_x000D_
[a, b] = [b, a + b];_x000D_
return {_x000D_
n: n++,_x000D_
fiboNum: fiboNum_x000D_
};_x000D_
};_x000D_
}_x000D_
_x000D_
// Gets the sequence until given nth number. Always returns a new copy of the main function, so it is possible to generate multiple independent sequences._x000D_
_x000D_
const generateFiboClosure = n => {_x000D_
const newSequence = fiboGenClosure();_x000D_
for (let i = 0; i <= n; i++) {_x000D_
console.log(newSequence());_x000D_
}_x000D_
}_x000D_
_x000D_
generateFiboClosure(21);
_x000D_
Similar to the closure pattern above, using the advantages of generator function and for..of loop.
// The 'n' argument is a substitute for index._x000D_
_x000D_
function* fiboGen(n = 0) {_x000D_
let [a, b] = [0, 1];_x000D_
while (true) {_x000D_
yield [a, n++];_x000D_
[a, b] = [b, a + b];_x000D_
}_x000D_
}_x000D_
_x000D_
// Also gives a new sequence every time is invoked._x000D_
_x000D_
const generateFibonacci = n => {_x000D_
const iterator = fiboGen();_x000D_
for (let [value, index] of iterator) {_x000D_
console.log({_x000D_
n: index,_x000D_
fiboNum: value_x000D_
});_x000D_
if (index >= n) break;_x000D_
}_x000D_
}_x000D_
_x000D_
generateFibonacci(21);
_x000D_
This one is a little tricky, because, now in late 2018, TC optimization is still an issue. But honestly – if you don't use any smart tricks to allow the default JS engine to use a really big numbers, it will get dizzy and claims that the next fibonacci number is "Infinity" by iteration 1477. The stack would probably overflow somewhere around iteration 10 000 (vastly depends on browser, memory etc…). Could be probably padded by try… catch block or check if "Infinity" was reached.
const fibonacciRTC = (n, i = 0, a = 0, b = 1) => {_x000D_
console.log({_x000D_
n: i,_x000D_
fibonacci: a_x000D_
});_x000D_
if (n === 0) return;_x000D_
return fibonacciRTC(--n, ++i, b, a + b);_x000D_
}_x000D_
_x000D_
fibonacciRTC(21)
_x000D_
It can be written as a one-liner, if we throe away the console.log
thing and simply return a number:
const fibonacciRTC2 = (n, a = 0, b = 1) => n === 0 ? a : fibonacciRTC2(n - 1, b, a + b);_x000D_
_x000D_
console.log(fibonacciRTC2(21))
_x000D_
As I found out reading this mathIsFun article, the fibonacci sequence is valid for negative numbers as well! I tried to implement that in the recursive tail call form above like that:
const fibonacciRTC3 = (n, a = 0, b = 1, sign = n >= 0 ? 1 : -1) => { _x000D_
if (n === 0) return a * sign;_x000D_
return fibonacciRTC3(n - sign, b, a + b, sign);_x000D_
}_x000D_
_x000D_
console.log(fibonacciRTC3(8)); // 21_x000D_
console.log(fibonacciRTC3(-8)); // -21
_x000D_
function fib(n) {
if (n <= 1) {
return n;
} else {
return fib(n - 1) + fib(n - 2);
}
}
fib(10); // returns 55
I think this one is simple enough to understand:
function fibonacci(limit) {
let result = [0, 1];
for (var i = 2; i < limit; i++) {
result[result.length] = result[result.length - 1] + result[result.length - 2];
}
return result;
}
// [0, 1, 1, 2, 3, 5, 8, 13, 21, 34]
console.log(fibonacci(10));
Another easy way to achieve this:
function listFibonacci(n) {
// declare the array starting with the first 2 values of the fibonacci sequence
// starting at array index 1, and push current index + previous index to the array
for (var fibonacci = [0, 1], i = 1; i < n; i++)
fibonacci.push(fibonacci[i] + fibonacci[i - 1])
return fibonacci
}
console.log( listFibonacci(10) )
_x000D_
My 2 cents:
function fibonacci(num) {_x000D_
return Array.apply(null, Array(num)).reduce(function(acc, curr, idx) {_x000D_
return idx > 2 ? acc.concat(acc[idx-1] + acc[idx-2]) : acc;_x000D_
}, [0, 1, 1]);_x000D_
}_x000D_
_x000D_
console.log(fibonacci(10));
_x000D_
// using recursive approach and in one line
const fib = x => (x <= 1)? x : fib (x - 1) + fib(x -2);
fib(15); // 610
// display the 15 first
Array.from({ length: 15 }, (v, i) => fib(i));
// [0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, 233, 377]
// using memoization approach
function fibonacci(num, memo) {
memo = memo || {};
if (memo[num]) return memo[num];
if (num === 0) return 0;
if (num === 1) return 1;
return memo[num] = fibonacci(num - 1, memo) + fibonacci(num - 2, memo);
}
fibonacci(15); // 610
// display the 15 first
Array.from({ length: 15 }, (v, i) => fibonacci(i));
// [0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, 233, 377]
You Could Try This Fibonacci Solution Here
var a = 0;
console.log(a);
var b = 1;
console.log(b);
var c;
for (i = 0; i < 3; i++) {
c = a + b;
console.log(c);
a = b + c;
console.log(a);
b = c + a;
console.log(b);
}
<!DOCTYPE HTML PUBLIC "-//W3C//DTD HTML 4.01//EN" "http://www.w3.org/TR/html4/strict.dtd">
<html>
<head>
<meta http-equiv="Content-Type" content="text/html; charset=iso-8859-1">
<title>fibonacci series</title>
<script type="text/javascript">
function generateseries(){
var fno = document.getElementById("firstno").value;
var sno = document.getElementById("secondno").value;
var a = parseInt(fno);
var result = new Array();
result[0] = a;
var b = ++fno;
var c = b;
while (b <= sno) {
result.push(c);
document.getElementById("maindiv").innerHTML = "Fibonacci Series between "+fno+ " and " +sno+ " is " +result;
c = a + b;
a = b;
b = c;
}
}
function numeric(evt){
var theEvent = evt || window.event;
var key = theEvent.keyCode || theEvent.which;
key = String.fromCharCode(key);
var regex = /[0-9]|\./;
if (!regex.test(key)) {
theEvent.returnValue = false;
if (theEvent.preventDefault)
theEvent.preventDefault();
}
}
</script>
<h1 align="center">Fibonacci Series</h1>
</head>
<body>
<div id="resultdiv" align="center">
<input type="text" name="firstno" id="firstno" onkeypress="numeric(event)"><br>
<input type="text" name="secondno" id="secondno" onkeypress="numeric(event)"><br>
<input type="button" id="result" value="Result" onclick="generateseries();">
<div id="maindiv"></div>
</div>
</body>
</html>
The golden ration "phi" ^ n / sqrt(5) is asymptotic to the fibonacci of n, if we round that value up, we indeed get the fibonacci value.
function fib(n) {
let phi = (1 + Math.sqrt(5))/2;
let asymp = Math.pow(phi, n) / Math.sqrt(5);
return Math.round(asymp);
}
fib(1000); // 4.346655768693734e+208 in just 0.62s
This runs faster on large numbers compared to the recursion based solutions.
Here is a function that displays a generated Fibonacci sequence in full while using recursion:
function fibonacci (n, length) {
if (n < 2) {
return [1];
}
if (n < 3) {
return [1, 1];
}
let a = fibonacci(n - 1);
a.push(a[n - 2] + a[n - 3]);
return (a.length === length)
? a.map(val => console.log(val))
: a;
};
The output for fibonacci(5, 5)
will be:
1
1
2
3
5
The value that is assigned to a
is the returned value of the fibonacci
function. On the following line, the next value of the fibonacci sequence is calculated and pushed to the end of the a
array.
The length
parameter of the fibonacci
function is used to compare the length of the sequence that is the a
array and must be the same as n
parameter. When the length of the sequence matches the length parameter, the a
array is outputted to the console, otherwise the function returns the a
array and repeats.
This script will take a number as parameter, that you want your Fibonacci sequence to go.
function calculateFib(num) {
var fibArray = [];
var counter = 0;
if (fibArray.length == 0) {
fibArray.push(
counter
);
counter++
};
fibArray.push(fibArray[fibArray.length - 1] + counter);
do {
var lastIndex = fibArray[fibArray.length - 1];
var snLastIndex = fibArray[fibArray.length - 2];
if (lastIndex + snLastIndex < num) {
fibArray.push(lastIndex + snLastIndex);
}
} while (lastIndex + snLastIndex < num);
return fibArray;
};
Here are examples how to write fibonacci using recursion, generator and reduce.
'use strict'_x000D_
_x000D_
//------------- using recursion ------------_x000D_
function fibonacciRecursion(n) {_x000D_
return (n < 2) ? n : fibonacciRecursion(n - 2) + fibonacciRecursion(n - 1)_x000D_
}_x000D_
_x000D_
// usage_x000D_
for (let i = 0; i < 10; i++) {_x000D_
console.log(fibonacciRecursion(i))_x000D_
}_x000D_
_x000D_
_x000D_
//-------------- using generator -----------------_x000D_
function* fibonacciGenerator() {_x000D_
let a = 1,_x000D_
b = 0_x000D_
while (true) {_x000D_
yield b;_x000D_
[a, b] = [b, a + b]_x000D_
}_x000D_
}_x000D_
_x000D_
// usage_x000D_
const gen = fibonacciGenerator()_x000D_
for (let i = 0; i < 10; i++) {_x000D_
console.log(gen.next().value)_x000D_
}_x000D_
_x000D_
//------------- using reduce ---------------------_x000D_
function fibonacciReduce(n) {_x000D_
return new Array(n).fill(0)_x000D_
.reduce((prev, curr) => ([prev[0], prev[1]] = [prev[1], prev[0] + prev[1]], prev), [0, 1])[0]_x000D_
}_x000D_
_x000D_
// usage_x000D_
for (let i = 0; i < 10; i++) {_x000D_
console.log(fibonacciReduce(i))_x000D_
}
_x000D_
Here's a simple function to iterate the Fibonacci sequence into an array using arguments in the for
function more than the body of the loop:
fib = function(numMax){
for(var fibArray = [0,1], i=0,j=1,k=0; k<numMax;i=j,j=x,k++ ){
x=i+j;
fibArray.push(x);
}
console.log(fibArray);
}
fib(10)
[ 0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89 ]
You can use recursion and cache the results in a functional way.
const fibonacci = (n, cache = {1: 1, 2: 1}) =>_x000D_
cache[n] || (cache[n] = fibonacci(--n, cache) + fibonacci(--n, cache));_x000D_
_x000D_
console.log(fibonacci(1000));_x000D_
console.log(fibonacci(100));_x000D_
console.log(fibonacci(10));
_x000D_
es6 - Symbol.iterator and generator functions:
let fibonacci = {
*[Symbol.iterator]() {
let pre = 0, cur = 1
for (;;) {
[ pre, cur ] = [ cur, pre + cur ]
yield cur
}
}
}
for (let n of fibonacci) {
if (n > 1000)
break
console.log(n)
}
Beginner, not too elegant, but shows the basic steps and deductions in JavaScript
/* Array Four Million Numbers */
var j = [];
var x = [1,2];
var even = [];
for (var i = 1;i<4000001;i++){
j.push(i);
}
// Array Even Million
i = 1;
while (i<4000001){
var k = j[i] + j[i-1];
j[i + 1] = k;
if (k < 4000001){
x.push(k);
}
i++;
}
var total = 0;
for (w in x){
if (x[w] %2 === 0){
even.push(x[w]);
}
}
for (num in even){
total += even[num];
}
console.log(x);
console.log(even);
console.log(total);
You can refer to below simple recursive function.
function fib(n){
if (n <= 2) return 1;
return fib(n-1) + fib(n-2);
}
console.log(fib(10)) //55 // Pass on any value to get fibonacci of.
There is no need for slow loops, generators or recursive functions (with or without caching). Here is a fast one-liner using Array
and reduce
.
ECMAScript 6:
var fibonacci=(n)=>Array(n).fill().reduce((a,b,c)=>a.concat(c<2?c:a[c-1]+a[c-2]),[])
ECMAScript 5:
function fibonacci(n){
return Array.apply(null,{length:n}).reduce(function(a,b,c){return a.concat((c<2)?c:a[c-1]+a[c-2]);},[]);
}
Tested in Chrome 59 (Windows 10):
fibonacci(10); // 0 ms -> (10) [0, 1, 1, 2, 3, 5, 8, 13, 21, 34]
JavaScript can handle numbers up to 1476 before reaching Infinity
.
fibonacci(1476); // 11ms -> (1476) [0, 1, 1, 2, 3, 5, 8, 13, 21, 34, ...]
Here is another one with proper tail call.
The recursive inner fib
function can reuse the stack because everything is needed (the array of numbers) to produce the next number is passed in as an argument, no additional expressions to evaluate.
However tail call optimization introduced in ES2015.
Also one drawback is it gets the array length in every iteration (but only once) to generate the following number and getting the elements of the array upon their index (it is faster though than pop or splice or other array methods) but I did not performance tested the whole solution.
var fibonacci = function(len) {_x000D_
var fib = function(seq) {_x000D_
var seqLen = seq.length;_x000D_
if (seqLen === len) {_x000D_
return seq;_x000D_
} else {_x000D_
var curr = seq[seqLen - 1];_x000D_
var prev = seq[seqLen - 2];_x000D_
seq[seqLen] = curr + prev;_x000D_
return fib(seq);_x000D_
}_x000D_
}_x000D_
return len < 2 ? [0] : fib([0, 1]);_x000D_
}_x000D_
_x000D_
console.log(fibonacci(100));
_x000D_
If using ES2015
const fib = (n, prev = 0, current = 1) => n
? fib(--n, current, prev + current)
: prev + current
console.log( fib(10) )
_x000D_
There is also a generalization of Binet's formula for negative integers:
static float phi = (1.0f + sqrt(5.0f)) / 2.0f;
int generalized_binet_fib(int n) {
return round( (pow(phi, n) - cos(n * M_PI) * pow(phi, -n)) / sqrt(5.0f) );
}
...
for(int i = -10; i < 10; ++i)
printf("%i ", generalized_binet_fib(i));
A better option would be using recursion but the following example can help you to understand logic!
Edit: Correction, recursion will eventually exhaust system out of resources without archiving expected results. The following example it uses simple logic, and it can process very fast...
var sequence = [0,1];_x000D_
var range = 10;_x000D_
_x000D_
for(var i = 0; i < range-2; i++){_x000D_
sequence.push(sequence[i]+sequence[i+1]);_x000D_
}_x000D_
_x000D_
console.log(sequence);
_x000D_
I would like to add some more code as an answer :), Its never too late to code :P
function fibonacciRecursive(a, b, counter, len) {
if (counter <= len) {
console.log(a);
fibonacciRecursive(b, a + b, counter + 1, len);
}
}
fibonacciRecursive(0, 1, 1, 20);
Result
0 1 1 2 3 5 8 13 21 34 55 89 144 233 377 610 987 1597 2584 4181
var a = -1;
var b=0;
var temp =0;
var arry = [];
for(var i=1;i<100;i++){
temp = a+b;
a=b;
b=temp;
arry.push(b*-1);
}
console.log(arry);
ty @geeves for the catch, I replaced Math.floor
for Math.round
which seems to get it up to 76 where floating point issues come into play :/ ...
either way, I wouldn't want to be using recursion up and until that point.
/**_x000D_
* Binet Fibonacci number formula for determining_x000D_
* sequence values_x000D_
* @param {int} pos - the position in sequence to lookup_x000D_
* @returns {int} the Fibonacci value of sequence @pos_x000D_
*/_x000D_
_x000D_
var test = [0,1,1,2,3,5,8,13,21,34,55,89,144,233,377,610,987,1597,2584,4181,6765,10946,17711,28657,46368,75025,121393,196418,317811,514229,832040,1346269,2178309,3524578,5702887,9227465,14930352,24157817,39088169,63245986,102334155,165580141,267914296,433494437,701408733,1134903170,1836311903,2971215073,4807526976,7778742049,12586269025,20365011074,32951280099,53316291173,86267571272,139583862445,225851433717,365435296162,591286729879,956722026041,1548008755920,2504730781961,4052739537881,6557470319842,10610209857723,17167680177565,27777890035288,44945570212853,72723460248141,117669030460994,190392490709135,308061521170129,498454011879264,806515533049393,1304969544928657,2111485077978050,3416454622906707,5527939700884757,8944394323791464,14472334024676221,23416728348467685,37889062373143906,61305790721611591,99194853094755497,160500643816367088,259695496911122585,420196140727489673,679891637638612258,1100087778366101931,1779979416004714189,2880067194370816120,4660046610375530309,7540113804746346429,12200160415121876738,19740274219868223167,31940434634990099905,51680708854858323072,83621143489848422977,135301852344706746049,218922995834555169026];_x000D_
var fib = function (pos) {_x000D_
return Math.round((Math.pow( 1 + Math.sqrt(5), pos) _x000D_
- Math.pow( 1 - Math.sqrt(5), pos)) _x000D_
/ (Math.pow(2, pos) * Math.sqrt(5)));_x000D_
};_x000D_
_x000D_
/* This is only for the test */_x000D_
var max = test.length,_x000D_
i = 0,_x000D_
frag = document.createDocumentFragment(),_x000D_
_div = document.createElement('div'),_x000D_
_text = document.createTextNode(''),_x000D_
div,_x000D_
text,_x000D_
err,_x000D_
num;_x000D_
for ( ; i < max; i++) {_x000D_
div = _div.cloneNode();_x000D_
text = _text.cloneNode();_x000D_
num = fib(i);_x000D_
if (num !== test[i]) {_x000D_
err = i + ' == ' + test[i] + '; got ' + num;_x000D_
div.style.color = 'red';_x000D_
}_x000D_
text.nodeValue = i + ': ' + num;_x000D_
div.appendChild(text);_x000D_
frag.appendChild(div);_x000D_
}_x000D_
document.body.appendChild(frag);
_x000D_
Yet another answer would be to use es6 generator functions.
function* fib() {
var current = a = b = 1;
yield 1;
while (true) {
current = b;
yield current;
b = a + b;
a = current;
}
}
sequence = fib();
sequence.next(); // 1
sequence.next(); // 1
sequence.next(); // 2
// ...
According to the Interview Cake question, the sequence goes 0,1,1,2,3,5,8,13,21. If this is the case, this solution works and is recursive without the use of arrays.
function fibonacci(n) {
return n < 1 ? 0
: n <= 2 ? 1
: fibonacci(n - 1) + fibonacci(n - 2);
}
console.log(fibonacci(4));
Think of it like this.
fibonacci(4) .--------> 2 + 1 = 3
| / |
'--> fibonacci(3) + fibonacci(2)
| ^
| '----------- 2 = 1 + 1 <----------.
1st step -> | ^ |
| | |
'----> fibonacci(2) -' + fibonacci(1)-'
Take note, this solution is not very efficient though.
I got asked this question recently, and this was my solution:
function fib(n) {_x000D_
const arr = [0,1]; // the inital array, we need something to sum at the very beginning_x000D_
for (let i = 2; i <= n; i++) { // we want the last number, so don't forget the '=' sign_x000D_
let a = arr[i-1]; // previous Number_x000D_
let b = arr[i-2]; // the one before that_x000D_
arr.push(a+b); // push the result_x000D_
}_x000D_
return arr; // if you want the n-th number, just return arr[n] or arr.length - 1_x000D_
}_x000D_
_x000D_
console.log(fib(4));
_x000D_
A recursive solution would be:
// NOTE: This has extremly bad performance => Exponential time complexity 2^n_x000D_
_x000D_
function fib(n) {_x000D_
if (n < 2) {_x000D_
return n;_x000D_
}_x000D_
return fib(n-1) + fib(n-2);_x000D_
}_x000D_
_x000D_
console.log('The n-th fibonacci number: ', fib(6));_x000D_
console.log('The entire fibonacci sequence: ');_x000D_
_x000D_
// Let's see the entire fibonacci sequence_x000D_
for (let i = 0; i <= 6; i++) {_x000D_
console.log(fib(i));_x000D_
}
_x000D_
Like mentioned earlier, the above recursive solution has a very bad impact on performance. Fortunately, there's a solution and it's called memoization:
// LET'S CREATE A MEMO FUNCTION _x000D_
// (and use it on the recursive **fib** function from above):_x000D_
_x000D_
// We want to pass in a function which is going to, eventually, _x000D_
// use this utility function_x000D_
function memo(fn) { _x000D_
const cache = {}; _x000D_
// let's make it reusable, and by that I mean, let's assume that_x000D_
// we don't know the number of arguments that will be eventually passed in _x000D_
return function(...args) {_x000D_
// if we already call this function with the same args?_x000D_
// YES => return them_x000D_
if(cache[args]) { _x000D_
console.log('cached', args[0]);_x000D_
return cache[args];_x000D_
}_x000D_
// otherwise, we want to call our function _x000D_
// (the one using this 'memo' function) and pass in the arguments_x000D_
// w/ the help of 'apply'_x000D_
const res = fn.apply(this, args);_x000D_
cache[args] = res; _x000D_
// we want to store the result, so later if we'll be able to_x000D_
// return that if the args don't change_x000D_
console.log('not cached', args[0]);_x000D_
return res; // don't forget to return the result of it :)_x000D_
}_x000D_
}_x000D_
_x000D_
// Now, let's use the memoized function:_x000D_
// NOTE: Remember the above function has to change in a way_x000D_
// that it calls the memoized function instead of itself_x000D_
_x000D_
function fastFib(n) {_x000D_
// SAME LOGIC AS BEFORE_x000D_
if (n<2) { _x000D_
return n;_x000D_
}_x000D_
// But, here is where the 'magic' happens_x000D_
// Very important: We want to call the instantiated 'fibMemo' function _x000D_
// and NOT 'fastFib', cause then it wouldn't be so fast, right :) _x000D_
return fibMemo(n-1) + fibMemo(n-2);_x000D_
}_x000D_
_x000D_
// DO NOT CALL IT, JUST PASS IT IN_x000D_
const fibMemo = memo(fastFib); _x000D_
_x000D_
// HERE WE WANT TO PASS IN THE ARGUMENT_x000D_
console.log(fibMemo(6));
_x000D_
fibonacci 1,000 ... 10,000 ... 100,000
Some answers run into issues when trying to calculate large fibonacci numbers. Others are approximating numbers using phi. This answer will show you how to calculate a precise series of large fibonacci numbers without running into limitations set by JavaScript's floating point implementation.
Below, we generate the first 1,000 fibonacci numbers in a few milliseconds. Later, we'll do 100,000!
const { fromInt, toString, add } =
Bignum
const bigfib = function* (n = 0)
{
let a = fromInt (0)
let b = fromInt (1)
let _
while (n >= 0) {
yield toString (a)
_ = a
a = b
b = add (b, _)
n = n - 1
}
}
console.time ('bigfib')
const seq = Array.from (bigfib (1000))
console.timeEnd ('bigfib')
// 25 ms
console.log (seq.length)
// 1001
console.log (seq)
// [ 0, 1, 1, 2, 3, ... 995 more elements ]
Let's see the 1,000th fibonacci number
console.log (seq [1000])
// 43466557686937456435688527675040625802564660517371780402481729089536555417949051890403879840079255169295922593080322634775209689623239873322471161642996440906533187938298969649928516003704476137795166849228875
10,000
This solution scales quite nicely. We can calculate the first 10,000 fibonacci numbers in under 2 seconds. At this point in the sequence, the numbers are over 2,000 digits long – way beyond the capacity of JavaScript's floating point numbers. Still, our result includes precise values without making approximations.
console.time ('bigfib')
const seq = Array.from (bigfib (10000))
console.timeEnd ('bigfib')
// 1877 ms
console.log (seq.length)
// 10001
console.log (seq [10000] .length)
// 2090
console.log (seq [10000])
// 3364476487 ... 2070 more digits ... 9947366875
Of course all of that magic takes place in Bignum
, which we will share now. To get an intuition for how we will design Bignum
, recall how you added big numbers using pen and paper as a child...
1259601512351095520986368
+ 50695640938240596831104
---------------------------
?
You add each column, right to left, and when a column overflows into the double digits, remembering to carry the 1 over to the next column...
... <-001
1259601512351095520986368
+ 50695640938240596831104
---------------------------
... <-472
Above, we can see that if we had two 10-digit numbers, it would take approximately 30 simple additions (3 per column) to compute the answer. This is how we will design Bignum
to work
const Bignum =
{ fromInt: (n = 0) =>
n < 10
? [ n ]
: [ n % 10, ...Bignum.fromInt (n / 10 >> 0) ]
, fromString: (s = "0") =>
Array.from (s, Number) .reverse ()
, toString: (b) =>
Array.from (b) .reverse () .join ('')
, add: (b1, b2) =>
{
const len = Math.max (b1.length, b2.length)
let answer = []
let carry = 0
for (let i = 0; i < len; i = i + 1) {
const x = b1[i] || 0
const y = b2[i] || 0
const sum = x + y + carry
answer.push (sum % 10)
carry = sum / 10 >> 0
}
if (carry > 0) answer.push (carry)
return answer
}
}
We'll run a quick test to verify our example above
const x =
fromString ('1259601512351095520986368')
const y =
fromString ('50695640938240596831104')
console.log (toString (add (x,y)))
// 1310297153289336117817472
And now a complete program demonstration. Expand it to calculate the precise 10,000th fibonacci number in your own browser! Note, the result is the same as the answer provided by wolfram alpha
const Bignum =_x000D_
{ fromInt: (n = 0) =>_x000D_
n < 10_x000D_
? [ n ]_x000D_
: [ n % 10, ...Bignum.fromInt (n / 10 >> 0) ]_x000D_
_x000D_
, fromString: (s = "0") =>_x000D_
Array.from (s, Number) .reverse ()_x000D_
_x000D_
, toString: (b) =>_x000D_
Array.from (b) .reverse () .join ('')_x000D_
_x000D_
, add: (b1, b2) =>_x000D_
{_x000D_
const len = Math.max (b1.length, b2.length)_x000D_
let answer = []_x000D_
let carry = 0_x000D_
for (let i = 0; i < len; i = i + 1) {_x000D_
const x = b1[i] || 0_x000D_
const y = b2[i] || 0_x000D_
const sum = x + y + carry_x000D_
answer.push (sum % 10)_x000D_
carry = sum / 10 >> 0_x000D_
}_x000D_
if (carry > 0) answer.push (carry)_x000D_
return answer_x000D_
}_x000D_
}_x000D_
_x000D_
const { fromInt, toString, add } =_x000D_
Bignum_x000D_
_x000D_
const bigfib = function* (n = 0)_x000D_
{_x000D_
let a = fromInt (0)_x000D_
let b = fromInt (1)_x000D_
let __x000D_
while (n >= 0) {_x000D_
yield toString (a)_x000D_
_ = a_x000D_
a = b_x000D_
b = add (b, _)_x000D_
n = n - 1_x000D_
}_x000D_
}_x000D_
_x000D_
console.time ('bigfib')_x000D_
const seq = Array.from (bigfib (10000))_x000D_
console.timeEnd ('bigfib')_x000D_
// 1877 ms_x000D_
_x000D_
console.log (seq.length)_x000D_
// 10001_x000D_
_x000D_
console.log (seq [10000] .length)_x000D_
// 2090_x000D_
_x000D_
console.log (seq [10000])_x000D_
// 3364476487 ... 2070 more digits ... 9947366875
_x000D_
100,000
I was just curious how far this little script could go. It seems like the only limitation is just time and memory. Below, we calculate the first 100,000 fibonacci numbers without approximation. Numbers at this point in the sequence are over 20,000 digits long, wow! It takes 3.18 minutes to complete but the result still matches the answer from wolfram alpha
console.time ('bigfib')
const seq = Array.from (bigfib (100000))
console.timeEnd ('bigfib')
// 191078 ms
console.log (seq .length)
// 100001
console.log (seq [100000] .length)
// 20899
console.log (seq [100000])
// 2597406934 ... 20879 more digits ... 3428746875
(function fib(max,i,j) {
i = i||this[0];j=j||this[1];
if (max!==0) {
this.push(i+j);
max--;
return fib.bind(this, max, j, i+j)();
} else {
return this;
}
}.bind([0,1], 10))();
result :[ 0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89 ]
You can get some cache to speedup the algorithm...
var tools = {
fibonacci : function(n) {
var cache = {};
// optional seed cache
cache[2] = 1;
cache[3] = 2;
cache[4] = 3;
cache[5] = 5;
cache[6] = 8;
return execute(n);
function execute(n) {
// special cases 0 or 1
if (n < 2) return n;
var a = n - 1;
var b = n - 2;
if(!cache[a]) cache[a] = execute(a);
if(!cache[b]) cache[b] = execute(b);
return cache[a] + cache[b];
}
}
};
You should've declared the fib
variable to be an array in the first place (such as var fib = []
or var fib = new Array()
) and I think you're a bit confused about the algorithm.
If you use an array to store the fibonacci sequence, you do not need the other auxiliar variables (x,y,z
) :
var fib = [0, 1];
for(var i=fib.length; i<10; i++) {
fib[i] = fib[i-2] + fib[i-1];
}
console.log(fib);
You should consider the recursive method too (note that this is an optimised version) :
function fib(n, undefined){
if(fib.cache[n] === undefined){
fib.cache[n] = fib(n-1) + fib(n-2);
}
return fib.cache[n];
}
fib.cache = [0, 1, 1];
and then, after you call the fibonacci function, you have all the sequence in the fib.cache
field :
fib(1000);
console.log(fib.cache);
function fibo(count) {
//when count is 0, just return
if (!count) return;
//Push 0 as the first element into an array
var fibArr = [0];
//when count is 1, just print and return
if (count === 1) {
console.log(fibArr);
return;
}
//Now push 1 as the next element to the same array
fibArr.push(1);
//Start the iteration from 2 to the count
for(var i = 2, len = count; i < len; i++) {
//Addition of previous and one before previous
fibArr.push(fibArr[i-1] + fibArr[i-2]);
}
//outputs the final fibonacci series
console.log(fibArr);
}
Whatever count we need, we can give it to above fibo method and get the fibonacci series upto the count.
fibo(20); //output: [0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, 233, 377, 610, 987, 1597, 2584, 4181]
sparkida, found an issue with your method. If you check position 10, it returns 54 and causes all subsequent values to be incorrect. You can see this appearing here: http://jsfiddle.net/createanaccount/cdrgyzdz/5/
(function() {_x000D_
_x000D_
function fib(n) {_x000D_
var root5 = Math.sqrt(5);_x000D_
var val1 = (1 + root5) / 2;_x000D_
var val2 = 1 - val1;_x000D_
var value = (Math.pow(val1, n) - Math.pow(val2, n)) / root5;_x000D_
_x000D_
return Math.floor(value + 0.5);_x000D_
}_x000D_
for (var i = 0; i < 100; i++) {_x000D_
document.getElementById("sequence").innerHTML += (0 < i ? ", " : "") + fib(i);_x000D_
}_x000D_
_x000D_
}());
_x000D_
<div id="sequence">_x000D_
_x000D_
</div>
_x000D_
This is what I came up with
//fibonacci numbers
//0,1,1,2,3,5,8,13,21,34,55,89
//print out the first ten fibonacci numbers
'use strict';
function printFobonacciNumbers(n) {
var firstNumber = 0,
secondNumber = 1,
fibNumbers = [];
if (n <= 0) {
return fibNumbers;
}
if (n === 1) {
return fibNumbers.push(firstNumber);
}
//if we are here,we should have at least two numbers in the array
fibNumbers[0] = firstNumber;
fibNumbers[1] = secondNumber;
for (var i = 2; i <= n; i++) {
fibNumbers[i] = fibNumbers[(i - 1)] + fibNumbers[(i - 2)];
}
return fibNumbers;
}
var result = printFobonacciNumbers(10);
if (result) {
for (var i = 0; i < result.length; i++) {
console.log(result[i]);
}
}
I know this is a bit of an old question, but I realized that many of the answers here are utilizing for loops rather than while loops.
Sometimes, while loops are faster than for loops, so I figured I'd contribute some code that runs the Fibonacci sequence in a while loop as well! Use whatever you find suitable to your needs.
function fib(length) {
var fibArr = [],
i = 0,
j = 1;
fibArr.push(i);
fibArr.push(j);
while (fibArr.length <= length) {
fibArr.push(fibArr[j] + fibArr[i]);
j++;
i++;
}
return fibArr;
};
fib(15);
I've tried this: it might work:
<!DOCTYPE html>
<html lang="en">
<head>
<meta charset="UTF-8">
<meta name="viewport" content="width=device-width, initial-scale=1.0">
<title>Fibonacci</title>
<style>
* {
outline: 0px;
margin: 0px;
}
input[type="number"] {
color: blue;
border: 2px solid black;
width: 99.58vw;
}
</style>
</head>
<body>
<div id="myDiv" style="color: white;background-color: blue;">Numbers Here</div>
<input type="number" id="input1" oninput="fibonacciProgram(this.value)" placeholder="Type Some Numbers Here">
<script>
function fibonacciProgram(numberCount) {
let resultElement = document.getElementById("myDiv");
resultElement.innerHTML = " ";
if (isNaN(numberCount) || numberCount <= 0) {
resultElement.innerHTML = "please enter a number";
return;
}
let firstBox = 0;
let secondBox = 1;
let swichBox;
let entries = [];
entries.push(secondBox);
while (numberCount > 1) {
swichBox = firstBox + secondBox;
entries.push(swichBox);
firstBox = secondBox;
secondBox = swichBox;
numberCount--;
}
resultElement.innerHTML = entries.join(', ');
}
</script>
</body>
</html>
You're not assigning a value to z
, so what do you expect y=z;
to do? Likewise you're never actually reading from the array. It looks like you're trying a combination of two different approaches here... try getting rid of the array entirely, and just use:
// Initialization of x and y as before
for (i = 2; i <= 10; i++)
{
alert(x + y);
z = x + y;
x = y;
y = z;
}
EDIT: The OP changed the code after I'd added this answer. Originally the last line of the loop was y = z;
- and that makes sense if you've initialized z
as per my code.
If the array is required later, then obviously that needs to be populated still - but otherwise, the code I've given should be fine.
I just would like to contribute with a tail call optimized version by ES6. It's quite simple;
var fibonacci = (n, f = 0, s = 1) => n === 0 ? f : fibonacci(--n, s, f + s);_x000D_
console.log(fibonacci(12));
_x000D_
function getFibonacciNumbers(n) {
var sequence = [0, 1];
if (n === 0 || n === 1) {
return sequence[n];
}
else {
for (var i = 2; i < n; i++ ) {
var sum = sequence[i - 1] + sequence[i - 2];
sequence.push(sum);
}
return sequence;
}
}
console.log(getFibonacciNumbers(0));
console.log(getFibonacciNumbers(1));
console.log(getFibonacciNumbers(9));
Another solution could be:
const fib = (num) => {
if(num === 0) return 0;
const arr=[0,1];
let counter=2;
while(counter <=num){
arr[counter]=arr[counter -1] + arr[counter -2]
counter ++
}
return arr
}
This function returns an Array of the Fibonacci sequence based on given limit.
fib(5) // returns [0, 1, 1, 2, 3, 5]
Fibonacci (one-liner)
function fibonacci(n) {
return (n <= 1) ? n : fibonacci(n - 1) + fibonacci(n - 2);
}
Fibonacci (recursive)
function fibonacci(number) {_x000D_
// n <= 1_x000D_
if (number <= 0) {_x000D_
return n;_x000D_
} else {_x000D_
// f(n) = f(n-1) + f(n-2)_x000D_
return fibonacci(number - 1) + fibonacci(number - 2);_x000D_
}_x000D_
};_x000D_
_x000D_
console.log('f(14) = ' + fibonacci(14)); // 377
_x000D_
Fibonacci (iterative)
function fibonacci(number) {_x000D_
// n < 2_x000D_
if (number <= 0) {_x000D_
return number ;_x000D_
} else {_x000D_
var n = 2; // n = 2_x000D_
var fn_1 = 0; // f(n-2), if n=2_x000D_
var fn_2 = 1; // f(n-1), if n=2 _x000D_
_x000D_
// n >= 2_x000D_
while (n <= number) {_x000D_
var aa = fn_2; // f(n-1)_x000D_
var fn = fn_1 + fn_2; // f(n)_x000D_
_x000D_
// Preparation for next loop_x000D_
fn_1 = aa;_x000D_
fn_2 = fn;_x000D_
_x000D_
n++;_x000D_
}_x000D_
_x000D_
return fn_2;_x000D_
}_x000D_
};_x000D_
_x000D_
console.log('f(14) = ' + fibonacci(14)); // 377
_x000D_
Fibonacci (with Tail Call Optimization)
function fibonacci(number) {_x000D_
if (number <= 1) {_x000D_
return number;_x000D_
}_x000D_
_x000D_
function recursion(length, originalLength, previous, next) {_x000D_
if (length === originalLength)_x000D_
return previous + next;_x000D_
_x000D_
return recursion(length + 1, originalLength, next, previous + next);_x000D_
}_x000D_
_x000D_
return recursion(1, number - 1, 0, 1);_x000D_
}_x000D_
_x000D_
console.log(`f(14) = ${fibonacci(14)}`); // 377
_x000D_
Another implementation, while recursive is very fast and uses single inline function. It hits the javascript 64-bit number precision limit, starting 80th sequence (as do all other algorithms): For example if you want the 78th term (78 goes in the last parenthesis):
(function (n,i,p,r){p=(p||0)+r||1;i=i?i+1:1;return i<=n?arguments.callee(n,i,r,p):r}(78));
will return: 8944394323791464
This is backwards compatible all the way to ECMASCRIPT4 - I tested it with IE7 and it works!
Source: Stackoverflow.com