Article View: comp.arch
Article #21115Re: Complex Instructions
From: Paul Dietz
Date: Mon, 08 May 1989 17:40
Date: Mon, 08 May 1989 17:40
15 lines
1152 bytes
1152 bytes
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
Technical Details
Message-ID:
<1989May8.134036.7309@cs.rochester.edu>Path:
arc1-ca.pugleaf.net!utzoo!utgpu!jarvis.csri.toronto.edu!mailrus!cornell!rochester!dietzReferences:
<57252@yale-celray.yale.UUCP> <4101@tolerant.UUCP> <134@dg.dg.com> <2253@pembina.UUCP> <1287@l.cc.purdue.edu> <13396@pasteur.Berkeley.EDU>Show Full Headers
Complete Article Headers
Path: arc1-ca.pugleaf.net!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