FilesExpand file tree

 master

/

fast_fibonacci.py

Copy path

Blame

More file actions

Blame

More file actions

Latest commit

 

History

History

History

44 lines (37 loc) · 1.05 KB

 master

/

fast_fibonacci.py

Copy path

Top

File metadata and controls

• Code
• Blame

44 lines (37 loc) · 1.05 KB

Raw

Copy raw file

Download raw file

Open symbols panel

Edit and raw actions

1

2

3

4

5

6

7

8

9

10

11

12

13

14

15

16

17

18

19

20

21

22

23

24

25

26

27

28

29

30

31

32

33

34

35

36

37

38

39

40

41

42

43

44

#!/usr/bin/python

"""

This program calculates the nth Fibonacci number in O(log(n)).

It's possible to calculate F(1000000) in less than a second.

"""

import sys

# returns F(n)

def fibonacci(n: int): # noqa: E999 This syntax is Python 3 only

if n < 0:

raise ValueError("Negative arguments are not supported")

return _fib(n)[0]

# returns (F(n), F(n-1))

def _fib(n: int): # noqa: E999 This syntax is Python 3 only

if n == 0:

# (F(0), F(1))

return (0, 1)

else:

# F(2n) = F(n)[2F(n+1) − F(n)]

# F(2n+1) = F(n+1)^2+F(n)^2

a, b = _fib(n // 2)

c = a * (b * 2 - a)

d = a * a + b * b

if n % 2 == 0:

return (c, d)

else:

return (d, c + d)

if __name__ == "__main__":

args = sys.argv[1:]

if len(args) != 1:

print("Too few or too much parameters given.")

exit(1)

try:

n = int(args[0])

except ValueError:

print("Could not convert data to an integer.")

exit(1)

print("F(%d) = %d" % (n, fibonacci(n)))