DouKaku?

require "mathn"

class Fib
  def initialize
    @fib_a=[1,1]
  end
  def [](n)
    (@fib_a.size..n).each{|i| @fib_a<<=@fib_a[i-2]+@fib_a[i-1]}  
    @fib_a[n-1]
  end
end

def gcd(n,m)
  c=0
  until(n==m)
    n,m=m,n if n<m
    return [1,c] if m==1
    m1=m
    while(m1<n)
      m1<<=1
      c+=1       
    end
    m1>>=1
    n-=m1
    c+=1
  end
  [n,c]
end

fib=Fib.new
p gcd(fib[2000],fib[1999])