前些日子,無意中訪問到三思科學網,裡面介紹了許多數論問題,這也是我兒時的愛好,於是就利用空閒時間編寫了一個用於數論計算的無符號大整數類。
一、類的基本結構Class CUSuperInt
{
public:
//構造及析構函數
CUSuperInt();
CUSuperInt(DWORD dwValue);
CUSuperInt(char* pszVal);
CUSuperInt(CUSuperInt& x);
virtual ~CUSuperInt();
protected:
DWORD *pValue; //指向一個DWORD數組,用於存放數值
DWORD len; //DWORD數組的長度
DWORD last; //數組中的有效長度
};
類名為CUSuperInt,第二個字母表示無符號的意思。當然只要你通過增加一個表示符號的成員,再經簡單擴充即可變成有符號大整數類。
pValue指向的DWORD數組采用動態分配策略,當數組長度不夠時,采用成倍分配的策略,即長度變為2*len。(這也許不是一個最好的分配方案,但可以簡化設計)
last成員指示數組中數據的有效長度,這樣可以減少一些不必要的運算量。last成員最小值為1,當last=1時實際就已蛻變為了一個DWORD了。
二、構造函數
類定義了四個構造函數,其中有一個構造函數的參數是一個字符串指針,它表示將一個字符串轉換為一個CUSuperInt類。這樣的字符串可以是十進制或十六進制的字符串,表示方式跟C語言的規范差不多,如"12345678901","0x123456789abcdef",前者表示十進制數,後者表示十六進制數。同時為了在應用中方便,也允許數字字符串中間用空格來分節,如"12345 567890"、"0x123 4567 89ab cdef"等。
三、重載運算符
重載了賦值運算符,可以將DWORD,字符串,以及CUSuperInt賦值給一個CUSuperInt對象。
重載了加減乘除等四則運算,以及++,――運算符。不過注意對於/=運算返回值為余數,商在左操作數中。而對於/運算返回商,余數丟失。
重載了%運算符,可以計算模。
重載了比較運算符,可以進行比較運算,返回一個bool值。
定義了一個Dobule()成員用於乘以2的n次方,有用邏輯左移算法。
定義了一個Half()成員用於除以2的n次,采用邏輯右移算法,所以這個函數將丟失余數。
四、數據的輸出
定義了ToDecStr()和ToHexStr()兩個成員分別用於將其轉換為十進制和十六進制字符串輸出。
五、處理0除和越界異常
自定義了一個CMyException異常類。
越界是指由於機器字長的影響,使得內存(包括虛擬內存)的大小有限,自定義了一個上界,當數據越過時拋出一個越界異常。
事實上一個win32程序可用的內存空間名義上有4G,實際除了操作系統和一些額外開銷,不足2G,一個DWORD占4字節,所以最大長度為2G/4= 0x20000000;加上要運算,肯定有多個數,考慮MaxLen為0x1000000比較合適,這時能表示的數表示成十進制數能超過1.6億位,已經非常大了。這個長度計算公式是MaxLen * 32位 * log(2) / log(10) + 1;
六、使用
如同整數一樣可以進行加減乘除四則運算和比較。如果你處理的數很大時,一般建議你在程序中要處理異常。例子代碼見源程序。另外建議將你的程序優先級設置得低些,因為數值運算是非常耗CPU資源的。
七、優化
優化要從算法和代碼上進行。在代碼上,核心代碼盡量用內聯匯編代碼編寫,以提高速度。對於一些經常使用的函數,可以考慮采用VC和匯編混合編寫的方法,程序中使用了這樣一個例子,即對meccpy函數用匯編編寫。(系統提供的這個函數因為要考慮按DWORD對齊的問題,使得代碼長了一些。但本程序中不用考慮這個問題,所以重新編寫。當然也可使用內聯匯編的方式,但從編譯得到的匯編代碼看,在函數體內開始幾句語句有點多余。所以用純匯編編寫更加簡單)
在算法上,由於作者水平有限,參考書籍也有限,不能找到最好的算法。下面簡單介紹一下除法
和ToDecStr()采用的算法。
除法采用二進制除法:
它是這樣進行的(設被除數為a,除數為x,商為r):
1、首先計算r的長度並擴展,令r.last為計算得到的長度,還要將r.pValue指向的DWORD數組清0。
2、建立一個減數數組XX[32], 其值依次為x,,2*x,,4*x,8*x,……
3、如果a<x,則結果已得到,進行下面第10步
4、根據a和x的長度,計算出r的最高可能商十進制1的位數。然後判斷該位能否商1
5、如果不能商1,則r的下一位肯定能商1。
6、根據商1的位數,得到應相減的減數數組號nXX
7、a的高n個DWORD減XX[nXX],(其中n為XX[nXX]的有效長度)。
8、r的相應位置1
9、跳到上面的第3步
10、返回結果。
ToDecStr()的算法分析:
基本算法是將數除以10,得到的余數為最低位。這樣反復進行,直到結束,就可計算結果。
但對於一個長度很長的CUSuperInt對象,除法是非常耗時間的,為了盡量減少除法的次數,將除數設為1000000000(這根據一個DWORD能表示的最大十進制數為429467295,其位數有10位而定的),這樣每除一次,得到的余數是一個不大於9位十進制位的數,然後將其轉換成十進制字符串,作為低9位。
八、問題
各種運算的正確性,尚需在使用過程中得到進一步的驗證。因為數大了,我們不大可能用手工或計算器來驗證,所以只能從算法上保證運算的正確性。
進一步的優化,如對兩個CUSuperInt相乘,可以全部用內聯匯編編寫。
由於代碼中使用了大量的匯編,而在代碼中未涉及段寄存器,適用的程序只能是Win32程序。(作者水平有限,不知做出這樣的判斷是否正確,請讀者指正)。
本代碼在VC6.0+WinMe以及WinXP環境下調試運行正確。
本文配套源碼