Relay-Version: version B 2.10 5/3/83; site utzoo.UUCP
Posting-Version: version B 2.10.1 6/24/83; site mit-athena.ARPA
Path: utzoo!watmath!clyde!burl!hou3c!hocda!houxm!vax135!cornell!uw-beaver!tektronix!hplabs!intelca!qantel!dual!amd!decwrl!decvax!mit-athena!martillo
From: martillo@mit-athena.ARPA (Joaquim Martillo)
Newsgroups: net.math
Subject: Re: Shortest Fib in Machine Language (Co
Message-ID: <274@mit-athena.ARPA>
Date: Fri, 7-Sep-84 17:00:49 EDT
Article-I.D.: mit-athena.274
Posted: Fri Sep  7 17:00:49 1984
Date-Received: Fri, 14-Sep-84 07:03:37 EDT
References: <249@mit-athe.UUCP>, <13900002@hp-pcd.UUCP>
Organization: MIT, Project Athena, Cambridge, Ma.
Lines: 21


>    Probably the shortest recursive routine is:
>
>    function fib(n : integer) : integer;
>    begin
>     if n < 2 then fib := 1
>     else fib := fib(n-1) + fib(n-2);
>    end;
>
>    However, this requires exponential time.
>
>    (time is proportional to g**n  where g is the golden ratio, 1 + sqrt(5)
>                                                                ------------
>                                                                      2
>
>
>

I was really interested in fib written in machine language.  Writing fib
in a higher level language is no challenge and probably compiles to more
than 9 instructions.