Вычисление чисел Фибоначчи, по всем, наверное, хорошо известному примитивному алгоритму. Для достаточно больших значений (>45) вычисляется очень долго. При реализации на С++ была идея перенести вычисления на стадию компиляции. Но! Обнаружилось что и сборка исходика, и выполнение делаются практически моментально и никак не похоже, что в это время что-то вычисляется. Хотя я считал, что компилироваться это должно очень долго. Почему так происходит?

#include <stdio.h>
#include <stdlib.h>

unsigned long long fib(unsigned long long n) {
    if (n < 2) {
        return n;
    } else {
        return fib(n - 1) + fib(n - 2);
    }
}

int main(int argc, char** argv) {
    if (argc < 2) {
        return EXIT_SUCCESS;
    }
    long long n = atoll(argv[1]);
    unsigned long long res = fib(n < 0 ? -n : n);
    if (n < 0 && (n % 2) == 0) {
        printf("%lld\n", -res);
    } else {
        printf("%llu\n", res);
    }
    return EXIT_SUCCESS;
}

Это-же самое, переписанное на C++:

#include <cstdio>
#include <cstdlib>
#include <stdexcept>

template <int N> struct Fib { static const unsigned long long VALUE = Fib<N - 1>::VALUE + Fib<N - 2>::VALUE; };
template <> struct Fib<0> { static const unsigned long long VALUE = 0; };
template <> struct Fib<1> { static const unsigned long long VALUE = 1; };

#define FIB_V(n) (Fib<(n)>::VALUE)

unsigned long long fib(unsigned long long n) {
    static const unsigned long long fib_nums[] = {
        FIB_V(0), FIB_V(1), FIB_V(2), FIB_V(3), FIB_V(4), FIB_V(5), FIB_V(6), FIB_V(7), FIB_V(8), FIB_V(9),
        FIB_V(10), FIB_V(11), FIB_V(12), FIB_V(13), FIB_V(14), FIB_V(15), FIB_V(16), FIB_V(17), FIB_V(18), FIB_V(19),
        FIB_V(20), FIB_V(21), FIB_V(22), FIB_V(23), FIB_V(24), FIB_V(25), FIB_V(26), FIB_V(27), FIB_V(28), FIB_V(29),
        FIB_V(30), FIB_V(31), FIB_V(32), FIB_V(33), FIB_V(34), FIB_V(35), FIB_V(36), FIB_V(37), FIB_V(38), FIB_V(39),
        FIB_V(40), FIB_V(41), FIB_V(42), FIB_V(43), FIB_V(44), FIB_V(45), FIB_V(46), FIB_V(47), FIB_V(48), FIB_V(49),
        FIB_V(50), FIB_V(51), FIB_V(52), FIB_V(53), FIB_V(54), FIB_V(55), FIB_V(56), FIB_V(57), FIB_V(58), FIB_V(59),
        FIB_V(60), FIB_V(61), FIB_V(62), FIB_V(63), FIB_V(64), FIB_V(65), FIB_V(66), FIB_V(67), FIB_V(68), FIB_V(69),
        FIB_V(70), FIB_V(71), FIB_V(72), FIB_V(73), FIB_V(74), FIB_V(75), FIB_V(76), FIB_V(77), FIB_V(78), FIB_V(79),
        FIB_V(80), FIB_V(81), FIB_V(82), FIB_V(83), FIB_V(84), FIB_V(85), FIB_V(86), FIB_V(87), FIB_V(88), FIB_V(89),
        FIB_V(90), FIB_V(91), FIB_V(92), FIB_V(93)
    };
    if (n < (sizeof(fib_nums) / sizeof(fib_nums[0]))) { return fib_nums[n]; }
    else { throw std::overflow_error("overflow error"); }
}

int main(int argc, char** argv) {
    if (argc < 2) {
        return EXIT_SUCCESS;
    }
    long long n = std::atoll(argv[1]);
    try {
        unsigned long long res = fib(n < 0 ? -n : n);
        if (n < 0 && (n % 2) == 0) {
            std::printf("%lld\n", -res);
        } else {
            std::printf("%llu\n", res);
        }
    } catch (std::overflow_error const& e) {
        std::printf("%s!\n", e.what());
    }
    return EXIT_SUCCESS;
}

