Write Optimized Code – Part 1

Share the knowledge with others
  •  
  •  
  •  
  •  
  •  
  •  
  •  
  •  
  •  
  •  
  •  
  •  
  •  
  •  
  •  
  •  
  •  
  •  
  •  
  •  
  •  
  •  
  •  
  •  
  •  
  •  
  •  
  •  
  •  
  •  
  •  
  •  
  •  
  •  
  •  
  •  
  •  
  •  
  •  
  •  
  •  
  •  
  •  
  •  
  •  
  •  
  •  
  •  
  •  
  •  
  •  
  •  
  •  
  •  
  •  
  •  
  •  
  •  
  •  
  •  
  •  
  •  
  •  
  •  
  •  

This is my very first post in writing optimized code. In this post, I will be more focused on one of the important factor for writing optimized logic and code that can perform the desired task in lesser time as compared to other algorithms you might have thought through.

In this post, I want to highlight to check the code or algorithm if it is doing things which are understood. Avoiding that will definitely increase your performance of the application.

For example, let’s consider that you have been assigned a task to write a program to display a range of Prime Numbers up to a given number N.

A prime number is a number that is divisible by 1 or by itself. The prime number starts at 2 and up to N where any number meets the preceding condition. Examples: 2, 3, 5, 7, 11, 13….

To accomplish this we can use the very basic algorithm, which has a complexity of O(n).

  1. If the number in question (N) is less than or equal to 1 then return false (Not a Prime Number), else go to step 2.
  2. Try to divide N with numbers (X) starting from 2 to N-1 and check if the remainder is ZERO. If N mod X (N%X) is ZERO then return false and stop further tests. Or else, if you reach out to X=N-1 then return true (It is a Prime Number).
private static void PrintPrimeNumbers()
        {
            int upto;
            Console.WriteLine("The program will print" +
                " all Prime Numbers starting from" +
                " 2 to your desired number.");
 
            Console.WriteLine("Enter Any Number");
            if (int.TryParse(Console.ReadLine(), out upto))
            {
                Stopwatch sw = new Stopwatch();
                sw.Start();
                if (upto <= 1)
                {
                    Console.WriteLine("We do not find " +
                        "any Prime Numbers in " +
                        "your desired range.");
                    sw.Stop();
                }
                else
                {
                    int loopCount;
                    for (int n = 2; n < upton++)
                    {
                        loopCount = 0;
                        if (IsPrime(n,ref loopCount))
                        {
                            Console.WriteLine($"{n} is a Prime Number." +
                                $" Total test cycles {loopCount+1}.");
                        }
                    }
                    sw.Stop();
                }
                Console.WriteLine();
                Console.WriteLine($"Displaying Prime " +
                    $"Numbers took sw.ElapsedMilliseconds } " +
                    $"Milliseconds.");
                Console.WriteLine();
                Console.WriteLine($"Prime functon " +
                    $"called {primeFunctionTestCalled+1} times.");
            }
            else
            {
                Console.WriteLine("Invalid Input");
            }
            
        }
        static int primeFunctionTestCalled = 0;
        private static bool IsPrime(int nref int loopCount)
        {
            bool isPrime = true;
            primeFunctionTestCalled++;
            for (int x = 2; x < n-1; x++)
            {
                loopCount++;
                if (n%x==0)
                {
                    isPrime = false;
                    break;
                }
            }
            return isPrime;
        }
Hanumantey Software Solutions | Ankur Tech Center
Running the program to print all prime numbers up to 300000
Hanumantey Software Solutions | Ankur Tech Center
The Result of the Execution

Do you think this can be optimized? Yes, it is. The problem with this approach is that we are checking up to N – 1, whereas, we can check up to the square root of N ( √n ) as a larger factor of N must be a multiple of smaller factor.

The other important known factor is that the only even number, which is prime is 2. Every other even number is not prime. But let’s play even smarter. All prime numbers except 2 and 3 are a form of 6 * K ± 1. It may give some false positive but every Prime Number must satisfy this equation. Let’s understand this with the help of an example.

6 * K ± 1 where K starts from 1 to M.

