Add Euler solutions in C# for the first eight.

[macauleym]

Here is my contribution of Project Euler solutions written in C#. ProjectEulerMain will run all of the current solutions.

[johnbfair]

@Orthak don't look at this as a rejection of the PR, but more so as a code review (which is how inline code commenting on GitHub is meant to be used). I think there's faster ways to process (maybe even faster than our F# implementations). Might as well throw the gauntlet down eh? :wink:

[macauleym]

@johnbfair Of course, the feedback is great! I didn't even know about the Parallels library. I wouldn't have known how to improve it, without your suggestions. I'll look into making these changes. I can't get better if I always get everything right anyways, haha. Thanks!

[ghost]

We can squeeze out a little bit more performance in Euler 8.

private static int LargestProduct()
{
    // This is a very large number...
    string thousandDigit =
        "73167176531330624919225119674426574742355349194934" +
        "96983520312774506326239578318016984801869478851843" +
        "85861560789112949495459501737958331952853208805511" +
        "12540698747158523863050715693290963295227443043557" +
        "66896648950445244523161731856403098711121722383113" +
        "62229893423380308135336276614282806444486645238749" +
        "30358907296290491560440772390713810515859307960866" +
        "70172427121883998797908792274921901699720888093776" +
        "65727333001053367881220235421809751254540594752243" +
        "52584907711670556013604839586446706324415722155397" +
        "53697817977846174064955149290862569321978468622482" +
        "83972241375657056057490261407972968652414535100474" +
        "82166370484403199890008895243450658541227588666881" +
        "16427171479924442928230863465674813919123162824586" +
        "17866458359124566529476545682848912883142607690042" +
        "24219022671055626321111109370544217506941658960408" +
        "07198403850962455444362981230987879927244284909188" +
        "84580156166097919133875499200524063689912560717606" +
        "05886116467109405077541002256983155200055935729725" +
        "71636269561882670428252483600823257530420752963450";

    var thousandArray = thousandDigit.ToCharArray();

    var productsList = new BlockingCollection<int>();

    Parallel.For(0, thousandArray.Length - 4, i => {
        int product = AsciiCharToIntegerFast(thousandArray[i])
            * AsciiCharToIntegerFast(thousandArray[i + 1])
            * AsciiCharToIntegerFast(thousandArray[i + 2])
            * AsciiCharToIntegerFast(thousandArray[i + 3])
            * AsciiCharToIntegerFast(thousandArray[i + 4]);

        productsList.Add(product);
    });

    return productsList.Max();
}

private static int AsciiCharToIntegerFast(char c)
{
    // Subtracts the ASCII char value c from '0' which is the integer 48
    // Integers 1 - 9 are characters 49 - 57
    return (int)(c - '0');
}

[macauleym]

Updated these 8 based on the comments and suggestions. If there are any other changes or improvements that I can make, please let me know!

[ghost]

I took a look at Euler 7 and it has a race condition from the end of the lock statement to the end of the block which may allow additional values to be added to the collection before the Parallel.For breaks. The TPL is a good thing, but not every solution is parallelizable (the lock statement defeats the purpose of Parallel.For) or worth parallelizing. Try benchmarking the code with and without parallelization to gauge whether the performance improvement is worthwhile.

I think it is probably best to revert it to a for statement since the algorithm isn't parallelizable in its current form.

I also have a simpler implementation that you can look at made from the Sieve of Eratosthenes.

// Start with a somewhat close bounding value
// or the sieve will take longer than necessary
private const long Limit = int.MaxValue / 16384;
private static PrimeGenerator Generator = new PrimeGenerator(Limit);

private static long FindThePrime()
{
    return Generator.GetNextPrime().Skip(10000).Take(1).First();
}

public class PrimeGenerator
{
    private readonly long _limit;
    private readonly bool[] _isPrime;

    public PrimeGenerator(long limit)
    {
        _limit = limit;
        _isPrime = new bool[_limit];

        // Initalize the sieve to true
        for(var i = 0L; i < _limit; i++)
        {
            _isPrime[i] = true;
        }
    }

    public IEnumerable<long> GetNextPrime()
    {
        for(var candidate = 2L; candidate < _limit; candidate++)
        {
            // Every true candidate is prime because
            // every multiple of the previous candidate
            // is marked false
            if(!_isPrime[candidate]) continue;

            yield return candidate;

            // This section is parallelizable
            // but with a small sieve the performance
            // with parallelization is less than
            // the performance single threaded
            for(var multiple = candidate * candidate;
                multiple < _limit;
                multiple += candidate)
            {
                _isPrime[multiple] = false;
            }
        }
    }
}

[macauleym]

Oh wow, that's really awesome. I didn't even know about that. Shows me how much I know, haha. Since it looks like I've got a long way to go, is there any research material you can suggest? I'd love to dive into this a lot more.