Path: utzoo!utgpu!jarvis.csri.toronto.edu!mailrus!uflorida!ukma!rutgers!aramis.rutgers.edu!klaatu.rutgers.edu!josh
From: josh@klaatu.rutgers.edu (J Storrs Hall)
Newsgroups: comp.arch
Subject: Re: Complex Instructions
Keywords: algorithms
Message-ID: <May.8.19.11.11.1989.7009@klaatu.rutgers.edu>
Date: 8 May 89 23:11:16 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> <1989May8.134036.7309@cs.rochester.edu>
Organization: Rutgers Univ., New Brunswick, N.J.
Lines: 20

Paul F. Dietz writes:

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

Or, using the same trick, generate all the fibonacci numbers up to
the nth in log n time in arithmetic vector operations.  

However, there is a catch:  the arithmetic operations are multiply
rather than add.  And since we're talking about architecture here,
remember that for any of this to make any difference at all you 
must be considering values of n where the size of the number is way
over any reasonable word size.  Every arbitrary-precision arithmetic
package I've seen has linear add and quadratic multiply.  Given
that, both algorithms are quadratic in n.

--JoSH