## Friday, March 25, 2011

### Project Euler problem 2

By considering the terms in the Fibonacci sequence whose values do not exceed four million, find the sum of the even-valued terms.

`:- module p2.:- interface.:- import_module io.:- pred main(io::di, io::uo) is det.`

In our implementation, we will again use the `int` module. Because the range of terms to sum is not definite (we do not know how many terms are less than four million without prior analysis), `solutions` will not be useful to us. (Note that even the `solutions.do_while` predicate cannot be relied upon, as the order in which terms are generated is not guaranteed, and we have no efficient way of knowing if we’ve found all the terms of interest.)

`:- implementation.:- import_module int.`

First let’s define the recursive function `fibonacci` of one argument to compute the `I`th Fibonacci number.

`:- func fibonacci(int) = int.:- pragma memo(fibonacci/1).fibonacci(I) =    (if I = 0 then 1     else if I = 1 then 2     else fibonacci(I - 1) + fibonacci(I - 2)).`

Normally a function so defined would be exponential with `I`. However, by instructing the Mercury compiler to memoize `fibonacci` via the `memo` pragma, we achieve linear performance as if we had used a dynamic programming algorithm. (Note that memoization is not yet available in all compilation grades, including Java.)

To perform the summation, we can define a recursive function which recurs on successive values of `I` until `fibonacci(I)` is not less than four million:

`sum_fibonaccis(I) =    (if fibonacci(I) @ Fibo < 4000000 then        sum_fibonaccis(I + 1) +            (if even(Fibo) then Fibo else 0)     else 0).`

The `@` function is used to bind `fibonacci(I)` to `Fibo` in an expression context (akin to C’s `=` operator). The built-in predicate `int.even` is used to test for evenness.

Those readers familiar with functional programming will likely notice that this function is not tail-recursive; i.e., the result of the recursive call is not returned directly. This will cause unnecessary (though, in this case, benign) stack growth. The typical solution is to rewrite `fibonacci` with an accumulator argument:

`sum_fibonaccis_acc(I, Sum) =    (if fibonacci(I) @ Fibo < 4000000 then        sum_fibonaccis_acc(I + 1, Sum +            (if even(Fibo) then Fibo else 0))     else Sum).`

Mercury however is able to automatically perform this transformation, provided we inform it that `(Fibo0 + Fibo1 + ...) + FiboN` is indeed the same as `Fibo0 + (Fibo1 + ... + FiboN)` – that is, that addition is associative:

`:- promise all [A, B, C, ABC] (A + B) + C = ABC <=> A + (B + C) = ABC.`

This optimization is enabled with the `--introduce-accumulators` option to `mmc`. The compiler unfortunately can recognize only a narrow set of functions and predicates as candidates for accumulator introduction. In particular, altering our definition of `sum_fibonaccis` to bind `Fibo = fibonacci(I)` in a separate body instead of using `@`, or moving the innermost `if` to outside the recursive call, causes the compiler not to recognize this function as a candidate for accumulator introduction.

The remainder of our implementation is unremarkable:

`p2 = sum_fibonaccis(0).main --> print(p2), nl.`

Compiling the program with `mmc --infer-all --introduce-accumulators --make p2` produces a large warning concerning possible performance problems due to the accumulator introduction altering the order of summation. This is obviously not a problem for addition and can be safely ignored; the warning is meant for operations such as linked list concatenation, the performance of which depends on the value of one operand more than that of the other. If desired this warning can be disabled with the `--inhibit-accumulator-warnings` option.

The resulting program runs in about 100 ms on my dual-core 1.6 GHz machine.