Binet's Formula - Finding n-th Fibonacci without Using Loop

In this tutorial, we will learn about Binet's formula, which is a quick and efficient way to calculate the n-th Fibonacci number.

By using this formula, no loop is required and can be useful when you want to directly find the n-th Fibonacci number in O(1) time complexity.

What is Binet's Formula?
Implementation of Binet's Formula
Algorithm Complexity

What is Binet's Formula?

Binet (pronounced as BEE-nay or buh-NET) is a French mathematician who discovered a formula to calculate the n-th Fibonacci number called Binet's formula.

Binet's formula is a closed-form expression allowing us to directly calculate the n-th Fibonacci number without using iterative loops. The formula is as follows:

or in shortened form:

where phi is the golden ratio

Implementation of Binet's Formula

Let's see how we can apply Binet's formula to calculate the n-th Fibonacci number without using a loop.

Binet's Formula in C++

binets-formula.cpp


#include <stdc++.h>
 
using namespace std;
 
double calculateFibonacci(int n) {
double phi = (1 + sqrt(5)) / 2;
return (pow(phi, n) - pow(-phi, -n)) / sqrt(5);
}
 
int main() {
int n;
 
cout << "Enter the value of n: ";
cin >> n;
 
double fibonacci = calculateFibonacci(n);
 
cout << "The " << n << "-th Fibonacci number is: " << fibonacci << '\n';
 
return 0;
}

On the other hand, given a number, you can also check if it is a Fibonacci number.

Binet's Formula in Java

BinetsFormula.java


public class FibonacciCalculator {
  public static double calculateFibonacci(int n) {
    double phi = (1 + Math.sqrt(5)) / 2;
    return (Math.pow(phi, n) - Math.pow(-phi, -n)) / Math.sqrt(5);
  }
 
  public static void main(String[] args) {
    System.out.print("Enter the value of n: ");
    int n = new Scanner(System.in).nextInt();
    double fibonacci = calculateFibonacci(n);
    System.out.println("The " + n + "-th Fibonacci number is: " + fibonacci);
  }
}

Binet's Formula in Python

binets-formula.py


def calculate_fibonacci(n):
  phi = (1 + 5 ** 0.5) / 2
  return (phi ** n - (-phi) ** (-n)) / 5 ** 0.5
 
if __name__ == '__main__':
  n = int(input('Enter the value of n: '))
  fibonacci = calculate_fibonacci(n)
  print(f'The {n}-th Fibonacci number is: {fibonacci}')

See how to print the Fibonacci sequence in Python.

Binet's Formula in JavaScript

binets-formula.js


function calculateFibonacci(n) {
  const phi = (1 + Math.sqrt(5)) / 2;
  return (phi ** n - (-phi) ** -n) / Math.sqrt(5);
}
 
const n = 10;
const fibonacci = parseInt(calculateFibonacci(n).toString(), 10);
console.log(`The ${n}-th Fibonacci number is: ${fibonacci}`);

We define a function calculateFibonacci that accepts an integer n as input. The function then returns the n-th Fibonacci number using Binet's formula.

We calculate the value of phi using the golden ratio formula (1 + sqrt(5)) / 2 and then apply Binet's formula to calculate the Fibonacci number.

Below are some examples:

Example 1

console


Enter the value of n: 5
The 5-th Fibonacci number is: 5

Example 2

console


Enter the value of n: 10
The 10-th Fibonacci number is: 55

The algorithm complexity of calculating the n-th Fibonacci number using Binet's formula is O(1), which means it has a constant time complexity. This is because the calculation involves only a few mathematical operations and does not depend on the value of n.

Binet's Formula - Finding n-th Fibonacci without Using Loop

Contents

What is Binet's Formula?

Implementation of Binet's Formula

Binet's Formula in C++

Binet's Formula in Java

Binet's Formula in Python

Binet's Formula in JavaScript

Example 1

Example 2

Example 3

Algorithm Complexity

Contents

What is Binet's Formula?

Implementation of Binet's Formula

Binet's Formula in C++

Binet's Formula in Java

Binet's Formula in Python

Binet's Formula in JavaScript

Example 1

Example 2

Example 3

Algorithm Complexity

Most Read