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
Conclusion

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

shell

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

Example 2

shell

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.