Цель
Мы хотим находить где:
И хочется это делать очень быстро, абсолютно точно и со всеми знаками.
Простой алгоритм
Заметим, чтобы найти число надо знать числа
и
. Значит для поиска очередного числа Фибоначчи нам нужно знать два предыдущих. Поэтому мы будем хранить пары
. По этой паре можно вычислить следующую
, а по этой следующую и тд. Таким образом по паре
мы можем найти пару
. И так мы нашли
.
С помощью такого алгоритма мы можем вычислять за
операций над числами фибоначчи. Но нам этого не достаточно! Ускорим алгоритм!
Ускоренный алгоритм
Теперь мы хотим по вычислять сразу
. Для этого воспользуемся формулой, взятой с википедии:
Немного её преобразуем для наших нужд:
Заметим что и преобразуем первую формулу:
Итоговый вид:
И теперь мы можем по вычислять
.
Но как это ускорит алгоритм? А очень просто! Нам нужно вычислить рассмотрим два случая:
-
Если
:
Воспользуемся новой формулой и по
вычислим результат.
-
Если n = 2k + 1
Воспользуемся старой формулой и по
вычислим результат, а
мы найдем через пункт 1.
Таким образом, на каждом шаге, число n уменьшается не менее в 2 раза. Значит операций над числами Фибоначчи будет . Но и в этом алгоритме есть что улучшить.
Ускоряем ускоренный алгоритм
Немного отвлечёмся от формул и подумаем, как мы будем считать числа абсолютно точно. Для этого нужно воспользоваться длинной арифметикой. В этой статье не будем углубляться, что это такое. Нам нужен только один факт:
Умножение длинных чисел выполняется медленно.
Для тех кому интересно, как быстро умножать длинные числа, есть крутая статья.
Значит, чтобы код работал ещё быстрее, нам нужно свести количество умножений к минимуму. Сейчас у нас используется 3 умножения. Сведём их к двум!
Немного пошаманим над :
Вспомним что и тогда получим:
Итоговый вид:
И теперь наш код использует в 3 / 2 раза меньше умножений, чем прошлый алгоритм!
И ещё небольшая оптимизация
А также в конце нам не обязательно вычислять пару чисел, поэтому будем вычислять одно. Это значит:
Если n четно, мы избавимся ещё от одного умножения (при этом над очень большим числом).
Если 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%).
Всем удачи, всем до новых статей :-)
Комментарии (40)
white-wild
14.08.2024 09:19+6А почему не рассматривали через матричные вычисления плюс быстрое возведение в степень?
KukarekusUltra Автор
14.08.2024 09:19+2При матричном возведении в степень используется 8 умножений, а это медленно. Плюс про этот метод написано много статей.
sci_nov
14.08.2024 09:19Матрицы можно хорошо оптимизировать под конвейер процессора, плюс векторизация
rbdr
14.08.2024 09:19+2А теперь надо эти мегабайты-гигабайты как-то красиво визуализировать!
wataru
14.08.2024 09:19+10f3 = std::move(f6); f2 = f6 - f4;Вот тут у вас UB. Нельзя f6 использовать после того, как вы оттуда сделали move.
Еще, в коде вы там используете fib_addone, когда как выше у вас определена неиспользуемая fib_next.
Советую перечитать весь код в статье и причесать его.
wataru
14.08.2024 09:19+1Кстати, раз уж вы с gmp работаете, было бы интересно сравнить ваше решение с встроенным в gmp: mpz_fib_ui
vlad_gatsenko
14.08.2024 09:19+2Интересно, что Python не уступает в скорости: 1 млрд - низкие 5 секунд :)
Код Python
import gmpy2 import time def fib_next(f2, f1): return f1, f2 + f1 def fib_double(f3, f2): f6 = (f3 + f2 * 2) * f3 f4 = (f3 * 2 - f2) * f2 return f6, f6 - f4 def fib_get(N): R = N % 2 N = (N + 1) // 2 a = gmpy2.mpz(1) b = gmpy2.mpz(0) i = N.bit_length() - 1 h = 1 for i in range(i - 1, -1, -1): a, b = fib_double(a, b) h *= 2 if N & (1 << i): a, b = fib_next(a, b) h += 1 if R: a = a * a + b * b else: a = (a + b * 2) * a return a if __name__ == "__main__": n = int(input("Enter the Fibonacci number: ")) start_time = time.time() answer = fib_get(n) end_time = time.time() print(f"Calculation time: {end_time - start_time} seconds") with open("answer.txt", "w") as f: f.write(answer.digits(16)) # Запись числа в 16-ричной системе print("Finish")1 миллиард: 5.22 сек
Hidden text
10 миллиардов: 77.17 сек
Hidden text
И это на ноутбуке с довольно стареньким Core i9 8950HK и TDP 35W.
gev
14.08.2024 09:19Код дает неверную последовательность, проверьте, например, первые 10
vlad_gatsenko
14.08.2024 09:19Замените f.write(answer.digits(16)) # Запись числа в 16-ричной системе на f.write(str(answer)) # Запись числа в десятичной системе
gev
14.08.2024 09:19for i in range(1, 11): print(fib_get(i).digits(10))Выдает
1 1 2 3 5 5 13 21 29 24
chnav
14.08.2024 09:19(off) Странно, но в статье не видно КДПВ и текста под ней, поэтому не получается через Ctrl-Enter отправить в личку сообщение об ошибке в тексте на заглавной.Очень глаз режет :peace:
wataru
14.08.2024 09:19+4Это уже давно так на хабре стало: текст в ленте - это не часть текста из статьи до какого-то якоря, а вообще отдельный текст. В редакторе для него отдельное поле есть. Бесит на самом деле, что при написании статьи надо постоянно не забывать исправлять текст и там и там.
CitizenOfDreams
14.08.2024 09:19Вот было бы здорово, если бы программисты писали эффективные программы не только на собеседованиях, но и на работе. А то вычислить за пять секунд миллиард чисел мы можем, а запустить какой-нибудь Фотошоп - нет.
AlexanderS
14.08.2024 09:19+1100 миллионное число Фибоначчи считает за 0.589 секунды, и файл с ответом весит 17мб.
Миллиардное число Фибоначчи считает за 6.958 секунды, и файл с ответом весит 166мб.
10 миллиардное число Фибоначчи считает за 1 минуту 12.879 секунды, и файл с ответом весит 1.7гб.
Дальше мне стало страшно тестить...
А почему страшно? Для 100 миллиардного ~14 мин и ~17 Гб? )
0xC0CAC01A
А разве нет просто формулы для n-го числа Фибоначчи, чтоб вычислять за O(1)?
white-wild
Можно через золотое сечение вычислить, но там возможны погрешности.
KukarekusUltra Автор
К сожалению нет(
mordens
Есть такая формула!
KukarekusUltra Автор
Тут используется возведение в степень, оно работает не за константное время
mordens
Вы правы! Формулы для вычисления за O(1) действительно нет. Но красота формулы и ее вывода стоят упоминания здесь.
aamonster
Умножение длинных чисел, и даже сложение или копирование тоже работает не за константное время, потому что числа имеют длину O(n) :-)
В статье у вас этот момент обойдён, потому что вы пишете O(log n) операций над числами Фибоначчи. Если возведение в степень тоже считать операцией – получим O(1). А если честно считать сложность по времени – то у вас что-то вроде O(n*log n*...) получается (что под многоточием – определяется выбранным алгоритмом умножения), и вроде это предел (если какой-нибудь гений не изобретёт алгоритм вычисления чисел Фибоначчи цифра за цифрой или типа того).
Забавно, что мой коммент ниже, где я упомянул реальную временную сложность с учётом длины чисел, нахватал минусов, кто-то даже не поленился в карму минуснуть.
niktor_mpt
Причём второе слагаемое меньше 1 и его можно не вычислять, отбрасывая дробную часть от первого слагаемого.
Надо прикинуть, с какой точностью sqrt(5) вычислять придётся.
alcotel
Если приближённо вычислять через быстрое возведение в степень 2**(n*log2(x)) - да, кажется вообще быстро. Но чтобы считать точно, придётся экспоненту ручками считать с точностью в хулиард знаков. А это та же итерационная процедура.
gres_84
Последний кусок в этой формуле настолько мал, что при больших n его можно отбросить и просто округлять результат до ближайшего целого.
aamonster
За O(1) вы не можете его даже напечатать или скопировать из памяти в память, потому что длина числа O(n).
alcotel
Действительно. И время выполнения тестов у автора чуть больше, чем О(n) как раз и получается:
n =10e8 0,6 секунд
n=10e9 7 ceкунд
n=10e10 73 секунды
Где же тут O(log n) !?
aamonster
Ну, у автора в посте упомянуты "O(log n) операций над числами Фибоначчи", к нему претензий нет. А вот минимум двое минуснувших (один в карму даже не поленился) – показатель.
wataru
На самом деле тут O(n log n) получается суммарно. Грубая оценка O(n log^2 n): O(log n) длинных умножений, каждое из которых O(n log n), через FFT. Но они не все такие длинные же. Там в конце пара умножений длины n, потом пара длины n/2, потом пара n/4... В итоге получаем n log n + n/2 log(n/2) + ... и это все можно граничить сверху 2n log n.