Как я посчитал миллионное число Фибоначчи

Автор оригинала: Kush
  • Перевод

Все мы понимаем, что рекурсивное вычисление чисел Фибоначчи крайне неэффективно. Многим людям наверняка хотелось проверить, где пределы (не)эффективности, но не доходили руки, не хватало времени. Специально к старту нового потока курса Fullstack-разработчик на Python мы решили поделиться переводом статьи, автор которой шаг за шагом показывает возможности современного Python на примере разных подходов к вычислению чисел Фибоначчи. В статье вы найдёте проблемные значения n и сравнение производительности оптимального и неоптимального решений на графике.


Нет, заголовок вообще не кликбейтный. Несколько дней назад я действительно хотел найти оптимальное решение для расчёта чисел Фибоначчи, хотелось попробовать вычислить стотысячное число последовательности, но я задумался; если я могу вычислить стотысячное число, то что остановит меня в поисках миллионного числа Фибоначчи? Сегодня я покажу, как шёл к вычислению и с какими проблемами столкнулся.

Последовательность Фибоначчи — одна из наиболее известных математических последовательностей и самый простой пример рекуррентных отношений. Каждое число последовательности — это сумма двух предыдущих чисел, начиная с 0 и 1. Получается такая последовательность:

0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144 и так далее...

В следующие несколько минут я исследую несколько разных подходов, а затем покажу оптимальное решение:

  1. Простая рекурсия.

  2. Кеш с рекурсией.

  3. Итеративный метод.

  4. Формула Бине.

  5. Расчёт 1000000-го числа Фибоначчи.

Но, прежде чем мы начнём, я должен сказать, что все упомянутые тайминги касаются оборудования, на котором я работаю сейчас, а версия Python — 3.9.1.

Простая рекурсия

Это очень простой способ получить N-ное число Фибоначчи на Python:

def recursiveFib(n):
    if n == 1 or n == 2:
        return 1

    return recursiveFib(n - 1) + recursiveFib(n - 2)

В коде используется рекурсия, он вызывает сам себя несколько раз, вычисляя предыдущее число и используя это число для вычисления следующего. Но это также недостаток, поскольку функция чрезвычайно неэффективна и ресурсоёмка: на каждом этапе она вычисляет предыдущие 2 числа, а также предыдущие 2 числа этих чисел и т. д.

Вскоре вы достигаете точки, когда вычисление следующего числа занимает слишком много времени, например, на моём компьютере мне потребовалось 1,43 секунды, чтобы вычислить 35-е число. Очевидно, что вычисление более высоких значений будет чрезвычайно медленным и практически невозможным.

Кеш с рекурсией

Поскольку мы постоянно вычисляем предыдущие 2 числа, для хранения числа можно воспользоваться возможностями кеширования, не нужно будет вычислять числа несколько раз. Встроенный модуль functools позволяет нам работать с LRU кешем; этот тип кеша организует элементы в порядке их использования. Такой подход может значительно ускорить процесс.

from functools import lru_cache

@lru_cache()
def recursiveFibCached(n):
    if n == 1 or n == 2:
        return 1

    return recursiveFibCached(n - 1) + recursiveFibCached (n - 2)

Во-первых, нам нужно импортировать декоратор lru_cache из модуля functools и поместить его перед нашей функцией. Мы можем указать значение maxsize, чтобы сообщить кешу, сколько элементов нужно хранить, но по умолчанию оно равно 128, это значение прекрасно работает. Используя кеш, мы можем вычислить 200-е число Фибоначчи всего за 0,0002252 секунды!

Одна проблема с использованием рекурсии заключается в том, что если вы попытаетесь вычислить 501-е число, то получите ошибку RecursionError: maximum recursion depth exceeded in comparison. Но, к счастью, проблему можно решить, установив большее значение глубины рекурсии:

import sys

sys.setrecursionlimit(5000)

Теперь мы можем вычислить 1000-е число Фибоначчи, на вычисление которого мне потребовалось всего 0,001198 секунды. Однако это создало для меня ещё одну проблему: по какой-то странной причине я не мог вычислить 1553-е число в последовательности, и даже после увеличения предела рекурсии ничего не произойдёт, ничего не будет распечатано на терминале, и программа просто закончит выполнение. Очевидно, что это проблема и недостаток на моём пути к вычислению миллионного числа Фибоначчи.

