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;
while (true)
a = b;
b = c;
c = a + b;
catch (OverflowException)
yield break;
yield return c;

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.


1 comment:

Smith said...

Hi, Great.. Tutorial is just awesome..It is really helpful for a newbie like me.. I am a regular follower of your blog. Really very informative post you shared here. Kindly keep blogging. If anyone wants to become a .Net developer learn from Dot Net Training in Chennai. or learn thru ASP.NET Essential Training Online . Nowadays Dot Net has tons of job opportunities on various vertical industry.
or Javascript Training in Chennai. Nowadays JavaScript has tons of job opportunities on various vertical industry.