|
dReKurCe has asked for the wisdom of the Perl Monks concerning the following question:
Greetings Monks,
The following is my version of Fibonaccii generation,but I figured there must be some cool one liners to do the same.
Any offerings?
#! / usr/bin/perl
{fib(0,1)};
for (1...23){
fib ($sum ,$val0) ;
print " fibonaci number $_ is $sum \n";
}
sub fib{
($val0, $val1) =@_;
$sum= $val0 + $val1;
}
|
Re: Fibonacci Numbers
by jweed (Chaplain) on Feb 10, 2005 at 02:28 UTC
|
2 things:
If you stick with the original form of your answer (a recurrance-based one), try Memoizing it, viz.:
# Compute Fibonacci numbers, straight from Memoize docs
use Memoize;
memoize('fib');
sub fib {
my $n = shift;
return $n if $n < 2;
fib($n-1) + fib($n-2);
}
my $foo = fib(24);
Such a strategy stores the results of previous iterations for later use, so you only have to calculate each result once. Once you do, it's stored (behind the scenes) in a hash which reconstructs it on demand. This makes things much faster.
But more importantly, I would offer this verson of an answer as a possible contender. It's a one-liner, but of a different style:
sub fib{int(((((1+sqrt(5))/2)**$_[0])/sqrt(5))+.5)}
enjoy!
| [reply]
[d/l]
[select] |
|
|
Sweet! The Binet Formula! This Mathworld entry shows how the Fibonacci sequence, the Binet Forms and the Golden Ratio fit together.
For all the times the Fibonacci sequence comes up as an exercise in programming recursion, I've never seen it solved quite like that. Goes to show that TIMTOWTDI, as usual.
| [reply] |
|
|
If you stick with the original form of your answer (a recurrance-based one), try Memoizing it, viz.:
But the original form of his answer was not recursive:
sub fib{
($val0, $val1) =@_;
$sum= $val0 + $val1;
}
| [reply]
[d/l] |
|
|
Honourable friar,
Am I wrong to think that recurrsion is utilized by passing the value of $sum as computed by sub fib back into sub fib? Otherwise, the binet formula is extremely cool. Thanks.
| [reply] |
|
|
|
|
|
|
sub fib {int(((((1+sqrt(5))/2)**$_[0])/sqrt(5))+.5)}
sub fib2 {
my ($n) = @_;
my ($x, $y) = (1, 1);
($x, $y) = ($y, $x + $y)
for 3 .. $n;
return $y;
}
for (my $n = 1; 1; $n++) {
my ($x, $y) = (fib($n), fib2($n));
if ($x != $y) {
print "$n: $x $y";
last;
}
}
__END__
71: 308061521170130 308061521170129
Regards,
ihb
See perltoc if you don't know which perldoc to read!
| [reply]
[d/l] |
|
|
Try Math::BigFloat's rounding handling instead of the int(foo+.5) trick, and things should work out.
| [reply] |
Re: Fibonacci Numbers
by artist (Parson) on Feb 10, 2005 at 02:30 UTC
|
use Math::Fibonacci qw(series);
my @series = series ( 23 );
| [reply]
[d/l] |
Re: Fibonacci Numbers
by saintmike (Vicar) on Feb 10, 2005 at 01:02 UTC
|
There was a perlgolf competition on this. The winner's script had 41 characters. | [reply] |
Re: Fibonacci Numbers
by sh1tn (Priest) on Feb 10, 2005 at 01:23 UTC
|
If this is the right place for this one-liner:
@a=(1);map{push@a,$a[-2]+$a[-1];print"$_:$a[$#a]$/"}1..23
| [reply]
[d/l] |
|
|
$.++;$.+=$l,$l=$.-$l,print"$. "for 1..23
| [reply]
[d/l] |
|
|
Honourable monk,
This is interesting, does the output of the second need to be piped through the first?
| [reply] |
|
|
Re: Fibonacci Numbers
by ambrus (Abbot) on Feb 10, 2005 at 07:50 UTC
|
Here are some variations.
-
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";
-
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).
| [reply]
[d/l]
[select] |
Re: Fibonacci Numbers
by murugu (Curate) on Feb 10, 2005 at 09:27 UTC
|
@_=(0,1);map{print $_[0];push@_,shift(@_)+$_[0]}1..pop
Regards,
Murugesan Kandasamy.
| [reply]
[d/l] |
|
|
Not exactly a one-liner, but interesting in it own right as well. This is for a 64-bit integer perl - a 32-bit integer version needs a smaller table.
#!/usr/bin/perl
use strict;
use warnings;
my @fib = (
0,
1,
1,
2,
3,
5,
8,
13,
21,
34,
55,
89,
144,
233,
377,
610,
987,
1597,
2584,
4181,
6765,
10946,
17711,
28657,
46368,
75025,
121393,
196418,
317811,
514229,
832040,
1346269,
2178309,
3524578,
5702887,
9227465,
14930352,
24157817,
39088169,
63245986,
102334155,
165580141,
267914296,
433494437,
701408733,
1134903170,
1836311903,
2971215073,
4807526976,
7778742049,
12586269025,
20365011074,
32951280099,
53316291173,
86267571272,
139583862445,
225851433717,
365435296162,
591286729879,
956722026041,
1548008755920,
2504730781961,
4052739537881,
6557470319842,
10610209857723,
17167680177565,
27777890035288,
44945570212853,
72723460248141,
117669030460994,
190392490709135,
308061521170129,
498454011879264,
806515533049393,
1304969544928657,
2111485077978050,
3416454622906707,
5527939700884757,
8944394323791464,
14472334024676221,
23416728348467685,
37889062373143906,
61305790721611591,
99194853094755497,
160500643816367088,
259695496911122585,
420196140727489673,
679891637638612258,
1100087778366101931,
1779979416004714189,
2880067194370816120,
4660046610375530309,
7540113804746346429,
);
sub fib {$fib[$_[0]]}
__END__
No calculations needed. | [reply]
[d/l] |
|
|
Honourable abbot,
Your one liner failed to generate output, perhaps I'm missing something. i plan to
study the map function to make
more sence of it. Thanks.
| [reply] |
|
|
This was addressed to murugu.
| [reply] |
|
|
Re: Fibonacci Numbers
by gube (Parson) on Feb 10, 2005 at 08:11 UTC
|
@ar = (1);
map{push@ar,$ar[-2]+$ar[-1]}1..23;
print "\n$_" for (@ar);
Regards,
Gubendran.L | [reply]
[d/l] |
Re: Fibonacci Numbers
by tmoertel (Chaplain) on Feb 11, 2005 at 02:21 UTC
|
Cool one liners for the Fibonacci series? Sure, there are bunches of
them. Here's one that I wrote during an email exchange on the subject
in which I was dared to "do something with bitwise ops":
perl -le'map{$_=$b.$a|"~",$b=$a,$a=$_,print}1..pop' 10
It doesn't just compute the series but also graphs it.
In the same exchange, the author of the dare (who shall remain
nameless) also made the wisecrack that "recursion is for wimps."
That compelled me to trot out the old Haskell classic:
fibs@(_:x) = 1 : 1 : zipWith (+) fibs x
That's it. The whole infinite series. Want the
first 50 elements?
Fib> take 50 fibs
[1,1,2,3,5,8,13,21,34,55,89,144,233,377,610,987,1597,2584,4181,6765,10
+946,17711,28657,46368,75025,121393,196418,317811,514229,832040,134626
+9,2178309,3524578,5702887,9227465,14930352,24157817,39088169,63245986
+,102334155,165580141,267914296,433494437,701408733,1134903170,1836311
+903,2971215073,4807526976,7778742049,12586269025]
Fun stuff.
Cheers,
Tom
| [reply]
[d/l]
[select] |
Re: Fibonacci Numbers
by sh1tn (Priest) on Jun 17, 2005 at 03:15 UTC
|
$.++;$.+=$,,$,=$.-$,,print$.for@_
| [reply]
[d/l] |
Re: Fibonacci Numbers
by johndageek (Hermit) on Feb 10, 2005 at 21:47 UTC
|
@_=(1,1);
for(1...23){
$a=!$a+0;
print @_[$a]=@_[!$a] + @_[$a] . "\n";
}
| [reply]
[d/l] |
|
|
| [reply]
[d/l] |
|
|
Really? Sure, with warnings, you get a warning message.
However, the program produces what it should produce, so the
warnings generated are a nuisance.
Perhaps you say "yeah, I know, but golly, perhaps in the
future '@_[$a]' will mean something else". But that, I don't
believe. In fact, in the future, in perl6, '@_[$a]' will be
the correct way and '$_[$a]' will be wrong way. I don't think
anyone will give '@_[$a]' a meaning other than '$_[$a]' in
perl 5.12, or another perl5 version. Ever.
(As for why this is all in 'code' tags, I've used [] several
times in the posts. It's too much of a hassle to type 13
characters for each occurance)
| [reply]
[d/l] |
|
|
|
|
|
|
