Liczby Fibonacciego za pomocą potęgowania macierzy


Tematy pokrewne
Liczby Fibonacciego
Macierze
Podstawowe pojęcia dotyczące macierzy
Reprezentacja macierzy w pamięci komputera
Mnożenie macierzy przez skalar
Dodawanie macierzy
Transponowanie macierzy
Mnożenie macierzy
Potęgowanie macierzy
Liczby Fibonacciego
Eliminacja Gaussa
Eliminacja Gaussa-Crouta
Wyznacznik macierzy
Rozkład LU
Rozkład LU – rozwiązywanie układu równań liniowych
Rozkład LU – macierz odwrotna
Rozkład LU – wyznacznik macierzy

Problem

Wyznaczyć szybko n-tą liczbę ciągu Fibonacciego



 

Przypomnijmy, liczby Fibonacciego tworzą ciąg rekurencyjny:

 

F0 = 0
F1 = 1
Fn = Fn-2 + Fn-1, dla n > 1.

 

Ciąg ten jest następujący:

 

0 1 1 2 3 5 8 13 21 34 55 89 144 233 377 610 987 1597 ...

 

Za wyjątkiem pierwszych dwóch każda kolejna liczba Fibonacciego powstaje jako suma dwóch poprzednich. Liczby te posiadają dosyć duże znaczenie w różnych dziedzinach nauki, również w informatyce. Algorytm rekurencyjny obliczania liczb Fibonacciego posiada wykładniczą klasę złożoności obliczeniowej i nie nadaje się do poważniejszych zastosowań. Algorytm wykorzystujący programowanie dynamiczne ma już liniową klasę złożoności obliczeniowej. Zachodzi pytanie, czy nie istnieje lepszy sposób wyznaczania wartości tych liczb. Otóż istnieje i wykorzystuje potęgowanie macierzy. Korzystamy tutaj ze wzoru:

 

 

Ze wzoru wynika, iż podniesienie lewej macierzy do potęgi n-tej daje nam macierz, której wyrazy są liczbami Fibonacciego. Macierz po lewej stronie równania jest oznaczana zwykle literą Q i nosi nazwę macierzy Q Fibonacciego (ang. Fibonacci Q-matrix). Ponieważ macierz możemy podnieść do n-tej potęgi przy złożoności obliczeniowej O(logn), to również z taką samą złożonością możemy wyliczyć n-tą liczbę Fibonacciego. Praktycznie macierz wystarczy podnieść do potęgi n-1, wtedy w pierwszym wierszu i pierwszej kolumnie otrzymamy poszukiwaną n-tą liczbę Fibonacciego. Oczywiście ten sposób obliczania liczb Fibonacciego sprawdza się dla dużych n. Jednakże musisz pamiętać, że liczby Fibonacciego rosną szybko i standardowe typy danych mogą nie wystarczyć do przechowania ich wartości.

 

Algorytm obliczania n-tej liczby Fibonacciego za pomocą szybkiego potęgowania macierzy Q

Wejście
n  –  numer liczby Fibonacciego do obliczenia, n N
Wyjście:

Fn – wartość n-tej liczby Fibonacciego, Fn N

Elementy pomocnicze:
Q  –  macierz Q Fibonacciego o wymiarze 2 x 2, Q N
P  –  macierz pomocnicza o wymiarze 2 x 2, P N
W  – macierz wyniku potęgowania o wymiarze 2 x 2, W N
Lista kroków:
K01: Jeśli n < 2, to zakończ z wynikiem n ; dla n = 0, 1 liczba Fibonacciego ma wartość n
K02: Ustaw macierz Q  
K03: Ustaw macierz jednostkową w W  
K04: nn - 1 ; potrzebujemy potęgę n-1 macierzy Q
K05: Dopóki n > 0, wykonuj K06...K12 ; w pętli obliczamy potęgę n-1 Q
K06:     Jeśli n and 1 = 0, to idź do K09 ; testujemy kolejne bity n
K07     P W × Q ; jeśli bit jest ustawiony, to do W dołączamy Q
K08:     W P  
K09     nn shr 1 ; przesuwamy w prawo bity n
K10     Jeśli n = 0, to idź do K13  
K11:     P Q × Q ; wyznaczamy kolejny kwadrat Q
K12     Q P  
K13: Zakończ z wynikiem W[1,1]  

 

Program

Ważne:

Zanim uruchomisz program, przeczytaj wstęp do tego artykułu, w którym wyjaśniamy funkcje tych programów oraz sposób korzystania z nich.

 

Program wyświetla liczby Fibonacciego od F0 do F93. Kolejna liczba Fibonacciego F94 wykracza już poza zakres 64 bitowych liczb całkowitych. Ze względu na nieduży rozmiar macierzy Q, P i W nie tworzyliśmy dla nich tablic dwuwymiarowych. Również obliczenia są przeprowadzane bezpośrednio na elementach macierzy bez korzystania z pętli, co przyspiesza działanie programu.

 

