用于计算斐波那契数列的模板元编程

Question

最近在一次求职面试中，我被要求给出 3rd-class 斐波那契数列的第 100 个元素的结果(Fib(n)=Fib(n-1)+Fib(n-2) +Fib(n-3)。我通过数学归纳法完成并构造了一个 class 来呈现大于 long long 的数字。然后我被要求通过模板元编程实现它。问题是结果会超过long long 的范围，我不知道如何解决这个问题。这是我使用模板元编程的代码。

template<long long num>
struct fib
{
    enum { result = fib<num - 1>::result + fib<num - 2>::result + fib<num - 3>::result};
};

template<>
struct fib<0>
{
    enum { result = 1 };
};

template<>
struct fib<1>
{
    enum { result = 1 };
};

template<>
struct fib<2>
{
    enum { result = 2 };
};

template<>
struct fib<3>
{
    enum { result = 4 };
};

int main()
{

    cout << fib<100>::result << endl;

    return 0;
}

Answer 1

一种可能的实现是使用自定义结构而不是内置类型来存储数字。例如，您可以像这样存储数字：

template <int... Digits>
struct number<Digits... > { };

注：为了加法简单，我把数字倒序存储，所以数字275存储为number<5, 7, 2>。

Fibonacci 只需要加法，所以你只需要定义加法，例如模板add（实际实现见答案末尾）

然后您可以很容易地定义 fib 模板：

template <int N>
struct fib_impl {
    using type = add_t<
        typename fib_impl<N-1>::type, 
        typename fib_impl<N-2>::type,
        typename fib_impl<N-3>::type>;
};

template <>
struct fib_impl<0> { using type = number<0>; };
template <>
struct fib_impl<1> { using type = number<0>; };
template <>
struct fib_impl<2> { using type = number<1>; };

template <int N>
using fib = typename fib_impl<N>::type;

并使用适当的输出运算符（见下文），您可以打印第 100 个 Tribonacci 数：

int main() {
    std::cout << fib<100>{} << "\n";
}

输出：

53324762928098149064722658

虽然 OEIS 中没有第 100 个，但您可以检查第 37 个是否正确：

static_assert(std::is_same_v<fib<37>, number<2, 5, 8, 6, 3, 4, 2, 3, 1, 1>>);

实施`operator<<`：

std::ostream& operator<<(std::ostream &out, number<>) {
    return out;
}

template <int Digit, int... Digits>
std::ostream& operator<<(std::ostream &out, number<Digit, Digits... >) {
    // Do not forget that number<> is in reverse order:
    return out << number<Digits... >{} << Digit;
}

`add` 模板的实施：

这是一个用于连接数字的 cat 小实用程序：

// Small concatenation utility:
template <class N1, class N2>
struct cat;

template <int... N1, int... N2>
struct cat<number<N1... >, number<N2... >> {
    using type = number<N1... , N2...>;
};

template <class N1, class N2>
using cat_t = typename cat<N1, N2>::type;

加法的实际实现：

template <class AccNumber, int Carry, class Number1, class Number2>
struct add_impl;

template <class AccNumber, int Carry>
struct add_impl<AccNumber, Carry, number<>, number<>> {
    using type = std::conditional_t<Carry == 0, AccNumber, cat_t<AccNumber, number<1>>>;
};

template <class AccNumber, int Carry,
          int Digit2, int... Digits2>
struct add_impl<AccNumber, Carry, number<>, number<Digit2, Digits2...>> {
    using type = typename add_impl<
        cat_t<AccNumber, number<(Digit2 + Carry) % 10>>,
        (Digit2 + Carry) / 10,
        number<Digits2... >, number<>>::type;
};
template <class AccNumber, int Carry,
          int Digit1, int... Digits1>
struct add_impl<AccNumber, Carry, number<Digit1, Digits1... >, number<>> {
    using type = typename add_impl<
        cat_t<AccNumber, number<(Digit1 + Carry) % 10>>,
        (Digit1 + Carry) / 10,
        number<Digits1... >, number<>>::type;
};

template <class AccNumber, int Carry,
          int Digit1, int... Digits1, int Digit2, int... Digits2>
struct add_impl<AccNumber, Carry, number<Digit1, Digits1... >, number<Digit2, Digits2...>> {
    using type = typename add_impl<
                    cat_t<AccNumber, number<(Digit1 + Digit2 + Carry) % 10>>,
                    (Digit1 + Digit2 + Carry) / 10,
                    number<Digits1... >, number<Digits2... >>::type;
};

短包装：

template <class... Numbers>
struct add;

template <class Number>
struct add<Number> {
    using type = Number;
};

template <class Number, class... Numbers>
struct add<Number, Numbers... > {
    using type = typename add_impl<
        number<>, 0, Number, typename add<Numbers... >::type>::type;
};


template <class... Numbers>
using add_t = typename add<Numbers... >::type;

Answer 2

我不知道模板有随时可用的任意精度工具。但是，可以容纳大于 long long 的数字的玩具数字类型很容易编写：

template <long long H,long long L> 
struct my_number {
    static const long long high = H;
    static const long long low = L;
    static const long long mod = 10000000000;
    static void print() {
        std::cout << high << setw(10) << setfill('0') << low;
    }
};

它将结果的最后 10 位存储在 low 中，前导数字存储在 high 中。两个my_number可以通过

求和

template <typename A,typename B>
struct sum {
    static const long long low = (A::low + B::low) % A::mod;
    static const long long high = A::high + B::high + (A::low + B::low) / A::mod;
    using number = my_number<high,low>;
};

3 个号码：

template <typename A,typename B,typename C>
struct sum3 { using number = typename sum<A,sum<B,C>>::number; };

如前所述，这只是一个玩具示例。无论如何，一旦您拥有可以表示足够大数字的数字类型，您只需稍作修改即可 fib：

template<long long num> struct fib {
    using result_t = typename sum3< typename fib<num-1>::result_t, 
                                    typename fib<num-2>::result_t,
                                    typename fib<num-3>::result_t
                                   >::number;
};

template<> struct fib<0> { using result_t = my_number<0,1>; };
template<> struct fib<1> { using result_t = my_number<0,1>; };
template<> struct fib<2> { using result_t = my_number<0,2>; };
template<> struct fib<3> { using result_t = my_number<0,4>; };

int main() {
    fib<100>::result_t::print();
}

我找不到 fib<100> 正确值的可靠来源，所以很遗憾我无法对此进行测试。

完整示例为 here.

Answer 3

您可以使用 Boost 版本 1.72 和 boost::multiprecision:

完成此操作

#include <iostream>
#include <boost/multiprecision/cpp_int.hpp>

template <int x>
struct fib
{
    static constexpr boost::multiprecision::uint1024_t value = x * fib<x - 1>::value;
};

template <>
struct fib<0>
{
    static constexpr boost::multiprecision::uint1024_t value = 1;
};

int main()
{
    std::cout << fib<100>::value;
}

输出：

93326215443944152681699238856266700490715968264381621468592963895217599993229915608941463976156518286253697920827223758251185210916864000000000000000000000000

这是运行使用 Visual Studio 2019 和 boost 1.72。请注意 boost::multiprecision 的早期版本并不完整 constexpr，因此这可能无法与早期版本的 boost 一起编译。

编辑：这是第三个-class版本。这几乎是原发帖者版本的原样，唯一的区别是使用 constexpr 启用的大数字 class 来自 boost:

#include <iostream>
#include <boost/multiprecision/cpp_int.hpp>

template<long long num>
struct fib
{
    static constexpr boost::multiprecision::uint1024_t value = fib<num - 1>::value + fib<num - 2>::value + fib<num - 3>::value;
};

template<>
struct fib<0>
{
    static constexpr boost::multiprecision::uint1024_t value = 1;
};

template<>
struct fib<1>
{
    static constexpr boost::multiprecision::uint1024_t value = 1;
};

template<>
struct fib<2>
{
    static constexpr boost::multiprecision::uint1024_t value = 2;
};

template<>
struct fib<3>
{
    static constexpr boost::multiprecision::uint1024_t value = 4;
};

int main()
{
    std::cout << fib<100>::value;
}

输出：

180396380815100901214157639

用于计算斐波那契数列的模板元编程

Template Metaprogramming to calculate Fibonacci

c++

templates

metaprogramming

fibonacci

biginteger

实施`operator<<`：

`add` 模板的实施：

用于计算斐波那契数列的模板元编程

Template Metaprogramming to calculate Fibonacci

c++

templates

metaprogramming

fibonacci

biginteger

实施operator<<：

add 模板的实施：

实施`operator<<`：

`add` 模板的实施：