[boost] Re: Memoization library

From: Thorsten Ottosen (nesotto_at_[hidden])
Date: 2003-12-12 22:52:36

"David Abrahams" <dave_at_[hidden]> wrote in message
news:uhe05zerm.fsf_at_boost-consulting.com...
> Jim Apple <japple_at_[hidden]> writes:
>
[snip]
> > The
> > classic example of this is computing the Fibonacci numbers, which have
> > the following recursive definition:
> >
> > f(0) = 1
> > f(1) = 1
> > f(n) = f(n-1) + f (n-2)
> >
> > The naive implementation is miserably slow: it's performace is
> > exponential.
>
> You'd have to be *pretty* naive to write it that way.
>
> > The smart way to calculate f(n) is to create a table, building
> > incrementally.
>
> I guess, if you need to calculate f(n) for many different
> non-consecutive n, that's smart.  If you only need to do it once you
> just:
>
>     unsigned fib(unsigned n)  // linear, no table.
>     {
>         if (n < 2) return 1;
>         unsigned n1 = 1, n2 = 1;
>         for (unsigned i = 2; i < n; ++i)
>         {
>             unsigned x = n1 + n2;
>             n2 = n1;
>             n1 = x;
>         }
>         return n1 + n2;
>     }

There is a formula for the n'th fibonacci number.

br

-Thorsten