Re: Fibonacci Numbers

[ambrus]

Here are some variations.

1. To generate fibonacci-numbers sequentially.

   my $x = 1/sqrt(5); for my $n (0 .. 28) { print int($x + 0.5), " "; $x 
   +*= (sqrt(5) + 1)/2; } print "\n";
   

   or

   my($x, $y) = (1, 0); for my $n (0 .. 28) { print $y, " "; ($x, $y) = (
   +$y, $x + $y); } print "\n";
   

2. To generate the nth fibonacci number directly:

   my $n = 28; $x = int(((1 + sqrt(5))/2)**$n / sqrt(5) + 0.5); print $x,
   + "\n";
   

   or

   my $n = 28; my($a, $b, $c, $d, $x, $y) = (0, 1, 1, 1, 1, 0); { 0 != ($
   +n & 1) and ($x, $y) = ($a*$x + $b*$y, $c*$x + $d*$y); $n <= 1 and las
   +t; $n >>= 1; ($a, $b, $c, $d) = ($a*$a + $b*$c, $a*$b + $b*$d, $c*$a 
   ++ $d*$c, $c*$b + $d*$d); redo} print $y, "\n";
   

   (Update: I wonder whether I really need all seven variables for this)

   Update: of course not, $b and $c are the same, so you can omit one of them like this:

   my $n = 28;
   my($a, $b, $d, $x, $y) = (0, 1, 1, 1, 0);
   {
           0 != ($n & 1) and ($x, $y) = ($a*$x + $b*$y, $b*$x + $d*$y);
           $n <= 1 and last;
           $n >>= 1;
           ($a, $b, $d) = ($a*$a + $b*$b, $a*$b + $b*$d, $b*$b + $d*$d);
   redo}
   print $y, "\n";
   

   also I've updated the above code to have $n = 28 instead of $n = '$n'

Update 2006 nov 15: another interesting way for sequentially generating the numbers is this (all four are equivalent).

perl -le'$==1;1while print$==(1+$=+$=*sqrt 5)/2'
perl -le'$==1;1while print$==(1+sqrt 5)*$=/2+.5'
perl -le'$==1;1while print$==$=*1.6180339887+.5'
perl -le'for ($x = 1; $x = int(0.5 + $x * (sqrt(5) + 1)/2); ) { print 
+$x; }'

See also Re: Fibonacci numbers (again).