Итеративный метод

Вы можете увидеть, что применение рекурсивного решения проблемы в компьютерной науке часто рассматривается как халатность, а итеративные методы считаются намного лучше. Для генерации чисел Фибоначчи мы можем создать итеративное решение:

def iterativeFib(n):
    a, b = 0, 1

    for i in range(n):
        a, b = b, a + b

    return a

Мы можем воспользоваться им, чтобы вычислить любое число Фибоначчи (я не тестировал подход с особенно большими числами), и часто этот подход работает также очень быстро, 1000-е число вычислилось всего за 0,0028195 секунды.

Вы можете задаться вопросом, почему нельзя воспользоваться этим подходом для вычисления 1000000-го числа, и да, это возможно, но займёт немного времени. Продолжайте читать, и я расскажу, почему.

Формула Бине

Формула Бине — это формула, которая может использоваться для вычисления n-го члена последовательности Фибоначчи, а это именно то, что мы хотим сделать; эта формула названа в честь открывшего её французского математика Жака Филиппа Мари Бине. Вот она:

Формула Бине для вычисления n-ного числа Fibonacci
Формула Бине для вычисления n-ного числа Fibonacci

Вы можете заметить греческую букву PHI (ϕ), она означает золотое сечение:

Уравнение золотого сечения, phi
Уравнение золотого сечения, phi

Можно написать формулу на Python и сразу же начать работать с ней:

def formulaFib(n):
    root_5 = 5 ** 0.5
    phi = ((1 + root_5) / 2)

    a = ((phi ** n) - ((-phi) ** -n)) / root_5

    return round(a)

Примечание: для реализации на Python нам нужно вернуть округление вычисляемого числа, потому что при вычислении большого числа Python вернёт результат, в котором может быть более двадцати девяток после запятой.

Всё это хорошо, так как теперь у нас нет никаких циклов и мы можем мгновенно вычислить ответ, верно? Что ж, в этом методе есть небольшая загвоздка. Если мы попытаемся вычислить что-либо выше 1475-го числа, то столкнёмся с ошибкой: OverflowError: (34, result too large). Это связано с тем, как в python реализованы числа с плавающей точкой, они могут иметь конкретное максимальное значение, которое мы превышаем, когда используем этот метод.

Однако исправить ситуацию очень легко. Мы можем использовать встроенный модуль под названием decimal, чтобы создать десятичный объект с гораздо более высокой точностью и подходящим для работы с уравнением размером:

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)

В этой новой функции мы устанавливаем значение точности длиной 10000 цифр, преобразуем наше значение квадратного корня из 5 в десятичное значение объекта и используем его в нашем уравнении. Это позволяет нам легко вычислить 10000-е число в последовательности за поразительные 0,0692986 секунды, а это по сравнению со всеми нашими предыдущими методами огромное улучшение.

Расчёт 1000000-го числа Фибоначчи

Теперь вы, возможно, заметили, что формула работает медленнее итерационного решения, когда n=10000. Это связано с тем, что в формуле нам нужно создать десятичный объект и использовать его в уравнении, этот процесс занимает больше времени, чем повторение одной простой инструкции 10000 раз. Но история ещё не окончена.

Увеличение количества циклов может радикально увеличить длительность всего процесса. В какой-то момент, когда n составляет приблизительно 89200, время, необходимое итеративному решению для вычисления ответа, равно времени, которое необходимо при вычислении по формуле; когда же n увеличивается, время выполнения итеративного алгоритма возрастает с большей скоростью, чем время на решение по формуле.

График, показывающий время работы формулы Бине и итерационного решения
График, показывающий время работы формулы Бине и итерационного решения

На графике видно точку пересечения времени выполнения формулы и итерационных графиков. Исходя из этого мы можем сказать, что с увеличением n время вычисления числа Фибоначчи по формуле возрастает линейно. Но при итеративном решении время увеличивается с увеличением n. Это даёт нам понять, что для вычисления миллионного числа Фибоначчи нам нужно использовать формулу. Дополнительное изменение, которое я должен был сделать, чтобы правильно вычислить число, — увеличить точность моего десятичного объекта строкой кода decimal.getcontext().prec = 300000.

