## Wednesday, May 28, 2008

### LINQing the Fibonacci Sequence

I've never been one for algorithms and/or academic type of questions/examples. However, while interviewing for my latest job I was asked to write code to generate the Fibonacci sequence... I struggled through it as much as my poor interviewing skills allowed. It was only my second job interview ever (for my second job ever) so I guess that means I'm batting a 1.000, even if I suck at interviewing ;)

Thinking of something to blog about tonight I figured I could make a FibonacciSequence generator that implemented IEnumerable just for shits and giggles (and I'll send the link to Johnny Mac for possible redemption).

There are a dozen ways to generate the sequence (albeit in the interview I could barely find one - lol), but I chose this way because it easily allowed for the "yield" keyword.

Also, then we can use LINQ over it... Our final code can do this:
`//an enumerator over every Fibonacci //number divisible by 3var qry = (from ulong i                in new FibonacciSequence()           where i % 3 == 0           select i);`

What's even better, is now I'm prepared for that next interview question, which could be "create an enumeration over a distinct ascending ordered list of every Fibonacci number divisible by 3 times every Fibonacci number divisible by 5 whose product is divisible by 17:
`var qry = (from ulong i                in new FibonacciSequence()           from ulong j               in new FibonacciSequence()           where j % 5 == 0               && i % 3 == 0           let res = (double)i*j           where res % 17 == 0           orderby res           select res).Distinct();`

Amazingly, the above code will print out all elements of the enumeration in under 1 second.

And finally, here's the FibonacciSequence class.
`public class FibonacciSequence : IEnumerable<ulong>{    public IEnumerator<ulong> GetEnumerator()    {        yield return 0;        yield return 1;        ulong a = 0;        ulong b = 0;        ulong c = 1;        checked        {            while (true)            {                a = b;                b = c;                try                {                    c = a + b;                }                catch (OverflowException)                {                    yield break;                }                yield return c;            }        }    }    System.Collections.IEnumerator          System.Collections.IEnumerable.GetEnumerator()    {        return GetEnumerator();    }}`

As a final disclaimer - yes, the ulong to double conversion in the first example does result in a loss of precision, so please don't comment on that.

Cheers!