Template generation of Fibonacci numbers.
CplusplusNewbie
is pasted from a website.
As I understand it, this is not really a template design at all
because only one type is used -- integers -- whereas the purpose of
templates is to allow generalizations across multiple types.
The reason the language of templates is used (it seems to me) is that
this is a trick to avoid recursive function calls, and take advantage
of compilation rules regarding templates.
Is this really the best way to avoid the recursion problem? Any other
comments on this code?
Another thing I realise is that the "uint" designation is not portable
and could be replaced by "unsigned" but that's not really what I'd
like to ask about.
Many Thanks.
#include <iostream>
#include <cassert>
using namespace std;
template<int stage>
struct Fib
{
//Make this value a constant value equal to the (stage-1) + (stage
-2)
//which the compile will generate for us and save in the types of:
// Fib<stage-1> and Fib<stage-2>. This all works because stage is
known at compile
// time, as all template parameters must be.
static const uint64_t value = Fib<stage-1>::value +
Fib<stage-2>::value;
static inline uint64_t getValue(int i)
{
if (i == stage) // Does the current class hold the given place?
{
return value; // Return it!
} else {
return Fib<stage-1>::getValue(i); // Get it from the previous
class!
}
}
};
template<> // Template specialization for the 0's case.
struct Fib<0>
{
static const uint64_t value = 1;
static inline uint64_t getValue(int i)
{
assert(i == 0);
return 1;
}
};
template<> // Template specialization for the 1's case
struct Fib<1>
{
static const uint64_t value = 1;
static inline uint64_t getValue(int i)
{
if (i == 1)
{
return value;
} else {
return Fib<0>::getValue(i);
}
}
};
int main(int, char *[])
{
//Generate (at compile time) 100 places of the Fib sequence.
//Then, (at runtime) output the 100 calculated places.
//Note: a 64 bit int overflows at place 92
for (int i = 0; i < 100; ++i)
{
cout << "n:=" << i << " => " << Fib<100>::getValue(i) << endl;
}
}
Ron
> I'm concerned about this code for generating Fibonacci numbers which
> is pasted from a website.
> As I understand it, this is not really a template design at all
> because only one type is used -- integers -- whereas the purpose of
> templates is to allow generalizations across multiple types.
> The reason the language of templates is used (it seems to me) is that
> this is a trick to avoid recursive function calls, and take advantage
> of compilation rules regarding templates.
It is a trick, but this kind of programming task is a good mental
exercise in how
to do things with templates. You are WRONG about templates. The
purpose of templates
are whatever you can use them for. While being able to template based
on a type
is perhaps the MOST common use. Templating on the integer value
>
> Is this really the best way to avoid the recursion problem?
It's got little to do with that. It's a clever hack to due the
recursion at COMPILE
time rather than in execution of the program. Again, not a
tremendously good use in
this example, but it shows you the ways that you may be able to use
templates for a less
trivial case later.
I use templates like this in some real specialized high performance
code to unroll a series
of complex operations into a single function to avoid a lot of
execution time testing and
branching (and subroutine linkage).
Michael Doubez
> I'm concerned about this code for generating Fibonacci numbers which
> is pasted from a website.
> As I understand it, this is not really a template design at all
> because only one type is used -- integers -- whereas the purpose of
> templates is to allow generalizations across multiple types.
The purpose of template is being able to abstract from the algorithm.
In practice, the type of the data to process is part of the
parameters. There is nothing wrong with other kinds of parameter:
numerical parameters, function pointer parameters or other templates.
> The reason the language of templates is used (it seems to me) is that
> this is a trick to avoid recursive function calls, and take advantage
> of compilation rules regarding templates.
The reason the language of templates is used is that it allows
generating code automatically at compile time. Some speak about
generative programming and meta-models ... check it out.
> Is this really the best way to avoid the recursion problem?
The best way to avoid recursion it using iteration.
The fact is that template programming is recursive thinking by nature
and there is no way to iterate (though that can be emulated with some
kind of list).
> Any other comments on this code?
This code is not very useful in practice.
A more useful code would be to generate fibonacci into a container
(IMO a balanced tree) and provide a function to retrieve the value of
a stage at runtime.
[snip: code]
--
Michael
Pavel
Why not a simple array (place fib(i) at index i)? -Pavel
> [snip: code]
>
> --
> Michael
Juha Nieminen
> As I understand it, this is not really a template design at all
> because only one type is used -- integers -- whereas the purpose of
> templates is to allow generalizations across multiple types.
No. Templates are not designed solely to generate code for multiple
types. They are also designed to generate code for integral constants.
std::bitset would be the quintessential example.
The fact that code can be generated for integral constants can be used
to perform integral arithmetic at compile time.
Frank Bergemann
> I'm concerned about this code for generating Fibonacci numbers which
> is pasted from a website.
You might wanna have a look at the book "C++ Template
Metaprogramming" (David Abrahams & Aleksey Gurtovoy). It uses the same
example (amongst others) and explains the story behind
- about "computing with types".
Let me also refer to "Generative Programming, Methods, Tools &
Applications" (Krysztof Czarnecki & Ulrich W. Eisenecker). It holds a
chapter about static metapramming in C++ using templates, which - in
my view - is easier to understand, than "C++ Template
Metaprogramming".
Cheers,
Frank