fib_challenge.py 480 B

1234567891011121314151617181920212223
  1. #!/usr/bin/env python3
  2. def fib(n):
  3. if n >= 0:
  4. return fibiter(1, 0, 0, 1, n)
  5. if n < 0:
  6. a, b = 0, 1
  7. for _ in range(0, n, -1):
  8. a, b = b - a, a
  9. return a
  10. def fibiter(a, b, p, q, count):
  11. if count == 0:
  12. return b
  13. if count % 2 == 0:
  14. return fibiter(a, b, p * p + q * q, q * q + 2 * p * q, count / 2)
  15. else:
  16. return fibiter(b * q + a * q + a * p, b * p + a * q, p, q, count - 1)
  17. print(fib(1000000))