Understanding Delegates in C# for beginners

ROADBLOCKS TO PROPER UNDERSTANDING

Delegates as a technical concept in C# create a lot of confusion in the beginners’ mind. It is a fairly simple concept but most of the examples floating around on the web are so trivial that they do not expose the real benefits of delegates. Look at the below sample :

public delegate double Delegate(int a,int b);
class Class1
{
    static double fn_ToHookToTheDelegate(int val1, int val2)
    {
        return val1 * val2;
    }

    static void Main(string[] args)
    {
        //Creating the Delegate Instance
        Delegate delObj = new Delegate(fn_ToHookToTheDelegate);
        Console.Write("Please Enter Values");
        int v1 = Int32.Parse(Console.ReadLine());
        int v2 = Int32.Parse(Console.ReadLine());
        //Call delegate for processing
        double res = delObj(v1, v2);
        Console.WriteLine ("Result: " + res);
        Console.ReadLine();
     }
}

In this example, everything exists within the confines of the same class. The delegate (or the hook, as I call it) and the function to be hooked to it are both in the same class. The following line of code in the Main() makes no pragmatic sense:

Delegate delObj = new Delegate(fn_ToHookToTheDelegate);

We could have saved ourselves some time and typing by simply calling the function instead of wrapping it in a delegate. When the uninitiated reader is presented with such code, there is absolutely no learning that takes place. This is exactly why I decided to create a series of elaborate articles to note down my thoughts on topics I learn. The sample above and the discussion may not make any sense to the reader at present, but please keep reading. Things will surely become crystal clear by the end of this article, I promise 😉

JUMPING OVER THE ROADBLOCKS

I frequented Stackoverflow and tried to find my “eureka” moment there. I received a lot of help, no doubts, but I was still far from real understanding. That is when I started spending inordinate amounts of time conjuring up hypothetical scenarios where I would use Delegate. This exercise helped me a lot. I started reading Jon Skeet’s C# In Depth and Mark Michaelis’s Essential C# and got a better understading of the concept. I am, by no means, an expert but this is what I feel a newcomer should do:

  1. Understand that programming is not for the weak hearted. Lack of talent is not an issue, lack of determination is.
  2. Join Stackoverflow
  3. Read books. There is no alternative.
  4. Try to relate everything to the world around us. That is the real meaning of Object Orientation – a programming model that tries to mimic the real world, the objects in it and their interactions.

The meaning of the word delegate is:

noun
  • a person designated to act for or represent another or others; deputy; representative, as in a political convention.
  • (formerly) the representative of a Territory in the U.S. House of Representatives.
  • a member of the lower house of the state legislature of Maryland, Virginia, or West Virginia.
verb (used with object)
  • to send or appoint (a person) as deputy or representative.
  • to commit (powers, functions, etc.) to another as agent or deputy.

It is utterly important to understand the meaning of a technical term. This helps in gaining insights that would be otherwise impossible to gain.

BACKGROUND

Basic knowledge of C# is assumed. This means the reader should possess a fairly basic understanding of Object Oriented Programming and is at ease with simple C# programs and Visual Studio. I will not be explaining what a delegate is. I will explain one scenario where it can be employed. Delegates are very powerful and can be gainfully employed in a lot of design patterns. Please read the following articles before proceeding with this article:

Reading the above-mentioned articles is NOT optional. I have tried to explain the concept using a small story that tries to be very close to the real world. The code sample added in this article is also trivial but gives the reader a feel of how to use delegates in the real world for modular software design. Although the code sample is in C#, the concept is universal. I have intentionally avoided topics that could complicate things for beginners. I would like the reader to get a basic understanding of the concept and build a mental picture before dealing with technicalities. I would take the reader for a deep dive once the story ends. Read the code provided thoroughly. The code is heavily commented to clear any doubts the reader might have. Reading the code comments is NOT optional. Read the comments thoroughly. The code compiles just fine.

A MOVING STORY

THE PROBLEM

There is a software development firm, IWorkForThee Corporation. This company specializes in developing state-of-the-art software libraries aimed at solving computation problems. IWorkForThee Corporation produces closed source components.They sell a lot of software. This means they have a great list of customers. Now, IWorkForThee Corporation has sold the first version of its new library DoSomethingLibrary. This library is in the form of a DLL. The code of the library looks like this:

