Parallelcoding.com

Project Euler problem #6 is

Find the difference between the sum of the squares of the first one hundred natural numbers and the square of the sum.

When I first began looking at this problem I wanted to experiment a bit with the Parallel Extensions for .NET, so I started where any parallel algorithm begins: with a sequential algorithm. The algorithm here is rather trivial: Loop over the natural numbers from 1 to 100. In order to sum the squares I will sum the square of each number. In order to square the sum I will sum the numbers and then square them. The difference is the answer. So, first, I came up with two functions: SumOfSquares and SquareOfSums.

My first attempt at these functions ended up something like this:

1
2
3
4
5
6
7
8
9
10
11
12
13
14

static double SumOfSquares(int min, int max) {
    double result = 0;
    for(int x = min; x <= max; x++) {
        result += Math.Pow(x, 2);
     }
     return result;
}
static double SquareOfSums(int min, int max) {
    double result = 0;
    for(int x = min; x <= max; x++) {
        result += x;
    }
    return Math.Pow(result, 2);
}

Both of those functions are very straight forward. My first thought after writing these was, “Hey, why not use some LINQ?” So I did. Here is how the functions change:

1
2
3
4
5
6

static double LinqSumOfSquares(int min, int max) {
    return Enumerable.Range(min, max).Select(d => Math.Pow(d, 2)).Sum();           
}
static double LinqSquareOfSums(int min, int max) {
    return Math.Pow(Enumerable.Range(min, max).Select(d => d).Sum(), 2);    
}

Wow! Talk about incredible, shrinking functions! I love finding a way to make code more succinct, readable, and elegant and these changes seem to have hit the nail on the head! Anyways, that is basically all the pieces for the sequential algorithm. All you have to do is call each of those functions and take the difference. Simple, huh? But the real question is how can we parallelize these bad boys? I have a few thoughts.

1. Call each function in parallel. In other words let the sumOfSquares and SquareOfSum function run at the same time in different threads.
2. Parallelize each function invidvidually. In other words leverage the loops inside of each function in order to parallelize them.

So let’s take a look at each method using the Parallel Extensions for .NET. The first method is calling each function in parallel. My first thought here was to use Parallel.Invoke in order to call each function at the same time. A little further research quickly revealed that Parallel.Invoke cannot return any values. My initial response to that: “Well that sucks.” Luckily there’s another class in the Parallel library called Futures. What’s a future? From DevX –

“In TPL terms, a Future is basically a task that returns a value. It’s like a deferred function. You start it running and then use its value later. If the Future hasn’t finished calculating its value by the time you need it, it makes you wait while it finishes.”

Sounds good to me. So how do we use futures? Like this:

1
2
3
4
5
6
7
8

static long Problem6Futures(int min, int max) {
 
    Future<double> fSumOfSquares = Future.Create(() => SumOfSquares(min, max));
    Future<double> fSquareOfSums = Future.Create(() => SquareOfSums(min, max));
    double result = fSquareOfSums.Value - fSumOfSquares.Value;
 
    return result;
}

Easy, huh? All you have to remember is that Futures are deferred functions that return values. The result of Future operation gets stored in an object of type Future and the value is stored in Object.Value. So how about the second method of parallelizing this algorithm? Well, it’s even easier because of PLINQ – or Parallel LINQ. Let’s see what it looks like.

1
2
3
4
5
6

static double ParallelSumOfSquares(int min, int max) {
    return Enumerable.Range(min, max).AsParallel().Select(d => Math.Pow(d, 2)).Sum();
}
static double ParallelSquareOfSums(int min, int max) {
    return Math.Pow(Enumerable.Range(min, max).AsParallel().Sum(), 2);
}

Hah! Even easier! All that I did was add .AsParrallel() to our data. That tells LINQ to do the processing in parallel!

So, there’s Project Euler Problem #6 for you. Was it a hard problem? Not really. Are you going to see major performance results through the parallelization of this algorithm? No. But you gotta’ start somewhere when you’re learning how to parallelize algorithms using a new library. Today I used Futures and PLINQ and that sound’s like a pretty solid start to me.

Project Euler #3 is :

Find the largest prime factor of a composite number.

My first attempt at this whipped up some typical code that simply brute forced my way to the solution. My code looked like this:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36

