n-е число Фибоначчи в сублинейном времени

Question

Есть ли какой-нибудь алгоритм для вычисления n-го числа Фибоначчи за сублинейное время?

Answer 1

Вот одна строка, которая вычисляет F (n), используя целые числа размера O (n), в O (log n) арифметических операциях:

for i in range(1, 50):
    print(i, pow(2<<i, i, (4<<2*i)-(2<<i)-1)//(2<<i))

Разумно использовать целые числа размера O (n), поскольку это сопоставимо с размером ответа.

Чтобы понять это, пусть phi - золотое сечение (наибольшее решение для x ^ 2 = x + 1), а F (n) - n-ое число Фибоначчи, где F (0) = 0, F (1 ) = Р (2) = 1

Теперь phi ^ n = F (n-1) + F (n) phi.

Доказательство по индукции: phi ^ 1 = 0 + 1 * phi = F (0) + F (1) phi. И если фи ^ п = F (n-1) + F (n) фи, затем фи ^ (n + 1) = F (n-1) фи + F (n) фи ^ 2 = F (n-1) фи + F (n) (phi + 1) = F (n) + (F (n) + F (n-1)) phi = F (n) + F (n + 1) phi. Единственный сложный шаг в этом расчете - это тот, который заменяет фи ^ 2 на (1 + фи), что следует из-за того, что фи - это золотое сечение.

Также числа вида (a + b * phi), где a, b целые числа, замкнуты при умножении.

Доказательство: (p0 + p1 * phi) (q0 + q1 * phi) = p0q0 + (p0q1 + q1p0) phi + p1q1 * phi ^ 2 = p0q0 + (p0q1 + q1p0) phi + p1q1 * (phi + 1) = (p0q0 + p1q1) + (P0q1 + q1p0 + p1q1) * фита.

Используя это представление, можно вычислить phi ^ n в O (log n) целочисленных операциях, используя возведение в степень путем возведения в квадрат. Результатом будет F (n-1) + F (n) phi, из которого можно прочитать n-е число Фибоначчи.

def mul(p, q):
    return p[0]*q[0]+p[1]*q[1], p[0]*q[1]+p[1]*q[0]+p[1]*q[1]

def pow(p, n):
    r=1,0
    while n:
        if n&1: r=mul(r, p)
        p=mul(p, p)
        n=n>>1
    return r

for i in range(1, 50):
    print(i, pow((0, 1), i)[1])

Обратите внимание, что большая часть этого кода представляет собой стандартную функцию возведения в квадрат в квадрате.

Чтобы добраться до строки, начинающей этот ответ, можно заметить, что, представляя phi достаточно большим целым числом X, можно выполнить (a+b*phi)(c+d*phi) как целочисленную операцию (a+bX)(c+dX) modulo (X^2-X-1). Затем функцию pow можно заменить стандартной функцией Python pow (которая обычно включает в себя третий аргумент z, который вычисляет результат по модулю z. Выбранный X равен 2<<i.

Answer 2

Вы можете использовать странное уравнение квадратного корня, чтобы получить точный ответ. Причина в том, что $ \ sqrt (5) $ выпадает в конце, вам просто нужно отслеживать коэффициенты с вашим собственным форматом умножения.

def rootiply(a1,b1,a2,b2,c):
    ''' multipy a1+b1*sqrt(c) and a2+b2*sqrt(c)... return a,b'''
    return a1*a2 + b1*b2*c, a1*b2 + a2*b1

def rootipower(a,b,c,n):
    ''' raise a + b * sqrt(c) to the nth power... returns the new a,b and c of the result in the same format'''
    ar,br = 1,0
    while n != 0:
        if n%2:
            ar,br = rootiply(ar,br,a,b,c)
        a,b = rootiply(a,b,a,b,c)
        n /= 2
    return ar,br

def fib(k):
    ''' the kth fibonacci number'''
    a1,b1 = rootipower(1,1,5,k)
    a2,b2 = rootipower(1,-1,5,k)
    a = a1-a2
    b = b1-b2
    a,b = rootiply(0,1,a,b,5)
    # b should be 0!
    assert b == 0
    return a/2**k/5

if __name__ == "__main__":
    assert rootipower(1,2,3,3) == (37,30) # 1+2sqrt(3) **3 => 13 + 4sqrt(3) => 39 + 30sqrt(3)
    assert fib(10)==55

Answer 3

Арифметика с фиксированной точкой является неточной. Код C # Джейсона дает неправильный ответ для n = 71 (308061521170130 вместо 308061521170129) и далее

Для правильного ответа используйте систему вычислительной алгебры. Sympy - это такая библиотека для Python. Там есть интерактивная консоль на http://live.sympy.org/. Скопируйте и вставьте эту функцию

phi = (1 + sqrt(5)) / 2
def f(n):
    return floor(phi**n / sqrt(5) + 1/2)

Тогда рассчитайте

>>> f(10)
55

>>> f(71)
308061521170129

Вы можете попробовать проверить phi.

Answer 4

см. Алгоритм разделяй и властвуй здесь

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