Вычисляем миллиардное число Фибоначчи менее чем за 7 секунд

Цель

Мы хотим находить где:

И хочется это делать очень быстро, абсолютно точно и со всеми знаками.

Простой алгоритм

Заметим, чтобы найти число надо знать числа и . Значит для поиска очередного числа Фибоначчи нам нужно знать два предыдущих. Поэтому мы будем хранить пары . По этой паре можно вычислить следующую , а по этой следующую и тд. Таким образом по паре мы можем найти пару . И так мы нашли .

С помощью такого алгоритма мы можем вычислять за операций над числами фибоначчи. Но нам этого не достаточно! Ускорим алгоритм!

Ускоренный алгоритм

Теперь мы хотим по вычислять сразу . Для этого воспользуемся формулой, взятой с википедии:

Немного её преобразуем для наших нужд:

Заметим что и преобразуем первую формулу:

Итоговый вид:

И теперь мы можем по вычислять.

Но как это ускорит алгоритм? А очень просто! Нам нужно вычислить рассмотрим два случая:

1. Если :

   Воспользуемся новой формулой и по вычислим результат.

2. Если n = 2k + 1

   Воспользуемся старой формулой и по вычислим результат, а мы найдем через пункт 1.

Таким образом, на каждом шаге, число n уменьшается не менее в 2 раза. Значит операций над числами Фибоначчи будет . Но и в этом алгоритме есть что улучшить.

Ускоряем ускоренный алгоритм

Немного отвлечёмся от формул и подумаем, как мы будем считать числа абсолютно точно. Для этого нужно воспользоваться длинной арифметикой. В этой статье не будем углубляться, что это такое. Нам нужен только один факт:

Умножение длинных чисел выполняется медленно.

Для тех кому интересно, как быстро умножать длинные числа, есть крутая статья.

Значит, чтобы код работал ещё быстрее, нам нужно свести количество умножений к минимуму. Сейчас у нас используется 3 умножения. Сведём их к двум!

Немного пошаманим над :

Вспомним что и тогда получим:

Итоговый вид:

И теперь наш код использует в 3 / 2 раза меньше умножений, чем прошлый алгоритм!

И ещё небольшая оптимизация

А также в конце нам не обязательно вычислять пару чисел, поэтому будем вычислять одно. Это значит:

1. Если n четно, мы избавимся ещё от одного умножения (при этом над очень большим числом).

2. Если n нечетно, мы будем пользоваться формулой . Во первых здесь меньше операций, и во вторых здесь квадраты чисел, что скорее всего положительно влияет на производительность.

Это мне сэкономило 30 секунд при вычислении 10.000.000.000 числа.

Реализация

Я буду писать на C++ и буду пользоваться библиотекой gmp, она обычно встроена в gcc.

Хедеры которые я использовал:

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

Функция для расчета следующего числа Фибоначчи:

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

Функция для расчета удвоенного числа Фибоначчи:

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 = f3 - f4;
}

Функция для получения числа Фибоначчи:

mpz_class fib_get(size_t N) {
  // запоминаем остаток от деления на два
  bool R = N % 2;
  // уменьшаем N в два раза, с учётом формул
  N = (N + 1) / 2;

  mpz_class a = 1;
  mpz_class b = 0;
  
  // Это номер бита в числе n (начинаем с последнего)
  int i = sizeof(size_t) * CHAR_BIT - 1;
  
  // ищем первый не нулевой бит
  for (; i >= 0; --i) {
    if (1ULL & (N >> i)) {
      break;
    }
  }
  // И дальше считаем
  -- i;
  size_t h = 1; // переменная показывает какое число фибоначи уже посчиталось
  for (; i >= 0; --i) {
    fib_double(a, b);
    h *= 2ULL;
    if (N & ((size_t)1ULL << i)) {
      fib_next(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;
}

Реализация немного кривая, но я не хотел писать через рекурсию.

И 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 << "Finishn";
}

Программа считывает число из консоли и записывает ответ в файл answer.txt. Компилируется при помощи команды g++ main.cpp -lgmpxx -lgmp

Тесты

100 миллионное число Фибоначчи считает за 0.589 секунды, и файл с ответом весит 17мб.

Миллиардное число Фибоначчи считает за 6.958 секунды, и файл с ответом весит 166мб.

10 миллиардное число Фибоначчи считает за 1 минуту 12.879 секунды, и файл с ответом весит 1.7гб.

Дальше мне стало страшно тестить...

Итог

Нигде в интернете я не смог найти подсчет 10,000,000,000 числа Фибоначчи. Это была моя первая статья, надеюсь это было интересно (практическое применение 0%).

Всем удачи, всем до новых статей :-)