Комментарии 46
А разве нет просто формулы для n-го числа Фибоначчи, чтоб вычислять за O(1)?
Можно через золотое сечение вычислить, но там возможны погрешности.
К сожалению нет(
Есть такая формула!
Тут используется возведение в степень, оно работает не за константное время
Вы правы! Формулы для вычисления за O(1) действительно нет. Но красота формулы и ее вывода стоят упоминания здесь.
Умножение длинных чисел, и даже сложение или копирование тоже работает не за константное время, потому что числа имеют длину O(n) :-)
В статье у вас этот момент обойдён, потому что вы пишете O(log n) операций над числами Фибоначчи. Если возведение в степень тоже считать операцией – получим O(1). А если честно считать сложность по времени – то у вас что-то вроде O(n*log n*...) получается (что под многоточием – определяется выбранным алгоритмом умножения), и вроде это предел (если какой-нибудь гений не изобретёт алгоритм вычисления чисел Фибоначчи цифра за цифрой или типа того).
Забавно, что мой коммент ниже, где я упомянул реальную временную сложность с учётом длины чисел, нахватал минусов, кто-то даже не поленился в карму минуснуть.
Причём второе слагаемое меньше 1 и его можно не вычислять, отбрасывая дробную часть от первого слагаемого.
Надо прикинуть, с какой точностью sqrt(5) вычислять придётся.
Если приближённо вычислять через быстрое возведение в степень 2**(n*log2(x)) - да, кажется вообще быстро. Но чтобы считать точно, придётся экспоненту ручками считать с точностью в хулиард знаков. А это та же итерационная процедура.
Последний кусок в этой формуле настолько мал, что при больших n его можно отбросить и просто округлять результат до ближайшего целого.
Вот, кстати, решение на Python через эту формулу. Только оно ощутимо медленнее:
Код на Python
from gmpy2 import mpz
class R5:
def __init__(self, a=0, b=0):
self.a = mpz(a)
self.b = mpz(b)
def __repr__(self):
return f'R5({self.a}, {self.b})'
def __str__(self):
if self.a and self.b:
return f'({self.a}{self.b:+}√5)'
elif self.b:
return f'{self.b}√5'
else:
return f'{self.a}'
def __add__(x, y):
return R5(x.a + y.a, x.b + y.b)
def __sub__(x, y):
return R5(x.a - y.a, x.b - y.b)
def __mul__(x, y):
return R5(x.a * y.a + x.b * y.b * 5, x.a * y.b + x.b * y.a)
def __pow__(x, power):
if power == 0:
return R5(1, 0)
elif power % 2 == 1:
return x * (x ** (power - 1))
else:
sq = x ** (power // 2)
return sq * sq
def __floordiv__(x, n):
n = mpz(n)
return R5(x.a // n, x.b // n)
def fib_bine(n):
return (R5(1, 1) ** n - R5(1, -1) ** n).b // mpz(2) ** n
from time import perf_counter
for i in range(1, 10):
print(i, fib_bine(i))
N = 100_000_000
st = perf_counter()
y = fib_bine(N)
en = perf_counter()
print(f'{en - st:.4}с')
# 1_000_000_000 — 81.16с
За O(1) вы не можете его даже напечатать или скопировать из памяти в память, потому что длина числа O(n).
Действительно. И время выполнения тестов у автора чуть больше, чем О(n) как раз и получается:
Тесты
n =10e8 0,6 секунд
n=10e9 7 ceкунд
n=10e10 73 секунды
Где же тут O(log n) !?
Ну, у автора в посте упомянуты "O(log n) операций над числами Фибоначчи", к нему претензий нет. А вот минимум двое минуснувших (один в карму даже не поленился) – показатель.
На самом деле тут O(n log n) получается суммарно. Грубая оценка O(n log^2 n): O(log n) длинных умножений, каждое из которых O(n log n), через FFT. Но они не все такие длинные же. Там в конце пара умножений длины n, потом пара длины n/2, потом пара n/4... В итоге получаем n log n + n/2 log(n/2) + ... и это все можно граничить сверху 2n log n.
А почему не рассматривали через матричные вычисления плюс быстрое возведение в степень?
А есть ли какое-нибудь практическое применение знанию миллиардного числа?
А теперь надо эти мегабайты-гигабайты как-то красиво визуализировать!
f3 = std::move(f6);
f2 = f6 - f4;Вот тут у вас UB. Нельзя f6 использовать после того, как вы оттуда сделали move.
Еще, в коде вы там используете fib_addone, когда как выше у вас определена неиспользуемая fib_next.
Советую перечитать весь код в статье и причесать его.
Кстати, раз уж вы с gmp работаете, было бы интересно сравнить ваше решение с встроенным в gmp: mpz_fib_ui
Интересно, что Python не уступает в скорости: 1 млрд - низкие 5 секунд :)
Код Python
import gmpy2
import time
def fib_next(f2, f1):
return f1, f2 + f1
def fib_double(f3, f2):
f6 = (f3 + f2 * 2) * f3
f4 = (f3 * 2 - f2) * f2
return f6, f6 - f4
def fib_get(N):
R = N % 2
N = (N + 1) // 2
a = gmpy2.mpz(1)
b = gmpy2.mpz(0)
i = N.bit_length() - 1
h = 1
for i in range(i - 1, -1, -1):
a, b = fib_double(a, b)
h *= 2
if N & (1 << i):
a, b = fib_next(a, b)
h += 1
if R:
a = a * a + b * b
else:
a = (a + b * 2) * a
return a
if __name__ == "__main__":
n = int(input("Enter the Fibonacci number: "))
start_time = time.time()
answer = fib_get(n)
end_time = time.time()
print(f"Calculation time: {end_time - start_time} seconds")
with open("answer.txt", "w") as f:
f.write(answer.digits(16)) # Запись числа в 16-ричной системе
print("Finish")
1 миллиард: 5.22 сек
Hidden text
10 миллиардов: 77.17 сек
Hidden text
И это на ноутбуке с довольно стареньким Core i9 8950HK и TDP 35W.
(off) Странно, но в статье не видно КДПВ и текста под ней, поэтому не получается через Ctrl-Enter отправить в личку сообщение об ошибке в тексте на заглавной.Очень глаз режет :peace:
Вот было бы здорово, если бы программисты писали эффективные программы не только на собеседованиях, но и на работе. А то вычислить за пять секунд миллиард чисел мы можем, а запустить какой-нибудь Фотошоп - нет.
100 миллионное число Фибоначчи считает за 0.589 секунды, и файл с ответом весит 17мб.
Миллиардное число Фибоначчи считает за 6.958 секунды, и файл с ответом весит 166мб.
10 миллиардное число Фибоначчи считает за 1 минуту 12.879 секунды, и файл с ответом весит 1.7гб.
Дальше мне стало страшно тестить...
А почему страшно? Для 100 миллиардного ~14 мин и ~17 Гб? )
Занятно, недавно наткнулся на похожее видео - https://www.youtube.com/watch?v=KzT9I1d-LlQ
интересно, а можно сделать незаконное число Фибоначчи?
Вычисляем миллиардное число Фибоначчи менее чем за 7 секунд