การหาค่าลำดับ Fibonacci

Image from https://cutewallpaper.org/

โจทย์การเขียนโปรแกรมพื้นฐานที่มักจะได้เห็นกันโดยทั่วไป คือ การให้เขียนโปรแกรมหาค่าลำดับฟีโบนัชชี ซึ่งก็มีหลายวิธีในการหาค่าออกมา แต่ก่อนอื่น มารู้จักลำดับฟีโบนัชชี กันก่อน
ลำดับฟีโบนัชชี(Fibonacci) คือ ชุดตัวเลขดังนี้ 1, 1, 2, 3, 5, 8, 13, …
โดยที่เลขตัวแรก และ ตัวที่สอง เท่ากับ 1 ตั้งแต่ตัวที่ 3 เป็นต้นไป คือ
F(n) = F(n-1) + F(n-2)
หรือ พูดง่าย ๆ คือ ตั้งแต่ตัวที่ 3 เป็นต้นไป ให้เอาเลขก่อนหน้า 2 ตัว บวกกัน เช่น ตัวที่ 5 มีค่าเท่ากับ 5 เกิดจาก 2+3 , ตัวที่ 7 มีค่าเท่ากับ13 เกิดจาก 5+8 เป็นแบบนี้ไปเรื่อย ๆ

ในบทความนี้จะแสดงตัวอย่างอัลกอริทึมวิธีการหาค่าลำดับฟีโบนัชชี ดังนี้

วิธีที่ 1 : Recursive

# Recursive
def fibo_recursive(n):
    if n <= 2:
        return 1
    else :
        return fibo_recursive(n-1)+fibo_recursive(n-2)
print(fibo_recursive(7)) # 13

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

Image by Author

จากรูปจะเห็นว่าต้องมีการคำนวณซ้ำสิ่งที่เคยคำนวณไปแล้วอยู่หลายครั้ง(node ที่เป็นวงกลมสีฟ้า)

วิธีที่ 2 : เขียนแบบ Memoization

# Memoization
def fibo_memo(n) :
    if n not in memo :
        memo[n] = fibo_memo(n-1) + fibo_memo(n-2)
    return memo[n]
memo = {1:1,2:1}
print(fibo_memo(7))     # 13
print(memo)             # {1: 1, 2: 1, 3: 2, 4: 3, 5: 5, 6: 8, 7: 13}
# ใช้ได้แค่ ถึง 1026 ตั้งแต่ 1027 จะ error

จาก code ด้านบนปรับปรุงจากวิธี recursive คือ หากค่าใดทำการคำนวณไปแล้วก็ให้เก็บผลลัพธ์นั้นไว้ หากต้องคำนวณค่าเดิมอีกก็ให้เอาผลลัพธ์ที่เก็บไว้มาใช้ได้เลย

Image by Author

ดังรูปจะเห็นว่าสามารถตัดการทำงานที่ซ้ำเดิมออกไปได้ในปริมาณมากทำให้โปรแกรมทำงานได้เร็วขึ้นมาก

จากโปรแกรมจะเห็นว่าเราทำการเขียนให้เก็บผลลัพธ์จากการคำนวณเอง ทั้งนี้ในภาษา Python จะมี Decorator ที่จะจัดการเรื่อง Memoization ให้ ดังนี้

# Recursive + lru_caache = Memoization
import functools
@functools.lru_cache(None)
def fibo_recursive(n):
    if n <= 2:
        return 1
    else :
        return fibo_recursive(n-1)+fibo_recursive(n-2)
print(fibo_recursive(7))    # 13
# ใชได้ถึง 513 ตั้งแต่ 514 จะ error

จาก code ด้านบนจะเห็นว่าเราทำการเพิ่ม 2 บรรทัด คือ import functool และ @functools.lru_cache(None) จาก code โปรแกรม Recursive
แต่เทคนิคนี้หากต้องการหาลำดับที่มีตำแหน่งมาก ๆ จะมีข้อจำกัดเรื่อง maximum recursion depth exceeded

วิธีที่ 3 : Dynamic Programming

# Dynamic Programming
def fibo_dynamic(n) :
    fibo = [1,1]
    for i in range(2,n) :
        fibo.append(fibo[-1] + fibo[-2])
##    print(fibo)
    return fibo[n-1]
print(fibo_dynamic(7))  # 13

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

