4
\$\begingroup\$

In an effort to learn C# / improve my coding skills, I've started working on the Project Euler problems. I see that I may have been overthinking things a bit after finishing problem 7:

By listing the first six prime numbers: 2, 3, 5, 7, 11, and 13, we can see that the 6th prime is 13.

What is the 10 001st prime number?

But even so I believe that my solution should be faster than what is presented in the problem overview. While this may not be an issue when searching for a "small" number of primes, the previous problems have focused quite a bit on optimizing the codes so I am wondering if I have missed something obvious.

In other words, how does my code compare to the pseudocode presented in the overview of the problem? Are there any obvious mistakes I make in my code?

using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using System.Threading.Tasks;
using System.Diagnostics;

namespace ProjectEulerTasks
{
    class Program
    {
        static void Main(string[] args)
        {
            int no_of_primes_found = 0;
            int current_number = 0;
            List<int> found_primes = new List<int>();
            bool n_minus_found = false;
            bool n_plus_found = false;

            found_primes.Add(2);
            found_primes.Add(3);
            found_primes.Add(5);
            found_primes.Add(7);
            found_primes.Add(11);
            found_primes.Add(13);

            current_number = 12;
            no_of_primes_found = 6;

            while (no_of_primes_found < 10001)
            {
                current_number += 6;
                n_minus_found = false;
                n_plus_found = false;
                foreach (int current_prime in found_primes)
                {
                    if (!n_minus_found && (current_number - 1) % current_prime == 0)
                    {
                        n_minus_found = true;
                    }
                    if (!n_plus_found && (current_number + 1) % current_prime == 0)
                    {
                        n_plus_found = true;
                    }
                    if (n_minus_found && n_plus_found)
                    {
                        break;
                    }
                }
                if (!n_minus_found)
                {
                    found_primes.Add(current_number - 1);
                    no_of_primes_found = no_of_primes_found + 1;
                }
                if (!n_plus_found && no_of_primes_found < 10001)
                {
                    found_primes.Add(current_number + 1);
                    no_of_primes_found = no_of_primes_found + 1;
                }
            }
            System.Diagnostics.Debug.Print(Convert.ToString(no_of_primes_found));
            System.Diagnostics.Debug.Print(Convert.ToString(found_primes[found_primes.Count - 1]));
        }
    }
}

Project Euler pseudocode:

enter image description here

\$\endgroup\$
4
\$\begingroup\$

Overall your code is a pleasure to read. Symbol names are well-chosen and descriptive, the code layout makes it easy to follow your intentions.

However, somehow I can't shake the feeling that this code wants to be slimmer (which is probably caused by the complicated branching structure). Another thing that gives the code a strangely odd feeling is the initialisation of the primes vector. Necessity demands that the wheel primes - 2 and 3 - be pulled out of thin air and stuffed into the found_primes list. You are adding a couple more, but there is nothing that tells us why.

Also, it would have felt more natural to see the vector initialised like this:

var found_primes = new List<uint> { 2, 3 };  // pull the wheel primes out of thin air

This way the type needs to be mentioned - and read/checked - only once, and the initialisation doesn't grab undue amounts of screen space and attention. Plus, one doesn't have to hunt around to find out what the initial value of the list is going to be. This makes the code slimmer and easier to read.

As a rule of thumb, it is often better to defer the declaration of a variable until it enters centre stage and one has a value to give to it. This reduces the amount of scanning back and forth that a reader has to do, and it gives more natural flow to things.

The initialisation of no_of_primes_found to a constant instead of found_primes.Count contributes to the uneasy feeling. That part of the code is not performance-critical, and so there's no explanation why the brittle method of using a programmer-computed constant was chosen instead of the robust method of assigning the vector's Count property. Last but not least, why use a separate variable for counting the primes at all when the List<> already does it for you?

It would also have been slightly more natural (easier to follow) if you had moved the loop increment to the tail of the loop instead of using a pre-incrementing loop where the reader has to add 12 and 6 in order to know the first number tested. Pre-increment is more robust in while loops with continue statements, but simple plain for loops are just as robust and often make it easier to understand the iteration logic because everything is gathered together in a single source line.

for (uint n = 18; found_primes.Count < 10001; n += 6)
{
   ...
}

