sum of even fibonacci numbers returning infinity?

Question

Hi so I'm trying to find the sum of all even Fibonacci numbers whose value do not exceed 4 million and the result I get keeps returning infinity... If anyone can find the error in the JS code I've written I'd greatly appreciate the feedback! Thanks in advance!

("problem_2_range" is already defined in my HTML as 4000000)

var evenFibonacciSum = function() {
    var sum = 0;
    var arr = [1, 2];
    for (i = 2; i<=document.getElementById("problem_2_range").value; i++) {
        var fib = arr[i-2] + arr[i-1];
        arr.push(fib);
    }
    for (i=0; i < arr.length; i++) {
        if (arr[i] % 2 === 0) {
            sum += arr[i];
        } else {
            continue;
        }
    }
    document.getElementById("answer2").innerHTML = sum;
}

You are over the max number http://stackoverflow.com/questions/21126311/javascript-factorial-prevent-infinity — epascarello, Oct 14 '15 at 20:25
You need to use a long (64 bit) data type. Interestingly, I just did that problem the other night. — Eric J., Oct 14 '15 at 20:26

score 0 · Answer 1 · answered Oct 14 '15 at 20:57

0

Use math.js's bignumber function

F.X and replace the first line with

var sum = math.bignumber(0);

answered Oct 14 '15 at 20:57

Þorvaldur Rúnarsson

879
7
15

score 0 · Answer 2 · answered Oct 14 '15 at 21:14

It depends on what you mean by "value". If you mean the result of the Fibonacci-function (e.g.: the 55 you get with Fibonacci(10)) then it is doable, of course, because the total sum cannot exceed (x*(x+1))/2 = 8,000,002,000,000 which is smaller than 2^53 (the Number object is defined as an IEEE-754 "double").

Computing the actual Fibonacci function is quite expensive and I would check the magnitude with Binet's formula but I can tell you that the result of fibonacci(34) exceeds 4,000,000 already.

If, on the other side you want the n in n-th Fibonacci number not to exceed 4,000,000 let me tell you that fibonacci(3999999)~1.0058e835950.

It is doable with a fast biginteger library (the one in Math.js isn't very fast) by using a trick with matrix exponentiation which works roughly as (in pseudocode)

fibonacci(n){
  i = n -1, t = 0;
  /*
              | 1 0 |
     matrix = | 0 1 |   
  */
  a = 1, b = 0, c = 0, d = 1;
  while (i > 0) {
    if(i % 0x1){
      t = d*(a + b) + c*b;
      a = d*b + c*a;
      b = t;
    }
    t = d*(2*c + d);
    c = c*c + d*d;
    d = t;
    i >>>= 1;
  }
  t = a + b;
  return t;
}

It is probably faster to use the following linear algorithm for f(n<79)

function fb(n){
  var i = 1, j = 0, k, l;
  for (k = 1; k <= n; k++) {
    l = i + j;
    i = j;
    j = l;
  }
  return j;
}

sum of even fibonacci numbers returning infinity?

2 Answers2