Еще один алгоритм вычисления чисел Фибоначчи

Перед прочтением статьи, решил попробовать придумать свой алгоритм. Времени понадобилось не очень много. Ниже описание идеи и пример на С++.

Достаточно просто получить вот такую формулу:
, где

Формула доказывается легко по индукции. При m = 0 формула верна:

Предположим, что формула верна при m = p

Докажем, что формула верна при m = p + 1:

— получили такое же выражение, как и для случая m = p, т.е. при m = p + 1 формула остается верной
Легко получить через те же числа:

При нечетном N, m можно подобрать так, чтобы выполнялись равенства и . Это число равно
После упрощения получаем такие формулы:

Используя последние формулы можно получить простой рекурсивный алгоритм.

#include <iostream>
using namespace std;

void factorial_recursive(int n, int& fn, int& fn1)
{
    int gn, gn1;
    if (n < 2) {
        fn = n;
        fn1 = 1; 
        return; 
    } 
    factorial_recursive(n / 2, gn, gn1);
    if (n % 2) {
        fn = gn1 * gn1 + gn * gn;
        fn1 = gn1 * gn1 + 2 * gn * gn1;
    } else {
        fn = 2 * gn * gn1 - gn * gn;
        fn1 = gn1 * gn1 + gn * gn;
    }
}

int factorial(int n)
{
    int fn, fn1;
    factorial_recursive(n, fn, fn1);
    return fn;
}

int main()
{
   for (int i = 0; i < 20; i++)
     cout << factorial(i) << " ";
   return 0;
}

От рекурсии уйти достаточно просто:

#include <iostream>
using namespace std;

unsigned factorial(unsigned n)
{
    if (n < 2)
        return n;
    unsigned mask = 1, m = n;
    while (m > 1) {
        m >>= 1;
        mask <<= 1;
    }
    unsigned fn = 1, fn1 = 1, gn, gn1;
    while (mask > 1) {
        mask >>= 1;
        gn = fn;
        gn1 = fn1;
        if (n & mask) {
            fn = gn1 * gn1 + gn * gn;
            fn1 = gn1 * gn1 + 2 * gn * gn1;
        } else {
            fn = 2 * gn * gn1 - gn * gn;
            fn1 = gn1 * gn1 + gn * gn;
        }
    }
    return fn;
}

int main()
{
   for (int i = 0; i < 20; i++)
     cout << factorial(i) << " ";
   return 0;
}

Автор: alexeibs