/** Print ascending members of the Fibonacci sequence that are
representable as 64-bit signed integers, prefixed by their term
numbers, and followed by the ratio of successive terms, to
demonstrate the 1.618...^n growth (the ratio approaches the golden
ratio, (1 + sqrt(5))/2 = 1.6180339887498949, and reaches it (to
machine precision) at 41 terms: the fourth item on each line is
the difference from the golden ratio).

This version uses a modification of a linear recursion algorithm that
is given on p. 371 of this book:

	@String{pub-PH                  = "Pren{\-}tice-Hall"}
	@String{pub-PH:adr              = "Upper Saddle River, NJ 07458, USA"}

	@Book{Evans:2003:IAP,
	  author =       "James S. Evans and Gregory L. Trimper",
	  title =        "{Itanium} architecture for programmers: understanding
			 64-bit processors and {EPIC} principles",
	  publisher =    pub-PH,
	  address =      pub-PH:adr,
	  pages =        "xxxiv + 529",
	  year =         "2003",
	  ISBN =         "0-13-101372-6",
	  LCCN =         "QA76.8.I83 E83 2003",
	  bibdate =      "Wed Aug 20 08:55:32 MDT 2003",
	  acknowledgement = ack-nhfb,
	  keywords =     "Itanium (microprocessor)",
	}

P.S. The obvious simple recursive function evaluation is impractical,
because it suffers exponential growth in run time.
*/

#include <stdio.h>
#include <stdlib.h>
#include <math.h>

#if defined(__sun)
#include <sunmath.h>
#endif

long long
fib_internal(long long n, long long i, long long previous, long long present)
{
    return (i == n) ? present : fib_internal(n, i + 1, present, previous + present);
}

long long
fib(long long n)
{
    return fib_internal(n, 1, 0, 1);
}

int
main(void)
{
    long long fn = 1LL;
    long long fnm1 = 1LL;
    long long n = 1LL;
    long double ratio;
    long double golden_ratio = (1.0 + sqrtl(5.0))/2.0;

    (void)printf("%2lld\t%19lld\n", n, fnm1);

    for (;;)
    {
	n++;
	fnm1 = fn;
	fn = fib(n);
	if (fn < 0LL)
		break;			/* here's the loop exit at integer overflow */
	ratio = (long double)fn/(long double)fnm1;
	(void)printf("%2lld\t%19lld\t%37.33Lf\t%37.33Lf\n",
		     n, fn, ratio, (ratio - golden_ratio));
    }
    return (EXIT_SUCCESS);
}