Здравствуйте, DangerMan, Вы писали:

DM>Вычисление чисел Фибоначчи, по всем, наверное, хорошо известному примитивному алгоритму. Для достаточно больших значений (>45) вычисляется очень долго.

Дак не пользуйся рекурсивным алгоритмом.
Ты прикинь сколько операций надо на вычисление "в лоб".
Избавься от рекурсии и вычисляй с помощью простого цикла.
Можно еще формулу Бине использовать.
Ну а если максимальная скорость нужна,
то заведи lookup table и будешь вычислять за одну операцию

Здравствуйте, Аноним, Вы писали:

А>Дак не пользуйся рекурсивным алгоритмом.
А>Ты прикинь сколько операций надо на вычисление "в лоб".
А>Избавься от рекурсии и вычисляй с помощью простого цикла.
А>Можно еще формулу Бине использовать.
А>Ну а если максимальная скорость нужна,
А>то заведи lookup table и будешь вычислять за одну операцию

Так как раз алгоритм и принципиален. Мне интересно, как компилятор смог практически за нулевое время посчитать все числа по этому, очень неоптимальному, алгоритму?

Здравствуйте, DangerMan, Вы писали:

DM>Вычисление чисел Фибоначчи, по всем, наверное, хорошо известному примитивному алгоритму. Для достаточно больших значений (>45) вычисляется очень долго. При реализации на С++ была идея перенести вычисления на стадию компиляции. Но! Обнаружилось что и сборка исходика, и выполнение делаются практически моментально и никак не похоже, что в это время что-то вычисляется. Хотя я считал, что компилироваться это должно очень долго. Почему так происходит?

Потому что компилятор инстанцирует каждую специализацию шаблона всего один раз. А потом берет уже готовый. Они у него в чем-то вроде хэштаблицы лежат. Т.е, при вычислении, скажем, Fib<17>::VALUE, он не будет проходить заново всю цепочку, огромное количество раз вычисляя Fib<1>::VALUE, а просто сложит уже посчитанные Fib<16>::VALUE и Fib<15>::VALUE.

Выдвину версию.
В первом случае программа вычисляет все значения т.е.
f(46) = f(45) + f(44) (1)
при этом f(45) в (1) это
f(45) = f(44) + f(43) (2)
а f(44) в (1)
это f(44)=f(43) + f(42)

уже тут f(44) и f(43) Вычисляется 2 раза каждая, но каждая из них раскрывается в такое же дерево вычислений!!!
мне трудно даже представить сложность, но она колоссальная подозреваю что порядка 2^n т.е 2 в 45 степени

во втором примере, когда компилер инстанирует шаблон класса он запоминает о его существовании и не вычисляет её более. т.е. f(1),f2 .. и т.д.
будут вычислены всего один раз. Тоесть компилеру понадобиться всего 93 темплятных класса.


Другими словами — вся беда в рекурсии и втом что в твоем примере не запоминается уже вычисленный результат. Надо написать нерекурсивную функцию которая будет помнить чему равно f(N) если оно хоть раз вычислялось.

Оценил сложность: N факториал проходов функции при первом алгоритме, загнется любой проц.

Здравствуйте, dev_null, Вы писали:

_>Другими словами — вся беда в рекурсии и втом что в твоем примере не запоминается уже вычисленный результат. Надо написать нерекурсивную функцию которая будет помнить чему равно f(N) если оно хоть раз вычислялось.

Зачем же обязательно нерекурсивную?

class FCalc {
public:
    FCalc( int f1, int f2 )
    {
         data.Set( 1, f1 );
         data.Set( 2, f2 );
    }
    double Calc( int x )
    {
        assert( x >= 0 );
        if( data.Has( x ) )
            return data[x];
        double res = Calc( x - 1 ) + Calc( x - 2 );
        data.Set( x, res );
        return res;
    }
    
private:
    MySuperPuperHashMap<int, double> data;
};

Здравствуйте, DangerMan, Вы писали:

