Note: The code below applies to version 0.3 of Microsoft Axum. If you are not using this version of Axum, then your code may differ from that shown here.
I have just solved Problem 2 of Project Euler using Microsoft Axum. The problem statement is as follows:
Find the sum of all the even-valued terms in the Fibonacci sequence which do not exceed four million..
Solution
My Axum-based solution is as follows:
1: using System;
2: using Microsoft.Axum;
3: using System.Concurrency.Messaging;
4:
5: namespace Problem002
6: {
7: // http://projecteuler.net/index.php?section=problems&id=2
8: //
9: // Each new term in the Fibonacci sequence is generated by adding the previous two terms.
10: // By starting with 1 and 2, the first 10 terms will be:
11: // 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, ...
12: // Find the sum of all the even-valued terms in the sequence which do not exceed four million.
13:
14: channel Problem002Channel
15: {
16: input long Maximum;
17: output long Sum;
18: }
19:
20: agent Problem002Agent : channel Problem002Channel
21: {
22: long CalculatedSum = 0;
23: bool ContinueCalculation = true;
24: long Max = 0;
25:
26: public Problem002Agent()
27: {
28: Max = receive(PrimaryChannel::Maximum);
29: long InputValue = 1;
30: while(ContinueCalculation)
31: {
32: long Result;
33:
34: if(InputValue % 3 == 0)
35: {
36: Result = Fibonacci(InputValue);
37: if(Result > Max)
38: {
39: ContinueCalculation = false;
40: continue;
41: }
42: CalculatedSum += Result;
43: }
44: InputValue++;
45: }
46: PrimaryChannel::Sum <-- CalculatedSum;
47: }
48:
49: function long Fibonacci(long n)
50: {
51: if(n <= 1)
52: return n;
53: return Fibonacci(n - 1) + Fibonacci(n - 2);
54: }
55: }
56:
57: agent MainAgent : channel Application
58: {
59: public MainAgent()
60: {
61: var AgentInstance = Problem002Agent.CreateInNewDomain();
62: AgentInstance::Maximum <-- (long)4000000;
63: var Sum = receive(AgentInstance::Sum); // should be 4613732
64: Console.Write("The sum of all the even-valued terms in the sequence which do not exceed 4,000,000 is ");
65: Console.Write(Sum);
66: Console.WriteLine(".");
67: Console.ReadLine();
68: PrimaryChannel::ExitCode <-- 0;
69: }
70: }
71: }
This is a very simple Axum design, with a main Application-based agent called MainAgent and a second agent called Problem002Agent that performs the actual calculation. The input to the Problem002Agent is the calculation maximum, which in this case is 400000 and the output is the calculated sum of the even terms. Most of the work is performed in the constructor of the Problem002Agent, which also contains a recursive Fibonacci function.
You may be curious as to why the Problem002Agent constructor calls the Fibonacci function only once every three times in lines 34-44. This is a mathematical optimization that we can take advantage of thanks to the problem statement. The problem statement notes that only even-valued Fibonacci terms are to be added up. A careful study of the Fibonacci sequence shows that only every third term in the sequence is an even-numbered term. The first few terms in the sequence are:
1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, 233, 377, 610, …
The pattern with respect to odd and even terms are:
odd, odd, even, odd, odd, even, odd, odd, even, odd, odd, even, odd, odd, even, …
Given this fact, and the fact that the problem domain asks that only even terms be calculated, only every third term needs to be computed. This also explains why there is no check to make sure that the calculated output of the Fibonacci function is an even number, because we know it to be even since only every third term is used as input. Calculating the Fibonacci number for every term is certainly possible, but, given the problem statement, would simply be a waste of computing.
Failed Attempts
In one of my earlier attempts to solve this problem using Axum, I had a pipeline built that started with an ordered list of integers, and a pipeline that looked something like this:
1: numbers ==> Fibonacci ==> EvenTerm ==> CalculateSum
The EvenTerm() function was designed to take in the output of a Fibonacci term and send it into a function that would return the value if it was an even number and zero otherwise:
1: function long EvenTerm(long Input)
2: {
3: if(Input % 2 == 0)
4: return Input;
5: return 0;
6: }
That output would be fed into code that would keep track of the sum:
1: long CalculatedSum = 0;
2:
3: void CalculateSum(long Input)
4: {
5: CalculatedSum += Input;
6: }
With this approach, all Fibonacci terms would be calculated, but the odd terms would be weeded out by the EvenTerm() pipeline function which would effectively turn them into zeros when added to the sum.
The problem that I had with the pipeline approach is that I didn’t know how to stop the pipeline once the Fibonacci terms exceeded 4,000,000. I would need to write something like this:
1: var numbers = new OrderedInteractionList<int>();
2: var PipelineInput = 1;
3: while(Fibonacci terms have not exceeded the max)
4: numbers <-- PipelineInput++;
I don’t (yet) know how to write line 3 in terms of Axum given its multiple-thread model. I like the pipeline approach, because it would make the code feel more like Axum and less like C#, but the Axum threading model would have the code filling the numbers list in one thread and calculating in another thread, possibly causing too many items to be added the the list. Perhaps I can find a more “Axum-like” solution for this problem as Axum matures.