 Pathologically Eclectic Rubbish Lister PerlMonks

Explain Fibonacci one-liner ??

 on May 10, 2010 at 15:36 UTC Need Help??

Anonymous Monk has asked for the wisdom of the Perl Monks concerning the following question:

Hi all,
Can anyone please explain this code for printing fibonacci series

\$ perl -le ' \$==1,(1 x \$_)=~/(^)(1|11\1)*(?{\$=++})^/,print \$= for 0..1 +0'
2 3 5 8 13 21 34 55 89 144 233

Replies are listed 'Best First'.
Re: Explain Fibonacci one-liner ??
by JavaFan (Canon) on May 10, 2010 at 15:47 UTC
Main loop initializes \$= each time to 1, and creates a string of sizes 0, 1, 2, ... 10. This string is matched against the regexp.

Note that the pattern does not match (due to the trailing ^), so basically what's happening that \$= counts the number of times the regexp engine will backtrack. We can simplify the pattern a little:

/^(1|11)*^/
(the capture and backref of the anchor are just there to confuse the optimizer). So, what the pattern is counting how many times it can partition a string into 1 and 2 character substrings. Let's call this number F(n), for a string of size n. The pattern says "either match '1' or match '11'; then recurse with the rest". How many times can we do that? F(n+1) + F(n+2). So, we derive:
F(n) = F(n+1) + F(n+2)
Hmmm. That's exactly the definition of the Fibonacci series (except for the initial condition).
Re: Explain Fibonacci one-liner ??
by Marshall (Canon) on May 10, 2010 at 16:56 UTC
This is an unnecessary obfuscation for no apparent reason. The statement albeit short is very obtuse. JavaFan has given a great explanation of how this obscure thing works.

A Perl implementation of a more traditional and MUCH faster approach is below. Perl allows very obscure looking code to be written, but why do it?

#!/usr/bin/perl -w use strict; foreach (1..15) { print fibonacci(\$_), " "; } # prints: 1 1 2 3 5 8 13 21 34 55 89 144 233 377 610 sub fibonacci { my \$number = shift; my \$cur_num = 1; my \$prev_num = 1; my \$sum; return 1 if (\$number == 1 || \$number == 2); # to get Op's output, supress the above by this: # return "" if (\$number == 1 || \$number == 2); # or of course just start the sequence at a different number \$number -= 2; while (\$number--) { \$sum = \$cur_num + \$prev_num; \$prev_num = \$cur_num; \$cur_num = \$sum; } return \$sum; }
And even faster again is a solution based on the property:
F(n) = floor((((1+sqrt(5))/2)**n) / sqrt(5)) + 0.5)
my \$PHI = (1 + sqrt(5)) / 2; sub fib (\$) {int(\$PHI ** \$_ / sqrt(5) + 0.5)} say fib \$_ for 0 .. 10; __END__ 0 1 1 2 3 5 8 13 21 34 55
Re: Explain Fibonacci one-liner ??
by ambrus (Abbot) on May 10, 2010 at 19:02 UTC

See Explain one liner for fibonacci for the exact same question and answers.

For reference, the original source for that one-liner is Re^2: The Oldest Plays the Piano.

Update: As that thread also links to the explanation, I wonder where you found this one-liner but not the explanation. Maybe I've posted this node anonymously while sleepwalking to popularize my obfu?

Re: Explain Fibonacci one-liner ??
by biohisham (Priest) on May 10, 2010 at 19:17 UTC
Memoize provides an interesting direct forward example on implementing Fibonnaci's series and making functions faster ...

Excellence is an Endeavor of Persistence. Chance Favors a Prepared Mind.
Re: Explain Fibonacci one-liner ??
by Marshall (Canon) on May 10, 2010 at 22:04 UTC
I ran some benchmarks on this fibonacci code.
The JavaFan code is the fastest. My code is 2nd. There is no 3rd, 4th or 5th place. Things go "downhill" very fast (not just factor of 2x, 3x, but orders of magnitude).
The JavaFan code is the fastest. My code is 2nd. There is no 3rd, 4th or 5th place. Things go "downhill" very fast (not just factor of 2x, 3x, but orders of magnitude).
Actually, so does yours. It's just not visible because of the very limited range. Upping the range to 1..90 gives:
Benchmark: running JavaFan, Marshall for at least 2 CPU seconds... JavaFan: 2 wallclock secs ( 2.18 usr + 0.00 sys = 2.18 CPU) @ 44 +81.19/s (n=9769) Marshall: 1 wallclock secs ( 2.00 usr + 0.00 sys = 2.00 CPU) @ 34 +2.50/s (n=685)
Also note that your move to put the assignment of \$PHI inside the subroutine reduced the running speed by about 10% (it does 5063.11 iterations/s with \$PHI only assigned to once).

Incrementing the range even further would increase the difference even more, but for some N between 90 and 100, F(N) no longer fits inside a 64bit integer. And I didn't want to spend the time to write a benchmark using Math::BigFloat/Math::BigInt.

I don't want to write more benchmarks either. I think enough said about this. If the Op wants to beat it to death..he/she has a lot of info to work with.

Create A New User
Domain Nodelet?
Node Status?
node history
Node Type: perlquestion [id://839244]
Approved by Corion
Front-paged by Corion
help
Chatterbox?
and the web crawler heard nothing...

How do I use this? | Other CB clients
Other Users?
Others making s'mores by the fire in the courtyard of the Monastery: (7)
As of 2022-01-18 22:20 GMT
Sections?
Information?
Find Nodes?
Leftovers?
Voting Booth?
In 2022, my preferred method to securely store passwords is:

Results (54 votes). Check out past polls.

Notices?