普通にFibonacci Matrixから導かれるNを1/2にしていく漸化式で
ループをN回からlog2(N)回にするコードを書いてみたら
1000万個目のフィボナッチ数もすぐに求まったよ
ただしそれを10進数表示する方は何分もかかった