[net.math] Shortest Fib in Machine Language

joseph@hp-pcd.UUCP (joseph) (08/15/84)

    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

martillo@mit-athena.ARPA (Joaquim Martillo) (08/17/84)

I meant the shortest recursive version of fib.

martillo@mit-athena.ARPA (Joaquim Martillo) (09/08/84)

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