4
\$\begingroup\$

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

fib = (x) ->
  return 0 if x == 0
  return 1 if x == 1
  return fib(x-1) + fib(x-2)

i = 2
fib_sum = 0

while (fib i) < 4000000
  n = fib i 
  if n % 2 is 0 then fib_sum += fib i
  i++

alert fib_sum

I am looking for a more "functional" solution but I am stuck.

Edit

Optimized the solution:

limit = 4000000

sum = 0
a = 1
b = 1

while b < limit
  if b % 2 is 0 then sum += b
  h = a + b
  a = b
  b = h

alert sum #4613732
\$\endgroup\$
  • \$\begingroup\$ 1) If your code is working, an advice would be to go to the thread corresponding to that problem on projecteuler. It's always pretty interesting. 2) If your code isn't working (or is too slow which might be the case) : you might want to write not a more functional but a more efficient way to compute the fibonacci numbers (try to think of the different recursive calls you are generating when computing fib(10) for instance). \$\endgroup\$ – SylvainD Jan 25 '12 at 16:29
  • \$\begingroup\$ Thanks, forgot they had solutions attached after it is solved. This algorithm made it a ton faster(edited above), although not the elegant functional solution I was looking for. \$\endgroup\$ – crocaduck81 Jan 25 '12 at 16:52
2
\$\begingroup\$

Better CoffeeScript

First of all, if you're going to use CoffeeScript, then use its full potential and do away with h:

limit = 4000000
sum = 0 

[a, b] = [1, 1]

while b < limit
  sum += b if b % 2 is 0
  [a, b] = [b, a + b]

console.log sum

It's nice and easy to read, and I'd use this implementation instead of a recursive one in "real code", but it's still instructive to think about a functional equivalent.

Memoization

What you're looking for is named memoization. The trick is that you should store the values of fib(n) in an array. This allows you to lookup in the array for most cases instead of computing the value again. You'll be able to use fib() in a natural but optimized way.

memo = [1, 1]

fib = (x) ->
    if typeof memo[x]  != 'number'
        memo[x] = fib(x - 1) + fib(x - 2)

    return memo[x]

Now we have a function that compute memo[x] if needed, and returns it for every call. This means that the first call to fib(3) is going to compute it using memo[2] and memo[1], but all subsequent calls are going to be "free".

I can now use this implementation to compute the sum over even values:

fib_sum = (i) ->
    // Initialize i to 0 for the first call
    if i is undefined then i = 0

    return 0 if fib(i) > limit

    if fib(i) % 2 == 0
        return fib_sum(i + 1) + fib(i)
    else 
        return fib_sum(i + 1)

You can use a tail-recursive function if you want but this won't help since you're probably going to overflow before doing a stack overflow.

Purely functional from the outside

Now the implementation seems functional but there's still this "memo" array that we would like to hide. Well, closures are the perfect way to achieve this. This is called the "pattern module" in JavaScript. Here's the full code:

fibonacci = (() ->
    'use strict'

    memo = [1, 1]
    limit = 4000000

    fib = (x) ->
        if typeof memo[x]  != 'number'
            memo[x] = fib(x - 1) + fib(x - 2)

        return memo[x]

    even_sum = (i) ->
        if i is undefined then i = 0

        return 0 if fib(i) > limit

        if fib(i) % 2 == 0
            return even_sum(i + 1) + fib(i)
        else 
            return even_sum(i + 1)

    return {nth: fib, even_sum: even_sum}
)()

console.log fibonacci.even_sum(); # 4613732

There's no way to know that out fibonacci module uses an array internally, but it's still used and allows for very fast code. Benchmarking show that it's as fast as the iterative version, and takes about 0.02s on my machine.

Automatic memoization?

It turns out that JavaScript: The Good Parts mentions that you can have automatic memoization and uses fibonacci as an example. It can be interesting to try to apply this to our fib_sum, but I'll leave it as an exercise. :)

\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.