Lazarus
// Obliczanie liczb Fibonacciego za pomocą potęgowania macierzy
// Data: 19.02.2012
// (C)2012 mgr Jerzy Wałaszek
//-------------------------------------------------------------

program fib_matrix;

// Oblicza n-tą liczbę Fibonacciego
//---------------------------------
function fibo(n : integer) : qword;
var
  q11,q12,q21,q22 : qword; // macierz Q
  p11,p12,p21,p22 : qword; // macierz P
  w11,w12,w21,w22 : qword; // macierz W
begin
  if n < 2 then  fibo := n
  else
  begin

    // ustawiamy macierz Q

    q11 := 1; q12 := 1;
    q21 := 1; q22 := 0;

    // w macierzy W tworzymy macierz jednostkową

    w11 := 1; w12 := 0;
    w21 := 0; w22 := 1;

    dec(n);      // będzie nam potrzebna n-1 potęga Q

    while n > 0 do
    begin

      if (n and 1) = 1 then
      begin

        // wykonujemy mnożenie P = W x Q

        p11 := w11*q11 + w12 * q21; p12 := w11*q12 + w12 * q22;
        p21 := w21*q11 + w22 * q21; p22 := w21*q12 + w22 * q22;

        // wynik przenosimy: W = P

        w11 := p11; w12 := p12;
        w21 := p21; w22 := p22;

      end;

      n := n shr 1;    // usuwamy z n sprawdzony bit

      if n = 0 then break;

      // podnosimy Q do kwadratu:  P = Q x Q

      p11 := q11*q11 + q12 * q21; p12 := q11*q12 + q12 * q22;
      p21 := q21*q11 + q22 * q21; p22 := q21*q12 + q22 * q22;

      // wynik przenosimy: Q = p

      q11 := p11; q12 := p12;
      q21 := p21; q22 := p22;

    end;

    fibo := w11;

  end;

end;

// Program główny
//---------------

var
  i : integer;

begin
  for i := 0 to 93 do writeln('F(',i,') = ',fibo(i));
end.
Code::Blocks
// Obliczanie liczb Fibonacciego za pomocą potęgowania macierzy
// Data: 19.02.2012
// (C)2012 mgr Jerzy Wałaszek
//-------------------------------------------------------------

#include <iostream>

using namespace std;

// Oblicza n-tą liczbę Fibonacciego
//---------------------------------
unsigned long long fibo(int n)
{
  unsigned long long q11,q12,q21,q22, // macierz Q
                     p11,p12,p21,p22, // macierz P
                     w11,w12,w21,w22; // macierz W

  if(n < 2) return n;

  // ustawiamy macierz Q

  q11 = q12 = q21 = 1;
  q22 = 0;

  // w macierzy W tworzymy macierz jednostkową

  w11 = w22 = 1;
  w12 = w21 = 0;

  n--;      // będzie nam potrzebna n-1 potęga Q

  while(n)
  {
     if(n & 1)
     {
       // wykonujemy mnożenie P = W x Q

       p11 = w11*q11 + w12 * q21; p12 = w11*q12 + w12 * q22;
       p21 = w21*q11 + w22 * q21; p22 = w21*q12 + w22 * q22;

       // wynik przenosimy: W = P

       w11 = p11; w12 = p12;
       w21 = p21; w22 = p22;

     }

     n >>= 1;    // usuwamy z n sprawdzony bit

     if(!n) break;

     // podnosimy Q do kwadratu:  P = Q x Q

     p11 = q11*q11 + q12 * q21; p12 = q11*q12 + q12 * q22;
     p21 = q21*q11 + q22 * q21; p22 = q21*q12 + q22 * q22;

     // wynik przenosimy: Q = p

     q11 = p11; q12 = p12;
     q21 = p21; q22 = p22;

  }

  return w11;
}

// Program główny
//---------------

int main()
{
  for(int i = 0; i < 94; i++) cout << "F(" << i << ") = " << fibo(i) << endl;
  return 0;
}
Free Basic
' Obliczanie liczb Fibonacciego za pomocą potęgowania macierzy
' Data: 19.02.2012
' (C)2012 mgr Jerzy Wałaszek
'-------------------------------------------------------------