And now to the heart of the matter, the loop body. It has already been mentioned that the seductive elegance of foreach iteration made you forget to think about the termination condition of the inner loop - and thinking it does require. The simplest approach would be to re-compute the square root during each iteration of the outer loop:

uint sqrt_n = (uint)Math.Sqrt(n);

foreach (uint current_prime in found_primes)
{
   if (current_prime > sqrt_n)
      break;

   ...
}

However, the square root computation is quite expensive. An alternative that is often employed is to check whether the square of the current prime exceeds the current number or not. Since you are iterating over primes and not over regularly spaced numbers it is not possible to use strength reduction and to update the square incrementally. An alternative that is worthy of investigation is to store the squares alongside the primes. However, multiplication is quite cheap nowadays and so it is difficult to judge the merits (or lack thereof) of such an optimisation without implementing and benchmarking it.

There are plenty of other potential approaches for dealing with this but it is always going to be a bit tricky.

Now, the inner loop body. It sports an unrolling of the mod 6 wheel but it also contains an awful lot of branching. The conditionals are bound to create problems with branch prediction (unlike loop tails, which are always predicted correctly except during the final iteration) and may kill all gains from the unrolling. Modern processor don't like mispredicted branches at all and levy heavy fines on them.

What's definitely going to happen is that primes will drag composites along for a ride all the way to the end of the loop whereas simpler code would reject the pillions much faster; similar considerations apply for composites without small factors.

I would recommend benchmarking the code against a version that is not unrolled, and also to pit both versions against the simple-most single-stepper and a simple odds-only variant (stepping mod 2 instead of mod 6). Remember, all optimisations have to prove their worth and more than pay for the complication/uglification they are causing.

\$\endgroup\$
  • \$\begingroup\$ This would be better as an extension on your current answer. Feel free to edit it in and remove this one. \$\endgroup\$ – Mast Feb 16 '16 at 11:08
  • 4
    \$\begingroup\$ @Mast: The reason for making separate answers was that this one is purely focussed on code craft and the other one on aspects (math, algorithmics and so on) that are independent of language and coding. Also, both answers are quite longish already... However, should people concur with Mast (comment upvote) then I will comply. \$\endgroup\$ – DarthGizka Feb 16 '16 at 11:21
  • \$\begingroup\$ Clarification: people concurring with Mast about merging the two answers should upvote Mast's comment. Mea culpa. \$\endgroup\$ – DarthGizka Feb 16 '16 at 11:41
  • \$\begingroup\$ This is a review from a different perspective, and as such it's legit. There's also plenty of precedent. Thanks for bringing to our attention, but I think this is fine. Feel free to raise on Meta \$\endgroup\$ – janos Feb 16 '16 at 12:08
  • 2
    \$\begingroup\$ Here's the relevant meta link: meta.codereview.stackexchange.com/questions/20/… \$\endgroup\$ – janos Feb 16 '16 at 12:28
6
\$\begingroup\$

Your solution looks massively overcoded and woefully under-engineered - as if you had fixed on one particular solution facet (striding in the manner of the mod 6 wheel with unrolling of one revolution) of a particular approach (trial division) before analysing the problem.

Also, you didn't specify with regard to which quality you want your code to be compared to others. It is way too convoluted for scoring on elegance and simplicity, and it is way too slow for scoring on speed. Hence it is impossible to guess what you think its merit might be...

You obviously overlooked the bit about only scanning up to the square root of the current number in the pseudo code. This alone makes your code run much more slowly than the simplest, cleanest, most straightforward algorithm without any optimisations whatsoever. In other words, all that nonsense with wheeled striding and unrolling is for nought.

To answer your question: compared to the pseudo code your solution does not fare well at all.

If you are looking for speed in contexts that involve the enumeration of non-trivial numbers of primes then you might want to look at sieves. The Sieve of Eratosthenes is simple but offers an unbeatable bang for buck ratio.

For the piddling small numbers that Project Euler tasks deal in, I'd recommend going for simplicity, cleanness and elegance. At least that will give you are more thorough understanding of the algorithms. Forget all the half-understood supposed optimisations that you may have seen somewhere. They are only optimisations if they are needed, applicable, and applied correctly. In all other cases they are pessimisations, and they also keep you from understanding your own code, obviously.

Start simple. Measure. Add complications one by one and measure the effect.

