CODEWITHSUNDEEP
javascriptfibonacci
Ashot Tarumyan
Ashot Tarumyan

Reputation: 55

JS:checking if number belongs to Fibonacci sequence(without loop)

Is there an efficient way to check if number belongs to Fibonacci sequence?

I've seen many examples with a loop that creates the sequence in an array and checks every time if newly generated number of the sequence is equal to the input number. Is there another way?

Upvotes: 3

Views: 7438

Answers (5)

Umair Hamid
Umair Hamid

Reputation: 3557

The Fibonacci sequence is a series of numbers where a number is the addition of the last two numbers, starting with 0, and 1. Th following js function is explaining this.

    function isFabonacci(n) {
        if (n === 1 || n === 0) {
            return true;
        }
        let firstPrevNumber = n - 1;
        let secondPrevNumber = n - 2;
        return (firstPrevNumber + secondPrevNumber === n);
    }
    // isFabonacci(2) -> false
    // isFabonacci(3) -> true

Upvotes: -1

Keith.Abramo
Keith.Abramo

Reputation: 6955

function isPerfectSquare(n) {
    return n > 0 && Math.sqrt(n) % 1 === 0;
};

//Equation modified from http://www.geeksforgeeks.org/check-number-fibonacci-number/
function isFibonacci(numberToCheck)
{
    // numberToCheck is Fibinacci if one of 5*n*n + 4 or 5*n*n - 4 or both
    // is a perferct square
    return isPerfectSquare(5*numberToCheck*numberToCheck + 4) ||
           isPerfectSquare(5*numberToCheck*numberToCheck - 4);
}


for(var i = 0; i<= 10000; ++i) {
    console.log(i + " - " + isFibonacci(i));
}

This will most likely fail for larger numbers though.

Upvotes: 0

Raiyad Raad
Raiyad Raad

Reputation: 537

function isFibonacci(num, a = 0, b = 1) {
  if(num === 0 || num === 1) {
    return true;
  }

  let nextNumber = a+b;

  if(nextNumber === num) {
    return true;
  }
  else if(nextNumber > num) {
    return false;
  }

 return isFibonacci(num, b, nextNumber);
}

Upvotes: 2

EvSunWoodard
EvSunWoodard

Reputation: 1280

http://www.geeksforgeeks.org/check-number-fibonacci-number/

This link details that there is a special quality about fibonacci numbers that means that a number is Fibonacci if and only if one or both of (5*n2 + 4) or (5*n2 – 4) is a perfect square.

So, 

function (num) {
    if (isSquare(5*(num*num)-4) || isSquare(5*(num*num)+4)) {
       return true;
    } else { return false; }
}

Then isSquare would just be a simple checking function.

Edit: Worth noting that while this is a much more efficient and easy way to find fibonacci numbers, it does have an upper bound. At about the 70th Fibonacci number and above, you may see issues because the numbers are too large.

Upvotes: 7

Chang Liu
Chang Liu

Reputation: 1

def is_squared(number):
   temp_root = math.sqrt(number);
   temp_root = int(temp_root);
   return (temp_root * temp_root == number);

def check_all_fibo(test_number_list):
    result_fibo_list = [];
    for item in test_number_list:
        if item==0 or item == 1 or item == 2:
            result_fibo_list.append(item);
            continue;
        if is_squared(5 * item * item - 4) or is_squared(5 * item * item + 4):
            result_fibo_list.append(item);
    return result_fibo_list;

this is a python implementation by me. But keep in mind, the formula only works when the fib is not too large.

Upvotes: -1

Related Questions