Chad Perrin: SOB

15 December 2006

UCBLogo and the Fibonacci sequence

Filed under: Geek,Metalog — apotheon @ 02:54

I’ve recently commented on syntax for generating Fibonacci numbers. Slightly more recently, I compared UCBLogo and Perl on the subject of reversing the order of words in a string. I figured I might as well provide examples of UCBLogo, in some context, for generating Fibonacci numbers.

These examples will only generate the final number of a given Fibonacci sequence, and will not output the entire sequence (despite the fact that they tend to need to iterate or recurse through the whole sequence to get to that number, some more explicitly than others). I’ll start by repeating some already presented examples, then go on to the new stuff.

Perl:


sub fib {
  my ($n, $a, $b) = (shift, 0, 1);
  ($a, $b) = ($b, $a + $b) while $n-- > 0;
  $a;
}

Perl (recursion):


sub fib {
  my $n = shift;
  return $n if $n < 2;
  return fib($n - 1) + fib($n - 2);
}

Python (I’m sure scoth or ToyKeeper will tell me if I screwed it up):


import sys

def fib(): a, b, n = 0, 1, int(sys.argv[1]) while n >= 0: yield a a, b, n = b, a+b, n-1

UCBLogo, inefficient but pretty version:


to fib :n
  if :n<2 [output 1]
  output (fib :n-1)+(fib :n-2)
end

UCBLogo, succinct but otherwise intermediate version:


to fib :n
  output (cascade :n [?1+?2] 1 [?1] 0)
end

UCBLogo, verbose but efficient version:


to fib :n
  output first fiblist :n
end

to fiblist :n if :n<2 [output [1 1]] output newfib fiblist :n-1 end

to newfib :list output fput (sum first :list first butfirst :list) :list end

Just for the extra comparisons, I'll throw in a few more languages, as borrowed from others' code.

PHP (I shudder):


function generatefibonaccisequence( $length ) {
    for( $l = array(1,1), $i = 2, $x = 0; $i < $length; $i++ )
            $l[] = $l[$x++] + $l[$x];

return $l;

}

Lisp with recursion (of course):


(define fibo
  (lambda (x)
    (if (< x 2)
      x
      (+ (fibo (- x 1)) (fibo (- x 2))))))

Python (yes, more of it, this time with recursion so it's prettier):


def fib(n):
   if   n < 2: return 1
   else      : return fib(n - 1) + fib(n - 2)

Haskell (recursive, obviously):


fib 0 = 0
fib 1 = 1
fib n = fib (n-1) + fib (n-2)

OCaml (described as "a nice closed form" by its contributor on reddit):


let fibonacci n = let phi = ((1. +. sqrt 5.) /. 2.) in
  (intoffloat (((phi ** (floatofint n)) -. 
  ((1. -. phi) ** (floatofint n))) /. sqrt 5.))

let fibs n = let rec fibsi n i = match i with | 0 -> [fibonacci n] | _ -> fibonacci (n - i) :: fibs_i n (i - 1) in fibsi n n;;

Matlab (also from reddit):


([1 1; 1 0]^n)(1,1)

PHP (from reddit, natch):


function fib( $n ){
    return ( $n?2 )
           ? $n
           : fib( $n-1 )+fib( $n-2 );}

HSQL (yes, really -- only on reddit does this stuff arise): Read it HERE, since it's too long to use with code and pre tags without most of it being invisible in your browser if I post it here at SOB. Be forewarned, though, that you may need medical attention after viewing this code, particularly if you're epileptic. (note: Apparently, this code doesn't have anything to do with Fibonacci numbers, according to a commenter here. I really wouldn't know. It just looks like gibberish to me, anyway.)

Comments? Questions? Code snippets in other languages? Improvement to some here? It should be noted that I copied a couple of these things across (or linked to them) without understanding a word of it, like the HSQL. Ugh.

All original content Copyright Chad Perrin: Distributed under the terms of the Open Works License