Fibonacci数列高效解法大全及时间复杂度分析　连载【6】

在数学上，斐波那契数列是以递归的方法来定义

……续上回Fibonacci数列高效解法大全及时间复杂度分析　连载【5】

在GMP库里就有斐波那契数和数列的单独函数

11.? GMP内置fib函数解法

这直接引用即可以了

import gmpy2

def Fibonacci_sequence_09 (n: int) -> int:? #参数n是表示求第n项Fibonacci数

? ? ‘返回单项的GMP内置fib函数解法’

? ? assert isinstance(n, int), ‘n is an error of non-integer type.’

? ? if n>=0:

? ? ? ? return gmpy2.fib(n)

? ? else:

? ? ? ? return None

Fibonacci_sequence_09(1000000)

看一下耗时多少，同上例

Total time: 0.004522秒

算第100万项Fibonacci数用时只有二分递归解法的65.6%。果然更快速少量

GMP和Mathematica内置算Fibonacci数的函数都是用的同一种快速算法

是一种叫二进制模幂算法，让我们来看看是什么样

https://gmplib.org/manual/Fibonacci-Numbers-Algorithm.html#Fibonacci-Numbers-Algorithm

引自GMP官网上的资料，用的是这个递推式

把n分解为n的二进制表示形式，而后直接迭代递推。递推迭代是O(log n)，大整数乘方是O(n*log n))，那么整个算法时间复杂度也是O(n*(log n)^2)的

那为什么体现的比同样O(n*(log n)^2)的二分迭代解法更快呢

由于二进制模幂算法中每步只做两次大整数乘法，是目前算斐波那契数大整数乘法最少的算法。

12.? 二进制模幂解法

好，不用GMP那C写Fibonacci数库函数，用Python实现一遍这个二进制模幂解法（当然大数运算还是用到GMP）

我来写出来

import gmpy2

def Fibonacci_sequence_10 (n: int) -> int:? #参数n是表示求第n项Fibonacci数

? ? assert isinstance(n, int), ‘n is an error of non-integer type.’

? ? def Calculate_Fibonacci_sequence (n: int) -> int:

? ? ? ? ‘返回单项的二进制模幂解法’

? ? ? ? if n >= 1 :

? ? ? ? ? ? add_on = (2, -2)? #就是 2*(-1)^k 这项

? ? ? ? ? ? prev_num, current_num = gmpy2.mpz(1), gmpy2.mpz(1)? #设prev_num为F[1]，current_num为F[2]

? ? ? ? ? ? for i in range(gmpy2.bit_length(n) – 1, 0, -1):? #从最高位开始遍历除末位外的每个二进制位

? ? ? ? ? ? ? ? if gmpy2.bit_test(n, i):? #注意bit_test的i参数0就是第一位（二进制表示的最末尾一位）

? ? ? ? ? ? ? ? ? ? prev_num = current_num – prev_num? #prev_num = F[2k] = F[2k+1] – F[2k-1]，current_num就是等于F[2k+1]

? ? ? ? ? ? ? ? else:

? ? ? ? ? ? ? ? ? ? current_num = current_num – prev_num? #prev_num就是等于F[2k-1]，current_num = F[2k] = F[2k+1] – F[2k-1]

? ? ? ? ? ? ? ? sq_prev_num = prev_num ** 2; sq_current_num = current_num ** 2

? ? ? ? ? ? ? ? prev_num = sq_prev_num + sq_current_num? #F[2k-1] = F[k]^2 + F[k-1]^2

? ? ? ? ? ? ? ? current_num = sq_current_num * 4 – sq_prev_num + add_on[1 if gmpy2.bit_test(n, i) else 0]? #F[2k+1] = 4*F[k]^2 – F[k-1]^2 + 2*(-1)^k

? ? ? ? ? ? if n & 1 == 0:? #迭代完成，再对末位做个判断

? ? ? ? ? ? ? ? current_num = current_num – prev_num

? ? ? ? ? ? return current_num

? ? ? ? elif n == 0:

? ? ? ? ? ? return 0

? ? if n >=0:

? ? ? ? return Calculate_Fibonacci_sequence(n)

? ? else:

? ? ? ? return None

Fibonacci_sequence_10(1000000)

看耗时多少，同上例

Total time: 0.005285秒

只比纯C库实现的慢了不到1ms，Python还是不错的

未完待续……

Fibonacci数列高效解法大全及时间复杂度分析　连载【7】