Beefy Boxes and Bandwidth Generously Provided by pair Networks
XP is just a number

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.

Log In?

What's my password?
Create A New User
Node Status?
node history
Node Type: note [id://813838]
and all is quiet...

How do I use this? | Other CB clients
Other Users?
Others perusing the Monastery: (5)
As of 2017-09-20 17:40 GMT
Find Nodes?
    Voting Booth?
    During the recent solar eclipse, I:

    Results (237 votes). Check out past polls.