フィボナッチ数列の下20桁を高速に求めるには？

大きな自然数nに対しても、
フィボナッチ数列f(n)の下20桁を高速に求める
にはどうすればよろしいでしょうか？

なお、私は以下のように
f(n)を高速に求め（※）、mod をとりました。

# (a + b√x)^nの計算
def power(a, b, x, n)
  return [1, 0] if n == 0
  c, d = power(a, b, x, n >> 1)
  c, d =
  c * c + x * d * d,
  2 * c * d
  return [c, d] if n & 1 == 0
  c, d =
  a * c + x * b * d,
  a * d + b * c
  return [c, d]
end

# (1 + √5)^n = an + bn√5とすると、f(n) = bn / 2^(n - 1)
def f(n)
  power(1, 1, 5, n)[1] >> n - 1
end

Mod = 10 ** 20
(0..8).each{|i| p f(9 ** i) % Mod}

実行結果
1
34
37889062373143906
77515304438631163554
85142957433431151586
55029990705407376674
70162980353113645666
33971075843592127394
27265106508993618146

※次のように「f(n)を行列の累乗計算を使って求める方法」があるが、
上記の方が少し速い。

require 'matrix'

def f(n)
  v = Vector[1, 0]
  a = Matrix[[1, 1], [1, 0]]
  ((a ** n) * v)[1]
end

Mod = 10 ** 20
(0..8).each{|i| p f(9 ** i) % Mod}