mostlylucid

STATIC ARCHIVE of mostlylucid.co.uk of old
posts - 892, comments - 676, trackbacks - 11

My Links

News

follow me on twitter!

Archives

Post Categories

Misc. Coding

Fibonacci...coding efficiently (when doing nothing is the fastest route)

Just a little diversion, I posted previously about some code which I didn't think of until I was in the elevator following  a pretty important meeting (details may follow ). I asked how you'd make this code more efficient for multi-core CPUs...well I'll get to that but one thing I didn't point out was that with this as with any other computationally intensive code, the most efficient approach is not to do the operation in the first place.
Caching...not on the web but probably the simplest form of caching you could perform, store a previous result for future use. For the code I previously had we saw a double-expotential increase in the amount of computations that had to be performed with the result that you rapidly got to the point where even the fastest processor would grind to a halt. But one thing is obvious, you always use the previous two results to get the current one...so why not store these rather than recalculate each time? Which brings us to this:

using System;
namespace Fibonacci
{
    class Program
    {
        const int positions = 1000;
        static double[] valueArr = new double[positions];
        
        static void Main(string[] args)
        {
            for (int x = 0; x < positions; x++)
            {
                double val = CalFib(x);
                valueArr[x] = val;
                Console.WriteLine(val);
            }
            Console.Read();
        }
        static double CalFib(int n)
        {
            return n<=1? n : valueArr[n - 1] + valueArr[n - 2];
        }
    }
}

Simple, but a very nice way to demonstate the power of caching!

Print | posted on Sunday, September 30, 2007 3:38 PM | Filed Under [ .NET Code Snippets ]

Feedback

No comments posted yet.

Post Comment

Title  
Name  
Email
Url
Comment   
Please add 7 and 2 and type the answer here:

Powered by: