Проблема, конечно, в том, что после определенного момента это далеко не оптимально. Он эффективен, пока числа не слишком велики, но их длина растет со скоростью N*log(phi)/log(10), где N — N-е число Фибоначчи, а phi — золотое сечение ( (1 +sqrt(5))/2 ~ 1,6 ). Как оказалось, соотношение log(phi)/log(10) очень близко к 1/5. Таким образом, можно ожидать, что N-е число Фибоначчи будет состоять примерно из N/5 цифр.
Умножение матриц, черт возьми, умножение четных чисел, становится очень медленным, когда числа начинают состоять из миллионов или миллиардов цифр. Таким образом, вычисление F(100 000) заняло около 0,03 секунды (в Python), а F(1000 000) заняло примерно 5 секунд. Это вряд ли рост O(log(N)). По моей оценке, этот метод без улучшений оптимизирует вычисления только до уровня O( (log(N)) ^ (2.5)) или около того.
Вычисление миллиардного числа Фибоначчи с такой скоростью будет непомерно медленным (хотя оно будет состоять всего из ~ 1 000 000 000 / 5 цифр, поэтому оно легко умещается в 32-битной памяти). ).
Знает ли кто-нибудь реализацию или алгоритм, который позволил бы ускорить вычисления? Возможно, что-то, что позволило бы вычислить триллионное число Фибоначчи.
Для ясности: я не ищу приближения. Мне нужны точные вычисления (до последней цифры).
Редактировать 1: Я добавляю Код Python, показывающий, что я считаю алгоритмом O((log N) ^ 2.5)).
Код: Выделить всё
from operator import mul as mul
from time import clock
class TwoByTwoMatrix:
__slots__ = "rows"
def __init__(self, m):
self.rows = m
def __imul__(self, other):
self.rows = [[sum(map(mul, my_row, oth_col)) for oth_col in zip(*other.rows)] for my_row in self.rows]
return self
def intpow(self, i):
i = int(i)
result = TwoByTwoMatrix([[long(1),long(0)],[long(0),long(1)]])
if i >= 1
multiplier = TwoByTwoMatrix(self.rows)
while i > 0:
if i & 1:
result *= multiplier
multiplier *= multiplier # square it
i >>= 1
for j in xrange(k):
result *= result
return result
m = TwoByTwoMatrix([[0,1],[1,1]])
t1 = clock()
print len(str(m.intpow(100000).rows[1][1]))
t2 = clock()
print t2 - t1
t1 = clock()
print len(str(m.intpow(1000000).rows[1][1]))
t2 = clock()
print t2 - t1
Похоже, я не учел тот факт, что len(str(...)) внесет значительный вклад в общее время выполнения теста. Изменение тестов на
Код: Выделить всё
from math import log as log
t1 = clock()
print log(m.intpow(100000).rows[1][1])/log(10)
t2 = clock()
print t2 - t1
t1 = clock()
print log(m.intpow(1000000).rows[1][1])/log(10)
t2 = clock()
print t2 - t1
Поскольку M=[[0,1],[1,1]] в степени N равно [[F(N-2), F(N -1)], [F(N-1), F(N)]],
другим очевидным источником неэффективности было вычисление (0,1) и (1,0) элементов матрицы, как если бы они были отчетливыми. Это (и я перешел на Python3, но времена Python2.7 аналогичны):
Код: Выделить всё
class SymTwoByTwoMatrix():
# elments (0,0), (0,1), (1,1) of a symmetric 2x2 matrix are a, b, c.
# b is also the (1,0) element because the matrix is symmetric
def __init__(self, a, b, c):
self.a = a
self.b = b
self.c = c
def __imul__(self, other):
# this multiplication does work correctly because we
# are multiplying powers of the same symmetric matrix
self.a, self.b, self.c = \
self.a * other.a + self.b * other.b, \
self.a * other.b + self.b * other.c, \
self.b * other.b + self.c * other.c
return self
def intpow(self, i):
i = int(i)
result = SymTwoByTwoMatrix(1, 0, 1)
if i >= 1
multiplier = SymTwoByTwoMatrix(self.a, self.b, self.c)
while i > 0:
if i & 1:
result *= multiplier
multiplier *= multiplier # square it
i >>= 1
for j in range(k):
result *= result
return result
Чего и следовало ожидать. Он дает результаты на 45% быстрее для самого быстрого теста, и ожидается, что прирост должен асимптотически приближаться к
phi/(1+2*phi+phi*phi) ~ 23,6%.
Элемент (0,0) M^N на самом деле является N-2-м числом Фибоначчи:
Код: Выделить всё
for i in range(15):
x = m.intpow(i)
print([x.a,x.b,x.c])
Код: Выделить всё
[1, 0, 1]
[0, 1, 1]
[1, 1, 2]
[1, 2, 3]
[2, 3, 5]
[3, 5, 8]
[5, 8, 13]
[8, 13, 21]
[13, 21, 34]
[21, 34, 55]
[34, 55, 89]
[55, 89, 144]
[89, 144, 233]
[144, 233, 377]
[233, 377, 610]
И SymTwoByTwoMatrix, и lru_cache-of-F(2N)-and-F(2N-1) занимают примерно в 40 раз больше времени. вычислять каждый раз, когда N увеличивается в 10 раз. Я думаю, что это, возможно, связано с реализацией Python умножения длинных целых чисел. Я думаю, что умножение больших чисел и их сложение должны быть распараллеливаемы. Таким образом, многопоточное решение sub-O(N) должно быть возможным, хотя (как утверждает Дэниел Фишер в комментариях) решением F(N) является Theta(n).
Подробнее здесь: https://stackoverflow.com/questions/384 ... omputation
