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

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

73 голоса | спросил Biswajyoti Das 6 +04002009-10-06T17:16:48+04:00312009bEurope/MoscowTue, 06 Oct 2009 17:16:48 +0400 2009, 17:16:48

12 ответов


0

n число Фибоначчи задается как

f(n) = Floor(phi^n / sqrt(5) + 1/2) 

где

phi = (1 + sqrt(5)) / 2

Предполагая, что примитивные математические операции (+, -, * и /) являются O(1), вы можете использовать этот результат для вычисления n число Фибоначчи за O(log n) время (O(log n) из-за возведения в степень в формуле).

В C #:

static double inverseSqrt5 = 1 / Math.Sqrt(5);
static double phi = (1 + Math.Sqrt(5)) / 2;
/* should use 
   const double inverseSqrt5 = 0.44721359549995793928183473374626
   const double phi = 1.6180339887498948482045868343656
*/

static int Fibonacci(int n) {
    return (int)Math.Floor(Math.Pow(phi, n) * inverseSqrt5 + 0.5);
}
ответил jason 6 +04002009-10-06T17:20:18+04:00312009bEurope/MoscowTue, 06 Oct 2009 17:20:18 +0400 2009, 17:20:18
0

Исходя из ссылки Пиллси на возведение в степень матрицы, так что для матрицы

 M  = [1 1]
    [1 0]

тогда

 fib  ( n ) =  M   n  1,2 

Повышение матриц до степеней с помощью повторного умножения не очень эффективно.

Два подхода к возведению в матрицу - разделяй и властвуй, что приводит к M n в O ( ln n ) шаги, или разложение по собственным значениям, которое является постоянным временем, но может вносить ошибки из-за ограниченной точности с плавающей запятой.

Если вы хотите, чтобы точное значение превышало точность вашей реализации с плавающей запятой, вы должны использовать подход O (ln n), основанный на этом отношении:

 M   n   = ( M   n  /2 )  2 , если  n  четный
   =  M  ·  M   n  -1 , если  n  нечетное

Разложение по собственным значениям на M находит две матрицы U и Λ , такие что Λ диагональна и

 M  =  U   Λ   U   -1  M   n  = ( U   Λ   U   -1 )  п 
    =  U   Λ   U   -1  U   Λ   U   -1  U   Λ   U   -1  ... п раз
    =  U   Λ   Λ   Λ  ...  U   -1 
    =  U   Λ   n  U   -1 
Повышение диагональной матрицы Λ до степени n является простым делом повышения каждого элемента в Λ до значения n th, так что это дает O (1) метод повышения M до n -го уровня. Однако значения в Λ вряд ли будут целыми числами, поэтому возникнет некоторая ошибка.

Определение Λ для нашей матрицы 2x2 как

 Λ  = [λ  1  0]
  = [0 λ  2 ]

Чтобы найти каждое λ , мы решаем

|  M  - λ  I  | = 0

который дает

|  M  - λ  I  | = -λ (1 - λ) - 1

λ² - λ - 1 = 0

используя квадратную формулу

λ = (-b ± √ (b² - 4ac)) /2a
     = (1 ± √5) /2
 {λ  1 , λ  2 } = {Φ, 1-Φ}, где Φ = (1 + √5) /2

Если вы прочитали ответ Джейсона, вы сможете увидеть, куда это пойдет.

Решение для собственных векторов X 1 и X 2 :

если  X   1  = [ X   1,1 ,  X   1 , 2 ]

  M .  X   1 1  = λ  1  X   1  X   1,1  +  X   1,2  = λ  1  X   1,1  X   1,1  = λ  1  X   1,2 суб>

= >
  X   1  = [Φ, 1]
  X   2  = [1-Φ, 1]

Эти векторы дают U :

 U  = [ X   1,1 ,  X   2,2 ]
    [ X   1,1 ,  X   2,2 ]

  = [Φ, 1-Φ]
    [1, 1]

Инвертирование U с использованием

 A  = [a b]
      [  CD ]
= >
 A   -1  = (1 /|  A  |) [d -b]
                   [-c a]

