Project Euler Problem 16

問題16: 2^1000 の各桁の数字を合計した値を求めよ。[=>問題文]

bigint ライブラリの改良

　かなりヘビーな計算量になりそうなので、問題13で作った多倍長整数ライブラリの改良と、機能追加をします。改良点は２つ。まず、多倍長数をあらわすリストの要素を0〜9の1桁から、0〜9999の4桁に変更。計算速度が4倍になります。もう一つの改良は加算関数 bigint+ の効率化。以前のものは桁数の大きく異なる2数の和計算でとても非効率でした。
　追加機能は、乗算と累乗計算。ここまで作れば問題は解けたも同然です。

(defun bigint-expt (n m)
  "累乗計算。n:bigint, m:0以上の整数"
  (let ((result '(1)) (i 0) (cnt 0))
    (while (zerop (/ m 2))
      (incf cnt)
      (setq m (/ m 2)))
    (while (<= 0 (decf m))
      (setq result (bigint* result n)))
    (while (<= 0 (decf cnt))
      (setq result (bigint* result result)))
    result))

　累乗計算は、最初に指数 m を割れなくなるまで 2 で割ってその回数をカウントしてます。残りの m の回数だけ n を繰り返し積算したその結果を、最初に2で割った回数だけ二乗すれば答えがでます。これは掛け算の回数を減らす工夫ですが、パフォーマンスアップはさほどでもありませんでした。
　※多倍長演算ライブラリの全コードはこちらへ移動しました。

問題16の解答

(defun problem016 ()
  (let ((str (bigint-to-string
              (bigint-expt
               (string-to-bigint "2")
               1000))))
    (apply #'+
           (mapcar #'(lambda (c) (- c ?0)) str))))

　処理にかかった時間は 0.035 秒。なかなかのもんじゃないでしょうか。