public class HeavyWeightWorker
{
    public void HeavyWeightWork()
    {

        /*HeavyWeightWork code is an emulator which I am using to emulate
         *some huge processing or some huge job.
         *Let us imagine that this is a library
         *that does some heavy data crunching OR some
         *extremely complex data access job etc..
        */

        /*Let us imagine Console.WriteLine() as a function that does some heavy work
        */
        Console.WriteLine("Heavy Weight WORK Step 1");
        /*After each step this library tries to LOG.*/
        LogMessage("Heavy Weight WORK Log", "Step 1");

        Console.WriteLine("Heavy Weight WORK Step 2");
        /*After each step this library tries to LOG.*/
        LogMessage("Heavy Weight WORK Log ", "Step 2");

        Console.WriteLine("Heavy Weight WORK Step 3");
        /*After each step this library tries to LOG.*/
        LogMessage("Heavy Weight WORK Log ", "Step 3");
    }

    private static void LogMessage(string firstParam, string secondParam)
    {
        /*
         *This logger has '=' used as a decorator
         *In real scenarios the logger may be very complex.
         *Let us assume this is an HTML logger
        */
        Console.WriteLine("=============================");
        Console.WriteLine(firstParam + " - " + secondParam);
        Console.WriteLine("=============================");
    }
}

This is an absolutely simple way of doing things and it simply works. The consumers do the following to consume the library:

  • Add DoSomethingLibrary DLL as a reference to their executable’s project in Visual Studio
  • Use the DoSomethingLibrary namespace to access the library programmatically Create an instance HeavyWeightWorker and off they go…

The consumers are happy because they can use the library without much fuss. The IWorkForThee Corporation is also reaping the benefits of happy consumers. One of IWorkForThee Corporation’s consumers, the INeedThee Corporation has been in business with them for the past few years. They demand a new version of the DoSomethingLibrary with some advanced features. This is exactly what IWorkForThee Corporation was working on. So they tell INeedThee Corporation that they can have the new version in a few days. But INeedThee Corporation had another demand that threw IWorkForThee Corporation’s plans off balance. A new logging mechanism was demanded. They needed an XML log with a pre-defined format. This XML would then be used by INeedThee Corporation’s logging utility to perform advanced analysis etc.. IWorkForThee Corporation’s lead developer says that the new logging function can be completed in a week’s time. This made life easy for the management. But there was another bomb about to explode. Another customer, GreedyNeedy Corporation was very happy with the original logging mechanism. But they wanted more. They wanted another logger to log in XML format. The only issue was that their XML format was completely different from INeedThee Corporation’s format. The management was completely clueless on what approach to follow. They could implement all the loggers needed by all the consumers. But the following issues were noted down in the emergency meeting:

  • XML formats of INeedThee Corporation and GreedyNeedy Corporation are substantially different and would require huge effort.
  • Release date would surely be missed and other consumers may not be very happy
  • With so many loggers available there has to be a mechanism for the consumer to choose. This would require a change in the HeavyWeightWorker Class’s structure.
  • Costs would go up and the profits would go down.
  • What happens if the consumers change the format again?

There was a guy in the meeting who usually says very little. He spends time learning new things. He learns design patterns etc.. He is so good at making things beautiful that the whole idea of implementing all the loggers in the library made him sick. He proposed a solution that could change everything.

THE SOLUTION

The solution is to remove all loggers from the library. Why? If consumers are not happy with the logging that the library provides and need custom logging, let them implement the logging. In any case, the custom logging mechanism can be best implemented and maintained by the consumers. This is fairly simple. Right? No. This is not simple. With a little thought one can see that the logger needs to be detailed and for that reason it needs to be cleanly integrated with the DoSomethingLibrary DLL’s logic. If logging functionality resides in an outside entity, how do we integrate it with DoSomethingLibrary DLL’s logic so that we have a log after each step of the job? This is easily achieved if all logging functionality is included in the DLL itself. But that was the problem we wanted to solve. So what options do we have? Delegates come to our rescue. Using delegates we can delegate (look at the meaning) the logging functionality to the consumers. This will help us in the separation of concerns. That is, the DoSomethingLibrary is extremely good at doing what it does. Custom logging was getting too heavy for the library. This overhead of maintaining the custom loggers was just too much of unnecessary work. The guy who proposed the idea was asked to provide proof of concept models. He did that and managed to convince the management of the efficacy of the idea. The consumers and specifically the INeedThee Corporation and GreedyNeedy Corporation were informed of the decision to delegate DoSomethingLibrary’s logging functionality to them. This seemed to be a great option for all. Why? Because:

  • The logging is completely out of DoSomethingLibrary and IWorkForThee Corporation is happy as this means less code to maintain and no dependency on the consumers at all!
  • The logging is completely in control of consumers so they are happy. Now they can do whatever they want.

