#斐波那契数列的计算公式(不用递归)
This code, somewhat surprisingly, generates Fibonacci numbers.
def fib(n):
return (4 << n*(3+n)) // ((4 << 2*n) - (2 << n) - 1) & ((2 << n) - 1)
In this blog post, I'll explain where it comes from and how it works.
Before getting to explaining, I'll give a whirlwind background overview of Fibonacci numbers and how to compute them. If you're already a maths whiz, you can skip most of the introduction, quickly skim the section "Generating functions" and then read "An integer formula".
#Overview
The Fibonacci numbers are a well-known sequence of numbers:
1,1,2,3,5,8,13,21,34,55,…1,1,2,3,5,8,13,21,34,55,…
The nnth number in the sequence is defined to be the sum of the previous two, or formally by this recurrence relation:
Fib(0)Fib(1)Fib(n)===11Fib(n−1)+Fib(n−2)Fib(0)=1Fib(1)=1Fib(n)=Fib(n−1)+Fib(n−2)
I've chosen to start the sequence at index 0 rather than the more usual 1.