Euler problem 2

.

The older I get, the less I care about what people think about me. Therefore the older I get, the happier I am.

—

.

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

(defun fib (n)
  (cond ((= n 0) 0)
        ((= n 1) 1)
        ((> n 1) (+ (fib (- n 2)) (fib (- n 1))))))

(time (fib 40))

;; Evaluation took:
;;   2.648 seconds of real time
;;   2.640080 seconds of total run time
;;   99.70% CPU
;;   9,002,590,370 processor cycles
;;   0 bytes consed
;; 

;; tail resursion

(defun fib-t (n)
  (labels ((fib-iter (m a b)
            (if (= m 0)
            a
            (fib-iter (- m 1) b (+ a b)))))
        (fib-iter n 0 1)))

(time (fib-t 40))

;; Evaluation took:
;;   0.000 seconds of real time
;;   0.000002 seconds of total run time
;;   100.00% CPU
;;   2,184 processor cycles
;;   0 bytes consed
;;
  
;; infinite list

(defmacro append-last (lst obj)
  `(append ,lst (list ,obj)))

(defun fib-i (n)
  (labels ((fib-iter (m fib-list a b)
            (if (> m (- n 2))
            fib-list
            (fib-iter (1+ m)
                (append-last fib-list (+ a b))
                b
                (+ a b)))))
    (fib-iter 0 '(0 1) 0 1)))

(time (fib-i 40))

;; Evaluation took:
;;   0.000 seconds of real time
;;   0.000008 seconds of total run time 
;;   100.00% CPU
;;   21,960 processor cycles
;;   32,768 bytes consed


(defun filter (fn lst)
  (let ((acc nil))
    (dolist (x lst)
      (let ((val (funcall fn x)))
    (if val (push val acc))))
    (nreverse acc)))

(defmacro filter-list (fn lst)
  `(filter #'(lambda (x)
                (if (funcall ,fn x) x))
            ,lst))

(defmacro filter-2 (fn1 fn2 lst)
  `(filter-list #'(lambda (x)
                    (if (and
                    (funcall ,fn1 x)
                    (funcall ,fn2 x))
                    x))
                ,lst))

(reduce #'+ (filter-2 #'evenp
              #'(lambda (x) (< x 4000000))
              (fib-i 100)))

; 4613732

— Me@2022-08-07 12:34:19 PM

.

.

2022.08.09 Tuesday (c) All rights reserved by ACHK