Path: utzoo!utgpu!jarvis.csri.toronto.edu!mailrus!cornell!rochester!dietz
From: dietz@cs.rochester.edu (Paul Dietz)
Newsgroups: comp.arch
Subject: Re: Complex Instructions
Keywords: algorithms
Message-ID: <1989May8.134036.7309@cs.rochester.edu>
Date: 8 May 89 17:40:35 GMT
References: <57252@yale-celray.yale.UUCP> <4101@tolerant.UUCP> <134@dg.dg.com> <2253@pembina.UUCP> <1287@l.cc.purdue.edu> <13396@pasteur.Berkeley.EDU>
Reply-To: dietz@cs.rochester.edu (Paul Dietz)
Organization: U of Rochester, CS Dept, Rochester, NY
Lines: 15

In article <13396@pasteur.Berkeley.EDU> dean@columbine.Berkeley.EDU (R. Drew Dean) writes:

>	Look at generating Fibonacci numbers.  The obvious algorithm
>	F(n) = F(n-1) + F(n-2) generates a process with exponential
>	running time, but this can be transformed into a process with
>	linear running time...[new algorithm omitted]

You can generate the nth Fibonacci number using O(log n) arithmetic
operations (albeit operations on numbers with O(n) bits).

Hint:  if A is the 2x2 matrix ((0 1) (1 1)), the lower right corner
of A^n contains Fib(n+1).

	Paul F. Dietz
	dietz@cs.rochester.edu