Home//

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

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

By Minh Vu

Updated Nov 17, 2023

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?

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}')
``````

### 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
``````

### Example 3

shell
``````Enter the value of n: 15
The 15-th Fibonacci number is: 610
``````

## Algorithm Complexity

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`.

Minh Vu

Software Engineer

Hi guys, I'm the author of WiseCode Blog. I mainly work with the Elastic Stack and build AI & Python projects. I also love writing technical articles, hope you guys have good experience reading my blog!

Minh Vu

Software Engineer

### Related Posts

See All Posts

Do not find what you need?

Send us a message.