Question 199829 in Javascript Question posted in
A very good W3school tutorial can be found here.

Javascript – The following code fails the test for values such 1000 but for something like 4 it runs well

Sum All Odd Fibonacci Numbers
Given a positive integer num, return the sum of all odd Fibonacci numbers that are less than or equal to num.

The first two numbers in the Fibonacci sequence are 0 and 1. Every additional number in the sequence is the sum of the two previous numbers. The first seven numbers of the Fibonacci sequence are 0, 1, 1, 2, 3, 5 and 8.

For example, sumFibs(10) should return 10 because all odd Fibonacci numbers less than or equal to 10 are 1, 1, 3, and 5.

I submitted the following code which did not pass all the tests:

function sumFibs(num){
  const fibonaciArr = [0,1];
  let add = 0;
  for(let i = 0; i < num; i++){
    if(fibonaciArr[i+1]%2 !== 0) add+=fibonaciArr[i+1];
    fibonaciArr.push(fibonaciArr[i] + fibonaciArr[i + 1])
  
  }
  return add;
}

I used the fibonaciArr to come up with the sequence just to see whether the sequence is ok.

Tags:

3

Answers


  1. 0

    The Fibonacci numbers grow pretty fast. Using your code, sumFibs(76) is the last value that can be represented exactly in JavaScript or in any other language that uses the double-precision 64-bit binary format IEEE 754 to represent the real numbers. This format can represent exactly the integer numbers in the interval -253 + 1 to 253 – 1. JavaScript provides the constants Number.MIN_SAFE_INTEGER and Number.MAX_SAFE_INTEGER for these values.

    The values outside this interval are rounded to the nearest multiple of a power of 2. The values between 253 and 254 – 1 are rounded to the next multiple of 2, the values between 254 and 255 – 1 are rounded to the next multiple of 4 and so on.

    This means that the 77th and the subsequent Fibonacci numbers cannot be computed. They are rounded to even numbers and your code ignores the even numbers.

    You can solve this by using BigInt numbers.

    function sumFibs(num){
  const fibonaciArr = [0n, 1n];
  let add = 0n;

  for (let i = 0; i < num; i ++) {
    if (fibonaciArr[i + 1] % 2n !== 0n) {
      add += fibonaciArr[i + 1];
    }
    fibonaciArr.push(fibonaciArr[i] + fibonaciArr[i + 1])
  }

  return add;
}

console.log(sumFibs(76));
console.log(sumFibs(77));
console.log(sumFibs(100));
console.log(sumFibs(1000));

    Check it online.

    Read about how JavaScript works with numbers.

    Login or Signup to reply.
  2. 0

    Axiac’s answer perfectly addressed the problem. I just add that you can easily solve this problem in JavaScript by using BigInt numbers in place of plain numbers.

    In order to do so, you have to place a n after every your number literal:

    function sumFibs(num){
  const fibonaciArr = [0n, 1n];
  let add = 0n;
  for(let i = 0; i < num; i++){
    if(fibonaciArr[i+1]%2n !== 0n) add+=fibonaciArr[i+1];
    fibonaciArr.push(fibonaciArr[i] + fibonaciArr[i + 1])
  
  }
  return add;
}

    function sumFibs(num){
  const fibonaciArr = [0,1];
  let add = 0;
  for(let i = 0; i < num; i++){
    if(fibonaciArr[i+1]%2 !== 0) add+=fibonaciArr[i+1];
    fibonaciArr.push(fibonaciArr[i] + fibonaciArr[i + 1])
  
  }
  return add;
}

function sumFibsBigInt(num){
  const fibonaciArr = [0n,1n];
  let add = 0n;
  for(let i = 0; i < num; i++){
    if(fibonaciArr[i+1]%2n !== 0n) add+=fibonaciArr[i+1];
    fibonaciArr.push(fibonaciArr[i] + fibonaciArr[i + 1])
  
  }
  return add;
}

console.log(`Fib(1000) with plain numbers: ${sumFibs(1000)}`);
console.log(`Fib(1000) with BigInt numbers: ${sumFibsBigInt(1000)}`);
    Login or Signup to reply.
  3. 0

    As mentioned the Fibonacci sequence can get big pretty fast,.

    But since we are dealing in integers, you can convert your code into using BigInt.

    Below is an example.

    function sumFibs(num){
  const fibonaciArr = [0n,1n];
  let add = 0n; 
  for(let i = 0; i < num; i++){
    if(fibonaciArr[i+1]%2n !== 0n) add+=fibonaciArr[i+1];
    fibonaciArr.push(fibonaciArr[i] + fibonaciArr[i + 1])
  }
  return add;
}

document.body.innerText = sumFibs(1000).toString();
    body {
  overflow-wrap: anywhere;
}
    Login or Signup to reply.
Please signup or login to give your own answer.

Back To Top
Search