Комментарии 34
Я признаю, что возможно я нуб в этой теме, но у меня простецкий алгоритм тратит 10 секунд на расчет миллионного числа. Почему у меня нет таких проблем? Где я не прав? Это зависит от характеристик ПК?
Простецкий алгоритм
import time
import os
step = 1
now = 1
last = 0
startTime = time.time()
while step != 1000000:
nowF = now + last
last = now
now = nowF
step += 1
print(f'Need time: {time.time() - startTime}s')
print(f'Last element:\n=========\n{now}')
Ну а посчитай десятимиллионное число. Или стамиллионное. Будешь вечность ждать
Ваше время выполнения алгоритма может отличаться. На моём компьютере, чтобы вычислить 1000000-е число Фибоначчи, потребовалось:
8,832661 секунды при решении с итерацией;
1,151380 секунды с формулой Бине, это в 7,7 раза быстрее!
То есть ваш результат итерационного алгоритма почти совпал с результатом автора статьи: у вас 10 секунд, у автора 9 секунд.
Делал через матрицы. Мое исполнение:
https://dotnetfiddle.net/CiBDN0
Еще почему-то эта статья на хабре конченно работает. На опере вообще не загружается, а на файрфоксе ооочень медленно работает. Странно.
Так-то всю статью можно уложить в одно предложение:
У рекурсивного алгоритма вычисления числа фибоначчи экспоненциальная сложность, у итерационного O(n), а у вычисления по формуле — O(1)
Еслиб это была просто чья-то личная статья, или перевод, то я бы ее воспринял как просто чье-то личное мнение. Но прочитав в конце статьи приглашение к курсам, я ее воспринял как кусочек ваших курсов, замануха, типа: «вот я вам что-то рассказал из того, что мы на курсах рассказываем, если заинтересовал — милости просим, заходите, будет больше интересного». И в таком свете уже не важно, перевод это, или нет, статься прочиталась как часть вашего обучения.
Возможно у меня не правильное восприятие, но что-то мне подсказывает, что я с таким неправильным, вовсе не одинок.
"В реальном алгоритме приведет к n операций умножения" — это если в лоб, можно же быстрее (log n). Материалы на Хабре по теме:
N-е число Фибоначчи за O(log N)
(вместо формулы Бине используется быстрое вычисление по рекуррентной формуле посредством возведения матрицы в степень — сложность та же)
Используем быстрое возведение матриц в степень для написания очень быстрого интерпретатора простого языка программирования
(интересное развитие темы с обобщением на широкий класс рекуррентных последовательностей).
Вижу комментарий от eandr_67 ниже, в котором тоже упоминается сложность O(log(n)) — но без ссылок на существующие заметки, так что публикую ссылки здесь, мало ли, кому будет интересно.
а в реальном алгоритме приведет к n операций умножения
Да, я уже написал, что ошибся и будет логарифмическая сложность.
Возводить в степень можно не линейно, а логарифмически, если упрощенно, то перемножая результаты предыдущей итерации и деля на два остаток степени.
2^16 = 4^8 = 16^4 = 256^2 = 65536
А вообще говоря это асимптотика с точностью до количества перемножений, так как у n-ого числа Фибоначчи хотя бы n цифр, и перемножать их явно не O(1).
N.B. Если вы посмотрите, что выводит print(formulaFibWithDecimal(1000000)), то увидите число, имеющее 10000 значащих цифр и 198988 хвостовых нулей. Что «немного» отличается от приведённого в статье значения.
2. Почему-то было полностью проигнорировано вычисление чисел Фибоначчи через возведение матрицы в степень, обеспечивающее сложность O(log(n)) и на больших n безусловно обгоняющее O(n) итеративный метод.
Подтверждаю. Ранаем код автора
import decimal
def formulaFibWithDecimal(n):
decimal.getcontext().prec = 10000
root_5 = decimal.Decimal(5).sqrt()
phi = ((1 + root_5) / 2)
a = ((phi ** n) - ((-phi) ** -n)) / root_5
return round(a)
def iterativeFib(n):
a, b = 0, 1
for i in range(n):
a, b = b, a + b
return a
naive = iterativeFib(1_000_000)
smart = formulaFibWithDecimal(1_000_000)
print(f"Last 10 digits of the naive approach: {str(naive)[-10:]}")
print(f"Last 10 digits of the smart approach: {str(smart)[-10:]}")
Аутпут:
Last 10 digits of the naive approach: 8242546875
Last 10 digits of the smart approach: 0000000000
Если я нигде не ошибся, статья — мусор, даже непонятно, какую причину для минуса выбирать.
julia> fib(n) = ( BigInt.([1 1;1 0])^(n-1) )[1];
julia> @time N = fib(10_000_000);
0.498439 seconds (3.57 k allocations: 127.892 MiB, 10.53% gc time)
julia> length(string(N))
2089877
Мда. Взял формулу и по ней посчитал. Уровень статьи просто зашкаливает. Откуда она появилась? Почему она вообще правильная? О-большое в статье про алгоритмы? Нет, не слышали.
А если этот же алгоритм на С переписать и скомпилировать, то за примерно 0.00...01 с посчитаем и миллионное, и миллиардные числа..
А если в темплейт на С++ завернуть, так компилятор и сам посчитает в процессе компиляции...
Да мало ли ещё как можно с Фибоначчи пошутить)
Использовать для вычисления целого значения округление иррациональных чисел (которые уже округлены до рациональных) - это не очень чистый хак.
a + b * sqrt(5), где a, b — рациональные, и хранить только a, b в виде рациональных чисел. Вообще говоря эти числа образуют поле(расширяющее поле рациональных чисел), и их можно даже делить друг на друга, но там это не понадобится, если аккуратно использовать формулу. Если использовать первое равенство
то точность будет абсолютной.
Вот код, он вроде даже работает, временная сложность O(log n)(почти, так как вообще-то у n-ого числа Фибоначчи много цифр, и каждое перемножение дробей это gcd, но количество перемножений действительно log n)
def gcd(a, b):
while b != 0:
a, b = b, a % b
return a
class Frac:
def __init__(self, num, den):
g = gcd(num, den)
self.num = num // g
self.den = den // g
def __mul__(self, other):
return Frac(self.num * other.num, self.den * other.den)
def __add__(self, other):
return Frac(self.num * other.den + other.num * self.den, self.den * other.den)
def __sub__(self, other):
return Frac(self.num * other.den - other.num * self.den, self.den * other.den)
def __truediv__(self, other):
return Frac(self.num * other.den, self.den * other.num)
def __str__(self):
return f'{self.num}/{self.den}'
# a + b \sqrt{5}
class FieldElement:
def __init__(self, a, b):
self.a = a
self.b = b
def __add__(self, other):
return FieldElement(self.a + other.a, self.b + other.b)
def __sub__(self, other):
return FieldElement(self.a - other.a, self.b - other.b)
def __mul__(self, other):
return FieldElement(self.a * other.a + Frac(5, 1) * self.b * other.b, self.a * other.b + self.b * other.a)
def __str__(self):
return f'{self.a} + sqrt(5) * {self.b}'
def binpow(a, n):
if n == 1:
return a
if n % 2 == 0:
s = binpow(a, n // 2)
return s * s
return a * binpow(a, n - 1)
def naive_fib(n):
a, b = 1, 1
for i in range(2, n):
a, b = b, a + b
return b
def main():
n = int(input())
phi = FieldElement(Frac(1, 2), Frac(1, 2))
negphi = FieldElement(Frac(1, 2), Frac(-1, 2))
res = binpow(phi, n) - binpow(negphi, n)
print(res)
print(f'{n}-th number of fibonacci is {res.b.num}')
print(f'Naive result is {naive_fib(n)}')
if __name__ == '__main__':
main()
Также было бы неплохо пояснить, почему эта формула вообще верна, потому что это не совсем очевидно, хотя за этим стоит довольно простая вещь.
Ещё есть "fast doubling", тоже за O(ln N)
по какой-то странной причине я не мог вычислить 1553-е число в последовательностиА вот тут было бы очень интересно выяснить почему, собственно, ничего не вышло. Скажем, у меня 1553-е число по приведённому коду вычислилось нормально. Даже 100000-е без проблем.
А что не так с нормальной рекурсией здорового человека (TCO)? Не нужно просто «вызов самое себя изо всех щелей» называть рекурсией.
defmodule Fib do
def n(i) when i > 0, do: do_n(i + 1, {1, 0})
defp do_n(1, {_, acc}), do: acc
defp do_n(i, {p, pp}), do: do_n(i - 1, {p + pp, p})
end
(fn -> 1_000_000 |> Fib.n() end)
|> :timer.tc()
|> elem(0)
|> Kernel./(1_000_000)
#⇒ 11.513974
И это еще неоптимизированная под арифметику виртуальная машина, да в один убогий поток.
Как я посчитал миллионное число Фибоначчи