tao/elis gemini

tao-elis-gemini.lisp

;;;
;;; V(X) = sum_{k=1} floor(X / 2^k) を計算する Prolog 述語
;;; O(log X) のステップ数で高速に再帰計算を行う
;;;
(defrel &V
    ((_x _curr _ans)
     (:aux _next-curr _term _rest-ans)
     (== _term ,(floor _x _curr))
     (> _term 0)
     !
     (== _next-curr ,[_curr * 2])
     (&V _x _next-curr _rest-ans)
     (== _ans ,[_term + _rest-ans]))
    ((_x _curr 0)))

;;;
;;; Q(limit) を計算する Prolog 述語
;;; Q(limit) = m * V(limit/2) + V(limit/4) + floor(limit/4) を求める
;;;
(defrel &solve-q
    ((_limit _m _ans)
     (:aux _v1 _v2 _term1 _term2 _term3)
     (&V ,(floor _limit 2) 2 _v1)
     (&V ,(floor _limit 4) 2 _v2)
     (== _term1 ,[_m * _v1])
     (== _term2 _v2)
     (== _term3 ,(floor _limit 4))
     (== _ans ,[ [ _term1 + _term2 ] + _term3 ])))

;;;
;;; Q(10^12) を O(log limit) の対数時間で高速解決する solve 関数
;;; API: (project-euler-0561:solve)
;;;
(de solve (:opt (limit 1000000000000)
           :aux (m 904961))
    (& (:aux _ans)
       (&solve-q ,limit ,m _ans)
       _ans))


#+| Do it | (solve )
#|------------------------------------------------------------|
Timing the evaluation of (solve)

User time    =        0.005
System time  =        0.003
Elapsed time =        0.006
Allocation   = 4411488 bytes
78 Page faults
Calls to %EVAL    8252
GC time      =        0.001
 |------------------------------------------------------------|#
;;→ 452480999988235494