поэтому U -1 задается как

 U   -1  = (1 /(Φ - (1 - Φ)) [1 Φ-1]
                               [-1 Φ]
 U   -1  = (√5)  -1  [1 Φ-1]
               [-1 Φ]

Проверка работоспособности:

 UΛU   -1  = (√5)  -1  [Φ 1-Φ]. [Φ 0]. [1 Φ-1]
                     [1 1] [0 1-Φ] [-1 Φ]

пусть Ψ = 1-Φ, другое собственное значение

поскольку Φ является корнем λ²-λ-1 = 0
поэтому -ΨΦ = Φ²-Φ = 1
и Ψ + Φ = 1

 UΛU   -1  = (√5)  -1  [Φ Ψ]. [Φ 0]. [1 -Ψ]
                 [1 1] [0 Ψ] [-1 Φ]

       = (√5)  -1  [Φ Ψ]. [Φ -ΨΦ]
                 [1 1] [-Ψ ΨΦ]

       = (√5)  -1  [Φ Ψ]. [Φ 1]
                 [1 1] [-Ψ -1]

       = (√5)  -1  [Φ²-Ψ² Φ-Ψ]
                  [Φ-Ψ 0]

       = [Φ + Ψ 1]
         [1 0]

       = [1 1]
         [1 0]

       =  M 

Итак, проверка работоспособности выполняется.

Теперь у нас есть все, что нам нужно для вычисления M n 1,2 :

 M   n   =  U   Λ   n   U   1 
   = (√5)  -1  [Φ Ψ]. [Φ  n   0]. [1 -Ψ]
              [1 1] [0 sup  n  ] [-1 Φ]

   = (√5)  -1  [Φ Ψ]. [Φ  n   -ΨΦ  n  ]
              [1 1] [-Ψ  n   Ψ  n   Φ]

   = (√5)  -1  [Φ Ψ]. [Φ  n   Φ  n  -1 ]
              [1 1] [-Ψ  n   n  -1 ] при ΨΦ = -1

   = (√5)  -1  n  +1  n  +1  Φ  n   n  ]
              [Φ  n   n   Φ  n  -1  n  -1 ]

так

  fib  ( n ) =  M   n   1,2 к югу>
        = (Φ  n   - (1-Φ)  n  ) /√5

Что согласуется с формулой, приведенной в другом месте.

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

ответил Pete Kirkham 6 +04002009-10-06T21:00:58+04:00312009bEurope/MoscowTue, 06 Oct 2009 21:00:58 +0400 2009, 21:00:58
0

Если вам нужно точное число (которое является "bignum", а не int /float), то я боюсь, что

Это невозможно!

Как указано выше, формула для чисел Фибоначчи:

  

fib n = floor (phi n /√5 + 1 / 2 )

     

fib n ~ = phi n /√5

Сколько цифр fib n?

  

numDigits (fib n) = log (fib n) = log (phi n /√5) = log phi n - log √5 = n * log phi - журнал √5

     

numDigits (fib n) = n * const + const

     

это O ( n )

Поскольку запрошенный результат имеет значение O ( n ), его нельзя вычислить менее чем за O ( n ) время.

Если вам нужны только нижние цифры ответа, то можно рассчитать в сублинейном времени, используя метод возведения в степень матрицы.

ответил yairchu 11 +04002009-10-11T12:54:09+04:00312009bEurope/MoscowSun, 11 Oct 2009 12:54:09 +0400 2009, 12:54:09
0

Одно из упражнений в SICP об этом, ответ на который описан здесь.

В императивном стиле программа будет выглядеть примерно так

 Функция   Fib  ( count )
     а  ← 1
     B  ← 0
     P  ← 0
     Q  ← 1

     Пока   count > 0  Делать 
         Если  Четный ( count )  Тогда 
              p  p  ² +  q  ²
              q  ← 2  pq  +  q  ²
              count  count  ÷ 2
         Else 
              a  bq  +  aq  +  ap 
              b  bp  +  aq 
              считать  считать  - 1
         End If 
     Конец пока 

     Возврат   b 
 Конечная функция 
ответил Nietzche-jou 6 +04002009-10-06T18:45:25+04:00312009bEurope/MoscowTue, 06 Oct 2009 18:45:25 +0400 2009, 18:45:25
0

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

    / 1  1 \
M = |      |
    \ 1  0 /

тогда (M^n)[1, 2] будет равно n число Фибоначчи, если [] является индексом матрицы и ^ - матричное возведение в степень. Для матрицы фиксированного размера возведение в степень с положительной интегральной степенью может быть выполнено за O (log n) времени так же, как с действительными числами.

РЕДАКТИРОВАТЬ: . Конечно, в зависимости от типа ответа, который вы хотите, вы можете использовать алгоритм с постоянным временем. Как и в других формулах, число n -го числа Фибоначчи экспоненциально растет с n. Даже с 64-разрядными целыми числами без знака вам понадобится только таблица поиска из 94 записей, чтобы охватить весь диапазон.

ВТОРОЕ РЕДАКТИРОВАНИЕ: Выполнение экспоненциальной матрицы с собственным разложением в первую очередь точно эквивалентно решению JDunkerly, приведенному ниже. Собственными значениями этой матрицы являются (1 + sqrt(5))/2 и (1 - sqrt(5))/2.

ответил Pillsy 6 +04002009-10-06T17:46:38+04:00312009bEurope/MoscowTue, 06 Oct 2009 17:46:38 +0400 2009, 17:46:38
0

Википедия имеет закрытое решение http://en.wikipedia.org/wiki/Fibonacci_number

Или в c #:

    public static int Fibonacci(int N)
    {
        double sqrt5 = Math.Sqrt(5);
        double phi = (1 + sqrt5) / 2.0;
        double fn = (Math.Pow(phi, N) - Math.Pow(1 - phi, N)) / sqrt5;
        return (int)fn;
    }
