Tìm số Fibonacci bất kì

Nội dung


1. Giới thiệu bài toán

Đề bài nói lên tất cả, không có gì bí ẩn ở đây. Dãy số Fibonacci là dãy số mà số thứ \(n + 1\) trong dãy có giá trị bằng tổng của số thứ \(n\) và số thứ \(n - 1\): \(F_{n+1} = F_n + F_{n-1}\)

Với định nghĩa này thì ta có thể dễ dàng tìm số Fibonacci thứ \(n\) bất kì, nhưng với \(n\) cực lớn, ví dụ \(n = 1000000000\), thì cách này ngồi cộng tới Tết Congo quá. Chúng ta phải xài ma trận để tính lẹ. Trang Hackerrank có quẳng cho 1 cái link Wiki về công thức ma trận Fibonacci. Trước đó trong Congdongcviet mình đã có kinh qua Quora và tạm hiểu về cách tính bằng ma trận, hôm nay mình sẽ giải thích thêm về công thức này.

2. Tìm số Fibonacci bất kì bằng ma trận

Ta đã có công thức để tính số Fibonacci tiếp theo từ 2 số Fibonacci hiện tại, bây giờ ta thử viết công thức đó lại bằng ma trận:

$$ \begin{pmatrix} F_{n} \\ F_{n+1} \end{pmatrix} = \begin{pmatrix} ? & ? \\ ? & ? \\ \end{pmatrix} \begin{pmatrix} F_{n-1} \\ F_{n} \end{pmatrix} $$

Không có gì bí hiểm ở đây, nếu các bạn biết nhân ma trận thì có thể hiểu công thức này. Từ 2 số Fibonacci liên tục cho trước, lập một ma trận 2x1 (hoặc 1x2 nếu bạn muốn, ở đây mình lập 2x1). Bằng cách nhân với một ma trận 2x2 nào đó để ra cặp số Fibonacci tiếp theo. Rất dễ dàng tìm ra ma trận 2x2 đó:

$$ \begin{pmatrix} F_{n} \\ F_{n+1} \end{pmatrix} = \begin{pmatrix} 0 & 1 \\ 1 & 1 \\ \end{pmatrix} \begin{pmatrix} F_{n-1} \\ F_{n} \end{pmatrix} $$

Điều đáng kể ở đây là ta có thể tiếp tục phân tích \((F_{n-1} \hspace{6pt} F_n)^T\) theo \((F_{n-2} \hspace{6pt} F_{n-1})^T\) và tiếp tục cho tới khi chạm \((F_{0} \hspace{6pt} F_{1})^T\):

$$ \begin{align*} \begin{pmatrix} F_{n} \\ F_{n+1} \end{pmatrix} & = \begin{pmatrix} 0 & 1 \\ 1 & 1 \\ \end{pmatrix}^2 \begin{pmatrix} F_{n-2} \\ F_{n-1} \end{pmatrix} \\ & = \begin{pmatrix} 0 & 1 \\ 1 & 1 \\ \end{pmatrix}^3 \begin{pmatrix} F_{n-3} \\ F_{n-2} \end{pmatrix} \\ & \hspace{32pt} \vdots \\ & = \begin{pmatrix} 0 & 1 \\ 1 & 1 \\ \end{pmatrix}^n \begin{pmatrix} F_{0} \\ F_{1} \end{pmatrix} \\ & = A^n \begin{pmatrix} F_{0} \\ F_{1} \end{pmatrix} \end{align*} $$

Như vậy ta chỉ cần tính \(A^n\) là có thể tìm ra \(F_n\) bất kì. Và vì ta có \(A^x A^y = A^{x+y}\) nên ta có thể tính \(A^n\) thông qua đệ quy, chỉ tốn \(O(log n)\) phép nhân thay vì \(O(n)\) phép nhân. Cách này cho phép chúng ta tính \(F_n\) với \(n\) cực lớn, 1 tỷ, hoặc thậm chí 1 tỷ tỷ đều ngon lành cành đào:

