……續(xù)上回Fibonacci數(shù)列高效解法大全及時(shí)間復(fù)雜度分析 連載【5】
在GMP庫(kù)里就有斐波那契數(shù)和數(shù)列的單獨(dú)函數(shù)
11.? GMP內(nèi)置fib函數(shù)解法
這直接引用就可以了
import gmpy2
def Fibonacci_sequence_09 (n: int) -> int:? #參數(shù)n是表示求第n項(xiàng)Fibonacci數(shù)
? ? '返回單項(xiàng)的GMP內(nèi)置fib函數(shù)解法'
? ? 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)
看一下耗時(shí)多少，同上例
Total time: 0.004522秒
算第100萬(wàn)項(xiàng)Fibonacci數(shù)用時(shí)只有二分遞歸解法的65.6%研叫。果然更快速一些
GMP和Mathematica內(nèi)置算Fibonacci數(shù)的函數(shù)都是用的同一種快速算法
是一種叫二進(jìn)制模冪算法，讓我們來(lái)看看是什么樣
引自GMP官網(wǎng)上的資料，用的是這個(gè)遞推式
把n分解為n的二進(jìn)制表示形式灸芳，然后直接迭代遞推益老。遞推迭代是O(log n)孩革，大整數(shù)乘方是O(n*log n))，如前篇里解釋惶翻，那么整個(gè)算法時(shí)間復(fù)雜度也是O(n*(log n))的
那為什么表現(xiàn)的比同樣O(n*(log n))的二分迭代解法更快呢
因?yàn)槎M(jìn)制模冪算法中每步只做兩次大整數(shù)乘法姑蓝，是目前算斐波那契數(shù)大整數(shù)乘法最少的算法鹅心。
12.? 二進(jìn)制模冪解法
好吕粗，不用GMP那C寫Fibonacci數(shù)庫(kù)函數(shù)，用Python實(shí)現(xiàn)一遍這個(gè)二進(jìn)制模冪解法（當(dāng)然大數(shù)運(yùn)算還是用到GMP）
我來(lái)寫出來(lái)
import gmpy2
def Fibonacci_sequence_10 (n: int) -> int:? #參數(shù)n是表示求第n項(xiàng)Fibonacci數(shù)
? ? assert isinstance(n, int), 'n is an error of non-integer type.'
? ? def Calculate_Fibonacci_sequence (n: int) -> int:
? ? ? ? '返回單項(xiàng)的二進(jìn)制模冪解法'
? ? ? ? if n >= 1 :
? ? ? ? ? ? add_on = (2, -2)? #就是 2*(-1)^k 這項(xiàng)
? ? ? ? ? ? prev_num, current_num = gmpy2.mpz(1), gmpy2.mpz(1)? #設(shè)prev_num為F[1]旭愧，current_num為F[2]
? ? ? ? ? ? for i in range(gmpy2.bit_length(n) - 1, 0, -1):? #從最高位開始遍歷除末位外的每個(gè)二進(jìn)制位
? ? ? ? ? ? ? ? if gmpy2.bit_test(n, i):? #注意bit_test的i參數(shù)0就是第一位（二進(jìn)制表示的最末尾一位）
? ? ? ? ? ? ? ? ? ? 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:? #迭代完成输枯，再對(duì)末位做個(gè)判斷
? ? ? ? ? ? ? ? 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)
看耗時(shí)多少议泵，同上例
Total time: 0.005285秒
只比純C庫(kù)實(shí)現(xiàn)的慢了不到1ms，Python還是不錯(cuò)的
未完待續(xù)……
