/** 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
#include
#include
#if defined(__sun)
#include
#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);
}