Also, the work that is done fastest is the work that you don't do at all. Hence it always pays to look at a problem with an eye for opportunities not to do things. This includes donning first the glasses of the mathematician, then those of the algorithmist, and only last the loupe of the performance coder.

Answer to eirikdaude's question in the comment (posted here to give it space):

Wheeled striding can cut the workload by a certain (small) constant factor, by way of skipping a certain part of the numbers to be scanned.

Double striding cuts the load in half by skipping multiples of two; mod 6 striding skips a further third, mod 30 (2*3*5) striding a further fifth, and so on.

Effectiveness decreases as you add more small primes and the effort increases explosively. Double striding has the best bang-for-buck ratio in many cases, and it has other advantages (like regular strides, as opposed to the 2,4,2,4 step of the mod 6 wheel or the 48 step sequence of the mod 210 wheel). Higher wheel orders than 2 require careful coding and engineering to realise at goodish part of the theoretical speedup. Even the highest-order wheel with the most perfect coding can realise only a small constant speedup, typically not more than half an order of magnitude (without even considering the slow-down due to the much more complex code).

wheel efficiency vs. size

The column 'modulus' gives the wheel circumference, 'spokes' gives the number of hops in an increment sequence, 'ratio' gives the ratio of how many numbers need to be scanned compared to scanning all candidates.

The mod 30 wheel has a lot of nice advantages (starting with the fact that it maps nicely to eight-bit bytes) but cannot even double the performance of the mod 2 wheel, despite all the effort required for implementing it. Mod 210 wheels are occasionally found in heavy-duty industrial-grade code, and wheels higher than 13 (starting with 17, i.e. mod 510,510) definitely belong in the pyrrhic oddball category.

Use the 'ratio' column to gauge the limit on possible speedups due to workload reduction, and use the 'spokes' column to gauge the required code complexity (unrollings, sizes of lookup tables etc.).

Have a look at my answer in the topic Printing all the prime numbers between two bounds to see benchmarks for actual speedups gained from wheeled striding in a roughly similar setting. Compare actual speedups to the theoretical limits gleaned from the table, to the increase in code complexity despite the tricks employed, and how little this all accomplishes compared to algorithmic optimisations.

Morale: outside of academic papers, wheels can give you only a small constant boost.

On the other hand, scanning only candidate factors up to the square root of the current number instead of all candidates gives exponential benefits, several orders of magnitude already with the small Euler target (100001st prime).

I found it very rewarding to treat the Euler problems with respect, giving them the full math ponderation and pencil+paper preparation before throwing down the first line of code - and then striving for the simplest-possible, cleanest, most elegant code that I can manage (some might say this comes a couple decades too late, and they might not be entirely wrong about that...).

\$\endgroup\$
  • \$\begingroup\$ The pseudocode is also using wheeled striding though? The main difference between my solution, and the one there (apart from not checking against the square of the current number, which is an obvious mistake I of course should have noticed) is that I only check against every prime already found, instead of every odd number. I take it this is not worthwhile for relatively small numbers, as the ones in the question. As for the Sieve of Erasthostenes, Atkins, etc, are these still more efficient when you don't know the endpoint? \$\endgroup\$ – eirikdaude Feb 15 '16 at 20:50
  • \$\begingroup\$ @eirik: The are certain formulas that can give an upper bound for the value of the nth prime. An alternative could be a sieve that scans one cache-sized window after the other, stashing found primes and working offsets in an auxiliary vector ready for the next round. For Euler's small problem you could get away with a fixed-size bitset. There are many ideas worthy of being tried, but they need tougher targets than Euler's (e.g. find the 100,000,001st prime instead). \$\endgroup\$ – DarthGizka Feb 15 '16 at 21:37
  • 1
    \$\begingroup\$ I see. Thanks for putting all this effort into your answer, it was certainly enlightening to read through it (and your other answer). \$\endgroup\$ – eirikdaude Feb 15 '16 at 22:42
3
\$\begingroup\$

DarthGizka gave 2 good answers, and I agree totally with him (and you too) that your code shows too much overthinking. Your code has convoluted thinking and unnecessary variables like no_of_primes_found, n_minus_found, and n_plus_found.

Note in my code examples, I will be using var. For admitted beginners, I recommend they don't start out using var, which you don't so I do credit you for that. See Language Guidelines - Implicitly Typed Local Variables for more.

