Project Euler Problem 13

問題13: 提示された50桁の数字100個の総和の上位10桁を求める。[=>問題文]
　とうとうこの手の来てしまいましたね。多倍長演算ってライブラリや言語サポートがないとめんどくさいんだよな・・・。足し算だけなので最低限機能でサクっといきましょう。

問題13の解答

(require 'cl)

(defun string-to-bigint (str)
  (reverse (mapcar #'(lambda (c) (- c ?0))
                   (string-to-list str))))

(defun bigint-to-string (n)
  (apply #'concat
         (mapcar #'number-to-string (reverse n))))

(defun bigint+ (n1 n2)
  (let* ((len-n1 (length n1))
         (len-n2 (length n2))
         (m1 (if (< len-n1 len-n2) n2 n1))
         (m2 (append
              (if (eq m1 n1) n2 n1)
              (make-list (abs (- len-n1 len-n2)) 0)))
         (carry 0)
         (lis (mapcar*
               #'(lambda (a b)
                   (let ((n (+ a b carry)))
                     (setq carry (/ n 10))
                     (% n 10)))
               m1 m2)))
    (if (zerop carry)
        lis
      (append lis (list carry)))))

(defun problem013 (numbers)
  (let ((n nil)
        (sum (string-to-bigint (car numbers))))
    (dolist (n (cdr numbers))
      (setq sum (bigint+ sum (string-to-bigint n))))
    (subseq (bigint-to-string sum) 0 10)))

(defvar *numbers*)
(setq *numbers*
      '("37107287533902102798797998220837590246510135740250"
        "46376937677490009712648124896970078050417018260538"
        "74324986199524741059474233309513058123726617309629"
        "91942213363574161572522430563301811072406154908250"
        ;; 中略
        "77158542502016545090413245809786882778948721859617"
        "72107838435069186155435662884062257473692284509516"
        "20849603980134001723930671666823555245252804609722"
        "53503534226472524250874054075591789781264330331690"))

(problem013 *numbers*)

　多倍長整数と言っても、桁を一桁づつばらして逆順にした整数リストです。足し算でポイントとなるのは繰り上がりをどう処理するか。今回作った加算関数 bigint+ では、mapcar で 2つのリストを回しつつ、外側に置いた carry 変数で繰り上がりを受け渡しています。
　Emacs Lisp の mapcar はリストを一つしかとれない劣化版ですが、cl パッケージに mapcar* という Common Lisp 仕様の高階関数が用意されていました。
　mapcar* に渡すリストは同じ長さでなければ切り捨てられるため、事前に桁の少ないほうのリストを 0 埋めしてしています。

再帰版

　作ってみましたが相変わらず再帰が深いと怒られます。

(setq max-lisp-eval-depth 3000)
(setq max-specpdl-size 3000)

(defun bigint+ (n1 n2)
  (let* ((len-n1 (length n1))
         (len-n2 (length n2))
         (m1 (if (< len-n1 len-n2) n2 n1))
         (m2 (append
              (if (eq m1 n1) n2 n1)
              (make-list (abs (- len-n1 len-n2)) 0))))
    (labels
        ((repeat (m1 m2 carry)
                 (if (null m1)
                     (if (zerop carry)
                         nil
                       (list carry))
                   (let ((n (+ (car m1) (car m2) carry)))
                     (cons (% n 10)
                           (repeat (cdr m1) (cdr m2)
                                   (/ n 10)))))))
      (repeat m1 m2 0))))

プログラム修正

　文字列をリストにする時 reverse をかけ逆順になるようにしました。加算では下の桁から処理するのでこのほうが無駄がありません（修正前は加算前と後に２回 reverseをかけていた）。減算、積算もおそらくこの形式のほうがやりやすいんじゃないと思います。除算は･･････あんまり考えたくない･･･。