หมายเหตุ วิธีที่ 4 ถึงวิธีที่ 6 วิธีการพิสูจน์สูตร ดูเพิ่มเติมได้ที่ บทความ พิสูจน์ Binet’s formula / Matrix Exponentiation / Fast Doubling ในการหาค่าลำดับฟีโบนัชชี

วิธีที่ 4 : ใช้ Binet’s formula

# Binet's formula
import math
def fibo_binet(n) : 
    return int((( (1 + sqrt5) ** n - (1 - sqrt5) ** n ) / ( 2 ** n * sqrt5 )))
sqrt5 = math.sqrt(5) # 2.23606797749979
print(fibo_binet(7))    # 13
# ใช้ได้ถึงแค่ 72 จะยังให้ค่าที่ถูกต้อง

จาก code ด้านบนจะเป็นการอาศัย Binet’s formula

วิธีนี้สามารถคำนวณค่าลำดับฟีโบนัชชีได้เร็วมาก แต่ก็มีข้อเสียคือเมื่อต้องการหาค่าที่ตำแหน่งมาก ๆ จะได้ค่าที่ไม่แม่นตรง เช่น F(80) = 23416728348467685
แต่จาก Binet’s formula จะได้ F(80) = 23416728348467744

วิธีที่ 5 : Matrix Exponentiation

# Matrix Exponentiation
def fibo_matrix(n):
    v1, v2, v3 = 1, 1, 0
    for rec in bin(n)[3:]:
        calc = v2*v2
        v1, v2, v3 = v1*v1+calc, (v1+v3)*v2, calc+v3*v3
        if rec=='1':    v1, v2, v3 = v1+v2, v1, v2
    return v2
print(fibo_matrix(7))   # 13

จาก code ด้านบนทำการคำนวณโดยใช้ สูตร

วิธีนี้จะทำการยกกำลังเมทริกซ์ เพื่อให้ได้ค่าลำดับฟีโบนัชชีออกมา โดยการยกกำลังจะใช้เทคนิค Binary Exponentiation ดูเพิ่มเติมได้ที่ การหาค่าเลขยกกำลังโดยวิธี Binary Exponentiation

วิธีที่ 6 : Fast Doubling method

# Fast Doubling method
def fibo_fastdoubling(n):
    if n == 0:
        return (0, 1)
    else:
        a, b = fibo_fastdoubling(n // 2)
        c = a * (b * 2 - a)  # 2F(n+1)F(n) - F(n)^2
        d = a * a + b * b   # F(n+1)^2 + F(n)^2
        if n % 2 == 0:
            return (c, d)
        else:
            return (d, c + d)
print(fibo_fastdoubling(7)[0])

จาก code ด้านบนคือปรับปรุงจากวิธี Matrix Exponentiation เพื่อลดความซ้ำซ้อนลงทำให้คำนวณได้เร็วขึ้น คำนวณโดยใช้ สูตร

วิธีที่ 7 : ใช้ module sympy

# sympy
from sympy import fibonacci
print(fibonacci(7)) # 13

ในภาษา Python ก็จะมี module ที่สามารถหาค่าลำดับฟีโบนัชชีได้ โดยในที่นี้จะยกตัวอย่าง module sympy ซึ่งจะใช้สูตรในการคำนวณ ดังนี้

โดยที่ Φ คือ Golden ratio

ทั้งนี้จากอัลกอริทึมที่กล่าวมาในแต่ละวิธีนั้นก็จะมีข้อจำกัดต่าง ๆ อยู่ เช่น
-Recursive , Memoization : ต้องใช้หน่วยความจำมาก/ที่ตำแหน่งมาก ๆ หาค่าไม่ได้
-Dynamic Programming : ต้องคำนวณตัวก่อนหน้ามาก่อน
-Binet’s formula : ที่ตำแหน่งมาก ๆ หาค่าไม่ถูก
-Matrix Exponentiation : พิสูจน์จากคณิตศาสตร์ ซับซ้อน
-Fast Doubling : พิสูจน์จากคณิตศาสตร์ ซับซ้อน
-Sympy : จะไม่ทราบที่มาที่ไปของวิธีหาค่า

อัลกอริทึมที่กล่าวมาด้านบนพอจะสรุปได้ว่า Fast Doubling จะเป็นวิธีที่มีประสิทธิภาพมากที่สุดทั้งในด้านความเร็วในการหาค่าที่ตำแหน่งสูง ๆ และความถูกต้องของผลลัพธ์ที่ได้

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