CODEWITHSUNDEEP
c#math
Steve B
Steve B

Reputation: 37660

Possible optimization in my code?

In order to solve the Euler Project problem n°5, I wrote the following program:

class p5
{
    const int maxNumber = 20;
    static void Main(string[] args)
    {
        Job(); // First warm-up call to avoid Jit latency

        var sw = Stopwatch.StartNew();
        var result = Job();
        sw.Stop();

        Debug.Assert(result == 232792560);
        Console.WriteLine(result);
        Console.WriteLine(sw.Elapsed);
        Console.ReadLine();
    }

    private static int Job()
    {
        var result = Enumerable.Range(1, int.MaxValue - 1)
            .Where(
                n => Enumerable.Range(maxNumber / 2 + 1, maxNumber / 2).All(c => n % c == 0)
            ).First();
        return result;
    }
}

However, I found this is a bit long (17 seconds, in release mode), even if it's working.

Is there any possible optimization ?

FYI, I tried with AsParallel method, but as expected, the chunk of works are too small and the context switch was heavier than the benefits (more that 1 minute) :

    var result = Enumerable.Range(1, int.MaxValue - 1).AsParallel()
        .Where(
            n => Enumerable.Range(maxNumber / 2 + 1, maxNumber / 2).All(c => n % c == 0)
        ).First();
    return result;

[Edit] According martin's suggestion, this version divided by 10 the time taken :

    private static int Job()
    {
        var n =2;
        bool result;
        do
        {
            result = true;
            for (int c = maxNumber / 2; c <= maxNumber; c++)
            {
                if (n % c > 0)
                {
                    result = false;
                    break;
                }
            }
            n ++;//= 2;
        } while (!result);
        return n;
    }

[Edit] To sum up all my tests, rough execution time :

The latest suggestion is clearly the good answer. I thank drhirsch for suggesting another approach instead of only simple loop optimization

Upvotes: 2

Views: 327

Answers (3)

Gunther Piez
Gunther Piez

Reputation: 30419

A good optimization would be using a better algorithm.

This is asking for the least common multiple of the numbers 1..20, which can be calculated successive by finding lcm(1,2), then lcm(lcm(1,2),3) etc until 20.

A simple algorithm for finding the lcm is dividing the product of the two numbers by the greatest common divisor. The gcd can be found by the well known euklidian algorithm in a very short time.

#include <iostream>

long gcd(long a, long b) {
    if (!b) return a;
    return gcd(b, a-b*(a/b));
}

long lcm(long a, long b) {
    return (a*b)/gcd(a, b);
}

int main(int argc, char** argv) {
    long x = 1;
    for (long i=2; i<20; ++i) 
        x = lcm(x, i);
    std::cout << x << std::endl;
}

This spits out the solution instantly.

Upvotes: 6

martin
martin

Reputation: 2638

Using Enumerable is slow (see this for comparison of Enumerable.Repeat and for loop for initialization of an array). Try plain while/for loop like this:

        int maxNumber = 21;
        int n = 1;
        bool found = false;
        while(!found)
        {
            found = true;
            for(int i = 1; i < maxNumber; i++)
            {
                if(n % i != 0)
                {
                    found = false;
                    break;
                }
            }
            n++;
        }
        return n-1;

This runs for about 4 seconds on my computer in debug.

EDIT

When considering further optimizations, it is better to start testing modulo of larger numbers, so when I changed the for loop to:

for (int i = maxNumber; i > 1; i--)

the time dropped to under 2 seconds.

A mathematical insight would be that we only have to test divisibility by numbers that are not multiples of the numbers we already tested. In our case we can write:

    private int[] p = { 19, 17, 16, 13, 11, 9, 7, 5, 4, 3, 2 };
    int Job()
    {
        int n = 1;
        bool found = false;
        while (!found)
        {
            found = true;
            foreach (int i in p)
            {
                if (n % i != 0)
                {
                    found = false;
                    break;
                }
            }
            n++;
        }
        return n - 1;
    }

However, this is actually slower, about 2.5 seconds.

Upvotes: 1

Rivasa
Rivasa

Reputation: 6740

Well, one thing is that you only have to test even numbers, so start at 0, and increase by 2. this is due to the fact that an even number will never evenly divide into an odd number. you could also start the search at a factorial of 10, so 10*9*8*7..and so on so other words start at 10! which is 3 628 800. that may help run it faster. also on average my speed in C was 10 seconds, so you're code is actually fine.

Upvotes: 1

Related Questions