Timeline for Python 3 - Fibonacci Implementation
Current License: CC BY-SA 3.0
6 events
| when toggle format | what | by | license | comment | |
|---|---|---|---|---|---|
| Dec 20, 2017 at 18:43 | comment | added | President James K. Polk | This question is related. The answer by Paul Hankin I found particularly illuminating. | |
| Dec 20, 2017 at 10:44 | comment | added | Eric Duminil | Those identities are awesome! It's the first time I see them. Thanks! | |
| Dec 20, 2017 at 1:26 | comment | added | user7802048 | Isn't it possible to do without matrix exponentiation, just using the identities above? | |
| Dec 20, 2017 at 1:24 | comment | added | vnp |
@user7802048 It is essentially a (matrix) exponentiation by squaring. Compute the path from 1 to n by either doubling, or incrementing by 1. In other words, a binary representation of n.
|
|
| Dec 20, 2017 at 1:22 | comment | added | user7802048 | How could an iterative implementation using the stated identities look like? I just wrote a recursive function using the identities. It was way faster than the previous recursive implementation, but still slower than the normal iterative implementation. | |
| Dec 20, 2017 at 0:53 | history | answered | vnp | CC BY-SA 3.0 |