The version 2 of the DoSomethingLibrary is added. The code is self explanatory and the comments are elaborate:

public delegate void Logger(string firstParam, string secondParam);
/*
 *The above line is a public delegate declared at the base namespace level for global presence.
 *The question is WHY do we need to have a DELEGATE here?
 *The answer is: I do not want to implement the LOGGING logic. Why? Well, my consumers are many
 *and all are equally demanding. They all need different types of logging. Some need HTML logging,
 *some need XML logging for their custom log analyzer, some need plain text logging etc...
 *This is hell for me. How am I going to support all their demands. I cannot. Thus, I ask them to
 *implement LOGGING on their side. I am providing an INTERFACE(literal sense) in the guise of a DELEGATE.
 *A DELEGATE is a HOOK.
 *This is the hook that is needed for consumers to hook their custom loggers into the library.
*/

public class HeavyWeightWorker
{
    public Logger ConsumerLoggerHook;
    public void HeavyWeightWork()
    {
        /*After each step this library tries to LOG. But NOTE that this library
         *has no LOGGER implemented. Instead, this library has judiciously DELEGATED
         *the logging responsibilty to the CONSUMER of this library.
        */
        Console.WriteLine("Heavy Weight WORK Step 1");
        /*After each step this library tries to LOG.*/
        ConsumerLoggerHook("Heavy Weight WORK Log ", "Step 1");

        Console.WriteLine("Heavy Weight WORK Step 2");
        /*After each step this library tries to LOG.*/
        ConsumerLoggerHook("Heavy Weight WORK Log ", "Step 2");

        Console.WriteLine("Heavy Weight WORK Step 3");
        /*After each step this library tries to LOG.*/
        ConsumerLoggerHook("Heavy Weight WORK Log ", "Step 3");
    }
}

The version 1 of the DoSomethingLibrary DLL was so simple that the consumer code needed to integrate with it was trivial. That is not the case now. Thus, the consumer executable’s code is also added below: Let us assume that I have purchased the DoSomethingLibrary DLL from a vendor. I have to add the DLL as a reference to my executable’s project in Visual Studio. I also have to use the DoSomethingLibrary namespace to access the Logic in the DLL:

using DoSomethingLibrary;

class Program
{
    static void Main(string[] args)
    {
        /*
        * Creating an object of the lone class PrintingManiac in the DoSomethingLibrary
        */
        HeavyWeightWorker worker = new HeavyWeightWorker();

        /*
        * HOOKING my custom logger to the DoSomethingLibrary DLL.
        * I get the best of both the worlds. I have a well-tested and efficient library working for me
        * AND I have the best logging avaliable.
        * The DoSomethingLibrary DLL has no knowledge of what logging this executable is going to use.
        * This executable has to just satisfy the requirements
        * of the DELEGATE signature of DoSomethingLibrary DLL.
        */
         worker.ConsumerLoggerHook += new Logger(ClientsCustomizedLoggerTwo);
         worker.HeavyWeightWork();
         Console.ReadLine();
    }

    public static void ClientsCustomizedLoggerOne(string firstParam, string secondParam)
    {
        /*
         *This logger has '=' used as a decorator
         *In real scenarios the logger may be very complex.
         *Let us assume this is an HTML logger
         */
        Console.WriteLine("=============================");
        Console.WriteLine("Delegated Logging IN CONSUMER code " + firstParam + " - " + secondParam);
        Console.WriteLine("=============================");
    }

    public static void ClientsCustomizedLoggerTwo(string firstParam, string secondParam)
    {
        /*
        *This logger has '-' used as a decorator
        *Let us assume this is an XML logger
        */
        Console.WriteLine("------------------------------");
        Console.WriteLine("Delegated Logging IN CONSUMER code " + firstParam + " - " + secondParam);
        Console.WriteLine("------------------------------");
     }
}

