Path: utzoo!utgpu!news-server.csri.toronto.edu!cs.utexas.edu!swrinde!zaphod.mps.ohio-state.edu!rpi!uupsi!sunic!chalmers.se!mathrt0.math.chalmers.se!augustss
From: augustss@cs.chalmers.se (Lennart Augustsson)
Newsgroups: comp.benchmarks
Subject: Re: BYTE and benchmarks (anecdote)
Message-ID: <1991Jan10.135814.29579@mathrt0.math.chalmers.se>
Date: 10 Jan 91 13:58:14 GMT
References: <1991Jan8.101912.15157@odin.diku.dk> <EACHUS.91Jan8114647@aries.linus.mitre.org>
Sender: news@mathrt0.math.chalmers.se (Evald Nyhetsson)
Distribution: comp
Organization: Dept. of CS, Chalmers, Sweden
Lines: 35

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.)
>

To do this we consult the classic MIT HAKMEM, item 12.  This explains
exactly how to do it.  Define multiplication on pairs by
(a,b)(c,d)=(ac+ad+bc,ac+bd)
Note that (a,b)(1,0) = (a+b,a) and thus (1,0)**n = (fib(n),fib(n-1)).
Then use the usual trick with repeated squaring to do the exponentiation
in log n operations (which is log n time if you have constant time
arithmetic).

This is a nice method since it uses only integer arithmetic (as
opposed to solving the difference equation and computing
exponentiation of something with sqrt(5)).

Here is a Haskell program to do it:
------
instance (Num a) => Num (a,a) where
	(a,b) * (c,d) = (a*c+a*d+b*c, a*c+b*d)
fib n = fst ((1,0)^n)
------
Some sample results:
fib 10 = 55
fib 46 = 1836311903
fib 100 = 354224848179261915075
fib 1000 = 43466557686937456435688527675040625802564660517371780402481729
08953655541794905189040387984007925516929592259308032263477520968962323987332
2471161642996440906533187938298969649928516003704476137795166849228875
All of which take a very short time to compute (of course).

	-- Lennart Augustsson
[This signature is intentionally left blank.]