Path: utzoo!utgpu!news-server.csri.toronto.edu!cs.utexas.edu!uunet!bu.edu!xylogics!merk!alliant!linus!linus!eachus From: eachus@linus.mitre.org (Robert I. Eachus) Newsgroups: comp.benchmarks Subject: Re: BYTE and benchmarks (anecdote) Message-ID: Date: 8 Jan 91 16:46:47 GMT References: <1991Jan8.101912.15157@odin.diku.dk> Sender: usenet@linus.mitre.org Distribution: comp Organization: The Mitre Corporation, Bedford, MA Lines: 40 Nntp-Posting-Host: aries.mitre.org In-reply-to: torbenm@diku.dk's message of 8 Jan 91 10:19:12 GMT 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 actually wrote a Fibonacci program that worked this way (in APL, what else) and it is a very good example of how vectorizing or partitioning of code well is not something a compiler can do for you. Computing the entire vector of Fibonacci numbers (in an APL one-liner of course) is much faster than even the non-recursive formula, because there is only one line to interpret (once). The same thing occurs if you have a vector machine handy. Computing powers seems expensive until you realize that ANY straight line code which uses the vector pipes will win over an iterative (scalar) loop. (The square root of 5 is a constant {hint}, and the second term need not be computed if you truncate to an integer.) So here is a challenge to you vector machine freaks out there. My handy dandy pocket calculator tells me that F(50) = 12586269025 (hmmm, a little big for most people) and F(46) = 1836311903 (that's better--as in less than 2**31), so how fast can you calculate the first 46 (to put the integer and floating people on the same footing) Fibonacci numbers? Or better yet, how long does your function to compute a given Fibonacci number take to run, when called a equal number of times with arguments 0 to 46. This is not so much a benchmark as a challenge to find out how your favorite machine works, and to show how ferocious application of analysis of algorithms can speed up a program. 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