Как стать автором
Обновить

Комментарии 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 секунд.

Понял, пропустил этот момент

Мне тоже больше импонирует вариант с матричным возведением в степень, которое делается за O(logn). Без этой гадости с вещественными числами.

Еще почему-то эта статья на хабре конченно работает. На опере вообще не загружается, а на файрфоксе ооочень медленно работает. Странно.

Да, было такое. Браузер напрягали 208988 чисел в виде кода. Помогло только встраивание гита.
Сравнивать алгоритмы, рисовать даже графики времени их выполнения и никак не затронуть тему алгоритмической сложности. Вы так и людей обучаете тоже? Не думаю, что я-бы к вам пошел учиться.
Так-то всю статью можно уложить в одно предложение:
У рекурсивного алгоритма вычисления числа фибоначчи экспоненциальная сложность, у итерационного O(n), а у вычисления по формуле — O(1)
Любезный, к чему агрессия сразу? Вы дольше меня на Хабре, аж 10 лет уже, но не замечаете пометку «перевод» под заголовком и хабами?
Хорошо, объясню свою реакцию.
Еслиб это была просто чья-то личная статья, или перевод, то я бы ее воспринял как просто чье-то личное мнение. Но прочитав в конце статьи приглашение к курсам, я ее воспринял как кусочек ваших курсов, замануха, типа: «вот я вам что-то рассказал из того, что мы на курсах рассказываем, если заинтересовал — милости просим, заходите, будет больше интересного». И в таком свете уже не важно, перевод это, или нет, статься прочиталась как часть вашего обучения.
Возможно у меня не правильное восприятие, но что-то мне подсказывает, что я с таким неправильным, вовсе не одинок.
А Вы, видимо, имеете неудачный опыт учебы, раз считаете, что n-ую степень числа можно вычислить за O(1)?
Хм, действительно, там же возведение в ту-же самую n-ю степень. Ну значит вычисление по формуле будет иметь логарифмическую сложность.
Не будет там О(1) формула построена на возведении числа в степень n. А это только в формуле выглядит парой символов, а в реальном алгоритме приведет к n операций умножения. Что мы и наблюдаем на графике. Время выполнения медленно, но растет.

"В реальном алгоритме приведет к n операций умножения" — это если в лоб, можно же быстрее (log n). Материалы на Хабре по теме:
N-е число Фибоначчи за O(log N)
(вместо формулы Бине используется быстрое вычисление по рекуррентной формуле посредством возведения матрицы в степень — сложность та же)
Используем быстрое возведение матриц в степень для написания очень быстрого интерпретатора простого языка программирования
(интересное развитие темы с обобщением на широкий класс рекуррентных последовательностей).
Вижу комментарий от eandr_67 ниже, в котором тоже упоминается сложность O(log(n)) — но без ссылок на существующие заметки, так что публикую ссылки здесь, мало ли, кому будет интересно.

а в реальном алгоритме приведет к n операций умножения

Да, я уже написал, что ошибся и будет логарифмическая сложность.
Возводить в степень можно не линейно, а логарифмически, если упрощенно, то перемножая результаты предыдущей итерации и деля на два остаток степени.
2^16 = 4^8 = 16^4 = 256^2 = 65536
Как вы возводите в степень n за O(1)?
А вообще говоря это асимптотика с точностью до количества перемножений, так как у n-ого числа Фибоначчи хотя бы n цифр, и перемножать их явно не O(1).
1. Вы подтасовываете результаты для формулы Бине, используя decimal.getcontext().prec = 10000. В fib(1000000) не 10000 цифр, а более чем на порядок больше. Потому для формулы Бине при больших n вы получаете заведомо заниженное время вычислений — не вычисляя до 95% цифр числа.

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
Если установить точность, необходимую для миллионного числа(около 210000), то формула Бине быстрее итерационного алгоритма менее, чем на 1 секунду(на моем компьютере).
Не нужна никакая точность, когда всё можно считать в целых числах, и будет не сильно медленнее. См. комментарий ниже.

Мда. Взял формулу и по ней посчитал. Уровень статьи просто зашкаливает. Откуда она появилась? Почему она вообще правильная? О-большое в статье про алгоритмы? Нет, не слышали.

А если этот же алгоритм на С переписать и скомпилировать, то за примерно 0.00...01 с посчитаем и миллионное, и миллиардные числа..

А если в темплейт на С++ завернуть, так компилятор и сам посчитает в процессе компиляции...

Да мало ли ещё как можно с Фибоначчи пошутить)

А если этот же алгоритм на С переписать

На С нет этих проблем с О(n)?

А если в темплейт на С++ завернуть, так компилятор и сам посчитает в процессе компиляции...

Но доооолгооо...

Там длинку надо писать же, а она долгая. Или как?

Использовать для вычисления целого значения округление иррациональных чисел (которые уже округлены до рациональных) - это не очень чистый хак.

Для того, чтобы получить абсолютную точность можно реализовать класс чисел вида
a + b * sqrt(5), где a, b — рациональные, и хранить только a, b в виде рациональных чисел. Вообще говоря эти числа образуют поле(расширяющее поле рациональных чисел), и их можно даже делить друг на друга, но там это не понадобится, если аккуратно использовать формулу. Если использовать первое равенство image
то точность будет абсолютной.

Вот код, он вроде даже работает, временная сложность 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

И это еще неоптимизированная под арифметику виртуальная машина, да в один убогий поток.

Зарегистрируйтесь на Хабре , чтобы оставить комментарий