Path: utzoo!utgpu!news-server.csri.toronto.edu!rutgers!ucsd!sdd.hp.com!spool2.mu.edu!uunet!mcsun!hp4nl!ruuinf!ruunsa!hooft
From: hooft@ruunsa.fys.ruu.nl (Rob Hooft)
Newsgroups: comp.benchmarks
Subject: Re: BYTE and benchmarks (anecdote)
Message-ID: <1872@ruunsa.fys.ruu.nl>
Date: 10 Jan 91 08:47:19 GMT
References: <1991Jan8.101912.15157@odin.diku.dk> <EACHUS.91Jan8114647@aries.linus.mitre.org>
Distribution: comp
Organization: University of Utrecht, Dept. of Physics
Lines: 26

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

Do not read on if you want to try yourself. I tried to mail the result but
it bounced (user eachus unknown).

      program test
      do i=1,46
        write(*,*) ifib(i)
      enddo
      end

      function ifib(i)
c
c The actual function is:
c      fib=(((1.+5.**.5)/2.)**i-((1.-5.**.5)/2.)**i)/5.**.5
c
      ifib=int(aint(((1.d0+5.d0**.5d0)/2.d0)**i)/5.d0**.5d0)+1
      end
-- 
Rob Hooft, Chemistry department University of Utrecht.
hooft@hutruu54.bitnet hooft@chem.ruu.nl hooft@fys.ruu.nl