Template Metaprogramming to calculate Fibonacci
Asked Answered
S

3

5

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;
}
Superadd answered 3/1, 2020 at 14:33 Comment(8)
@Holt oh missed thatTopcoat
You could store the number in some kind of class that stores the digits, e.g., template <int... Digits> struct Number;. Fibonacci sequence only require addition, so you only have to implement an addition. You could even represent the number in base-2 for simpler addition.Berchtesgaden
Note that you starting number are (I think wrong), you should have 0, 0, 1 according to oeis.org/A000073.Berchtesgaden
do you nkow the correct answer?Topcoat
@max66 With 64 bits long long, the limit is reached at fib<72> (signed long long) or fib<73> (unsigned long long)Canary
@DavideCastronovo OP is using (compile-time) recursion. This hint doesn’t solve the issue with OP’s code regarding the range of integer data types.Dori
I think the correct term is "3rd order" sequence, not 3rd class.Anglophile
@James Reinstate Monica Polk Thanks for your correctionSuperadd
B
11

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:

  1. 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;
  1. 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;
};
  1. 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;
Berchtesgaden answered 3/1, 2020 at 15:21 Comment(5)
i knew arbitrary number of digits would be complicated, so I tried to keep it simple ;). Anyhow, this is rather cool stuff, do you know what is the limit for digits, ie limit for number of template parameters?Topcoat
@formerlyknownas_463035818 I don't really know... Its probably impossible to reach the limit by computing tribonaccy numbers since it already takes ~10s on my computer to compute for fib<400> and the number is only 107 digits long.Berchtesgaden
You code seems correct but it would be the 98th numbers if the initial sequence is 1,1, 2,4 (as in question source code) instead of 0,0,1,1 (as in OEIS). I got 98: 5.33248e+25 using doubles.Canary
@Canary Yes, I am taking the OEIS as reference here, I already notified the OP in a comment as I think it was a mistake on their side.Berchtesgaden
Thank you very much. You helped me a lot to understand template metaprogrammingSuperadd
T
2

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_numbers 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.

Topcoat answered 3/1, 2020 at 15:23 Comment(1)
Thank you very much. This answer is clean and useful. I checked your result and its correct.Superadd
F
1

You can accomplish this using Boost version 1.72 and 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;
}

Output:

93326215443944152681699238856266700490715968264381621468592963895217599993229915608941463976156518286253697920827223758251185210916864000000000000000000000000

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 
Fichu answered 3/1, 2020 at 16:10 Comment(2)
This is standard Fibonacci and not 3rd-class Fibonacci!Canary
With some adjustment, it should still work. See the Edit.Fichu

© 2022 - 2024 — McMap. All rights reserved.