Project Euler Problem 25

問題25: フィボナッチ数列の項 F(n) が千桁になる最初の n を求めよ。ただし F(1)=F(2)=1とする。[=>問題文]

問題25の解答

 bigint ライブラリの出番です。

;; Emacs Lisp
(require 'bigint)

(defun problem025 (digit)
  (do ((fn (string-to-bigint "0"))
       (fn-1 (string-to-bigint "1"))
       (fn-2 (string-to-bigint "1"))
       (n 2 (1+ n)))
      ((= digit (bigint-length fn)) n)
    (setq fn (bigint+ fn-1 fn-2))
    (setq fn-1 fn-2 fn-2 fn)))

(problem025 1000)

 bigint ライブラリに新たに桁数を取得する関数 bigint-length を追加しました。bigint-to-stringで文字列にして length を使えば長さは求まりますが処理コストに差が出ます。

多倍長整数(bigint)の桁数を取得する関数

(defun bigint-length (n)
  "桁数を取得"
  (let ((m (reverse n)))
    (+ (length (number-to-string (car m)))
       (* 4 (length (cdr m))))))

 problem025 は、bigint-to-string & length で作ると 2.5秒、bigint-length で作ると 0.6 秒となりました。