$$ \begin{align*} A &= \begin{pmatrix} 0 & 1 \\ 1 & 1 \\ \end{pmatrix} \\ A^{2k} &= A^k A^k\\ A^{2k+1} &= A^k A^k A \end{align*} $$

Hoặc chúng ta cũng có thể phân tích \(n\) ra thành \(n = 2^a + 2^b + \cdots + 2^x\) hay biểu diễn \(n\) dưới dạng số nhị phân, từ đó suy ra \(A^n = A^{2^a} A^{2^b} \cdots A^{2^x}\). Ưu điểm của cách này là không cần đệ quy, chỉ cần lưu một mảng \(P = \{A^{2^0}, A^{2^1}, A^{2^2}, A^{2^3}, \cdots, A^{2^{31}}\}\) là đủ xài cho tất cả số \(n\) là số nguyên 32-bit.

Ví dụ: \(n = 69\). Biểu diễn \(n\) dưới dạng nhị phân ta có \(n = (1000101)_2\), hay \(n = 64 + 4 + 1 = 2^6 + 2^2 + 2^0\), suy ra \(A^n = A^{2^6} A^{2^2} A^{2^0} = P_6 P_2 P_0\). Chỉ cần 2 phép nhân là ta đã tìm ra \(A^{69}\). Siêu lẹ.

Theo cách này thì ta chỉ cần khoảng 30 phép nhân ma trận với \(n\) là số nguyên 32-bit để tính \(A^n\) bất kì, từ đó suy ra \(F_n\) bất kì, không cần phải tính tới vài tỷ phép cộng trong trường hợp xấu nhất nữa.

3. Tối ưu hóa phép nhân "ma trận"

Mỗi lần nhân ma trận 2x2 thì lại tốn 8 phép nhân, không phải là vấn đề lớn, nhưng chúng ta có thể tối ưu còn 4 phép nhân. Xét \(A^1, A^2, A^3, A^4\):

$$ \begin{align*} A^1 &= \begin{pmatrix} 0 & 1 \\ 1 & 1 \\ \end{pmatrix} \\ A^2 &= \begin{pmatrix} 1 & 1 \\ 1 & 2 \\ \end{pmatrix} \\ A^3 &= \begin{pmatrix} 1 & 2 \\ 2 & 3 \\ \end{pmatrix} \\ A^4 &= \begin{pmatrix} 2 & 3 \\ 3 & 5 \\ \end{pmatrix} \end{align*} $$

Ta thấy tất cả các ma trận đều có \(a_{1,2} = a_{2,1}\), và hơn hết là có cái gì đó rất lạ, dường như tất cả \(a_{i,j}\) thuộc dãy Fibonacci hết. Ma thuật gì đây?

Nếu bắt đầu từ \(A\) và viết nó lại thành:

$$ A = \begin{pmatrix} 0 & 1 \\ 1 & 1 \\ \end{pmatrix} = \begin{pmatrix} F_0 & F_1 \\ F_1 & F_2 \\ \end{pmatrix} $$

Ở đây ta xài \(F_1 = F_2 = 1\), không có gì bí hiểm. Thử nhân với \(A\) để tạo \(A^2\)

$$ \begin{align*} A^2 &= \begin{pmatrix} F_0 & F_1 \\ F_1 & F_2 \\ \end{pmatrix} \begin{pmatrix} 0 & 1 \\ 1 & 1 \\ \end{pmatrix} \\ &= \begin{pmatrix} F_1 & F_0 + F_1 \\ F_2 & F_1 + F_2 \\ \end{pmatrix} \\ &= \begin{pmatrix} F_1 & F_2 \\ F_2 & F_3 \\ \end{pmatrix} \end{align*} $$

Nếu cứ tiếp tục nhân \(A\) lần lượt thì đúng là các phần tử trong \(A^n\) đều thuộc dãy Fibonacci. Bạn có thể chứng minh quy nạp để bảo đảm tính đúng đắn với mọi \(n\). Như vậy ta có:

