Utilizing memoization and Dijkstra’s Fibonacci algorithm to compute large values

More of an acute fascination than anything else I expanded my use of memoization for computation to use a more efficient means of calculating Fibonacci sequences for values of n greater than 40 (previous Fibonacci example takes several minutes to compute value at 45 and is fairly unusable beyond that). To perform the computing of Fibonacci I utilized Dijkstra's algoritm for graph search pathing (algorithm details can be found in EWD654 "In honor of Fibonacci").

Dijkstra's algorithm for Fibonacci:

 D(2n) = (2D(n-1) + D(n))D(n)
D(2n-1) = D(n-1)2 + D(n)2 

This algorithm in C#:

 public static Func Dijkstra = n =>
{
     if( n < 2 )
          return n;

     double half = ( n % 2 == 0 ) ? n / 2 : ( n / 2 ) + 1;

     double p1 = Dijkstra( half );
     double p2 = Dijkstra( half - 1 );
     double result = default( double );

     if( n % 2 == 0 )
          result = ( 2 * p2 + p1 ) * p1;
     else
          result = Math.Pow( p2, 2 ) + Math.Pow( p1, 2 );

     return result;
};

Utilizing the memoization technique the amount of computations performed drops significantly. To compute the value of 50 the following computations are performed:

F(50) = F(25) and F(24)

F(25) and F(24) = F(13) and F(12)

F(13) and F(12) = F(7) and F(6)

F(7) and F(6) = F(4) and F(3); F(3) and F(2)

F(4) and F(3) = F(2) and F(1)

F(3) = F(2) and F(1)

F(2) = F(1) and F(0)

F(1) and F(0) are 1 and 0

Utilizing this technique the number of computations required is 14. At the cost of some space the computations become faster as the graph becomes denser.

Technorati Tags: C#,code,tech,software,algorithms