Beefy Boxes and Bandwidth Generously Provided by pair Networks
P is for Practical
 
PerlMonks  

Re: Explain one liner for fibonacci

by JavaFan (Canon)
on Dec 22, 2009 at 09:41 UTC ( #813838=note: print w/ replies, xml ) Need Help??


in reply to Explain one liner for fibonacci

It exploits the fact the regexp will always fail. Note that the (?{$=++}) always succeeds, adding 1 to $= each time it's executed. The trailing ^ cause the pattern to fail. The (^)(1|11\1)* will always succeed, but in such a way the optimizer doesn't spoil things.

Now, because (1|11\1) eats either 1 or 2 characters, and then tries the trick on the rest of the pattern, the number of ways a string of length n can fail is:

F(n) = F(n-1) + F(n-2)
which is the formula for Fibonacci numbers.

Also note that $==1 just means $= = 1.


Comment on Re: Explain one liner for fibonacci
Select or Download Code

Log In?
Username:
Password:

What's my password?
Create A New User
Node Status?
node history
Node Type: note [id://813838]
help
Chatterbox?
and the web crawler heard nothing...

How do I use this? | Other CB clients
Other Users?
Others wandering the Monastery: (4)
As of 2014-11-28 03:11 GMT
Sections?
Information?
Find Nodes?
Leftovers?
    Voting Booth?

    My preferred Perl binaries come from:














    Results (192 votes), past polls