(n: int)
| 18 | |
| 19 | # returns (F(n), F(n-1)) |
| 20 | def _fib(n: int): # noqa: E999 This syntax is Python 3 only |
| 21 | if n == 0: |
| 22 | # (F(0), F(1)) |
| 23 | return (0, 1) |
| 24 | else: |
| 25 | # F(2n) = F(n)[2F(n+1) − F(n)] |
| 26 | # F(2n+1) = F(n+1)^2+F(n)^2 |
| 27 | a, b = _fib(n // 2) |
| 28 | c = a * (b * 2 - a) |
| 29 | d = a * a + b * b |
| 30 | if n % 2 == 0: |
| 31 | return (c, d) |
| 32 | else: |
| 33 | return (d, c + d) |
| 34 | |
| 35 | |
| 36 | if __name__ == "__main__": |