Creative Scratchpad

Well, in the end I couldn't resist any more and here we go, Project Euler, problem No. 2:

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, ...

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

Nice, so we get to work with Fibonacci numbers. The first thing that comes in mind is recursive solution, from the very definition of Fibonacci numbers, something like:

fn nthFibRec nr =
(
    if nr < 2 then nr
    else nthFibRec (nr-1) + nthFibRec (nr-2)
)

However, this approach makes so many nested function calls computing the same value over and over again and is a classic example given to discourage people from using recursion in the first place.

So, what can we do about it? There are two options, cache previous results or switch to iteration instead. So let's try both:

fibonacci = #(1L)

fn nthFibRec nr =
(
    if nr < 2 then nr
    else if fibonacci[nr] != undefined then fibonacci[nr]
    else fibonacci[nr] = nthFibRec (nr-1) + nthFibRec (nr-2)
)

And the iteration way:

fn nthFibIter nr =
(
    if nr < 2 then nr
    else
    (
        local fib = 1L
        local fibPrev = 1L
        for i = 3 to nr do
        (
            local temp = fib
            fib += fibPrev
            fibPrev = temp
        )
        fib
    )
)

And now for both of them even nthFib*** 90L works in no time, it is more or less up to our personal preference which one we will choose, both have their pros and cons.

Next we need to find out if the number is even or not. We could just use mod n 2 == 0 but there's a bit faster way, bitwise operations: bit.and 1L nr == 0 (let's say I'm trading a slightly better performance of it for the cost of a function call to keep readability):

  fn isEven nr = bit.and 1L nr == 0

Now that it looks like we have everything we may need, let's put it all together:

(
    fn isEven nr = bit.and 1L nr == 0

    fn nthFibIter nr =
    (
        if nr < 2 then nr
        else
        (
            local fib = 1L
            local fibPrev = 1L
            for i = 3 to nr do
            (
                local temp = fib
                fib += fibPrev
                fibPrev = temp
            )
            fib
        )
    )

    local midresult, result = 0

    for i = 3 to (1/.0) while (midResult = nthFibIter i) < 4000000
        where isEven midResult do
            result += midResult

    result
)

Well, this works but the method we arrive to the result has its issues, first and foremost it recalculates the midresults all the time which is not really needed as we are iterating all the Fibonacci numbers in the range anyway. With a little refactoring and using a dataPair data structure to hold the values, swapping its values and adding the first value (returned by swap) to the second one, we get this instead:

(
    fn isEven nr = bit.and 1L nr == 0L

    local sum = 0
    local pair = dataPair 0L 1L

    while pair.v1 < 4000000 do
    (
        if isEven pair.v1 do sum += pair.v1
        pair.v2 += swap pair.v1 pair.v2
    )
    sum
)

There are still many other approaches to try, for example the Binet's formula to get to the desired numbers faster. It uses the square root of five and we should make sure this number is as exact as possible. The double precision float should be good enough for this purpose.

We can compute the square root using 5.0d0^0.5 instead of sqrt 5.0d0. It doesn't make all that big difference here but there are some distinct advatages to it. First of all it doesn't change the number type: 2L^0.5 returns 1L while sqrt 2L returns single precision float, 1.41421 in this case, second: it's slightly faster as well.

(
    local phi = 5.0d0^0.5

    fn isEven nr = bit.and 1L nr == 0

    fn nthFibBinet nr =
        ((((double 0.5 + phi/2.0d0)^nr)/phi) + double 0.5) as integer64
    
    local midresult, result = 0

    for i = 3 to (1/.0) while (midResult = nthFibBinet i) < 4000000
        where isEven midResult do
            result += midResult

    result
)

All good things come in threes, so here's a third way of doing it, now using Prof. Edsgar W. Dijkstra's method:

(
    local fibVal = #(1.0d0,1.0d0)

    fn isEven nr = bit.and 1L nr == 0

    fn nthFibDijkstra nr =
    (
        if fibVal[nr] != undefined then fibVal[nr]
        else if isEven nr then
        (
            local half = nr/2
            fibVal[nr] = ((2*(nthFibDijkstra (half-1))) + nthFibDijkstra half) * (nthFibDijkstra half)
        )
        else fibVal[nr] = (nthFibDijkstra ((nr-1)/2.0d0)^2) + (nthFibDijkstra ((nr+1)/2.0d0)^2)
    )

    local midresult, result = 0

    for i = 3 to (1/.0) while (midResult = nthFibDijkstra i) < 4000000
        where isEven midResult do
            result += midResult

    result
)

It breaks the whole task in only a few steps and gets even more efficent when used for large numbers. That is not the case here, indeed, but still, it's good to know about it. NOTE: We can even safely cast the resulting value to integer here.

DISCLAIMER: All scripts and snippets are provided as is under Creative Commons Zero (public domain, no restrictions) license. The author and this blog cannot be held liable for any loss caused as a result of inaccuracy or error within these web pages. Use at your own risk.