Template generation of Fibonacci numbers.

Discussion in 'C++' started by CplusplusNewbie, Jun 26, 2009.

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

    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;
    }
    }
    CplusplusNewbie, Jun 26, 2009
    #1
    1. Advertising

  2. CplusplusNewbie

    Ron Guest

    On Jun 26, 7:26 am, CplusplusNewbie <> wrote:
    > 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).
    Ron, Jun 26, 2009
    #2
    1. Advertising

  3. On 26 juin, 13:26, CplusplusNewbie <> wrote:
    > 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
    Michael Doubez, Jun 26, 2009
    #3
  4. CplusplusNewbie

    Pavel Guest

    Michael Doubez wrote:
    > On 26 juin, 13:26, CplusplusNewbie <> wrote:
    >> 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.
    >


    Why not a simple array (place fib(i) at index i)? -Pavel

    > [snip: code]
    >
    > --
    > Michael
    Pavel, Jun 26, 2009
    #4
  5. CplusplusNewbie wrote:
    > 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.
    Juha Nieminen, Jun 27, 2009
    #5
  6. On 26 Jun., 13:26, CplusplusNewbie <> wrote:
    > 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
    Frank Bergemann, Jun 27, 2009
    #6
    1. Advertising

Want to reply to this thread or ask your own question?

It takes just 2 minutes to sign up (and it's free!). Just click the sign up button to choose a username and then you can ask your own questions on the forum.
Similar Threads
  1. Fibonacci numbers

    , Oct 10, 2003, in forum: C++
    Replies:
    28
    Views:
    1,359
    yousafzai
    Jun 5, 2011
  2. Alex Vinokur
    Replies:
    0
    Views:
    453
    Alex Vinokur
    Oct 29, 2003
  3. Alex Vinokur
    Replies:
    0
    Views:
    426
    Alex Vinokur
    Jul 26, 2004
  4. Andrew Tatum

    Fibonacci Numbers and Lucas Numbers

    Andrew Tatum, May 26, 2007, in forum: C++
    Replies:
    6
    Views:
    537
    Howard
    May 27, 2007
  5. RJB
    Replies:
    23
    Views:
    1,108
    Raymond Hettinger
    May 25, 2011
Loading...

Share This Page