ответил JDunkerley 6 +04002009-10-06T17:18:35+04:00312009bEurope/MoscowTue, 06 Oct 2009 17:18:35 +0400 2009, 17:18:35
0

Для действительно больших, эта рекурсивная функция работает. Используются следующие уравнения:

F(2n-1) = F(n-1)^2 + F(n)^2
F(2n) = (2*F(n-1) + F(n)) * F(n)

Вам нужна библиотека, которая позволяет работать с большими целыми числами. Я использую библиотеку BigInteger из https://mattmccutchen.net/bigint/.

Начните с массива чисел Фибоначчи. Используйте fibs [0] = 0, fibs [1] = 1, fibs [2] = 1, fibs [3] = 2, fibs [4] = 3 и т. Д. В этом примере я использую массив первых 501 (считая 0). Вы можете найти первые 500 ненулевых чисел Фибоначчи здесь: http://home.hiwaay.net /~jalison/Fib500.html . Требуется небольшое редактирование, чтобы перевести его в правильный формат, но это не так уж сложно.

Затем вы можете найти любое число Фибоначчи, используя эту функцию (в C):

BigUnsigned GetFib(int numfib)
{
int n;
BigUnsigned x, y, fib;  

if (numfib < 501) // Just get the Fibonacci number from the fibs array
    {
       fib=(stringToBigUnsigned(fibs[numfib]));
    }
else if (numfib%2) // numfib is odd
    {
       n=(numfib+1)/2;
       x=GetFib(n-1);
       y=GetFib(n);
       fib=((x*x)+(y*y));
    }
else // numfib is even
    {
       n=numfib/2;
       x=GetFib(n-1);
       y=GetFib(n);
       fib=(((big2*x)+y)*y);
   }
return(fib);
}

Я проверил это для 25 000-го числа Фибоначчи и тому подобное.

ответил user3137939 27 FriEurope/Moscow2013-12-27T02:43:35+04:00Europe/Moscow12bEurope/MoscowFri, 27 Dec 2013 02:43:35 +0400 2013, 02:43:35
0

Вот моя рекурсивная версия, которая рекурсирует log (n) раз. Я думаю, что проще всего читать в рекурсивной форме:

def my_fib(x):
  if x < 2:
    return x
  else:
    return my_fib_helper(x)[0]

def my_fib_helper(x):
  if x == 1:
    return (1, 0)
  if x % 2 == 1:
    (p,q) = my_fib_helper(x-1)
    return (p+q,p)
  else:
    (p,q) = my_fib_helper(x/2)
    return (p*p+2*p*q,p*p+q*q)

Это работает, потому что вы можете вычислить fib(n),fib(n-1), используя fib(n-1),fib(n-2) если n нечетное, а n четное, вы можете вычислить fib(n),fib(n-1), используя fib(n/2),fib(n/2-1)

Базовый случай и нечетный случай просты. Чтобы вывести четный случай, начните с a, b, c как последовательных значений Фибоначчи (например, 8,5,3) и запишите их в матрицу с a = b + c. Примечание:

[1 1] * [a b]  =  [a+b a]
[1 0]   [b c]     [a   b]

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

      n
[1 1]   =  [fib(n+1) fib(n)  ]
[1 0]      [fib(n)   fib(n-1)]

Итак:

      2n                        2
[1 1]    =  [fib(n+1) fib(n)  ]
[1 0]       [fib(n)   fib(n-1)]

Упрощение правой части приводит к четному случаю.

ответил Eyal 10 J0000006Europe/Moscow 2014, 18:26:44
0

используя R

l1 <- (1+sqrt(5))/2
l2 <- (1-sqrt(5))/2

P <- matrix(c(0,1,1,0),nrow=2) #permutation matrix
S <- matrix(c(l1,1,l2,1),nrow=2)
L <- matrix(c(l1,0,0,l2),nrow=2)
C <- c(-1/(l2-l1),1/(l2-l1))

k<-20 ; (S %*% L^k %*% C)[2]
[1] 6765
ответил George Dontas 17 J000000Saturday10 2010, 16:16:39
0

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

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

ответил Chinmay Lokesh 7 AM000000100000002831 2013, 10:12:28
0

Арифметика с фиксированной точкой является неточной. Код 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.

ответил Colonel Panic 7 PM00000020000005031 2013, 14:40:50
0

Вот строковая строка, которая вычисляет 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])

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

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

ответил Paul Hankin 7 Maypm18 2018, 12:08:50

Похожие вопросы

Популярные теги

security × 330linux × 316macos × 2827 × 268performance × 244command-line × 241sql-server × 235joomla-3.x × 222java × 189c++ × 186windows × 180cisco × 168bash × 158c# × 142gmail × 139arduino-uno × 139javascript × 134ssh × 133seo × 132mysql × 132