Fibonacci O(log n) solution

Fibonacci is defined as following.

The following eqution can be proved.

(Prove by induction)

1. When

2. Suppose it satisfy for , then for

To compute , we can just compute . This can be done in since

A Golang version code can be found in my GitHub. In my test, this solution is way more fast than the version.

$ go test -bench '^BenchmarkFibonacci(2|3)$'
goos: darwin
goarch: arm64
pkg: fibonacci
BenchmarkFibonacci2-8           382967418                4.912 ns/op
BenchmarkFibonacci3-8           1000000000               0.0000004 ns/op
PASS
ok      fibonacci       2.892s