patternModerate
Project Euler #2 (classic) - Sum of even fibonacci numbers below 4 million
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.
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
Variables
If you type your function in a Common Lisp interpreter/compiler, you will receive warnings
Primitive operators
The definition of
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:
Finally, since
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.