DM>Вычисление чисел Фибоначчи, по всем, наверное, хорошо известному примитивному алгоритму. Для достаточно больших значений (>45) вычисляется очень долго. При реализации на С++ была идея перенести вычисления на стадию компиляции. Но! Обнаружилось что и сборка исходика, и выполнение делаются практически моментально и никак не похоже, что в это время что-то вычисляется. Хотя я считал, что компилироваться это должно очень долго. Почему так происходит?

DM>[ccode]
DM>#include <stdio.h>
DM>#include <stdlib.h>

DM>unsigned long long fib(unsigned long long n) {
DM> if (n < 2) {
DM> return n;
DM> } else {
DM> return fib(n — 1) + fib(n — 2);
DM> }
DM>}

А вы шутник.
1) разверните реккурсию в цикл — считайте с O(N)-скоростью.
2) если вам надо считать числа Фиббоначи, ну скажем 10.000-ое и линейный цикл для вас медленный — перейдите в матичную запись и считайте с logN-скоростью.

Здравствуйте, Sergey, Вы писали:

S>Потому что компилятор инстанцирует каждую специализацию шаблона всего один раз. А потом берет уже готовый. Они у него в чем-то вроде хэштаблицы лежат. Т.е, при вычислении, скажем, Fib<17>::VALUE, он не будет проходить заново всю цепочку, огромное количество раз вычисляя Fib<1>::VALUE, а просто сложит уже посчитанные Fib<16>::VALUE и Fib<15>::VALUE.

Спасибо, примерно так я и думал. Но это может зависеть от компилятора?

Здравствуйте, DangerMan, Вы писали:

S>>Потому что компилятор инстанцирует каждую специализацию шаблона всего один раз. А потом берет уже готовый. Они у него в чем-то вроде хэштаблицы лежат. Т.е, при вычислении, скажем, Fib<17>::VALUE, он не будет проходить заново всю цепочку, огромное количество раз вычисляя Fib<1>::VALUE, а просто сложит уже посчитанные Fib<16>::VALUE и Fib<15>::VALUE.
DM>Спасибо, примерно так я и думал. Но это может зависеть от компилятора?
Нет.

> S>Потому что компилятор инстанцирует каждую специализацию шаблона всего один раз. А потом берет уже готовый. Они у него в чем-то вроде хэштаблицы лежат. Т.е, при вычислении, скажем, Fib<17>::VALUE, он не будет проходить заново всю цепочку, огромное количество раз вычисляя Fib<1>::VALUE, а просто сложит уже посчитанные Fib<16>::VALUE и Fib<15>::VALUE.
>
> Спасибо, примерно так я и думал. Но это может зависеть от компилятора?

Может, конечно. Но на практике вряд ли эта зависимость будет слишком сильной. Измерения на эту тему (для компиляторов gcc 2.95.3, 3.3, Intel 6.0, 8.0, VC 7.1, CW 9.2 и Comeau 4.3.3) есть в приложении к книге "C++ Template Metaprogramming: Concepts, Tools, and Techniques from Boost and Beyond", известной так же как mpl book. Там как раз есть пример с числами Фиббоначи, немного другой, но тоже рекурсивный. Время компиляции примерно O(N^3), результаты для разных компиляторов отличаются в 3 раза.

Здравствуйте, dev_null, Вы писали:

_>мне трудно даже представить сложность, но она колоссальная подозреваю что порядка 2^n т.е 2 в 45 степени

Чуть поменьше: не 2^n, а (ф1)^n, где ф1 — золотое сечение (sqrt(5)-1 = 1.61...)

Если говорить точно, то O(F(n)), где F — числа фибоначчи.
Просто потому, что выражение разворачивается в сумму единичек.

_>Другими словами — вся беда в рекурсии и втом что в твоем примере не запоминается уже вычисленный результат. Надо написать нерекурсивную функцию которая будет помнить чему равно f(N) если оно хоть раз вычислялось.

Смотря как рекурсию писать.

typedef unsigned long long fib_type;
typedef unsigned short fib_index;

fib_type f(fib_index n, fib_type f0, fib_type f1)
{
    return (n==0) ? f0 : f(n-1, f1, f0+f1);
}

fib_type F(fib_index n) { return f(n, 1, 1); }