段學松,曲中水,江緒楨,呂昌昊
(哈爾濱理工大學 計算機科學與技術(shù)學院,黑龍江 哈爾濱 150080)
快速冪算法,即快速計算一個數(shù)或者矩陣的冪次的算法,一直是加密算法中的重要算法,并且在數(shù)論中有著相當廣泛的應(yīng)用,更是算法競賽中最常遇到的問題,尤其在線性齊次遞推數(shù)列[1]的求解上。例如常見的斐波那契數(shù)列[1]第n 項的計算,通過構(gòu)造轉(zhuǎn)移矩陣[1]和快速計算矩陣冪次[1]的方式能夠大大降低計算線性齊次遞推數(shù)列的時間復雜度。但是隨著矩陣的行數(shù)和列數(shù)不斷增加,每一次矩陣乘法會變得相當耗時,對于稀疏矩陣,雖然存在優(yōu)化算法[2],甚至存在優(yōu)化算法的硬件實現(xiàn)[3],但是如何減少矩陣乘法計算的次數(shù)變得極其重要。目前計算快速冪,最常用的算法是二進制拆分法[4],但是對于一個固定的數(shù)或者是固定矩陣的冪次來說,二進制拆分法并沒有保留每次拆分的過程,導致拆分的過程會做大量的重復計算。因此對于固定的數(shù)或者固定矩陣的冪次,可以預處理部分數(shù)據(jù),達到減少重復運算,降低算法時間復雜度的目的。
計算an,傳統(tǒng)的快速冪算法的核心思想是二進制拆分。令m 為n 在二進制下最高位1 的位置,我們對n 進行二進制拆分,則有:
通過乘法原理,可以得到:
綜上,可以得到:
其中,ei是n 在二進制下第i 位的值,例如當n=13的時候,n 的二進制形式為:(1101)2,最高位 1 的位置 m=4,對n 進行二進制拆分得到的結(jié)果為:
T(n)=O(log2n)
由于二進制拆分快速冪算法用迭代實現(xiàn),在計算的過程中用于存儲計算用到的空間是常數(shù)級別的,因此二進制拆分快速冪算法的空間復雜度為:
S(n)=O(1)
如果計算k 次,總時間復雜度為:
T(n)=O(klog2n)
金壇區(qū)于2016年啟動長蕩湖清淤工程,在外源污染有效治理和控制的前提下,通過對長蕩湖湖區(qū)污染底泥實施生態(tài)清淤,有效削減底泥內(nèi)源污染,促進湖泊水體水質(zhì)改善,為長蕩湖水生態(tài)修復奠定基礎(chǔ)。
總空間復雜度為:
S(n)=O(1)
圖1 二進制拆分法的C++實現(xiàn)
當利用二進制拆分快速冪算法多次計算相同底數(shù)的冪次時,存在大量的冗余計算。例如:
首先我們用a mod b 表示a 對b 取余數(shù)。
證明 由取余運算的性質(zhì)[5]可得,定理1 成例。
證畢。
根據(jù)定理2 以及乘法原理可得:
由于 u∈[0,P],v∈(0,P),因此可以在計算快速冪前預處理出 a0,a1,a2…aP-1,aP以及(aP)0,(aP)1,(aP)2…(aP)P-1,(aP)P并存儲起來,每次計算an時,首先計算出以及v=n mod P,之后從提前預處理的數(shù)據(jù)中選擇(aP)u和av進行一次乘法運算即可得到an的結(jié)果。
3.2.1 預處理過程時間與空間復雜度分析
因為通過預處理能夠得到aP,因此,預處理(aP)0,(aP)1,(aP)2…(aP)P-1,(aP)P的時間復雜度:
所以,預處理的總時間復雜度:
3.2.2 計算快速冪的時間與空間復雜度分析
在計算快速冪的過程中,由于P,u,v 的計算消耗是常數(shù)級別的,而計算查表計算一次乘法的時間復雜度也是常數(shù)級別的,因此計算快速冪的時間復雜度:
T(n)=O(1)
計算過程中臨時變量的存儲空間都是常數(shù)級別的,因此計算快速冪的空間復雜度為:
S(n)=O(1)
3.2.3 計算k 次相同底數(shù)的an的總體時間空間復雜度分析
預處理的目的是去除重復運算,對于相同的底數(shù),多次計算快速冪只用進行一次預處理操作,k 次計算快速冪的總體時間復雜度是:
總體空間復雜度為:
圖2 基于預處理的快速冪算法的C++實現(xiàn)
本文分析了二進制拆分快速冪算法的缺點,并針對相同底數(shù)的多次快速冪運算,提出了一種基于預處理的快速冪算法,通過預處理少量的數(shù)據(jù),將時間復雜度為O(klog2n)求冪的算法優(yōu)化至并給出了該算法的時間復雜度與空間復雜度的分析以及C++編程實現(xiàn),為求解快速冪提供了新的思路。今后,隨著程序設(shè)計應(yīng)用的不斷深入以及人們對算法的研究,更多更復雜的數(shù)學問題必定會迎刃而解。