Ваше время выполнения алгоритма может отличаться. На моём компьютере, чтобы вычислить 1000000-е число Фибоначчи, потребовалось:

  • 8,832661 секунды при решении с итерацией;

  • 1,151380 секунды с формулой Бине, это в 7,7 раза быстрее!

Если вам хочется узнать число, оно состоит из 208988 цифр и в текстовом файле занимает 209 КБ:

Заключение

Вот так я вычислил миллионное число Фибоначчи, конечно, я мог бы вычислить число больше, но на самом деле для этого нет никакой реальной причины, и это заняло бы много времени, даже с использованием формулы Бине. Из приведённого выше графика я могу оценить затраты времени: чтобы вычислить миллиардное число Фибоначчи, мне потребуется примерно 310,8467 секунды, я оставлю это читателям. А чтобы получить специальность Fullstack-разработчик на Python — потребуется немногим более года. Но можно и быстрее — на нашем курсе студенты не привязаны к программе и скорость их прогресса зависит от них самих.

Узнайте, как прокачаться и в других специальностях или освоить их с нуля:

Другие профессии и курсы
SkillFactory
Школа Computer Science. Скидка 10% по коду HABR

Комментарии 34

    –3

    Я признаю, что возможно я нуб в этой теме, но у меня простецкий алгоритм тратит 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}')
      +2

      Ну а посчитай десятимиллионное число. Или стамиллионное. Будешь вечность ждать

        +5
        О каких именно проблемах вы спрашиваете? В статье так и написано:
        Ваше время выполнения алгоритма может отличаться. На моём компьютере, чтобы вычислить 1000000-е число Фибоначчи, потребовалось:

        8,832661 секунды при решении с итерацией;

        1,151380 секунды с формулой Бине, это в 7,7 раза быстрее!


        То есть ваш результат итерационного алгоритма почти совпал с результатом автора статьи: у вас 10 секунд, у автора 9 секунд.
          0

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

        0

        Делал через матрицы. Мое исполнение:
        https://dotnetfiddle.net/CiBDN0

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

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

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

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

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

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

                      N.B. Если вы посмотрите, что выводит print(formulaFibWithDecimal(1000000)), то увидите число, имеющее 10000 значащих цифр и 198988 хвостовых нулей. Что «немного» отличается от приведённого в статье значения.

                      2. Почему-то было полностью проигнорировано вычисление чисел Фибоначчи через возведение матрицы в степень, обеспечивающее сложность O(log(n)) и на больших n безусловно обгоняющее O(n) итеративный метод.
                        +5

                        Подтверждаю. Ранаем код автора


                        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

                        Если я нигде не ошибся, статья — мусор, даже непонятно, какую причину для минуса выбирать.

                          +4

                          Причина — переводная статья от еще одних онлайн-курсов, которые переводят любой шлак ради рекламного блока в конце статьи.

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

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

                              0

                              del, холиварчик намечается....

                              0

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

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

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

                                +1

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

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

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

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

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

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

                                    +4
                                    Для того, чтобы получить абсолютную точность можно реализовать класс чисел вида
                                    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()
                                    

                                    Также было бы неплохо пояснить, почему эта формула вообще верна, потому что это не совсем очевидно, хотя за этим стоит довольно простая вещь.
                                      0
                                      Ой, как интересно ;)
                                      Вот только при подсчёте 10000000 (1e7) числа Фибоначчи данный алгоритм уже не работает, потому что вы получаете decimal overflow.
                                      И это довольно очевидно: для того, чтобы точно реализовать формулу Бине нужно точно реализовать операции умножения и сложения в поле действительных чисел вида a + bsqrt(5), что, разумеется, не сделали авторы decimal, потому что там были другие цели.
                                      Для сравнения, алгоритм, вычисляющий число Фибоначчи, используя возведение матрицы 2x2 в степень, указанный ниже, вычисляет это число Фибоначчи всего за 94 секунды (в этом числе более 2 миллионов цифр).
                                      def multiply_2_2_matrices(a, b):
                                          c = [0, 0, 0, 0]
                                          c[0] = a[0] * b[0] + a[1] * b[2]
                                          c[2] = a[2] * b[0] + a[3] * b[2]
                                          c[1] = a[0] * b[1] + a[1] * b[3]
                                          c[3] = a[2] * b[1] + a[3] * b[3]
                                          return c
                                      
                                      def bin_pow(a, n):
                                          if n == 0:
                                              return [1, 0,
                                                      0, 1]
                                          if n & 1:
                                              return multiply_2_2_matrices(bin_pow(a, n - 1), a)
                                          else:
                                              x = bin_pow(a, n // 2)
                                              return multiply_2_2_matrices(x, x)
                                      
                                      n = int(input("Fibonacci number: "))
                                      print(bin_pow([1, 1,
                                                     1, 0], n)[1])


                                      Вот же реализация через поле:
                                      def gcd(x, y):
                                          while y != 0:
                                              tmp = x
                                              x = y
                                              y = tmp % y 
                                          return x
                                      
                                      class rational:
                                      
                                          def __init__(self, nom, denom):
                                              d = gcd(nom, denom)
                                              self.nom = nom // d
                                              self.denom = denom // d
                                      
                                          def __mul__(self, other):
                                              return rational(self.nom * other.nom, self.denom * other.denom)
                                          
                                          def __truediv__(self, other):
                                              return rational(self.nom * other.denom, self.denom * other.nom)
                                      
                                          def __add__(self, other):
                                              return rational(self.nom * other.denom + other.nom * self.denom, self.denom * other.denom)
                                      
                                          def __neg__(self):
                                              return rational(-self.nom, self.denom)
                                      
                                          def __sub__(self, other):
                                              return self + (-other)
                                          
                                          def __str__(self):
                                              if self.denom == 1:
                                                  return str(self.nom)
                                              return f"{self.nom}/{self.denom}"
                                      
                                      class num:
                                          # a + bsqrt(5)
                                      
                                          def __init__(self, a, b):
                                              self.a = a
                                              self.b = b
                                      
                                          def __mul__(self, other):
                                              # (a + bsqrt(5)) * (c + dsqrt(5)) = ac + (ad + bc)sqrt(5) + 5bd
                                              a = self.a * other.a + rational(5, 1) * self.b * other.b
                                              b = self.a * other.b + self.b * other.a
                                              return num(a, b)
                                      
                                          def div_int(self, n):
                                              return num(self.a / n, self.b / n)
                                      
                                          def __truediv__(self, other):
                                              # (a + bsqrt(5)) / (c + dsqrt(5)) = (a + bsqrt(5))(c - dsqrt(5)) / (c * c - 5 * d * d)
                                              denom = other.a * other.a - rational(5, 1) * other.b * other.b
                                              nom = self * num(other.a, -other.b)
                                              return nom.div_int(denom)
                                      
                                          def __add__(self, other):
                                              return num(self.a + other.a, self.b + other.b)
                                      
                                          def __sub__(self, other):
                                              return num(self.a - other.a, self.b - other.b)
                                      
                                          def __str__(self):
                                              if self.b.nom == 0:
                                                  return str(self.a)
                                              if self.a.nom == 0:
                                                  return f"{self.b}√5"
                                              return f"{self.a} + {self.b}√5"
                                      
                                      
                                      def bin_pow(a, n):
                                          if n == 0:
                                              return num(rational(1, 1), rational(0, 1))
                                          if n & 1:
                                              return bin_pow(a, n - 1) * a
                                          x = bin_pow(a, n // 2)
                                          return x * x
                                      
                                      phi = num(rational(1, 2), rational(1, 2))
                                      psi = num(rational(1, 2), rational(-1, 2))
                                      n = int(input("Fibonacci number: "))
                                      print((bin_pow(phi, n) - bin_pow(psi, n)) / num(rational(0, 1), rational(1, 1)))
                                      

                                      Она считает 1e7 число Фибоначчи за 95 секунд (то есть за то же время, что и решение с матрицами). Как и ожидалось, полученные двумя методами числа совпали.
                                        0

                                        Ещё есть "fast doubling", тоже за O(ln N)

                                          0
                                          по какой-то странной причине я не мог вычислить 1553-е число в последовательности
                                          А вот тут было бы очень интересно выяснить почему, собственно, ничего не вышло. Скажем, у меня 1553-е число по приведённому коду вычислилось нормально. Даже 100000-е без проблем.
                                            –1

                                            А что не так с нормальной рекурсией здорового человека (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

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

                                            Только полноправные пользователи могут оставлять комментарии. Войдите, пожалуйста.

                                            Самое читаемое