Path: csiph.com!eternal-september.org!reader02.eternal-september.org!.POSTED!not-for-mail
From: Tim Rentsch <tr.17687@z991.linuxsc.com>
Newsgroups: comp.lang.c
Subject: Re: Recursion v Memoization
Date: Thu, 31 Dec 2020 00:46:03 -0800
Organization: A noiseless patient Spider
Lines: 54
Message-ID: <861rf6uzw4.fsf@linuxsc.com>
References: <rsg72i$eq4$1@gioia.aioe.org>
Mime-Version: 1.0
Content-Type: text/plain; charset=us-ascii
Injection-Info: reader02.eternal-september.org; posting-host="cb646d62786edb6c079bbfa1e5ebfce0"; logging-data="18060"; mail-complaints-to="abuse@eternal-september.org";	posting-account="U2FsdGVkX1+6B/lVMYXTpko1MJscnTR7ZPBIzH07rkA="
User-Agent: Gnus/5.11 (Gnus v5.11) Emacs/22.4 (gnu/linux)
Cancel-Lock: sha1:v2mtyIVh9dGtF3THW0y9JYrQZkY= sha1:TXnpdqjt3YHjq26ckEAZP0of7R0=
Xref: csiph.com comp.lang.c:157930

Real Troll <real.Troll@trolls.com> writes:

> We sometimes resort to using simple methods such as Recursion
> functions or interactive functions but Memoization method can be
> very useful.  For example to generate 45 Fibonacci numbers using
> recursion I used this function:
>
> int fibonacci(int input)
> {
>  if (input == 0 || input == 1)
>  {
>  return input;
>  }
>  else
>  {
>  return fibonacci(input - 1) + fibonacci(input - 2);
>  }
> }
>
> but using an array to store the numbers and to reuse the previous
> calculated values can save a lot of time.  [...]

Better simply to use a non-exponential algorithm:

/*** cut here ***/
#include <stdio.h>

typedef unsigned long long ULL;

static  ULL  fibonacci( unsigned );
static  ULL  ff2( ULL, ULL, unsigned, unsigned );

int
main( int argc, char *argv[] ){
    unsigned n;
    for(  n = 0;  n < 94;  n++  ){
        ULL fn = fibonacci( n );
        if(  argc > 1  )  printf( " fib( %2u ) is %25llu\n", n, fn );
    }
    return  0;
}

ULL
fibonacci( unsigned n ){
    unsigned high_bit = -1U ^ -1U>>1;
    return  ff2( 1, 0, high_bit, n );
}

ULL
ff2( ULL a, ULL b, unsigned m, unsigned n ){
    return  m == 0  ?  b
        :   m & n   ?  ff2( 2*a*b + b*b, a*a + 2*a*b + 2*b*b, m>>1, n )
        :   ff2( a*a + b*b, 2*a*b + b*b,                      m>>1, n );
}