GOING DEEPER

What we have seen above is how a delegate is used. We have not dealt with anything even remotely advanced. Let us now dive a bit deeper. In the sample code above we could see that the consumer has two logger functions available:

  • ClientsCustomizedLoggerOne representing an HTML logger
  • ClientsCustomizedLoggerTwo representing an XML logger

This particular customer hooked the ClientsCustomizedLoggerTwo with the DoSomethingLibrary. So, the customer still has ClientsCustomizedLoggerOne sitting idle doing nothing. But the customer has the option of using either of the loggers as per requirements. Thus the customer can do the following and hook the ClientsCustomizedLoggerOne to the DoSomethingLibrary:

using DoSomethingLibrary;

class Program
{
    static void Main(string[] args)
    {
        HeavyWeightWorker worker = new HeavyWeightWorker();
        /*Following is the only line that needs to change so as to HOOK a different
         * logger to the DoSomethingLibrary. In the earlier example ClientsCustomizedLoggerTwo
         * was HOOKed and it is ClientsCustomizedLoggerOne now that has been hooked.
         */
        worker.ConsumerLoggerHook += new Logger(ClientsCustomizedLoggerOne);
        worker.HeavyWeightWork();
        Console.ReadLine();
    }

    public static void ClientsCustomizedLoggerOne(string firstParam, string secondParam)
    {
        /*
         *This logger has '=' used as a decorator
         *In real scenarios the logger may be very complex.
         *Let us assume this is an HTML logger
         */
        Console.WriteLine("=============================");
        Console.WriteLine("Delegated Logging IN CONSUMER code " + firstParam + " - " + secondParam);
        Console.WriteLine("=============================");
    }

    public static void ClientsCustomizedLoggerTwo(string firstParam, string secondParam)
    {
        /*
         *This logger has '-' used as a decorator
         *Let us assume this is an XML logger
         */
        Console.WriteLine("------------------------------");
        Console.WriteLine("Delegated Logging IN CONSUMER code " + firstParam + " - " + secondParam);
        Console.WriteLine("------------------------------");
    }
}

This is the new executable and it can log using the ClientsCustomizedLoggerOne logger that represents an XML logger. What happens if the consumer wants to hook both loggers to the DoSomethingLibrary? That is, how can the consumer hook both the HTML and XML loggers to the DoSomethingLibrary? This is where the MulticastDelegate concept comes into picture. All delegates must be convertible to System.Delegate. All delegate types are derived from System.MulticastDelegate. System.MulticastDelegate derives from System.Delegate. Thus all delegates are basically inherently Multicast. When we hook one method to the delegate it behaves as a Singlecast delegate. So what exactly is Singlecast and Multicast Delegate?

  • Multicast Delegate is fancy way of saying that you can hook multiple methods to the delegate.
  • Singlecast Delegate is a great way of saying that the delegate has just one method hooked to it. There is actually no such thing as Singlecast Delegate. All delegates are technically Multicast Delegate types. When only one method is hooked to the delegate people tend to call it SinglecastDelegate.

If the consumer wants to have both logs(HTML and XML) available for whatever reasons, the MulticastDelegate helps the consumer to do so. The below code will show what needs to be done so as to achieve the goal of hooking both loggers to the DoSomethingLibrary:

using DoSomethingLibrary;

class Program
{
    static void Main(string[] args)
    {
         HeavyWeightWorker worker = new HeavyWeightWorker
         /*The following two lines will HOOK the two loggers to the DoSomethingLibrary.
          * There is no more magic needed. That is it!!!
          */
         worker.ConsumerLoggerHook += new Logger(ClientsCustomizedLoggerOne);
         worker.ConsumerLoggerHook += new Logger(ClientsCustomizedLoggerTwo);
         worker.HeavyWeightWork();
         Console.ReadLine();
    }

    public static void ClientsCustomizedLoggerOne(string firstParam, string secondParam)
    {
        /*
         *This logger has '=' used as a decorator
         *In real scenarios the logger may be very complex.
         *Let us assume this is an HTML logger
         */
        Console.WriteLine("=============================");
        Console.WriteLine("Delegated Logging IN CONSUMER code " + firstParam + " - " + secondParam);
        Console.WriteLine("=============================");
    }

