2
\$\begingroup\$

I have this small C++ program for computing the \$n\$th Tribonacci number at compile-time. My main concern is: is it possible to get rid of the statickeyword (I had to use it in order to silence my compiler (VS 2019))?

Code

#include <cstdint>
#include <iostream>

template<uint64_t N>
struct tribonacci {
    constexpr static uint64_t value = tribonacci<N - 1>::value +
                                      tribonacci<N - 2>::value +
                                      tribonacci<N - 3>::value;
};

template<>
struct tribonacci<0> {
    constexpr static uint64_t value = 0;
};

template<>
struct tribonacci<1> {
    constexpr static uint64_t value = 0;
};

template<>
struct tribonacci<2> {
    constexpr static uint64_t value = 1;
};

int main() {
    std::cout << tribonacci<6>::value;
    return 0;
}
\$\endgroup\$

1 Answer 1

2
\$\begingroup\$

This is a pretty cool practice project, and your implementation is sound.

First to answer your concern… can you drop the static? The answer is no… and yes.

The way you’ve implemented the solution, no, you really can’t drop the static. The code doesn’t really make sense without it. If you are doing tribonacci<N>::value, and tribonacci<N> is a type (as it is in your code), then value must be a static data member. That’s what the :: means (in this context); tribonacci<N> is a type, and value is a property of the type.

However….

This is how you would implement a constexpr tribonacci sequence generator in C++11. That’s 3 versions old now, and counting. And one of the things that has advanced the most in each new version of C++ is constexpr capability.

If you don’t want value to be a class data member, you could make it a regular data member, like so:

template <std::size_t N>
struct tribonacci
{
    std::int_fast64_t const value = tribonacci<N - 1>{} + tribonacci<N - 2>{} + tribonacci<N - 3>{};

    constexpr operator std::int_fast64_t() const noexcept { return value; }
};

template <>
struct tribonacci<0>
{
    std::int_fast64_t const value = 0;

    constexpr operator std::int_fast64_t() const noexcept { return value; }
};

template <>
struct tribonacci<1>
{
    std::int_fast64_t const value = 0;

    constexpr operator std::int_fast64_t() const noexcept { return value; }
};

template <>
struct tribonacci<2>
{
    std::int_fast64_t const value = 1;

    constexpr operator std::int_fast64_t() const noexcept { return value; }
};

auto main() -> int
{
    constexpr auto sixth_trib_num = tribonacci<6>{}; // to prove it's constexpr

    std::cout << tribonacci<0>{} << '\n';       // will auto-convert to std::int_fast64_t
    std::cout << tribonacci<1>{}.value << '\n'; // or you can manually request the value
    std::cout << tribonacci<2>{} << '\n';
    std::cout << tribonacci<3>{} << '\n';
    std::cout << tribonacci<4>{} << '\n';
    std::cout << tribonacci<5>{} << '\n';
    std::cout << sixth_trib_num << '\n';
}

As you can see, no more static, but now you need to actually create an object (like tribonacci<6>{}) rather than just using the type (like tribonacci<6>), because now value is a property of the object, not the type (like tribonacci<6>{}.value).

Perhaps an even better option is to use variable templates. After all, each tribonacci number is just a number… it doesn’t need to be a type.

template <std::size_t N>
inline constexpr auto tribonacci = tribonacci<N - 1> + tribonacci<N - 2> + tribonacci<N - 3>;

template <>
inline constexpr auto tribonacci<0> = std::int_fast64_t{0};

template <>
inline constexpr auto tribonacci<1> = std::int_fast64_t{0};

template <>
inline constexpr auto tribonacci<2> = std::int_fast64_t{1};

auto main() -> int
{
    std::cout << tribonacci<0> << '\n';
    std::cout << tribonacci<1> << '\n';
    std::cout << tribonacci<2> << '\n';
    std::cout << tribonacci<3> << '\n';
    std::cout << tribonacci<4> << '\n';
    std::cout << tribonacci<5> << '\n';
    std::cout << tribonacci<6> << '\n';
}

With this, tribonacci<6> is a std::int_fast64_t constant. There are no classes to instantiate or any other cruft. This probably the way you want to go in C++14 and beyond; certainly in C++20 and beyond.

So, no, you can’t drop the static if you’re using the design you currently have. But there are other, better, alternatives in more modern versions of C++.

Now for your actual code review….

template<uint64_t N>
struct tribonacci {

First, if you’re going to use uint64_t, it should be spelled std::uint64_t.

But using uint64_t is generally a bad idea. You see, uint64_t is an optional type; it is not guaranteed to exist. And if it does, it is not guaranteed to be an efficient type; it could actually require significant emulation to work, and it could be tragically slow.

Better options are unsigned long long, std::uint_fast64_t, std::uint_least64_t. Which one you choose depends on what you really want:

