Monday, September 13, 2010

Finding Fibonacci numbers using regex

This is one of the more fun patterns I've written; it exploits the Second Identity of Fibonacci Numbers.


final String FIBONACCI = 
   "(?x) .? | ( \\2?+ (\\1|^.) )* ..";
                        
for (int n = 0; n < 10000; n++) {
   String s = new String(new char[n]);
   if (s.matches(FIBONACCI)) {
      System.out.printf("%s ", n);
   }
}
// 0 1 2 3 5 8 13 21 34 55 89 144 233 377 610 987 1597 2584 4181 6765
(see also on ideone.com | PHP | C#)

I should probably elaborate more on this for stackoverflow someday, but here are important variations of the pattern:
(?x) .? | (     \2?+ (\1|^.) )* ..
// possessive optional forward reference (Java, PCRE)

(?x) .? | (  (?>\2?) (\1|^.) )* ..
// greedy optional forward reference in an atomic group (Java, .NET, PCRE)

(?x) .? | ( (?:\2|^) (\1|^.) )* ..
// non-optional forward reference with explicit first iteration alternative (Java, .NET, PCRE)
The main purpose of making the forward reference optional in the first two patterns is to make it through the first iteration (before group 2 even captures anything). However, this also has the side effect of allowing it to opt out at the last iteration. In this setup, this is not a problem since \1 is always at least as long as \2, so if we're forced to opt out of matching \2, we can never then match \1.

Needless to say, it's crucial that the optional forward reference is non-backtrackable, because opting out on any iteration but the last would cause mismatches.

1 comment:

  1. Your algorithm got a question on stackoverflow and I did my best to answer it: http://stackoverflow.com/questions/18623801/finding-fibonacci-numbers-using-regex

    Let me know if my analysis seems correct to you.

    Thanks,

    James

    ReplyDelete