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.

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:

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

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:

• On an i5-4670 physical machine with 4 CPU cores and 32 GB RAM, the results are given below:

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:

The Naive Solution used Logical OR to filter the input:

[code language=”csharp”]
if ((i % 3 == 0) || (i % 5 == 0))
{
sum = sum + i;
}
[/code]

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:

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

S₃ = 3 + 6 + 9 + 12 + 15 + ...

and

S₅ = 5 + 10 + 15 + 20 + 25 + ...

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

S₃ and S₅ are sums of unique numbers, but when we are dealing S₃ + S₅, 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

S_{3 and 5} = S₃ + S₅

The truth, however, is

S_{3 and 5 actual} > S_{3 and 5 expected}

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

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

S_{3 and 5} = S₃ + S₅ - S₁₅

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

S_{3 and 5 actual} == S_{3 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:

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.

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

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 10¹⁴ as input

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

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