kozima #4793(2007/12/13 04:12 GMT) [ Common Lisp ] Rating4/4=1.00
gcd は組み込みで存在しますが、こんな式を基に書いてみました。呼び出し回数 1937 回。
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20
(defun *gcd (x y &optional (acc 1) (count 0)) (incf count) (cond ((= x y) (values count (* acc x))) ((and (oddp x) (oddp y)) ; odd, odd (*gcd (min x y) (ash (abs (- x y)) -1) acc count)) ((oddp x) ; odd, even (*gcd x (ash y -1) acc count)) ((oddp y) ; even, odd (*gcd (ash x -1) y acc count)) (t ; even, even (*gcd (ash x -1) (ash y -1) (ash acc 1) count)))) (defun fib (x) (loop with l = '(1 1) for i from 2 to x do (push (+ (car l) (cadr l)) l) finally (return (car l)))) (format t "~{Called ~D times, result is ~D~}" (multiple-value-list (*gcd (fib 2000) (fib 1999))))
Rating4/4=1.00-0+
1 reply [ reply ]
kozima #4794(2007/12/13 04:34 GMT) Rating0/0=0.00
書き忘れ。この方法だと各ステップで引数の少なくとも片方が半分以下になるので、ループ回数は引数の桁数に関して線形です。
[ reply ]
kozima
#4793()
[
Common Lisp
]
Rating4/4=1.00
gcd は組み込みで存在しますが、こんな式を基に書いてみました。呼び出し回数 1937 回。
(defun *gcd (x y &optional (acc 1) (count 0)) (incf count) (cond ((= x y) (values count (* acc x))) ((and (oddp x) (oddp y)) ; odd, odd (*gcd (min x y) (ash (abs (- x y)) -1) acc count)) ((oddp x) ; odd, even (*gcd x (ash y -1) acc count)) ((oddp y) ; even, odd (*gcd (ash x -1) y acc count)) (t ; even, even (*gcd (ash x -1) (ash y -1) (ash acc 1) count)))) (defun fib (x) (loop with l = '(1 1) for i from 2 to x do (push (+ (car l) (cadr l)) l) finally (return (car l)))) (format t "~{Called ~D times, result is ~D~}" (multiple-value-list (*gcd (fib 2000) (fib 1999))))Rating4/4=1.00-0+
1 reply [ reply ]