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

huangapple
go评论84阅读模式
英文:

Template Metaprogramming to calculate Fibonacci

问题

最近在一次面试中，我被要求给出第100个三阶斐波那契数列的结果（Fib(n)=Fib(n-1)+Fib(n-2)+Fib(n-3)）。我通过数学归纳法完成了这个问题，并构建了一个类来表示比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;
}
英文:

Recently in a job interview I was asked to give the result of 100th element of a 3rd-class Fibonacci sequence(Fib(n)=Fib(n-1)+Fib(n-2)+Fib(n-3). I finished by Mathematical Induction and constructing a class to present numbers larger than long long. Then I was asked to implement it via template meta-programming. The problem is that the result will exceed the range of long long and I don't know how to fix this. Here is my code using template meta-programming.

template&lt;long long num&gt;
struct fib
{
    enum { result = fib&lt;num - 1&gt;::result + fib&lt;num - 2&gt;::result + fib&lt;num - 3&gt;::result};
};

template&lt;&gt;
struct fib&lt;0&gt;
{
    enum { result = 1 };
};

template&lt;&gt;
struct fib&lt;1&gt;
{
    enum { result = 1 };
};

template&lt;&gt;
struct fib&lt;2&gt;
{
    enum { result = 2 };
};

template&lt;&gt;
struct fib&lt;3&gt;
{
    enum { result = 4 };
};

int main()
{

    cout &lt;&lt; fib&lt;100&gt;::result &lt;&lt; endl;

    return 0;
}

答案1

得分: 10

以下是翻译好的内容：

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

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

*注意：为了简单起见，当进行加法运算时，我将数字以相反的顺序存储，因此数字275存储为number<5, 7, 2>。

斐波那契序列只需要加法，所以您只需定义加法，例如，一个名为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

虽然第100个Tribonacci数不在OEIS中，但您可以检查第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...>) {
    // 不要忘记number<>是按相反的顺序排列的：
    return out << number<Digits...>{} << Digit;
}

add模板的实现：

  1. 这是一个用于连接数字的小型cat实用程序：
// 小型连接实用程序：
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;
  1. 加法的实际实现：
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;
};
  1. 一个简短的包装器：
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;

希望这些翻译对您有所帮助。如果您需要进一步的解释或有其他问题，请随时提问。

英文:

A possible implementation is to use a custom structure to store the numbers instead of a built-in type. You could for instance store numbers like this:

template &lt;int... Digits&gt;
struct number&lt;Digits... &gt; { };

Note: For the sake of simplicity when adding, I store the digits in reverse order, so the number 275 is stored as number&lt;5, 7, 2&gt;.

Fibonacci only requires addition, so you simply have to define addition, e.g., a template add (see the end of the answer for the actual implementation).

You can then define the fib template quite easily:

template &lt;int N&gt;
struct fib_impl {
    using type = add_t&lt;
        typename fib_impl&lt;N-1&gt;::type, 
        typename fib_impl&lt;N-2&gt;::type,
        typename fib_impl&lt;N-3&gt;::type&gt;;
};

template &lt;&gt;
struct fib_impl&lt;0&gt; { using type = number&lt;0&gt;; };
template &lt;&gt;
struct fib_impl&lt;1&gt; { using type = number&lt;0&gt;; };
template &lt;&gt;
struct fib_impl&lt;2&gt; { using type = number&lt;1&gt;; };

template &lt;int N&gt;
using fib = typename fib_impl&lt;N&gt;::type;

And with an appropriate output operator (see below), you can print the 100th Tribonacci number:

int main() {
    std::cout &lt;&lt; fib&lt;100&gt;{} &lt;&lt; &quot;\n&quot;;
}

Which outputs:

53324762928098149064722658

While the 100th is not present in the OEIS, you can check that the 37th one is correct:

static_assert(std::is_same_v&lt;fib&lt;37&gt;, number&lt;2, 5, 8, 6, 3, 4, 2, 3, 1, 1&gt;&gt;);

Implementation of operator&lt;&lt;:

std::ostream&amp; operator&lt;&lt;(std::ostream &amp;out, number&lt;&gt;) {
    return out;
}

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

Implementation of the add template:

  1. This is a small cat utility to concatenate numbers:
// Small concatenation utility:
template &lt;class N1, class N2&gt;
struct cat;

template &lt;int... N1, int... N2&gt;
struct cat&lt;number&lt;N1... &gt;, number&lt;N2... &gt;&gt; {
    using type = number&lt;N1... , N2...&gt;;
};

template &lt;class N1, class N2&gt;
using cat_t = typename cat&lt;N1, N2&gt;::type;
  1. The actual implementation of the addition:
template &lt;class AccNumber, int Carry, class Number1, class Number2&gt;
struct add_impl;

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

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

template &lt;class AccNumber, int Carry,
          int Digit1, int... Digits1, int Digit2, int... Digits2&gt;
struct add_impl&lt;AccNumber, Carry, number&lt;Digit1, Digits1... &gt;, number&lt;Digit2, Digits2...&gt;&gt; {
    using type = typename add_impl&lt;
                    cat_t&lt;AccNumber, number&lt;(Digit1 + Digit2 + Carry) % 10&gt;&gt;,
                    (Digit1 + Digit2 + Carry) / 10,
                    number&lt;Digits1... &gt;, number&lt;Digits2... &gt;&gt;::type;
};
  1. A short wrapper:
template &lt;class... Numbers&gt;
struct add;