$$ A^n = \begin{pmatrix} F_{n-1} & F_{n} \\ F_{n} & F_{n+1} \\ \end{pmatrix} $$

Như vậy ta không cần lưu 4 số cho ma trận \(A^n\), mà chỉ cần 3 số là đủ, à không, vì 3 số này là 3 số Fibonacci liên tục, nên ta chỉ cần 2 số là đủ, vì số còn lại có thể dễ dàng tính được từ 2 số này. Ví dụ ta chọn 2 số đó là \(F_{n-1}\)\(F_n\), thì \(F_{n+1}\) có thể tính thông qua tổng của 2 số đã chọn.

Vì chỉ còn có 2 số thay vì 4 số, nên số phép tính để nhân \(A^x\) với \(A^y\) cũng sẽ giảm đi một nửa, hay từ 8 phép nhân còn 4 phép nhân. Thật vậy ta có:

$$ \begin{align*} A^x A^y &= \begin{pmatrix} F_{x-1} & F_{x} \\ F_{x} & F_{x+1} \\ \end{pmatrix} \begin{pmatrix} F_{y-1} & F_{y} \\ F_{y} & F_{y+1} \\ \end{pmatrix} \\ &= \begin{pmatrix} F_{x-1}F_{y-1} + F_{x}F_{y} \hspace{12pt} F_{x-1}F_{y} + F_{x}F_{y+1} \\ F_{x}F_{y-1} + F_{x+1}F_{y} \hspace{12pt} F_{x}F_{y} + F_{x+1}F_{y+1} \\ \end{pmatrix} \\ &= \begin{pmatrix} F_{x+y-1} & F_{x+y} \\ F_{x+y} & F_{x+y+1} \\ \end{pmatrix} \end{align*} $$

Ta chỉ cần quan tâm tới \(F_{x+y-1}\)\(F_{x+y}\):

$$ \begin{align*} F_{x+y-1} &= F_{x-1}F_{y-1} + F_{x}F_{y} \\ F_{x+y} &= F_{x-1}F_{y} + F_{x}F_{y+1} \\ &= F_{x-1}F_{y} + F_{x}(F_{y-1} + F_y) \\ &= F_{x-1}F_{y} + F_{x}F_{y-1} + F_{x}F_{y} \\ \end{align*} $$

Như vậy để tính \(A^x A^y\), ta chỉ cần tính 4 phép nhân là \(F_{x-1}F_{y-1}\), \(F_{x-1}F_{y}\), \(F_{x}F_{y-1}\), và \(F_{x}F_{y}\), với \(A^x\) lưu \(F_{x-1}\)\(F_x\), \(A^y\) lưu \(F_{y-1}\)\(F_y\).

Chuyển sang code C++14 (để tránh tràn số thì ta cần modulo một số nào đó):

using FiboPair = std::array<int64_t, 2>;

FiboPair operator*(const FiboPair& fx, const FiboPair& fy)
{
    int64_t xy = (fx[0] * fy[0]) % MOD; //F_{x-1}*F_{y-1}
    int64_t xY = (fx[0] * fy[1]) % MOD; //F_{x-1}*F_{y}
    int64_t Xy = (fx[1] * fy[0]) % MOD; //F_{x}  *F_{y-1}
    int64_t XY = (fx[1] * fy[1]) % MOD; //F_{x}  *F_{y}
    return { (xy + XY) % MOD, (xY + Xy + XY) % MOD };
}

Và tới đây thì có lẽ bạn đã hiểu tại sao mình ghi là "ma trận", vì "ma trận" này chỉ là một cặp số, hay chỉ là một nửa của ma trận 2x2.

4. Kết luận

Về phần code thực hành thì có lẽ mình cũng "dọn cỗ" tới tận răng rồi, chỉ cần thêm tí xíu mắm muối nữa là giải được bài toán. Hy vọng bài viết của mình đã giúp đỡ được các bạn phần lý thuyết khi gặp các bài toán liên quan tới số Fibonacci cực lớn.



Thảo luận

▲ Đầu trang