Beefy Boxes and Bandwidth Generously Provided by pair Networks
Welcome to the Monastery
 
PerlMonks  

Re: Explain one liner for fibonacci

by JavaFan (Canon)
on Dec 22, 2009 at 09:41 UTC ( [id://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.

Log In?
Username:
Password:

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

How do I use this?Last hourOther CB clients
Other Users?
Others studying the Monastery: (4)
As of 2024-03-19 04:56 GMT
Sections?
Information?
Find Nodes?
Leftovers?
    Voting Booth?

    No recent polls found