英文:
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<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;
}
答案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
模板的实现:
- 这是一个用于连接数字的小型
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;
- 加法的实际实现:
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;
希望这些翻译对您有所帮助。如果您需要进一步的解释或有其他问题,请随时提问。
英文:
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 <int... Digits>
struct number<Digits... > { };
Note: For the sake of simplicity when adding, I store the digits in reverse order, so the number 275
is stored as number<5, 7, 2>
.
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 <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;
And with an appropriate output operator (see below), you can print the 100th Tribonacci number:
int main() {
std::cout << fib<100>{} << "\n";
}
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<fib<37>, number<2, 5, 8, 6, 3, 4, 2, 3, 1, 1>>);
Implementation of 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;
}
Implementation of the add
template:
- This is a small
cat
utility to concatenate numbers:
// 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;
- The actual implementation of the addition:
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;
};
- A short wrapper:
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;
答案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 <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;
}
};
It stores the last 10
digits of the result in low
and the leading digits in high
. Two my_number
s can be summed via
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>;
};
and for 3 numbers:
template <typename A,typename B,typename C>
struct sum3 { using number = typename sum<A,sum<B,C>>::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<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();
}
I couldn't find a reliable source for the correct value of fib<100>
, 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 <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;
}
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's version, with the only difference being the usage of the `constexpr`-enabled big number class from `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;
}
Output:
180396380815100901214157639
</details>
通过集体智慧和协作来改善编程学习和解决问题的方式。致力于成为全球开发者共同参与的知识库,让每个人都能够通过互相帮助和分享经验来进步。
评论