Calculate the Billionth Fibonacci Number in Less Than 7 Seconds

Target

We want to find Where:

And I want to do it very quickly, absolutely accurately and with all the signs.

Simple algorithm

Note that to find the number you need to know the numbers And . So to find the next Fibonacci number we need to know the two previous ones. Therefore, we will store pairs . From this pair we can calculate the following and on this one the next one and so on. Thus, in pairs we can find a pair . And so we found .

Using this algorithm we can calculate for operations on Fibonacci numbers. But that's not enough for us! Let's speed up the algorithm!

Accelerated algorithm

Now we want to calculate immediately . To do this, we will use the formula taken from Wikipedia:

Let's transform it a little for our needs:

Note that and transform the first formula:

Final appearance:

And now we can calculate.

But how will this speed up the algorithm? It's very simple! We need to calculate Let's consider two cases:

1. If :

   Let's use the new formula and Let's calculate the result.

2. If n = 2k + 1

   Let's use the old formula and we calculate the result, and we will find through point 1.

Thus, at each step, the number n decreases by at least 2 times. This means that there will be operations on Fibonacci numbers . But there is also room for improvement in this algorithm.

Speeding up the accelerated algorithm

Let's take a break from formulas and think about how we will count numbers absolutely accurately. To do this, we need to use long arithmetic. We won't go into detail about what it is in this article. We only need one fact:

Multiplication of long numbers is slow.

For those interested in how to quickly multiply long numbers, there is a cool article.

So, to make the code work even faster, we need to reduce the number of multiplications to a minimum. Right now we have 3 multiplications. Let's reduce them to two!

Let's do a little shamanism :

Let's remember that and then we get:

Final appearance:

And now our code uses 3/2 times fewer multiplications than the previous algorithm!

And another small optimization

And also at the end we don't have to calculate a pair of numbers, so we'll calculate one. This means:

1. If n even, we will get rid of one more multiplication (and over a very large number).

2. If n odd, we will use the formula . Firstly, there are fewer operations here, and secondly, there are squares of numbers, which most likely has a positive effect on performance.

This saved me 30 seconds when calculating the 10,000,000,000th number.

Implementation

I will write on C++ and I will use the library gmpit is usually built into gcc.

Headers I used:

#include <iostream>
#include <gmpxx.h>
#include <fstream>

Function to calculate the next Fibonacci number:

void fib_next(mpz_class& f2, mpz_class& f1) {
  std::swap(f2, f1);
  f2 += f1;
}

Function to calculate double Fibonacci number:

void fib_double(mpz_class& f3, mpz_class& f2) {
  mpz_class f6 = (f3 + f2 * 2) * f3;
  mpz_class f4 = (f3 * 2 - f2) * f2;
  f3 = std::move(f6);
  f2 = f6 - f4;
}

Function to get Fibonacci number:

mpz_class fib_get(size_t N) {
  // запоминаем остаток от деления на два
  bool R = N % 2;
  // уменьшаем N в два раза, с учётом формул
  N = (N + 1) / 2;
  
  mpz_class a = 1;
  mpz_class b = 0;
  int i = 63; // Это номер бита в числе n (начинаем с последнего)
  // ищем первый не нулевой бит
  for (; i >= 0; --i) {
    if (1ULL & (N >> i)) {
      break;
    }
  }
  // И дальше считаем
  -- i;
  size_t h = 1; // переменная показывает какое число фибоначи уже посчиталось
  for (; i >= 0; --i) {
    fib_double(a, b);
    h *= 2;
    if (N & (1ULL << i)) {
      fib_addone(a, b);
      ++ h;
    }
    // выводим информацию, чтобы небыло скучно ждать
    std::cout << "find: " << h << '\n';
  }

  // считаем окончательный ответ без пары
  if (R) {
    a = a * a + b * b;
    std::cout << "find: " << h * 2 - 1 << '\n'; 
  } else {
    a = (a + b * 2) * a;
    std::cout << "find: " << h * 2 << '\n'; 
  }
  return a;
}

The implementation is a bit crooked, but I didn't want to write it through recursion.

And main:

int main() {
  size_t n;
  std::cout << "Enter the fibonacci number: ";
  std::cin >> n;
  auto answer = fib_get(n);
  std::string str = answer.get_str(16); 
  // записываю в 16ричной системе исчисления
  // так как хочу, чтобы ответ быстрее записывало :D
  std::ofstream fout("answer.txt");
  fout << str;
  std::cout << "Finish\n";
}

The program reads a number from the console and writes the answer to a file. answer.txt. Compiled using the command g++ main.cpp -lgmpxx -lgmp

Tests

The 100 millionth Fibonacci number is calculated in 0.589 seconds, and the file with the answer weighs 17 MB.

The billionth Fibonacci number is calculated in 6.958 seconds, and the file with the answer weighs 166 MB.

The 10 billionth Fibonacci number is calculated in 1 minute 12.879 seconds, and the file with the answer weighs 1.7 GB.

Then I became afraid to test…

Summary

I couldn't find anywhere on the internet a calculation of 10,000,000,000 Fibonacci numbers. This was my first article, hopefully it was interesting (practical application 0%).

Good luck to everyone, until new articles 🙂