    public static void ClientsCustomizedLoggerTwo(string firstParam, string secondParam)
    {
        /*
         *This logger has '-' used as a decorator
         *Let us assume this is an XML logger
        */
        Console.WriteLine("------------------------------");
        Console.WriteLine("Delegated Logging IN CONSUMER code " + firstParam + " - " + secondParam);
        Console.WriteLine("------------------------------");
    }
}

This is simply beautiful. So how does the delegate manage multiple methods hooked to it? Always remember that any delegate is a MulticastDelegate. Thus one can easily hook many methods to a delegate. Each delegate maintains a list of hooked methods. This list is known as the Invocation List. The += operator helps in adding more hooks to the list. It is also possible to remove a hook by using the -= operator. When a Multicast Delegate is invoked, all the methods in the invocation list are invoked sequentially in the order in which those methods were added to the list. If an exception occurs during the processing of any of the methods in the list, the other methods in the list are not invoked. This limitation can be overcome if one can gain complete access to the invocation list. The GetInvocationList function helps in this regards. There are great number of things that can be achieved using delegates. Many design patterns depend on them. Delegates are a great concept. The details in this article should be enough to get a beginner to appreciate the beauty of this concept.

CONCLUSION

The story ends here folks. A small innovative step using a feature provided by the language helped the vendor and the consumers to de-couple. I hope everyone enjoyed the story. Please read the code as many times as possible or needed. The comments are elaborate.

Advertisements

Project Euler problem – Multiples of 3 and 5; Small yet insightful (Part 1)

PERSPECTIVE

Programming may not come naturally to everybody, but a little perspective can change things.

Familiarity with the most basic C# programs is assumed. No object-oriented concepts are needed to understand Part 1. If you are absolutely new to C#, it would be beneficial to go through, at least, the following. That is all I ask:

Hello World in C#

This post if for those new to programming and looking for a little perspective. If you can make C# dance to your tunes, do not fret. You can still read and help me improve this post.

PerspectiveRatatouille

It is always wonderful to see a small and simple problem, when properly handled, reveal so much beauty that it is almost impossible to believe.

There was a time when programming made no sense to me. I had no idea how to do it. That is when I found a very simple problem and I was enlightened:

Find if a given number is prime or not

Now, there is not much substance in this problem. So it seems till you poke it and a legion of mathematical beasts are unleashed to challenge your intellect. Number theorists of all ages have struggled to tame these beasts. They still roam about in the wilderness of Mathematics.

THE PROBLEM

This Friday, I was looking for some fun. I created an account on Project Euler . The first question that was thrown at me was:

If we list all the natural numbers below 10 that are multiples of 3 or 5, we get 3, 5, 6 and 9. The sum of these multiples is 23. Find the sum of all the multiples of 3 or 5 below 1000.

THE SOLUTIONS

This problem seems simple. It is if we have great computing power at our disposal. It is not if we want to properly tame it.

THE NAIVE SOLUTION


using System;

namespace ProjectEuler_Question_1
{
    class Program
    {
        static void Main(string[] args)
        {
            Console.WriteLine("Sum of all numbers below 1000 that are multiples of 3 or 5 are: ");
            Console.WriteLine(FindSumOfMultiplesOf3And5().ToString());
            Console.Read();
        }

        static double FindSumOfMultiplesOf3And5()
        {
            double sum = 0;
            for (double i = 0; i < 1000; i++)
            {
                /* % is the modulus operator */
                if ((i % 3 == 0) || (i % 5 == 0))
                {
                    sum = sum + i;
                }
            }
            return sum;
        }
    }
}

This is a solution. It works. The major elements of any computer programme are present:

  1. Data
    – do some operation on numbers below 1000
  2. Data Structure
    – data types used; double, in the code above, to store numbers
  3. Algorithm
    The loop, the modulus operator %, the summation

WhatIsProgramming

Why is this naive, then?
It is naive because of:

Inefficient use of hardware resources:

  • On a Windows 7 virtual machine with one CPU core and 8 GB RAM allotted, the results are given below:
Limit used Time taken
1000 sub-milliseconds range
100000 sub-milliseconds range
10000000 140.62 milliseconds
1000000000 13972.65 milliseconds ~= 14 seconds
100000000000 1599374.20 milliseconds ~= 26 minutes

