Path: utzoo!attcan!uunet!convex!news
From: patrick@convex.COM (Patrick F. McGehearty)
Newsgroups: comp.benchmarks
Subject: Re: BYTE and benchmarks (anecdote)
Message-ID: <1991Jan09.171216.21923@convex.com>
Date: 9 Jan 91 17:12:16 GMT
References: <1991Jan8.101912.15157@odin.diku.dk> <EACHUS.91Jan8114647@aries.linus.mitre.org>
Sender: news@convex.com (news access account)
Reply-To: patrick@convex.COM (Patrick F. McGehearty)
Distribution: comp
Organization: Convex Computer Corporation, Richardson, Tx.
Lines: 33
Nntp-Posting-Host: mozart.convex.com

In article <EACHUS.91Jan8114647@aries.linus.mitre.org> eachus@linus.mitre.org (Robert I. Eachus) writes:
>
>     Exercise for the reader: Write a function to compute the Nth
>Fibonacci number in O(log n) time.... (Constant time if you limit
>yourself to 32-bit integers.)
>
I'm not sure how vectors figure in, but with a constraint of
0 <= N <= 46, it can be quite easy:
	precompute the first 46 Fibonacci numbers and assign them in
	a DATA statement to FIBON.  Then the function is:
	INTEGER FUNCTION FIBONACCI(N)
	COMMON /FIB/FIBON(47)
	INTEGER FIBON
	FIBONACCI = FIBON(N+1)    ! compensate for one-based arrays
	RETURN
	END

Of course, good software engineering practice would check N for being
within bounds, and do something appropriate, but this is comp.benchmarks. :-)

Adding the constraint of computing the number on the fly with a maximum
of k prestored values instead of precomputing the table will add more of a
challenge to the exercise.  k << max(N)

>     I'll post a benchmark program in a couple of days, but I want to
>challenge some of you first...
>
>--
>
>					Robert I. Eachus
>
>     When the dictators are ready to make war upon us, they will not
>wait for an act of war on our part." - Franklin D. Roosevelt