1, 1, 2, 3, 5, 8, 13, 21, 34, 55, … แม้ว่าหลายคนจะไม่ถนัดคณิตศาสตร์และการคำนวณ แต่ก็น่าจะคุ้นเคยกับตัวเลขชุดนี้ที่ใครต่อใครต่างชมว่าเป็นรากฐานความงามในธรรมชาติอย่างแน่นอน หลักการคำนวณลำดับตัวเลขดังกล่าวก็อธิบายได้ไม่ยุ่งยากแต่อย่างใด “เมื่อต้องการคำนวณหาตัวเลขถัดไปในลำดับ ให้นำตัวเลขสองตัวก่อนหน้ามาบวกกัน (โดยกำหนดให้เลขสองตัวแรกในลำดับคือ 1)”

หรือเขียนเป็นสมการคณิตศาสตร์ได้เป็น

\[F_n = F_{n-1} + F_{n-2}\]

เมื่อ $F_n$ คือค่าของตัวเลขฟีโบนัชชีตำแหน่งที่ $n$ โดยมี $F_1=1$ และ $F_2=1$

ถึงตรงนี้ถ้าใครเรียนวิทยาการคอมพิวเตอร์มา ควรคุ้นหน้าคุ้นตาว่าการคำนวณข้างต้นใช้เทคนิคการเรียกตัวเองนั่นเอง แต่ถ้านำไปเขียนโปรแกรมตรงๆ ก็คงคำนวณได้ไม่ไกล เพราะการคำนวณค่าฟีโบนัชชีตำแหน่งสูงๆ จะเสียเวลาไปกับการคำนวณค่าตำแหน่งก่อนหน้าซ้ำเรื่อยๆ จนทำให้เวลาที่ใช้พุ่งสูงเป็น $O(2^n)$ ปัญหานี้สามารถแก้ได้ด้วยเทคนิคกำหนดการพลวัต คือ จดค่าในลำดับทั้งหมดที่เคยคำนวณเก็บไว้ เมื่อต้องการนำค่าเดิมมาใช้คำนวณค่าถัดไป ก็แค่เรียกค่าที่เคยจดไว้มาใช้ได้เลยโดยไม่ต้องคำนวณซ้ำอีก เทคนิคนี้สามารถลดเวลาได้เหลือ $O(n)$

แล้วเราสามารถทำให้การคำนวณค่าฟีโบนัชชีเร็วขึ้นได้หรือไม่?

หากต้องการลำดับฟีโบนัชชีทั้งลำดับ (ไล่มาตั้งแต่ตัวแรกจนถึงตำแหน่งที่สนใจ) การใช้กำหนดการพลวัตข้างต้นก็เหมาะสมกับการคำนวณอยู่แล้ว

แต่ถ้าเราต้องการค่าฟีโบนัชชีตำแหน่งที่ $n$ เพียงตัวเดียว โดยไม่สนใจค่าฟีโบนัชชีที่ตำแหน่งอื่นๆ เลย เราจะสามารถเร่งความเร็วการคำนวณได้โดยนำเมทริกซ์เข้ามาช่วย วิธีคิดหาสูตรที่สำหรับคำนวณก็มีอยู่หลากหลายวิธี ในที่นี้จะเสนอวิธีการคูณเมทริกซ์กับเวกเตอร์ (ซึ่งมีข้อดีคือสามารถนำหลักการนี้ไปประยุกต์ใช้กับลำดับที่นิยามด้วยการเรียกตัวเองในทำนองเดียวกันได้) โดยเริ่มจากการเขียนค่าฟีโบนัชชีตำแหน่งต่างๆ ให้อยู่ในรูปของเวกเตอร์ที่ถูกคูณด้วยเมทริกซ์ ดังนี้

\[\mathbf{M} \begin{bmatrix} F_{n-1} \\ F_{n-2} \end{bmatrix} = \begin{bmatrix} F_{n} \\ F_{n-1} \end{bmatrix}\]

โดยที่ $\mathbf{M}$ คือเมทริกซ์มิติ $2\times2$ ที่เราต้องการหาเพื่อให้สมการข้างต้นเป็นจริง ซึ่งเมื่อนำไปพิจารณาด้วยสมการดั้งเดิมในตอนต้นของบทความนี้แล้ว จะหาคำตอบได้ไม่ยากว่า

\[\mathbf{M} = \begin{bmatrix} 1 & 1 \\ 1 & 0 \end{bmatrix}\]

แต่ส่วนที่เป็นหัวใจสำคัญที่ของสมการนี้ อยู่ที่รูปแบบการเรียงค่าฟีโบนัชชีในเวกเตอร์ทั้งทางซ้ายและขวามือของสมการ เราจึงสามารถนำผลลัพธ์มาคำนวณต่อเนื่องได้ ดังตัวอย่างนี้

\[\mathbf{M}^2 \begin{bmatrix} F_{n-1} \\ F_{n-2} \end{bmatrix} = \mathbf{M} \begin{bmatrix} F_{n} \\ F_{n-1} \end{bmatrix} = \begin{bmatrix} F_{n+1} \\ F_{n} \end{bmatrix}\]

หรือสรุปได้เป็นกรณีทั่วไปสำหรับทุก $k\in\mathbb{N}$ ว่า

\[\mathbf{M}^k \begin{bmatrix} F_{n-1} \\ F_{n-2} \end{bmatrix} = \begin{bmatrix} F_{n-1+k} \\ F_{n-2+k} \end{bmatrix}\]

สูตรนี้ก็สวยแล้ว แต่เรายังใช้งานมันให้สุดทางกว่านี้อีก ตอนนี้เราจะกำจัด $n$ โดยการแทน $n=3$ เข้าไป

\[\mathbf{M}^k \begin{bmatrix} F_2 \\ F_1 \end{bmatrix} = \mathbf{M}^k \begin{bmatrix} 1 \\ 1 \end{bmatrix} = \begin{bmatrix} 1 & 1\\ 1 & 0 \end{bmatrix}^k \begin{bmatrix} 1 \\ 1 \end{bmatrix} = \begin{bmatrix} F_{k+2} \\ F_{k+1} \end{bmatrix}\]

เปลี่ยนชื่อตัวแปร $k$ กลับมาเป็น $n$ เพื่อความสวยงาม จึงสรุปสมการดังกล่าวได้ดังนี้

\[\begin{bmatrix} F_{n+1} \\ F_n \end{bmatrix} = \begin{bmatrix} 1 & 1\\ 1 & 0 \end{bmatrix}^{n-1} \begin{bmatrix} 1 \\ 1 \end{bmatrix}\]

สังเกตว่าส่วนที่กินเวลาการคำนวณมากที่สุดในสมการดังกล่าว คือการยกกำลังของเมทริกซ์ ซึ่งมีเทคนิคมากมายมาช่วยลดจำนวนการคูณที่ต้องทำ เช่น จับคู่เพียงพจน์ที่เหมือนกันมาคูณกัน แล้วแทนค่าคู่พจน์อื่นๆ ที่เหมือนกันด้วยค่าที่เพิ่งคำนวณไป จึงลดเหลือเวลาเพียง $O(\log n)$

ป.ล. หากรู้สึกว่าสมการข้างต้นยังสวยไม่พอ ฝาการบ้านกลับไปคิดต่อจนจัดสมการได้เป็นรูปนี้ดู

\[\begin{bmatrix} F_{n+1} & F_n \\ F_n & F_{n-1} \end{bmatrix} = \begin{bmatrix} 1 & 1\\ 1 & 0 \end{bmatrix}^n\]