Look at the CPU madness as witnessed by KSysGuard (KDE System Monitor) on my openSUSE host running on i7-4770 with 32 GB RAM:

CPUActivity

  • On an i5-4670 physical machine with 4 CPU cores and 32 GB RAM, the results are given below:
Limit used Time taken
100000000000 1407631.13 milliseconds ~= 23.5 minutes

There are a lot of variables that can affect the execution time. On of the most important is the hardware. A Pentium 4 PC would have made me wait for a few hours. So, do not assume that the algorithm would always run on great hardware. Design algorithms in such a way that they may run on low-end hardware too.

There is still one question here

Why would we bother about large inputs when the problem specifically speaks about 1000 as the upper limit?

This is a very important question. The answer is quite large. It will be answered in another part.

Inefficient use of intellectual resources:

If we had infinite computing power, data structures and algorithms would not have mattered at all, but we do not. So, it is imperative that we invest some time in finding a better algorithm for the job. This process can be slow and evolutionary in nature. It can even be sudden, but we have to make it happen.

There is another issue that we have not discussed:

How would we go about solving this problem if we had no computer at our disposal?

Just imagine the pain one would have to go through to find out all the multiples of 3 and 5 below 100000000000.

BETTER SOLUTION

A small investment of time can help us in breaking the problem into smaller pieces. These smaller pieces can be solved without any electronic computing power.

Realizing that we are dealing with a couple of Arithmetic Progressions can help us create better strategies. So, we are dealing with:

  1. Arithmetic Progression with 3 as the first number and a common difference of 3
  2. Arithmetic Progression with 5 as the first number and a common difference of 5
  3. Arithmetic Progression with 15 as the first number and a common difference of 15

Where did that Point 3 come from?

This needs some detailed explanation. Let us build a Truth Table for Logical OR to see where Point 3 comes from:

Multiple of 3 (A)
Multiple of 5 (B)
A OR B
T F T
F T T
T T T
F F F

Pictorially Logical OR could be represented as:

VennDiagram_ProjectEuler_Problem1The Naive Solution used Logical OR to filter the input:

if ((i % 3 == 0) || (i % 5 == 0))
{
    sum = sum + i;
}

What all this means is that:

An input can be a “Multiple of 3” OR a “Multiple of 5” OR both. In all these cases the input will be sieved into the conditional block. This happens ONLY once for any input. Thus, the sum is guaranteed to be the sum of unique numbers.

Now we have to take a look at another Truth Table. This time for Logical AND:

Multiple of 3 (A)
Multiple of 5 (B)
A AND B
T F F
F T F
T T T
F F F

When we break our problem into two Arithmetic Progressions, find their sums and add those sums together to get the final result, a small error creeps in. Imagine that we have two sets of numbers – one containing all the multiples of 3 and another that contains all multiples of 5. So, {3, 6, 9, 12, 15, …} is one set and {5, 10, 15, 20, 25…} another.

If we sum the sets individually, we have to do this:

S3 = 3 + 6 + 9 + 12 + 15 + ...

and

S5 = 5 + 10 + 15 + 20 + 25 + ...

As we can see, there are numbers that are in both the sets.

S3 and S5 are sums of unique numbers, but when we are dealing S3 + S5, certain numbers get added twice. 15, 30, 45 etcetera are examples of such numbers. These numbers form an Arithmetic Progression with 15 as the first number and a common difference of 15.

We may expect the answer of the problem to be

S3 and 5 = S3 + S5

The truth, however, is

S3 and 5 actual > S3 and 5 expected

So, to get rid of the error, we have to do the following:

VennDiagram_ProjectEuler_Problem1_3The above picture shows the filtering we need to do. We do that filtering implicitly when we do the following calculation:

S3 and 5 = S3 + S5 - S15

Now what we expect will be equal to the actual output:

S3 and 5 actual == S3 and 5 expected

Armed with so much knowledge, we are now in a position to attack the problem in a really profitable way. The code with the new algorithm is:

using System;

namespace ConsoleApplication5
{
    class Program
    {
        static double limit = 1000;

        static void Main(string[] args)
        {
            double a = FindSumOfArithmeticProgression(3);
            double b = FindSumOfArithmeticProgression(5);
            double c = FindSumOfArithmeticProgression(15);
            double sum = (a + b - c);
            Console.WriteLine(sum.ToString("N"));
            Console.Read();
        }