' Oblicza n-tą liczbę Fibonacciego
'---------------------------------
Function fibo(n As Integer) As ULongInt

  Dim As Ulongint q11,q12,q21,q22,_ ' macierz Q
                  p11,p12,p21,p22,_ ' macierz P
                  w11,w12,w21,w22   ' macierz W

  If n < 2 Then Return n

  ' ustawiamy macierz Q

  q11 = 1: q12 = 1
  q21 = 1: q22 = 0

  ' w macierzy W tworzymy macierz jednostkową

  w11 = 1: w12 = 0 
  w21 = 0: w22 = 1 

  n -= 1      ' będzie nam potrzebna n-1 potęga Q

  While n 
    If (n And 1) = 1 Then

       ' wykonujemy mnożenie P = W x Q

       p11 = w11*q11 + w12 * q21: p12 = w11*q12 + w12 * q22
       p21 = w21*q11 + w22 * q21: p22 = w21*q12 + w22 * q22

       ' wynik przenosimy: W = P

       w11 = p11: w12 = p12
       w21 = p21: w22 = p22

    End If

    n Shr= 1    ' usuwamy z n sprawdzony bit

    If n = 0 then Exit While

    ' podnosimy Q do kwadratu:  P = Q x Q

    p11 = q11*q11 + q12 * q21: p12 = q11*q12 + q12 * q22
    p21 = q21*q11 + q22 * q21: p22 = q21*q12 + q22 * q22

    ' wynik przenosimy: Q = p

    q11 = p11: q12 = p12
    q21 = p21: q22 = p22

  Wend

  fibo = w11
End Function

' Program główny
'---------------

Dim i As Integer

For i = 0 To 93
  Print "F(";i;") = ";fibo(i)
Next

End
Wynik
F(0) = 0
F(1) = 1
F(2) = 1
F(3) = 2
F(4) = 3
F(5) = 5
F(6) = 8
F(7) = 13
F(8) = 21
F(9) = 34
F(10) = 55
F(11) = 89
F(12) = 144
F(13) = 233
F(14) = 377
F(15) = 610
F(16) = 987
F(17) = 1597
F(18) = 2584
F(19) = 4181
F(20) = 6765
F(21) = 10946
F(22) = 17711
F(23) = 28657
F(24) = 46368
F(25) = 75025
F(26) = 121393
F(27) = 196418
F(28) = 317811
F(29) = 514229
F(30) = 832040
F(31) = 1346269
F(32) = 2178309
F(33) = 3524578
F(34) = 5702887
F(35) = 9227465
F(36) = 14930352
F(37) = 24157817
F(38) = 39088169
F(39) = 63245986
F(40) = 102334155
F(41) = 165580141
F(42) = 267914296
F(43) = 433494437
F(44) = 701408733
F(45) = 1134903170
F(46) = 1836311903
F(47) = 2971215073
F(48) = 4807526976
F(49) = 7778742049
F(50) = 12586269025
F(51) = 20365011074
F(52) = 32951280099
F(53) = 53316291173
F(54) = 86267571272
F(55) = 139583862445
F(56) = 225851433717
F(57) = 365435296162
F(58) = 591286729879
F(59) = 956722026041
F(60) = 1548008755920
F(61) = 2504730781961
F(62) = 4052739537881
F(63) = 6557470319842
F(64) = 10610209857723
F(65) = 17167680177565
F(66) = 27777890035288
F(67) = 44945570212853
F(68) = 72723460248141
F(69) = 117669030460994
F(70) = 190392490709135
F(71) = 308061521170129
F(72) = 498454011879264
F(73) = 806515533049393
F(74) = 1304969544928657
F(75) = 2111485077978050
F(76) = 3416454622906707
F(77) = 5527939700884757
F(78) = 8944394323791464
F(79) = 14472334024676221
F(80) = 23416728348467685
F(81) = 37889062373143906
F(82) = 61305790721611591
F(83) = 99194853094755497
F(84) = 160500643816367088
F(85) = 259695496911122585
F(86) = 420196140727489673
F(87) = 679891637638612258
F(88) = 1100087778366101931
F(89) = 1779979416004714189
F(90) = 2880067194370816120
F(91) = 4660046610375530309
F(92) = 7540113804746346429
F(93) = 12200160415121876738
 


List do administratora Serwisu Edukacyjnego Nauczycieli I LO

Twój email: (jeśli chcesz otrzymać odpowiedź)
Temat:
Uwaga: ← tutaj wpisz wyraz  ilo , inaczej list zostanie zignorowany

Poniżej wpisz swoje uwagi lub pytania dotyczące tego rozdziału (max. 2048 znaków).

Liczba znaków do wykorzystania: 2048

 

W związku z dużą liczbą listów do naszego serwisu edukacyjnego nie będziemy udzielać odpowiedzi na prośby rozwiązywania zadań, pisania programów zaliczeniowych, przesyłania materiałów czy też tłumaczenia zagadnień szeroko opisywanych w podręcznikach.



   I Liceum Ogólnokształcące   
im. Kazimierza Brodzińskiego
w Tarnowie

©2017 mgr Jerzy Wałaszek

Dokument ten rozpowszechniany jest zgodnie z zasadami licencji
GNU Free Documentation License.