If you tried to be more DRY (Don't Repeat Yourself), you will probably discover your code is more readable and more maintainable.

Your variable names are overall well chosen, except that underscores are frowned upon in variable names. See General Naming Conventions - Word Choice for more.

I'd suggest you keep Main more simplified and put your code into its own class. And for your own interest you may want to time what's happening. I will do this using a Stopwatch but keep in mind the stopwatch will also be timing the jitter time too.

And since you are new to C#, and possibly .NET, you should be aware that code running in Debug mode will be slower than in Release mode. Thus I encourage you not to use Debug.Print and instead use Console.WriteLine. One thing to be aware of with the console is that it may vanish upon completion of the exe, so you may want to request a Console.ReadLine or Console.Read to view your output.

Let's look at my Main:

using System.Diagnostics;

namespace Project_Euler_Problem_7
{
    class Program
    {
        static void Main(string[] args)
        {
            Console.WriteLine("Project Euler - Problem 7");
            Console.WriteLine("Find 10001st prime number:");

            var sw = Stopwatch.StartNew();
            var answer = Problem7.SolveWheel6(10001);
            sw.Stop();

            Console.WriteLine($"Answer: {answer} took {sw.ElapsedMilliseconds} ms");

            Console.WriteLine($"{Environment.NewLine}Press ENTER key");
            Console.ReadLine();
        }
    }
}

There are a couple of advantages doing it this way. For one, I have a timing mechanism in place. And two, whatever is particular about problem 7 is isolated into its own class.

I don't just have a single Solve method. I have 2 examples: SolveNaive and SolveWheel6. Let's look at my class:

public static class Problem7
{
    public static int SolveNaive(int nthPrimeToFind)
    {
        var knownPrimes = new List<int>() { 2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31 };

        if (knownPrimes.Count < nthPrimeToFind)
        {
            for (var number = knownPrimes.Last() + 2; knownPrimes.Count < nthPrimeToFind; number += 2)
            {
                if (IsPrime(number, knownPrimes))
                {
                    knownPrimes.Add(number);
                }
            }
        }
        return knownPrimes[nthPrimeToFind - 1];
    }

    public static int SolveWheel6(int nthPrimeToFind)
    {
        var knownPrimes = new List<int>() { 2, 3 };

        if (knownPrimes.Count < nthPrimeToFind)
        {
            for (var number = 6; knownPrimes.Count < nthPrimeToFind; number += 6)
            {
                if (IsPrime(number - 1, knownPrimes))
                {
                    knownPrimes.Add(number - 1);
                    if (knownPrimes.Count >= nthPrimeToFind) { break; }
                }
                if (IsPrime(number + 1, knownPrimes))
                {
                    knownPrimes.Add(number + 1);
                }
            }
        }
        return knownPrimes[nthPrimeToFind - 1];
    }

    private static bool IsPrime(int number, List<int> primes)
    {
        var root = (int)Math.Sqrt(number);
        foreach (var prime in primes)
        {
            if (prime > root) { break; }
            if (number % prime == 0)
            {
                return false;
            }
        }
        return true;
    }
}

Granted I have little limit checking for bad inputs. You could pass a negative as the nthPrimeToFind. I keep IsPrime private so I also don't have to check for < 2, 2, 3, evens, etc.

The main benefit of IsPrime is that it does ONE thing: check for primality, whereas your code checks it twice. My code also checks up to the square root of the number in question, which was lacking in your code.

What's missing is n_minus_found, n_plus_found, and no_of_primes_found. They really added little to the problem other than adding more code and confusion.

Here's an example of my output:

enter image description here

To summarize this answer:

  • Try to be more DRY.
  • Avoid underscores in names.
  • Consider adding a Stopwatch.
  • Replace Debug.Print with Console.Write to work in Release mode.
  • Use Console.Read to pause the page.
  • Keep Main simple.
  • Put your specific code into its own class.
\$\endgroup\$
  • \$\begingroup\$ Thanks for your answer, I've already made some of the simplifactions you suggest, such as putting all of the problems into their own class, creating an IsPrime-function, etc, checing against the square of the current prime, etc. Was gonna add a timer next, but hadn't gotten round to googling where a suitable function may be found, so you saved me a bit of time there, and the rest of your answer was an interesting read too. Thanks for putting your time in to help me. \$\endgroup\$ – eirikdaude Feb 16 '16 at 15:52

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.