Краткий обзор и сравнение способов вычисления чисел Фибоначчи (обозначаю $F_n$).
Общее замечание о размере: битовая длина $F_n$ примерно $\ell (n)\approx n{\log }_2\phi \approx 0.694n$ бит (десятичных цифр $\approx 0.209n$). Для больших $n$ стоимость арифметики нарастает с ростом $\ell (n)$.
1) Наивная рекурсия
- Идея: прямая рекурсивная формула $F_n=F_{n-1}+F_{n-2}$ с базами $F_0,F_1$.
- Время: экспоненциально, примерно $O({\phi }^n)$, где $\phi =(1+\sqrt{5})/2$.
- Память: стек рекурсии $O(n)$ в глубине; дополнительная — незначительна.
- Параллелизация: теоретически независимые вызовы можно распараллелить, но накладные расходы и экстремальное повторение вычислений делают это неэффективным.
- Применимость: пригодна только для очень малых $n$ (порядка десятков). Для больших $n$ неприемлема из‑за времени.
2) Рекурсия с мемоизацией (динамическое программирование сверху)
- Идея: кэшировать уже вычисленные $F_k$.
- Время: $O(n)$ арифметических операций (сложений).
- Память: $O(n)$ для кэша (+ стек до $O(n)$ в рекурсивной реализации).
- Параллелизация: ограничена — зависимости между значениями затрудняют эффективную параллельную обработку, но можно распараллелить вычисление блоков при аккуратном управлении кэшем.
- Применимость: хороша для средних $n$. При больших $n$ доминирует стоимость работы с длинными целыми числами (память для хранения всех $F_k$ растёт как $O(n^2)$ бит суммарно), поэтому для очень больших индексов лучше итератив/бинарный метод.
3) Итеративный (простая циклическая формула)
- Идея: посчитать последовательно от $0$ до $n$, держать только два предыдущих значения.
- Время: $O(n)$ сложений больших целых.
- Память: $O(1)$ (два числа) плюс память результата $O(\ell (n))$.
- Параллелизация: почти полностью последовательный; возможны блоковые методы (вычислить переходы по блокам), но это усложняет реализацию.
- Применимость: эффективен для умеренно больших $n$ и когда нужно поэтапно получить все значения до $n$. Для экстремально больших $n$ медленнее методов $O(\log n)$.
4) Матричное возведение в степень / быстрый удвоительный метод
- Идея: матрица $A=\left(\begin{array}{cc}1& 1\\ 1& 0\end{array}\right)$ даёт $A^n=\left(\begin{array}{cc}{F}_{n+1}& F_n\\ F_n& F_{n-1}\end{array}\right)$; возведение в степень быстрым возведением в степень или формулы удвоения:
- быстрый удвоительный вариант:
$$F_{2k}=F_k(2F_{k+1}-F_k),F_{2k+1}=F_{k+1}^2+F_k^2.$$ - Время (в терминах арифметических операций): $O(\log n)$ больших умножений/сложений (экспоненциация по возведению в степень).
- В битовой модели (учитывая стоимость умножения больших чисел): время $O(M(\ell (n))\log n)$, где $M(t)$ — стоимость умножения $t$-битных чисел (например, $M(t)=O(t^2)$ для школьного, $M(t)=O(t^{1.585})$ для Карацубы, или $O(t\log t)$ для FFT).
- Память: $O(1)$ для хранения нескольких больших чисел (плюс память под реализации умножения).
- Параллелизация: хорошая — умножения и рекурсивные ветви можно параллелить; также внутренние алгоритмы умножения (FFT) хорошо параллелятся.
- Применимость: лучший практический выбор для очень больших $n$ при наличии длинной арифметики. Быстрый удвоительный алгоритм обычно предпочтительнее матричной реализации из‑за меньшего константного фактора.
5) Формула Бине
- Формула:
$$F_n=\frac{{\phi }^n-{\psi }^n}{\sqrt{5}},\psi =(1-\sqrt{5})/2.$$ - Время (с плавающей арифметикой двойной точности): вычисление ${\phi }^n$ — $O(\log n)$ операций с плавающей арифметикой (возведение в степень через возведение в степень по возведению в степень), но точность ограничена.
- Точность/применимость: с обычным IEEE double (≈53 бита значимой мантиссы) формула даёт точные целые значения только до примерно $n\lesssim 70$ (поскольку размер $F_n$ растёт и требуется примерно $\ell (n)$ бит точности). С длинной арифметикой можно применять, но тогда вычисление ${\phi }^n$ с нужной точностью стоит примерно как логарифмическое возведение в степень с длинной арифметикой и уже не даёт простого выигрыша по сравнению с матричным/удвоительным методом.
- Параллелизация: возможна при большом-числовой арифметике, но точность и ошибки округления — главный предел.
- Вывод: формула Бине хороша для аналитики и небольших $n$; для точного вычисления больших $n$ лучше методы на целых числах.
Дополнительные практические замечания и пороговые значения
- Для 64‑бит целых чисел точные значения: $F_{92}$ помещается в знаковый 64‑бит тип ($F_{93}$ переполнит).
- С плавающей двойной точностью гарантированно безопасно до примерно $n\approx 70$.
- Для больших $n$ (тысячи и больше) единственно практичны алгоритмы $O(\log n)$ с длинной арифметикой (быстрый удвоительный / матрицы), плюс эффективные алгоритмы умножения (Карацуба/FFT) и параллельная реализация. Плюс учитывать память: хранение результата требует $O(\ell (n))$ бит.
Рекомендация
- Для небольших $n$ и простоты — итеративный алгоритм.
- Для общего точного вычисления больших $n$ — быстрый удвоительный алгоритм (эквивалент матричному возведению в степень) с использованием быстрого умножения больших целых. Формулу Бине использовать только для малых $n$ или при наличии высокоточной арифметики и осознанных затрат на неё.