ckv ckv - 1 month ago 18
C# Question

Optimized way to find Padovan numbers

What is the most optimized way to find Padovan number?
This is what I have currently.
Even though it returns correct result, I want to know what is the quickest method possible.

long Sum = 0;
public long Get(int number)
{
Sum = 0;
if (number == 0 || number == 1 || number == 2)
return 1;
return GetPadovanAlt(number);
}

public long GetPadovanAlt(int n)
{
if(n == 0 || n == 1 || n == 2)
return 1;
return GetPadovanAlt(n - 2) + GetPadovanAlt(n - 3);

}

Answer

Since you specifically ask about C# and optimization I have provided code which I think will set you in the correct direction. First the output of the program:

From https://oeis.org/A000931
Ref: 1  0  0  1  0  1  1  1  2  2  3  4  5  7  9  12  16  21  28  37  49  65  86  114  151  200  265
Rec: 1  0  0  1  0  1  1  1  2  2  3  4  5  7  9  12  16  21  28  37  49  65  86  114  151  200  265
Qik: 1  0  0  1  0  1  1  1  2  2  3  4  5  7  9  12  16  21  28  37  49  65  86  114  151  200  265

Recursive method:   709.238100 ms   checksum: 35676949
Quick     method:     0.004800 ms   checksum: 35676949

As you can see there is a considerable difference between the recursive and the 'quick' method. There are several reasons for this. First is that recursion requires considerable extra work moving addresses & values on and off the stack for each function call (and there are a lot of calls). Second this code uses a statically allocated array (not thread safe) as a work area when calling the quick method. You could allocate the array inside the method but that would require a small amount of extra time.

The quick method does little more than enter a for loop to calculate the values directly into the static array. You could make a class of this and initialize the first four array values only once. You could also keep track of the last value calculated so that you could start from that position when calculating larger values, or use the 'n' as an index to directly retrieve a pre-calculated value.

Here is the code (creatively named ConsoleApplication1 ;-))

using System;
using System.Diagnostics;

namespace ConsoleApplication1 {
    class Program {
        static public long GetPadovanRecursive(int n) {
            if (n == 0) { return 1; }
            if (n == 1) { return 0; }
            if (n == 2) { return 0; }
            if (n == 3) { return 1; }
            return GetPadovanRecursive(n - 2) + GetPadovanRecursive(n - 3);
            }

        static int N_Max = 8192;
        static long[] pdvn = new long[N_Max];

        static public long GetPadovanQuick(int n) {
            Debug.Assert(n < N_Max);
            if (n == 0) { return 1; }
            if (n == 1) { return 0; }
            if (n == 2) { return 0; }
            if (n == 3) { return 1; }

            pdvn[3] = 1;
            for (int i = 4; i <= n; i++) {
                pdvn[i] = pdvn[i - 2] + pdvn[i - 3];
                }
            return pdvn[n];
            }


        static void Main(string[] args) {
            const int Count = 64;
            Stopwatch stp = new Stopwatch();

            // Sanity check
            Console.WriteLine("From https://oeis.org/A000931");
            Console.WriteLine("Ref: 1  0  0  1  0  1  1  1  2  2  3  4  5  7  9  12  16  21  28  37  49  65  86  114  151  200  265");
            Console.Write("Rec: ");
            for (int i = 0; i < 27; i++) {
                Console.Write("{0}  ", GetPadovanRecursive(i));
                }
            Console.WriteLine();
            Console.Write("Qik: ");
            for (var i = 0; i < 27; i++) {
                Console.Write("{0}  ", GetPadovanQuick(i));
                }
            Console.WriteLine();
            Console.WriteLine();

            long sum = 0;
            stp.Start();
            for (int i = 0; i < Count; i++) {
                sum += GetPadovanRecursive(i);
                }
            stp.Stop();
            Console.WriteLine("Recursive method: {0,12:F6} ms   checksum: {1}", stp.Elapsed.TotalMilliseconds, sum);


        sum = 0;
        stp.Restart();
        for (var i = 0; i < Count; i++) {
            sum += GetPadovanQuick(i);
            }
        Console.WriteLine("Quick     method: {0,12:F6} ms   checksum: {1}", stp.Elapsed.TotalMilliseconds, sum);
        }
    }
}
Comments