程序師世界是廣大編程愛好者互助、分享、學習的平台,程序師世界有你更精彩!
首頁
編程語言
C語言|JAVA編程
Python編程
網頁編程
ASP編程|PHP編程
JSP編程
數據庫知識
MYSQL數據庫|SqlServer數據庫
Oracle數據庫|DB2數據庫
 程式師世界 >> 編程語言 >> C語言 >> VC >> 關於VC++ >> 可用於數論計算的無符號大整數類

可用於數論計算的無符號大整數類

編輯:關於VC++

前些日子,無意中訪問到三思科學網,裡面介紹了許多數論問題,這也是我兒時的愛好,於是就利用空閒時間編寫了一個用於數論計算的無符號大整數類。

一、類的基本結構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環境下調試運行正確。

本文配套源碼

  1. 上一頁:
  2. 下一頁:
欄目導航
Copyright © 程式師世界 All Rights Reserved