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 3
var 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!

No comments: