338. Computing Fibonacci element in logn

שבוע מתמטי טוב 2
Math

בהמשך לפעם הקודמת, אם מבקשים מאיתנו לכתוב קוד שמחשב את המספר הפיבונאצ’י הnי, בד”כ נכתוב משהו כזה:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
public static int Fibonacci(int n)
{
    int previous = 0;
    int current = 1;
    for (int i = 0; i < n; i++)
    {
        int temp = current;
        current = current + previous;
        previous = temp;
    }
    return previous;
}

זה מחשב את המספר הפיבונאצ’י הnי בסיבוכיות $ O \left(n\right) $.

מסתבר שגם כאן אפשר לחשב בצורה יותר מהירה: יהי $ \varphi $ מספר המקיים $ \varphi^2 = \varphi + 1 $ (למשוואה זו קוראים משוואת חתך הזהב ולאיבר החיובי המקיים משוואה זו קוראים חתך הזהב)

אזי מסתבר כי $ \varphi^n = F_n \cdot \varphi + F_{n - 1} $ כאשר $ F_n $ הוא מספר הפיבונאצ’י הn. (הוכחה פשוטה באינדוקציה)

כעת מתקיים:

$ \varphi^{n + m} = F_{n + m} \cdot \varphi + F_{n + m - 1} = \\ \varphi^{n + m} = \varphi^n \cdot \varphi^m = \\ \left(F_n \cdot \varphi + F_{n - 1} \right) \cdot \left(F_m \cdot \varphi + F_{m - 1} \right) = \\ F_n \cdot F_m \cdot \varphi^2 + F_{n - 1} \cdot F_m \cdot \varphi + F_n \cdot F_{m - 1} \cdot \varphi + F_{n - 1} \cdot F_{m - 1} = \\ F_n \cdot F_m \cdot \varphi + F_n \cdot F_m + F_{n - 1} \cdot F_m \cdot \varphi + F_n \cdot F_{m - 1} \cdot \varphi + F_{n - 1} \cdot F_{m - 1} = \\ (F_n \cdot F_m + F_{n - 1} \cdot F_m + F_n \cdot F_{m - 1}) \cdot \varphi + (F_n \cdot F_m + F_{n - 1} \cdot F_{m - 1}) $

כלומר

$ F_{n + m} \cdot \varphi + F_{n + m - 1} = \\ (F_n \cdot F_m + F_{n - 1} \cdot F_m + F_n \cdot F_{m - 1}) \cdot \varphi + (F_n \cdot F_m + F_{n - 1} \cdot F_{m - 1})$ $ F_{n + m} = F_n \cdot F_m + F_{n - 1} \cdot F_m + F_n \cdot F_{m - 1} \\ F_{n + m - 1} = F_n \cdot F_m + F_{n - 1} \cdot F_{m - 1} $

אפשר לחשב בצורה דומה למה שראינו פעם שעברה את הפיבונאצ’י הn ע"י הסחבות עם ארבע זוגות של מספרים (הנוכחי והקודם של התוצאה והנוכחי והקודם של החזקה הנוכחית של 2).

אבל מאחר ויותר נוח לעבוד כמו בני אדם עם חזקה של מספר בודד, אפשר ליצור struct שמייצג זוג מספרי פיבונאצ’י:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
public struct FibonacciPair
{
    private readonly int mCurrent;
    private readonly int mPrevious;
    public FibonacciPair(int current, int previous)
    {
        mCurrent = current;
        mPrevious = previous;
    }
    public int Previous
    {
        get { return mPrevious; }
    }
    public int Current
    {
        get { return mCurrent; }
    }
    public static FibonacciPair operator *(FibonacciPair first, FibonacciPair second)
    {
        return new FibonacciPair
            (first.mCurrent*second.mCurrent + first.mPrevious*second.mCurrent + first.mCurrent*second.mPrevious,
             first.mCurrent*second.mCurrent + first.mPrevious*second.mPrevious);
    }
}

כעת נוכל לחשב את הפיבונאצ’י הn בצורה דומה לפעם הקודמת: אנחנו מחשבים את $ \varphi^n $ בעזרת המחלקה של FibonacciPair בצורה דומה לזו של פעם קודמת:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
public static int Fibonacci(int n)
{
    FibonacciPair currentPower = new FibonacciPair(1, 0);
    FibonacciPair result = new FibonacciPair(0, 1);
    while (n > 0)
    {
        if (n % 2 == 1)
        {
            result *= currentPower;
        }
        currentPower *= currentPower;
        n /= 2;
    }
    return result.Current;
}

נראה לי שזה אולי טיפה יותר מפתיע ממה שראינו פעם קודמת… מספר הפיבונאצ’י ה$ n $ ב$ \log{n} $!

המשך יום פיבונאצ’י טוב.

שתף