static void Problem3() {
    long n = 600851475143;
    int factor = 2;
    int lastFactor = 1;
 
 
    if(n % 2 == 0) {
        lastFactor = 2;
        n = n / 2;
        while(n % 2 == 0) {
            n = n / 2;
        }
     } else {
         lastFactor = 1;
     }
     factor = 3;
 
     double maxFactor = Math.Sqrt(n);
     while(n > 1 && factor <= maxFactor) {
          if(n % factor == 0) {
              n = n / factor;
              lastFactor = factor;
              while(n % factor == 0) {
                  n = n / factor;
              }
              maxFactor = Math.Sqrt(n);
          }
          factor += 2;
      }
 
      if(n == 1) {
          Console.Write(lastFactor.ToString() + " ");
      } else {
          Console.Write(n.ToString() + " ");
      }
}

Not very elegant, but it works. So I set out to find something a bit prettier and I came across I LINQ solution here. All I did was tack on the .AsParallel() in order to give it a little speed boost. The code looks like:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35

static void LinqProblem3() {
    long largeNumber = 600851475143;
    var allPrimeFactors = from p in Primes.PrimeFactors(largeNumber).AsParallel()
                                 orderby p descending
                                 select p;
 
    foreach(var f in allPrimeFactors){
        Console.WriteLine(f);
    }
}
 
public static class Primes {
 
    // Find all prime factors.
    public static IEnumerable<int> PrimeFactors(long number) {
        // Start by removing the lowest prime (2)
        return MorePrimeFactors(number, 2);
    }
 
    // This recursive method finds all prime factors.
    private static IEnumerable<int> MorePrimeFactors(long number, int factor) {
        // Find the next prime factor
	while(number % factor != 0)
	    factor++;
	// Return it.
	yield return factor;
 
	// look again...
	if(number > factor)
		// recursively look for this factor again, using Num/factor
		// as the new big number
		foreach(int factors in MorePrimeFactors(number / factor, factor))
			yield return factors;
	}
}

Problem #2 in the Project Euler series is:

Each new term in the Fibonacci sequence is generated by adding the previous two terms. By starting with 1 and 2, the first 10 terms will be:

1, 2, 3, 5, 8, 13, 21, 34, 55, 89, …

Find the sum of all the even-valued terms in the sequence which do not exceed four million.

My solution:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24

static void Problem2() {
    int term1 = 0;
    int term2 = 1;
    int term3 = 1;
    int max = 4000000;
    double sum = 0;
 
    while(term1 < max && term2 < max && term3 < max) {
        term1 = term2 + term3;
        term2 = term1 + term3;
        term3 = term2 + term1;
 
        if(term1 % 2 == 0) {
            sum += term1;
        }
        if(term2 % 2 == 0) {
            sum += term2;
         }
         if(term3 % 2 == 0) {
            sum += term3;
         }
 
    }
}

Problem #1 in the Project Euler series is:

Add all the natural numbers below one thousand that are multiples of 3 or 5.

A few of the more interesting/elegant solutions I’ve seen are listed below.

C#

1
2

List<int> Numbers = (Enumerable.Range(0, upperLimit)).ToList();
int Result = (from n in Numbers where n % 3 == 0 || n % 5 == 0 select n).Sum();

F#

1
2
3
4
5
6
7
8
9

#light
let rec sum_mul xs =
    match xs with
        | []    -> 0
        | y::ys when y % 3 = 0 || y % 5 = 0 -> y + sum_mul ys
        | y::ys -> sum_mul ys
 
let sum = sum_mul [1 .. 999]
print_any sum

Ruby (from csLife)

1

puts (1...1000).select { |n| n % 3 == 0 or n % 5 == 0 }.inject { |sum, n| sum + n }

Haskell

1

sum [n | n <- [1..1000-1], n 'mod' 5 == 0 || n 'mod' 3 == 0]

Erlang

1
2
3
4
5

-module(euler_1).
-export([start/0,solve_euler_1/1]).
 
start() -> io:format("~w~n",[solve_euler_1(1000)]).
solve_euler_1(N) -> lists:sum([X || X <- lists:seq(1,N-1), (X rem 3 == 0) or (X rem 5 == 0)]).