neizod's speculation

insufficient data for meaningful answer

คำนวณค่าฟีโบนัชชีอย่างเร็วด้วยเมทริกซ์

Friday, November 10, 2017, 01:49 PM

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

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

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

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

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

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

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

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

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

หรือสรุปได้สำหรับกรณีทั่วไปว่า

สำหรับ $k\in\mathbb{Z}^\ge$ และเมื่อแทน $n=3$ เข้าไป จะได้ว่า

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

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

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