بسم الله الرحمن الرحيم
Telah dibahas di post sebelumnya cara untuk menghitung bilangan Fibonacci dengan menggunakan Dynamic Programming aka DP. Sekarang kita menghadapi masalah lain yang lebih sulit. Jika kita diminta menentukan bilangan Fibonacci ke-20000000000 maka akan memakan waktu cukup lama jika kita menggunakan DP.
Maka ada pendekatan yang cukup menarik untuk menyelesaikan masalah ini, yaitu Divide and Conquer (DnC). Sekilas tentang DnC, intinya ada 3 tahap utama :
Untuk detil lebih jelas tentang DnC silahkan mencari sendiri di internet. Ada banyak contoh-contoh aplikasi DnC seperti quicksort, mergesort, binary search, dsb. Beberapa halaman yang disarankan :
\[ \left( \begin{array}{cc} 1 & 1 \\ 1 & 0 \end{array} \right) \left( \begin{array}{cc} F_{n+1} & F_n \\ F_n & F_{n-1} \end{array} \right) \] maka hasilnya akan menjadi \[ \left( \begin{array}{cc} F_{n+1}+F_n & F_{n-1}+F_n \\ F_{n+1} & F_n \end{array} \right) = \left( \begin{array}{cc} F_{n+2} & F_{n+1} \\ F_{n+1} & F_n \end{array} \right) \]
sesuai identitas Fibonacci yang telah dibahas di post sebelumnya. Coba perhatikan juga bahwa persamaan matrix di atas memberi kesan bahwa DP Fibonacci juga bisa dilakukan secara perkalian matrix\[ \left( \begin{array}{cc} 1 & 1 \\ 1 & 0 \end{array} \right) \left( \begin{array}{cc} F_{n+1} & F_n \\ F_n & F_{n-1} \end{array} \right) = \left( \begin{array}{cc} F_{n+2} & F_{n+1} \\ F_{n+1} & F_n \end{array} \right) \]
Lalu apa basisnya?
Ketika n=1, maka \(F_n=1\), \(F_{n-1}=0\), dan \(F_{n+1}=1\). Sehingga matrixnya menjadi \( \left( \begin{array}{cc} 1 & 1 \\ 1 & 0 \end{array} \right) \)
yang ternyata sama dengan matrix pengali yang telah digunakan sebelumnya. Maka kita bisa definisikan \[ P_n = \left( \begin{array}{cc} F_{n+1} & F_n \\ F_n & F_{n-1} \end{array} \right) \]
Sampai sini kita telah menurunkan persamaan matrix Fibonacci dengan pemangkatan matrix. Lalu kenapa kita harus mengubah bentuk DP perkalian matrix yang sebelumnya telah kita peroleh menjadi pemangkatan matrix?
Kita telah bahas sebelumnya kita ingin mencari cara yang lebih cepat dari DP untuk mencari bilangan Fibonacci. Jika kita menggunakan perkalian matrix, kita masih bergelut dengan kompleksitas yang sama (malah cenderung lebih lambat karena mengalikan elemen-elemen matrix dibutuhkan beberapa kali operasi).
Maka tujuan kita sebenarnya adalah mengubah bentuk DP menjadi bentuk DnC yang bisa dipecah menjadi dua bagian matrix yang relatif sama. Prinsipnya sama seperti pemangkatan bilangan dengan DnC. Dengan DnC kita bisa dapatkan :
\[ P_n = A^n = \left\{ \begin{array}{ll} \left( P_{n/2} \right)^2 & \mbox{,n genap} \\ A \left( P_{ \left\lfloor{ n/2 }\right\rfloor } \right)^2 & \mbox{,n ganjil} \end{array} \right. \]
Dan kompleksitas yang diharapkan dari algoritma ini
\[ T(n) = \left\{ \begin{array}{ll} 1 & \mbox{,n=1} \\ T \left( \left\lfloor{ \frac{n}{2} }\right\rfloor \right) +1 & \mbox{,n>1} \end{array} \right. \]
yang memiliki penyelesaian \(O(log N)\). Dengan kata lain algoritma ini tumbuh sebanding dengan logaritma dari N yang mana sangat lambat sehingga sangat efisien untuk masukan yang besar (jika belum mengerti tentang kompleksitas silahkan lihat halaman Ristek Fasilkom).
Implementasi yang saya buat kurang lebih seperti berikut :
Bila ada kekurangan dimohon kritik dan sarannya untuk perbaikan kita bersama. Terimakasih.
- Divide : membagi problem menjadi beberapa subproblem yang relatif sama (idealnya sama)
- Conquer : menyelesaikan tiap bagian subproblem secara independen
- Combine : menggabungkan solusi tiap subproblem menjadi solusi yang dicari
Untuk detil lebih jelas tentang DnC silahkan mencari sendiri di internet. Ada banyak contoh-contoh aplikasi DnC seperti quicksort, mergesort, binary search, dsb. Beberapa halaman yang disarankan :
- Ristek Fasilkom
- http://www.math.ucsd.edu/~pcompeau/Ch07_DnC_LinearSpaceAlignment_Edited.pdf
- Materi Kuliah Pak Rinaldi Munir
Fibonacci Matrix Form
Misal kita punya dua matrix yang dikalikan sebagai berikut
\[ \left( \begin{array}{cc} 1 & 1 \\ 1 & 0 \end{array} \right) \left( \begin{array}{cc} F_{n+1} & F_n \\ F_n & F_{n-1} \end{array} \right) \] maka hasilnya akan menjadi \[ \left( \begin{array}{cc} F_{n+1}+F_n & F_{n-1}+F_n \\ F_{n+1} & F_n \end{array} \right) = \left( \begin{array}{cc} F_{n+2} & F_{n+1} \\ F_{n+1} & F_n \end{array} \right) \]
sesuai identitas Fibonacci yang telah dibahas di post sebelumnya. Coba perhatikan juga bahwa persamaan matrix di atas memberi kesan bahwa DP Fibonacci juga bisa dilakukan secara perkalian matrix\[ \left( \begin{array}{cc} 1 & 1 \\ 1 & 0 \end{array} \right) \left( \begin{array}{cc} F_{n+1} & F_n \\ F_n & F_{n-1} \end{array} \right) = \left( \begin{array}{cc} F_{n+2} & F_{n+1} \\ F_{n+1} & F_n \end{array} \right) \]
Lalu apa basisnya?
Ketika n=1, maka \(F_n=1\), \(F_{n-1}=0\), dan \(F_{n+1}=1\). Sehingga matrixnya menjadi \( \left( \begin{array}{cc} 1 & 1 \\ 1 & 0 \end{array} \right) \)
yang ternyata sama dengan matrix pengali yang telah digunakan sebelumnya. Maka kita bisa definisikan \[ P_n = \left( \begin{array}{cc} F_{n+1} & F_n \\ F_n & F_{n-1} \end{array} \right) \]
dan
\[ A = \left( \begin{array}{cc} 1 & 1 \\ 1 & 0 \end{array} \right) \]
sehingga
\[ \begin{eqnarray*}
P_n & = & A.P_{n-1} \\ & = & A^n
\\ \left( \begin{array}{cc} F_{n+1} & F_n \\ F_n & F_{n-1} \end{array} \right)
& = & \left( \begin{array}{cc} 1 & 1 \\ 1 & 0 \end{array} \right)^n
\end{eqnarray*} \]
Divide and Conquer Matrix Exponential
Kita telah bahas sebelumnya kita ingin mencari cara yang lebih cepat dari DP untuk mencari bilangan Fibonacci. Jika kita menggunakan perkalian matrix, kita masih bergelut dengan kompleksitas yang sama (malah cenderung lebih lambat karena mengalikan elemen-elemen matrix dibutuhkan beberapa kali operasi).
Maka tujuan kita sebenarnya adalah mengubah bentuk DP menjadi bentuk DnC yang bisa dipecah menjadi dua bagian matrix yang relatif sama. Prinsipnya sama seperti pemangkatan bilangan dengan DnC. Dengan DnC kita bisa dapatkan :
\[ P_n = A^n = \left\{ \begin{array}{ll} \left( P_{n/2} \right)^2 & \mbox{,n genap} \\ A \left( P_{ \left\lfloor{ n/2 }\right\rfloor } \right)^2 & \mbox{,n ganjil} \end{array} \right. \]
Dan kompleksitas yang diharapkan dari algoritma ini
\[ T(n) = \left\{ \begin{array}{ll} 1 & \mbox{,n=1} \\ T \left( \left\lfloor{ \frac{n}{2} }\right\rfloor \right) +1 & \mbox{,n>1} \end{array} \right. \]
yang memiliki penyelesaian \(O(log N)\). Dengan kata lain algoritma ini tumbuh sebanding dengan logaritma dari N yang mana sangat lambat sehingga sangat efisien untuk masukan yang besar (jika belum mengerti tentang kompleksitas silahkan lihat halaman Ristek Fasilkom).
Implementasi yang saya buat kurang lebih seperti berikut :
long long fibonacci(int n)
{
long long fib[2][2]= {{1,1},{1,0}}, //matrix A
ret[2][2]= {{1,0},{0,1}}, //matrix result
//initialized with identity matrix
tmp[2][2]= {{0,0},{0,0}}; //temporary matrix
int i,j,k;
while(n)
{
// if n odd multiply [ret] with [A]
if (n&1) {
memset(tmp,0,sizeof tmp);
for(i=0; i<2; i++)
for(j=0; j<2; j++)
for(k=0; k<2; k++)
tmp[i][j]=(tmp[i][j]+ret[i][k]*fib[k][j]);
for(i=0; i<2; i++)
for(j=0; j<2; j++)
ret[i][j]=tmp[i][j];
}
memset(tmp,0,sizeof tmp); // clear tmp
// multiply [ret] with [ret]
for(i=0; i<2; i++)
for(j=0; j<2; j++)
for(k=0; k<2; k++)
tmp[i][j]=(tmp[i][j]+fib[i][k]*fib[k][j]);
for(i=0; i<2; i++)
for(j=0; j<2; j++)
fib[i][j]=tmp[i][j];
n/=2;
}
return (ret[0][1]);
}
Bila ada kekurangan dimohon kritik dan sarannya untuk perbaikan kita bersama. Terimakasih.