最初に 1000桁に到達するフィボナッチ数は何番目？でベンチマーク

OOPL


@yukihiro_matz 経由で。


おもしろい。やってみよう。…っても、フィボナッチは愚直な再帰縛りでもなければたいした差はでませんから、どう書くかのほうが楽しめますね。^^;　ここでは各言語、takeWhile して得られた配列のサイズを調べる…って縛りで書いてみました。Clojure はまったく知らないので、ほとんどネタ元のをそのまんまです。あしからず。


Clojure

$ clojure
Clojure 1.1.0
user=> (. System exit 0)
$ clojure euler25.clj
4782
"Elapsed time: 30.579026 msecs"
$ cat euler25.cli
(time (do
  (def fib-seq (lazy-cat [0 1] (map + fib-seq (rest fib-seq))))
  (let [limit (.pow (BigInteger/TEN) 999)] (println (count (take-while #(< % limit) fib-seq))))))

Haskell

$ ghc --version
The Glorious Glasgow Haskell Compilation System, version 6.8.2
$ runhaskell euler25.hs
4782
33.949
$ cat euler25.hs
import Time

limit = 10^999
fibs = 1:1:[ a+b | (a,b) <- zip fibs (tail fibs) ]

main = do
  t1 <- getClockTime
  print $ (length $ takeWhile (< limit) fibs) + 1
  t2 <- getClockTime
  print $ fromInteger (tdPicosec $ diffClockTimes t2 t1) / 1.0e9

Python

$ python -V
Python 2.5.1
$ python euler25.py
4782
9.99999046326
$ cat euler25.py
from time import time
from itertools import takewhile

def fib():
  a = b = 1
  while True:
    yield a
    a,b = b,a+b

t1 = time()
print len([n for n in takewhile(lambda x : x < 10**999, fib())]) + 1
print (time() - t1) * 1e3

Ruby

$ ruby1.9 -v
ruby 1.9.1p0 (2009-01-30 revision 21907) [i386-cygwin]
$ ruby1.9 euler25.rb
4782
14.0
$ cat euler25.rb
limit = 10 ** 999
fibs = [1,1]
def fibs.[](n); n < size ? super : self[n]=self[n-2]+self[n-1] end

t1 = Time.now
#p fibs.take_while{ |x| x < limit }.size + 1   #←残念ながら、これはできない…
p (0..1.0/0).find{ |i| fibs[i] > limit } + 1
p (Time.now - t1) * 1e3

Squeak Smalltalk

| limit a b time fibs size |
limit := 1e999.
a := b := 1.
time := [
   fibs := Array streamContents: [:ss |
      ss nextPut: 1. [(ss nextPut: (b := a flag: (a := a + b))) > limit] whileFalse].
   size := fibs size.
] timeToRun.
^{size. time}   "=> #(4782 13) "
上の Ruby版と同じ方針（特異メソッドを活用）で
| limit fibs size |
limit := 1e999.
fibs := OrderedCollection instanceOfUniqueClass addAll: #(1 1); yourself.
fibs class compile: 'at: n
   ^n <= self size ifTrue: [super at: n] ifFalse: [
      self at: n ifAbsentPut: [(self at: n-2) + (self at: n-1)]]'.
^{[size := (1 to: Float infinity) detect: [:n | (fibs at: n) > limit]] timeToRun. size}   "=> #(27 4782) "