Вычисляем миллиардное число Фибоначчи менее чем за 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 << "Finish\n"; }

Программа считывает число из консоли и записывает ответ в файл 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%).

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