ccl で 1からNまで足してみた

exercism.io というプログラムの学習サイトで課題をこなしている。
そこであったlispの課題で、1からNまで足して二乗するという計算があった。
もちろん、数学の公式をつかえばいいのはわかっているんだけれども、これ以外の方法で試してみた。

(defun square (x)
  (* x x))

(defun square-of-sums (x)
  (square (/ (* x (1+ x)) 2)))

実行結果

とりあえず、CPSスタイルは処理時間がかかるのでお勧めしません。

n=1000 での比較 (total,user systemはミリ秒)

method	total	user	system	memory
normal	4	5	5	0
recursive	35	36	8	0
loop	19	20	3	0
cps	637	505	134	800000
apply +	216	170	48	160000
reduce	556	438	62	160000

n=1000000での比較 (total,user systemはミリ秒)

method	total	user	system	memory
normal	5	6	5	32
recursive	2114	2109	6	32
loop	2312	2286	37	32
cps	371697	294948	22582	80000032
apply +	-	-	-	-
reduce	103234	96548	6235	16000032

apply + は "Too many argument"というエラーが発生して実行できなかった

実装

(defun square-of-sums-loop (x)
  (square
   (loop for n upto x sum n)))

(defun square-of-sums-recursive (x)
  (labels
      ((sum (n acc)
	 (if (<= n 0)
	     acc
	     (sum (1- n) (+ acc n)))))
    (square (sum x 0))))

(defun square-of-sums-cps (x)
  (labels
      ((sum (n cont)
	 (if (<= n 0)
	     (funcall cont 0)
	     (sum (1- n) #'(lambda (x) (funcall cont (+ n x)))))))
    (square (sum x #'identity))))

(defun square-of-sums-+ (x)
  (square 
   (apply #'+ (iota x))))

(defun square-of-sums-reduce (x)
  (square
   (reduce #'+ (iota x))))

(defun iota (end &optional (start 0) (acc nil))
  (if (zerop end)
      (nreverse acc)
      (iota (1- end) (1+ start) (cons start acc))))