        static double FindSumOfArithmeticProgression(double multiplesOf)
        {
            /* We will use the following formula to calculate the sum of the Progression:
             * n(a + l)/2,
             * where a = first element, l = last element and n = total number of elements in the progression and 2 = well, 2
             * To find n, we have to use:
             * a + (n - 1)d = l => n = 1 + (l - a)/d
             */
            double a = multiplesOf, d = multiplesOf, l = 0;

            /*Find l */
            l = FindLastElement(multiplesOf);

            /* Find n */
            double n = 1 + (l - a) / d;

            /* Find l */

            /* Find sum */
            double sum = (double) (n * (a + l) / 2);
            return sum;
        }

        private static double FindLastElement(double multiplesOf)
        {
            /* Find the range in which we can find the last multiple
             * In our case, 1000 - 3 or 1000 - 5 is the answer
             */
            double rangeInWhichToFindTheLastMultiple = limit - multiplesOf;
            double l = 0;

            for (double i = rangeInWhichToFindTheLastMultiple; i < limit; i++)
            {
                if (i % multiplesOf == 0)
                {
                    l = i;
                    break;
                }
            }
            return l;
        }
    }
}

This is fast beyond belief. No input is big enough to make it sweat:

Limit used Time taken
1000 sub-milliseconds range
100000 sub-milliseconds range
10000000 sub-milliseconds range
1000000000 sub-milliseconds range
100000000000 sub-milliseconds range

From 26 minutes taken by the old naive algorithm to the sub-milliseconds taken by our new, shiny algorithm, for an input as large as 100000000000, the improvement is unbelievable.

Now that we have brought the execution time down, we are faced with another issue. Yes, we are not done yet. Far from it. The new problem is the output. It is not precise at all

23,333,333,331,666,700,000.00 while it should have been 23,333,333,331,666,666,668.00

What happened? Where did all the good digits go?

Why is the output not precise?

This is because we have not chosen the correct Data Structure. The data type double, chosen for the purpose of holding various numbers, has its limits. It is a 64-bit data type.

Type Approximate range Precision .NET Framework type
double ±5.0 × 10−324 to ±1.7 × 10308 15-16 digits System.Double

Read the System.Double documentation thoroughly to understand what limitations we are dealing with.

FROM double TO decimal

We have to get a better data type if we wish to solve the problem for very large numbers. Let us look at

Type Approximate Range Precision .NET Framework type
decimal (-7.9 x 1028 to 7.9 x 1028) / (100 to 28) 28-29 significant digits System.Decimal

Decimal loses steam when input is 1015.

For anything lesser than that, decimal will work. Decimal is a 128-bit data type. Read System.Decimal documentation for details.

Let us compare the output for double and decimal for 1014 as input

OUTPUT WHEN USING DOUBLE OUTPUT WHEN USING DECIMAL
2,333,333,333,333,320,000,000,000,000.00 2,333,333,333,333,316,666,666,666,668.00

Decimal can handle a really large input, but what if we have an input that is > 1014 ?

FROM decimal TO BigInteger

This is where we go to the data type that is the biggest of them all – The BigInteger.

BigInteger can hold arbitrarily large numbers with one thing to keep in mind

Because the BigInteger type is immutable (see Mutability and the BigInteger Structure) and because it has no upper or lower bounds, an OutOfMemoryException can be thrown for any operation that causes a BigInteger value to grow too large

Now that BigInteger has arrived to rescue us, there is another issue that crops up:

The biggest integer literal that can be defined in C# is ulong with max value of 18,446,744,073,709,551,615

Type Range Size .NET Framework type
ulong 0 to 18,446,744,073,709,551,615 Unsigned 64-bit integer System.UInt64

So anything larger than 18,446,744,073,709,551,615 will make the compiler writhe in pain. It lets us know by spewing out the following exception:

error CS1021: Integral constant is too large

BigInteger has us covered even in such situations. Turning the very large input into a string and using BigInteger.Parse function can help us overcome the issue.


using System;
using System.Numerics;

namespace ConsoleApplication5
{
    class Program
    {
        static BigInteger limit = BigInteger.Pow(10, 80);

        static void Main(string[] args)
        {
            BigInteger a = FindSumOfArithmeticProgression(3);
            BigInteger b = FindSumOfArithmeticProgression(5);
            BigInteger c = FindSumOfArithmeticProgression(15);
            BigInteger sum = (a + b - c);
            Console.WriteLine(sum.ToString("N"));
            Console.Read();
        }