template &lt;class Number&gt;
struct add&lt;Number&gt; {
    using type = Number;
};

template &lt;class Number, class... Numbers&gt;
struct add&lt;Number, Numbers... &gt; {
    using type = typename add_impl&lt;
        number&lt;&gt;, 0, Number, typename add&lt;Numbers... &gt;::type&gt;::type;
};


template &lt;class... Numbers&gt;
using add_t = typename add&lt;Numbers... &gt;::type;

答案2

得分: 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 << std::setw(10) << std::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>;
};

对于三个数字：

template <typename A, typename B, typename C>
struct sum3 { using number = typename sum<A, sum<B, C>::number>::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> 的正确值，所以很遗憾我无法进行测试。

完整示例在此处。

英文:

I am not aware of ready-to-use arbirtrary precicion facitlities for templates. However, a toy number-type that can hold numbers bigger than long long is easy to write:

template &lt;long long H,long long L&gt; 
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 &lt;&lt; high &lt;&lt; setw(10) &lt;&lt; setfill(&#39;0&#39;) &lt;&lt; low;
    }
};

It stores the last 10 digits of the result in low and the leading digits in high. Two my_numbers can be summed via

template &lt;typename A,typename B&gt;
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&lt;high,low&gt;;
};

and for 3 numbers:

template &lt;typename A,typename B,typename C&gt;
struct sum3 { using number = typename sum&lt;A,sum&lt;B,C&gt;&gt;::number; };

As already mentioned, this is just a toy example. Anyhow, once you have a number type that can represent big enough numbers you just have to adjust you fib with minor modifications:

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

template&lt;&gt; struct fib&lt;0&gt; { using result_t = my_number&lt;0,1&gt;; };
template&lt;&gt; struct fib&lt;1&gt; { using result_t = my_number&lt;0,1&gt;; };
template&lt;&gt; struct fib&lt;2&gt; { using result_t = my_number&lt;0,2&gt;; };
template&lt;&gt; struct fib&lt;3&gt; { using result_t = my_number&lt;0,4&gt;; };

int main() {
    fib&lt;100&gt;::result_t::print();
}

I couldn't find a reliable source for the correct value of fib&lt;100&gt;, so unfortunately I couldn't test against that.

Full example is here.

答案3

得分: 1

使用 Boost 版本 `1.72` 和 [boost::multiprecision][1]，您可以完成这个任务：

```cpp
#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 中可能无法编译。

编辑：
以下是第三类版本。这几乎与原始帖子的版本一致，唯一的区别是使用了来自 boost 的启用了 constexpr 的大数类：

#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


<details>
<summary>英文:</summary>

You can accomplish this using Boost version `1.72` and [boost::multiprecision][1]:

    #include &lt;iostream&gt;
    #include &lt;boost/multiprecision/cpp_int.hpp&gt;
    
    template &lt;int x&gt;
    struct fib
    {
    	static constexpr boost::multiprecision::uint1024_t value = x * fib&lt;x - 1&gt;::value;
    };
    
    template &lt;&gt;
    struct fib&lt;0&gt;
    {
    	static constexpr boost::multiprecision::uint1024_t value = 1;
    };
    
    int main()
    {
    	std::cout &lt;&lt; fib&lt;100&gt;::value;
    }

Output:

    93326215443944152681699238856266700490715968264381621468592963895217599993229915608941463976156518286253697920827223758251185210916864000000000000000000000000

  [1]: https://www.boost.org/doc/libs/1_72_0/libs/multiprecision/doc/html/index.html

This was run using Visual Studio 2019 and boost 1.72.  Note that earlier versions of `boost::multiprecision` were not full `constexpr`, so this probably will not compile with earlier versions of boost.

EDIT:
Here is the third-class version.  This is almost verbatim to the original poster&#39;s version, with the only difference being the usage of the `constexpr`-enabled big number class from `boost`:

    #include &lt;iostream&gt;
    #include &lt;boost/multiprecision/cpp_int.hpp&gt;
    
    template&lt;long long num&gt;
    struct fib
    {
    	static constexpr boost::multiprecision::uint1024_t value = fib&lt;num - 1&gt;::value + fib&lt;num - 2&gt;::value + fib&lt;num - 3&gt;::value;
    };
    
    template&lt;&gt;
    struct fib&lt;0&gt;
    {
    	static constexpr boost::multiprecision::uint1024_t value = 1;
    };
    
    template&lt;&gt;
    struct fib&lt;1&gt;
    {
    	static constexpr boost::multiprecision::uint1024_t value = 1;
    };
    
    template&lt;&gt;
    struct fib&lt;2&gt;
    {
    	static constexpr boost::multiprecision::uint1024_t value = 2;
    };
    
    template&lt;&gt;
    struct fib&lt;3&gt;
    {
    	static constexpr boost::multiprecision::uint1024_t value = 4;
    };
    
    int main()
    {
    	std::cout &lt;&lt; fib&lt;100&gt;::value;
    }

Output:

    180396380815100901214157639 

</details>

huangapple
  • 本文由 发表于 2020年1月3日 22:33:12
  • 转载请务必保留本文链接：https://go.coder-hub.com/59580362.html
  • biginteger
  • c++
  • fibonacci
  • metaprogramming
  • templates
匿名

发表评论

匿名网友

:?: :razz: :sad: :evil: :!: :smile: :oops: :grin: :eek: :shock: :???: :cool: :lol: :mad: :twisted: :roll: :wink: :idea: :arrow: :neutral: :cry: :mrgreen:

确定