Fibonacci is defined as following.

The following eqution can be proved.

(Prove by induction)

- When

- Suppose it satisfy for
, then for

To compute

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

```
$ 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
```