HiveBrain v1.2.0
Get Started
← Back to all entries
patternModerate

Project Euler #2 (classic) - Sum of even fibonacci numbers below 4 million

Submitted by: @import:stackexchange-codereview··
0
Viewed 0 times
millionfibonaccinumbersclassicprojecteulerbelowsumeven

Problem

I'm looking to use LISP as best I can, not just get the right answer. This is very early on in my LISP career so feedback is welcome and exciting! Recently asked about Project Euler #1, got some feedback and incorporated into this answer for #2, but I know there's a LOT left to be learned!

Description of Problem #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.

(defun sum (L)
  "sum a list"
  (reduce #'+ L))

(defun filter (L predicate)
  "filters a list"
  (remove-if (complement predicate) L))

(defun fiboNums (maxNum)
  "list of fibonacci numbers that are below maxNum"
  (setq A 1)
  (setq B 2)
  (setq next (+ A B))
  (loop while (< B maxNum) do
    (setq next (+ A B))
    (setq A B)
    (setq B next)
    collecting A))

(defvar answer (sum (filter (fiboNums (* 4 1000 1000)) #'evenp)))
(print answer)

Solution

Notation

It is a common convention in Lisp to avoid uppercase (or mixed lowercase and uppercase) letters in identifiers (symbols), so for instance use l instead of L, or fibo-nums instead of fiboNums, etc.

Variables

If you type your function in a Common Lisp interpreter/compiler, you will receive warnings undefined variable for A B and next. This is because you should introduce local variables before using them with the let or let special operators (let is needed if you need to initialize variables with the value other variables introduced). Then, you can assign these variables, as well as all the other type of variables, with setf, that can assign several variables in sequence. So, for instance:

(defun fibo-nums (max-num)
  "list of fibonacci numbers that are below max-num"
  (let* ((a 1)
         (b 2)
         (next (+ a b)))
  (loop while (< b max-num)
    do (setf next (+ a b)
             a b
             b next)
    collecting a)))


Primitive operators

The definition of filter is not necessary, your definition is equivalent to the primitive function remove-if-not.

Algorithm

In this case there is no need of generate a list of Fibonacci numbers and then visiting it, it is sufficient to sum the numbers while generating them:

(defun sum-of-even-fibo (max-num)
  (loop for a = 1 then b
     for b = 1 then next
     for next = (+ a b)
     while (< a max-num)
     when (evenp a)
     sum a))


Finally, since loop is a powerful macro with a complex syntax, here is an alternative version with the more simple macro do*, which has also a syntax more “lisp-style”:

(defun sum-of-even-fibo (max-num)
  (do* ((sum 0)
        (a 1 b)
        (b 1 next)
        (next (+ a b) (+ a b)))
       ((> a max-num) sum)
    (when (evenp a)
      (incf sum a))))

Code Snippets

(defun fibo-nums (max-num)
  "list of fibonacci numbers that are below max-num"
  (let* ((a 1)
         (b 2)
         (next (+ a b)))
  (loop while (< b max-num)
    do (setf next (+ a b)
             a b
             b next)
    collecting a)))
(defun sum-of-even-fibo (max-num)
  (loop for a = 1 then b
     for b = 1 then next
     for next = (+ a b)
     while (< a max-num)
     when (evenp a)
     sum a))
(defun sum-of-even-fibo (max-num)
  (do* ((sum 0)
        (a 1 b)
        (b 1 next)
        (next (+ a b) (+ a b)))
       ((> a max-num) sum)
    (when (evenp a)
      (incf sum a))))

Context

StackExchange Code Review Q#150180, answer score: 11

Revisions (0)

No revisions yet.