Вычисление чисел Фибоначчи во время компиляции

Не думаю, что кого-нибудь из программистов на C/C++, кроме, может быть, самых начинающих, затруднит написать функцию, вычисляющую по заданному целому числу n число Фибоначчи с номером n, используя O(n) цикл вместо O(n^2) рекурсии (получаемой переписыванием определения числа Фибоначчи на языке программирования).

В данный момент моя цель состоит не в демонстрации эффективного вычисления чисел Фибоначчи (их можно считать по аналитической формуле, кроме того, есть коллекция реализаций), а в демонстрации реализации линейного алгоритма на шаблонах C++ (похожий пример на Scheme).

Надеюсь, мой пример будет полезен изучающим обобщённое программирование на C++. Итак, заставим компилятор вычислить числа Фибоначчи «по определению».

// Fibonacci numbers via templates by definition

template <unsigned N> struct Fib
{
  static const unsigned value =
    Fib<N - 1>::value + Fib<N - 2>::value;
};

template <> struct Fib <0>
{
  static const unsigned value = 0;
};

template <> struct Fib <1>
{
  static const unsigned value = 1;
};

Теперь, например, Fib<10>::value == 55, что и требовалось. Естественно, параметр шаблона должен быть известен на момент компиляции. Линейный алгоритм использует предыдущее число, поэтому введём дополнительную константу prev. Далее, мы можем избавиться от упоминания Fib<N-2>, сохранив только Fib<N-1>.

// linear calculation of n-th Fibonacci number on templates
template <unsigned N>
struct Fib: protected Fib<N - 1>
{
protected:
  static const unsigned prev = 
    Fib<N - 1>::value;
public:
  static const unsigned value = 
    Fib<N - 1>::prev + prev;  
};

template <> struct Fib <0>
{
protected:
  static const unsigned prev = 0;
public:
  static const unsigned value = 0;
};

template <> struct Fib <1>
{
protected:
  static const unsigned prev = 0;
public:
  static const unsigned value = 1;
};

Замечание 1. Использовать protected, конечно, необязательно (тем более в таком простом случае), это было сделано в целях разделения «интерфейса» (value) и «реализации».

Замечание 2. На самом деле первый вариант квадратичным не является, т.к. инстанцирование (подстановка формальных параметров шаблона) Fib<N> для разных N происходит только однажды. Например, вычислим Fib<6>::value.

Fib<6>::value = Fib<5>::value + Fib<4>::value
Fib<5>::value = Fib<4>::value + Fib<3>::value
Fib<4>::value = Fib<3>::value + Fib<2>::value
Fib<3>::value = Fib<2>::value + 1 // Fib<1>::value
Fib<2>::value = 1 + 0 // Fib<0>::value
=> Fib<2>::value = 1
=> Fib<3>::value = 2
=> Fib<4>::value = 3
=> Fib<5>::value = 5
=> Fib<6>::value = 8

Аналогичный (однократному инстанцированию) приём можно использовать в run-time вычислениях (w:memoization, пример на C++11).

Реклама

One response

  1. […] лет назад я привёл пример вычисления целочисленных констант в рамках стандарта […]

Добавить комментарий

Заполните поля или щелкните по значку, чтобы оставить свой комментарий:

Логотип WordPress.com

Для комментария используется ваша учётная запись WordPress.com. Выход / Изменить )

Фотография Twitter

Для комментария используется ваша учётная запись Twitter. Выход / Изменить )

Фотография Facebook

Для комментария используется ваша учётная запись Facebook. Выход / Изменить )

Google+ photo

Для комментария используется ваша учётная запись Google+. Выход / Изменить )

Connecting to %s

%d такие блоггеры, как: