Beefy Boxes and Bandwidth Generously Provided by pair Networks
Pathologically Eclectic Rubbish Lister

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?

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

How do I use this? | Other CB clients
Other Users?
Others musing on the Monastery: (10)
As of 2015-12-01 21:54 GMT
Find Nodes?
    Voting Booth?

    My keyboard shows this many letters:

    Results (28 votes), past polls