Как стать автором
Обновить
2
0
Отправить сообщение
Не нужна никакая точность, когда всё можно считать в целых числах, и будет не сильно медленнее. См. комментарий ниже.
Как вы возводите в степень n за O(1)?
А вообще говоря это асимптотика с точностью до количества перемножений, так как у n-ого числа Фибоначчи хотя бы n цифр, и перемножать их явно не O(1).
Для того, чтобы получить абсолютную точность можно реализовать класс чисел вида
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()

Также было бы неплохо пояснить, почему эта формула вообще верна, потому что это не совсем очевидно, хотя за этим стоит довольно простая вещь.

Информация

В рейтинге
Не участвует
Откуда
Яхрома, Москва и Московская обл., Россия
Дата рождения
Зарегистрирован
Активность