6 * 1 – 1 = 6 – 1 = 5
6 * 1 + 1 = 6 + 1 = 7
6 * 2 – 1 = 12 – 1 = 11
6 * 2 + 1 = 12 + 1 = 13
6 * 3 – 1 = 18 – 1 = 17
6 * 3 + 1 = 18 + 1 = 19
6 * 4 – 1 = 24 – 1 = 23
6 * 4 + 1 = 24 + 1 = 25 //False Prime
6 * 5 – 1 = 30 – 1 = 29
6 * 5 + 1 = 30 + 1 = 31
6 * 6 – 1 = 36 – 1 = 35 //False Prime
6 * 6 + 1 = 36 + 1 = 37
6 * 7 – 1 = 42 – 1 = 41
6 * 7 + 1 = 42 + 1 = 43
6 * 8 – 1 = 48 – 1 = 47
6 * 8 + 1 = 48 + 1 = 49 //False Prime
6 * 9 – 1 = 54 – 1 = 53
6 * 9 + 1 = 54 + 1 = 55 //False Prime
6 * 10 – 1 = 60 – 1 = 59
6 * 10 + 1 = 60 + 1 = 61

So let’s look at our optimized code. Shall we?

private static void PrintPrimeNumbers()
        {
            int upto;
            Console.WriteLine("The program will print" +
                " all Prime Numbers starting from" +
                " 2 to your desired number.");
 
            Console.WriteLine("Enter Any Number");
            if (int.TryParse(Console.ReadLine(), out upto))
            {
                Stopwatch sw = new Stopwatch();
                sw.Start();
                if (upto <= 1)
                {
                    Console.WriteLine("We do not find " +
                        "any Prime Numbers in " +
                        "your desired range.");
                    sw.Stop();
                }
                else
                {
                    int loopCount;
                    int k = 1;
                    int lowNumberhighNumber;
                    while (true)
                    {
                        lowNumber = 6 * k - 1;
                        highNumber = 6 * k + 1;
                        if (lowNumber <= upto)
                        {
                            //for 6 * K - 1
                            loopCount = 0;
                            if (IsPrime(lowNumberref loopCount))
                            {
                                Console.WriteLine($"{lowNumber} is a" +
                                    $" Prime Number." +
                                    $" Total test cycles" +
                                    $" {loopCount + 1}.");
                            }
                            if (highNumber <= upto)
                            {
                                //for 6 * k + 1
                                loopCount = 0;
                                if (IsPrime(highNumberref loopCount))
                                {
                                    Console.WriteLine($"{highNumber} " +
                                        $"is a Prime Number." +
                                        $" Total test cycles" +
                                        $" {loopCount + 1}.");
                                }
                            }
                            else
                            {
                                break;
                            }
                        }
                        else
                        {
                            //We have printed all prime numbers as requested.
                            break;
                        }
 
 
                        k++;
                    }
                    sw.Stop();
                }
                Console.WriteLine();
                Console.WriteLine($"Displaying Prime " +
                    $"Numbers took sw.ElapsedMilliseconds } " +
                    $"Milliseconds.");
                Console.WriteLine();
                Console.WriteLine($"Prime functon " +
                    $"called {primeFunctionTestCalled + 1} times.");
            }
            else
            {
                Console.WriteLine("Invalid Input");
            }
 
        }
        static int primeFunctionTestCalled = 0;
        private static bool IsPrime(int nref int loopCount)
        {
            bool isPrime = true;
            primeFunctionTestCalled++;
            //2 and 3 are Prime Numbers
            if (n == 2 || n == 3)
                return isPrime;
            int sq = Convert.ToInt32(Math.Sqrt(n));
            //Starts with 5.
            for (int x = 5; x <= sqx+=2)
            {
                loopCount++;
                if (n % x == 0)
                {
                    isPrime = false;
                    break;
                }
            }
            return isPrime;
        }
Hanumantey Software Solutions | Ankur Tech Center
The Results of the Execution

Look at that!!! With the old school method, it took 19939 Milliseconds but with optimized code, it took only 4539 Milliseconds also we skip calling non-primes like all even numbers, which reduces the function call to 100000 instead of 299999 in old school method. Also, we concluded the largest prime number within the desired range is 299993 just running 273 tests as compared to 299991 tests in the old school method.

Thanks for reading this long post. I hope this worth reading. Please let me know your thoughts.


Share the knowledge with others
  •  
  •  
  •  
  •  
  •  
  •  
  •  
  •  
  •  
  •  
  •  
  •  
  •  
  •  
  •  
  •  
  •  
  •  
  •  
  •  
  •  
  •  
  •  
  •  
  •  
  •  
  •  
  •  
  •  
  •  
  •  
  •  
  •  
  •  
  •  
  •  
  •  
  •  
  •  
  •  
  •  
  •  
  •  
  •  
  •  
  •  
  •  
  •  
  •  
  •  
  •  
  •  
  •  
  •  
  •  
  •  
  •  
  •  
  •  
  •  
  •  
  •  
  •  
  •  
  •  

2 thoughts on “Write Optimized Code – Part 1

Leave a Reply

Your email address will not be published. Required fields are marked *