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 秒となりました。