        static BigInteger FindSumOfArithmeticProgression(BigInteger multiplesOf)
        {
            /* We will use the following formula to calculate the sum of the Progression:
             * n(a + l)/2,
             * where a = first element, l = last element and n = total number of elements in the progression and 2 = well, 2
             * To find n, we have to use:
             * a + (n - 1)d = l => n = 1 + (l - a)/d
             */
            BigInteger a = multiplesOf, d = multiplesOf, l = 0;

            /*Find l */
            l = FindLastElement(multiplesOf);

            /* Find n */
            BigInteger n = 1 + (l - a) / d;

            /* Find l */

            /* Find sum */
            BigInteger sum = (BigInteger) (n * (a + l) / 2);
            return sum;
        }

        private static BigInteger FindLastElement(BigInteger multiplesOf)
        {
            /* Find the range in which we can find the last multiple
             * In our case, 1000 - 3 or 1000 - 5 is the answer
             */
            BigInteger rangeInWhichToFindTheLastMultiple = limit - multiplesOf;
            BigInteger l = 0;

            for (BigInteger i = rangeInWhichToFindTheLastMultiple; i < limit; i++)
            {
                if (i % multiplesOf == 0)
                {
                    l = i;
                    break;
                }
            }
            return l;
        }
    }
}

The above code uses an arbitrarily large number to show how BigInteger when coupled with BigInteger.Parse can solve our issues.

CONCLUDING PART 1:

I have covered a lot in this part:

  • The basic structure of a program; data structures, algorithms etcetera
  • How execution time depends on hardware (there are other factors not covered)
  • How choice of data structure can affect the program and its output
  • How to choose proper data types for desired results

This is a work-in-progress and changes will be made. Next few parts will cover some advanced stuff.
There is a lot more to do so as to make the program beautifully generic. All that will be done in the next few posts. We have only breached the topmost layer of the beautiful world of Software Engineering or more precisely the Art of Software Engineering 🙂

When we had no computers, we had no programming problem either. When we had a few computers, we had a mild programming problem. Confronted with machines a million times as powerful, we are faced with a gigantic programming problem. – Edsger Dijkstra

The USING keyword in C#: How to clean unnecessary using directives in Visual Studio

using KEYWORD IN C#

There are two ways of using the using keyword in C#:

  1. As a statement
  2. As a directive

using KEYWORD AS A STATEMENT

MSDN says the using keyword

Provides a convenient syntax that ensures the correct use of IDisposable objects.

This is also a way of saying that this is the standard way of releasing unmanaged resources. The following is an example of its usage:


using(StreamWriter grepLog = new StreamWriter(fileName, true))
{
// ...log code here
}

using KEYWORD AS A DIRECTIVE

This is the most common usage of the using keyword. The following example shows how using keyword is used to access types in a namespace. This practice of using the using directives to access types in a namespace allows the developer to avoid fully qualifying the type. This save a lot of time and typing.


using System;

using System.Text;

Another use of using is to create aliases. An excellent discussion on this topic can be found in this Stackoverflow thread.

CLEANING using DIRECTIVES

There are many reasons why your .cs file may end up having more using directives than necessary. There is a very quick way to clean and organize using directives in Visual Studio. Just right-click on the text editor. The context menu pops up and the second option in the menu is Organize Usings.

This menu item has three sub-items:

  1. Remove Unused Usings
  2. Sort Usings
  3. Remove and Sort

OrganizeUsingsInVisualStudioTextEditorContextMenu

Remove Unused Usings:

This option simply removes unused using directives. The end result would be like:

OrganizeUsingsInVisualStudio_RemoveUnusedUsings

Sort Usings:

This option only sorts the using directives alphabetically. It does nothing else. Also, the sort can not be done in reverse alphabetical order:

OrganizeUsingsInVisualStudio_SortUsings

Remove and Sort Usings:

This option removes all unused using directives and sorts the list too. This sorting is also done alphabetically and no reverse alphabetical sorting option is available:

OrganizeUsingsInVisualStudio_RemoveAndSortUsings

This keeps the class file clean and some unnecessary lines of code can be reduced (if that sort of thing appeals to you).