  • unsigned long long: This is guaranteed to be at least 64 bits… but could (theoretically) be 128 bits, 256 bits, or anything else. If you only need 64 bits, it could be overkill. However, it will probably be at least as efficient (speed-wise, not space-wise) as any other option, if not more.
  • std::uint_fast64_t: If you really just need a 64-bit type, this should be your default choice. It will be the fastest type supported by the architecture that is at least 64 bits. So it may be more than 64 bits (like unsigned long long it may be 128 bits, or 256 bits, or whatever). But it may be smaller than unsigned long long, and probably as fast.
  • std::uint_least64_t: This is what you use when you want a type that is at least 64 bits, but you care more about conserving space than getting maximum speed. This will be the smallest type the platform supports that can hold 64-bit values… even if that type requires lots of code to emulate.

So, in a table, your options are (note that the size and speed are the worst case estimates):

Type Size Speed Notes
std::uint64_t Bad Bad Not guaranteed to exist
unsigned long long Bad Excellent Good choice if you need at least 64 bits, but much more is fine too
std::uint_fast64_t Good Good Best choice if you only need 64 bits
std::uint_least64_t Excellent Bad Best choice for saving space

There is another issue with uint64_t, and that is that it’s an unsigned type. Using unsigned types for general purpose numbers is a bad idea, for a number of reasons. You should only use unsigned numbers if you are doing bit-twiddling, or if you explicitly need modulo arithmetic. Otherwise, signed should be the default choice. The problems unsigned numbers cause are not worth the one extra bit of space.

Of course, you could also let the user pick the type:

template <std::size_t N, typename T = int> // defaults to regular old int
inline constexpr auto tribonacci = T(tribonacci<N - 1> + tribonacci<N - 2> + tribonacci<N - 3>);

// note in c++20, you could also constrain the type, like so:
//  template <std::size_t N, std::integral T = int>

template <typename T>
inline constexpr auto tribonacci<0, T> = T(0);

template <typename T>
inline constexpr auto tribonacci<1, T> = T(0);

template <typename T>
inline constexpr auto tribonacci<2, T> = T(1);

// if you're working with int_fast64_t a lot, then make a handy alias
template <std::size_t N>
inline constexpr auto tribonacci64 = tribonacci<N, std::int_fast64_t>;

auto main() -> int
{
    std::cout << tribonacci<0> << '\n';                 // int(0)
    std::cout << tribonacci<1, long> << '\n';           // long(0)
    std::cout << tribonacci<2, std::int64_t> << '\n' ;  // int64_t(1)
    std::cout << tribonacci64<3> << '\n';               // int_fast64_t(1)
}

Finally, I don’t know if you noticed, but in all the examples I made, I made the index type std::size_t, and the value type something else: int, std::uint_fast64_t or whatever. That’s because when you do auto v = tribonacci<N>, the N has nothing to do with the actual tribonacci number. It’s just the counter to pick which tribonacci number you want. v is the actual tribonacci number. That’s what you want to be at least 64 bits or whatever. N doesn’t need to be 64 bits; you’re going to blow past 64 bits by the 75th tribonacci number, so you only need N to be able to hold 7 bits for 64-bit tribonacci numbers.

std::size_t is the default type in C++ for counting, indexing, sizes, and so on. So it makes sense for N to be std::size_t. As for the value type… that should be whatever the user wants. Above I went with int by default (as you always should).

That’s pretty much it for the review. My recommendations:

  1. Don’t use uint64_t as the value type for the tribonacci number:
    • Don’t use unsigned types for general numbers.
    • Don’t use fixed size types. They’re not portable, and even when they are, they might be inefficient.
    • Let the user pick the type, though you can offer a sensible default (which should probably be int).
    • It’s std::uint64_t anyway.
  2. Don’t use uint64_t as the index type:
    • The default index type is std::size_t.
  3. Rather than old-school template meta-programming, using types for each tribonacci number, use variable templates.
\$\endgroup\$
5
  • \$\begingroup\$ Thanks a lot! You covered quite a bit of issues. \$\endgroup\$
    – coderodde
    Commented May 29, 2021 at 17:21
  • \$\begingroup\$ I think the table you presented is questionable. Why would unsigned long long have "excellent" speed vs. uint_fast64_t only having "good"? \$\endgroup\$
    – G. Sliepen
    Commented May 30, 2021 at 11:02
  • \$\begingroup\$ The table values are explained in the text just above it. \$\endgroup\$
    – indi
    Commented May 30, 2021 at 11:14
  • 1
    \$\begingroup\$ But why would unsigned long long "probably at least as efficient as any other option", when the whole point of uint_fast64_t is to be the fastest type that has at least 64 bits? I would just say: use uint_fast*_t if you want the fastest type, uint_least*_t if you want the smallest type, uint*_t if you want an exact type, and built-in types if you don't care either way. \$\endgroup\$
    – G. Sliepen
    Commented May 30, 2021 at 15:47
  • \$\begingroup\$ Isn’t that what the table says? The fast and least types are both “best” for their purposes, and unsigned long long is only “good” if you don’t really care. \$\endgroup\$
    – indi
    Commented May 31, 2021 at 19:45

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.