DH算法源程序

1、DH算法的C語言實現(xiàn)1. class SuperNumber 2. public:3.     SuperNumber() 4.         memset(data, 0, MAX_SIZE);5.         high = 0;6.     7.   

2、0; / 一般整型到SuperNumber的轉(zhuǎn)換，該版本中不支持負數(shù)8.     SuperNumber(unsigned long l) 9.         memset(data, 0, MAX_SIZE);10.         high = 0;11.     

3、;    while(l) 12.             data+high = l % 10;13.             l /= 10;14.         

4、15.     16.     / str為字符串形式表示的十進制數(shù)17.     SuperNumber(const char* str) 18.         assert(str != NULL);19.         high =

5、0;strlen(str);20.         for(int i = high, j = 0; i >= 1; i-, j+) 21.             datai = strj - '0'22. 

6、0;       23.     24.     SuperNumber(const SuperNumber& s) 25.         memcpy(data, s.data, MAX_SIZE);26.         hi

7、gh = s.high;27.     28.     operator const char*() const 29.         return toString(10);30.     31.     SuperNumber& operator=(const

8、60;SuperNumber& s) 32.         if(this != &s) 33.             memcpy(data, s.data, MAX_SIZE);34.           

9、  high = s.high;35.         36.         return *this;37.     38.39.     / 將數(shù)據(jù)置為040.     void reset() 41.   

10、60;     memset(data, 0, MAX_SIZE);42.         high = 0;43.     44.45.     / str為字符串形式表示的十進制數(shù)46.     void setToStr(const char* str) 

11、;47.         assert(str != NULL);48.         high = strlen(str);49.         for(int i = high, j = 0; i >= 1;

12、0;i-, j+) 50.             datai = strj - '0'51.         52.     53.     / 將數(shù)據(jù)轉(zhuǎn)換成以base指定的進制的字符串形式，默認為十進制54.  

13、0;  const char* toString(int base = 10) const 55.         static char bufMAX_SIZE;56.         const char table = "0123456789ABCDEFGHIJKLMNOP

14、QRSTUVWXYZ"57.58.         if(high = 0) return "0"59.60.         assert(base >= 2);      / 指定的進制應該不小于261.62.      

15、;   / 進制轉(zhuǎn)換63.         bufMAX_SIZE-1 = '/0'64.         int begin = MAX_SIZE-1;65.         char tempMAX_SIZE;66.   

16、;      memcpy(temp, data, MAX_SIZE);67.         while(1) 68.             / 找最高位的起始位置69.           &#

17、160; int h = high;70.             while(temph = 0 && h >= 1) h-;71.             if(h = 0) break;72.

18、73.             / 除基取余74.             int t = 0;75.             while(h >= 1) 76.

19、                t = t * 10 + temph;77.                 temph = t / base;78.   &#

20、160;             t = t % base;79.                 h-;80.             81. &#

21、160;           buf-begin = tablet;82.         83.84.         return buf+begin;85.     86.87.     / 乘法88.

22、    SuperNumber operator*(const SuperNumber& s) const 89.         SuperNumber result;     / default set to 090.         i

23、nt i, j;91.         92.         / 相乘93.         for(i = 1; i <= high; i+) 94.         &

24、#160;   for(j = 1; j <= s.high; j+) 95.                 int k = datai * s.dataj + result.datai+j-1;96.      

25、;           result.datai+j-1 = k % 10;97.                 result.datai+j += k / 10;98.       &#

26、160;     99.         100.         / 進位101.         for(i = 1; i < MAX_SIZE - 1; i+) 102.   &

27、#160;         if(result.datai >= 10) 103.                 result.datai+1 += result.datai / 10;104.       &#

28、160;         result.datai %= 10;105.             106.         107.         / 確定最高位108.   &

29、#160;     for(i = MAX_SIZE-1; i >= 1 && result.datai = 0; i-);109.         result.high = i;110.111.         return resu

30、lt;112.     113.114.     / 除法，內(nèi)部調(diào)用doDivide來實現(xiàn)115.     SuperNumber operator/(const SuperNumber& s) const 116.         SuperNumber q, r;117.    

31、;     doDivide(s, q, r);118.         return q;119.     120.     / 模運算，內(nèi)部調(diào)用doDivide來實現(xiàn)121.     SuperNumber operator%(const SuperNumber& s

32、) const 122.         SuperNumber q, r;123.         doDivide(s, q, r);124.         return r;125.     126.127.   

33、0; / 除法運算，一次除法運算中同時得到商和余數(shù)，運算符/和%的重載128.     / 內(nèi)部會調(diào)用這個函數(shù)，dest為除數(shù)，Q為商，R為余數(shù)，算法使用試除法129.     void doDivide(const SuperNumber& dest, SuperNumber& Q, SuperNumber& R) const 130.    

34、;     int i, j, t;131.132.         Q.reset();133.         Q.high = high - dest.high + 1; / 商的初始位數(shù)134.       &#

35、160; R = *this;                     / 余數(shù)初始實為被除數(shù)135.         t = dest.high;136.        

36、0;/ 判斷除法是否結(jié)束137.         while(R >= dest) 138.             / 循環(huán)相減進行試除139.             while(dest >= 

37、;R.sub(1, t) 140.                 Q.dataQ.high- = 0;141.                 +t;142.       

38、60;     143.             while(R.sub(1, t) >= dest) 144.                 / i為相減時被除數(shù)最低下標，j為除數(shù)最低下標145.  

39、               for(i=R.high-t+1,j=1; j<=dest.high; i+,j+) 146.                     R.datai -= des

40、t.dataj;147.                     if(R.datai < 0) 148.                      &#

41、160;  R.datai += 10;149.                         R.datai+1 -= 1;150.              

42、60;      151.                 152.                 while(R.datai < 0 && i 

43、<= R.high) 153.                     R.datai += 10;154.                     R.

44、datai+1 -= 1;155.                     +i;156.                 157.        &

45、#160;        Q.dataQ.high += 1;158.             159.             / 一次試除結(jié)束，更新商的最高位下標160.       &

46、#160;     Q.high -= 1;161.             / 更新被除數(shù)的最高位下標162.             while(R.dataR.high = 0) 163.     

47、60;           R.high-;164.                 t-;165.             166.       &

48、#160;     t+=1;               / 下一位被除數(shù)167.         168.169.         Q.high = high - dest.high&#

49、160;+ 1; 170.         while(Q.dataQ.high = 0) Q.high -= 1;171.         R.high = high;172.         while(R.dataR.high = 0)

50、0;R.high -= 1;173.     174.175.     / 大數(shù)模冪算法，很簡單的自然算法，即將指數(shù)分解為二進制，換句176.     / 更簡單的話來說，就是不斷地找平方模冪，而不是全部乘方后再177.     / 做一次最終的模運算178.     / a.power_mod(p, n)計算ap m

51、od n179.     SuperNumber power_mod(int power, SuperNumber n) const 180.         SuperNumber c("1"), t(*this);181.182.         while(power) 1

52、83.             if(power % 2) 184.                 c = c * t % n;185.        

53、60;        power -= 1;186.              else 187.                 t = t * t 

54、;% n;188.                 power /= 2;189.             190.         191.192.      

55、;   return c%n;193.     194.195.     bool operator>=(const SuperNumber& s) const 196.         if(high = s.high) 197.       

56、      int k = high;198.             while(datak = s.datak && k >= 1)k-;199.             if(k&#

57、160;< 1) return true; / equal200.             return datak > s.datak;201.          else if(high > s.high) return true;202

58、.         return false;        203.     204.205.     bool operator<(const SuperNumber& s) const 206.        

59、 return !(*this >= s);207.     208.209.     / 從十進制表示的最高位開始數(shù)起，數(shù)到第i位，從第i位開始截取連續(xù)210.     / 的c位數(shù)字出來組成一個新的數(shù)。例如：數(shù)據(jù)是，則211.     / sub(3, 5)返回數(shù)字34567，如果數(shù)字不夠取，例如在34567上運行212.   

60、  / sub(3, 5)，因為34567從高位數(shù)起第3個數(shù)字是5，剩下的數(shù)字是567，213.     / 最多只有三個，不夠取要求的5個，這個時候返回567，不報錯。214.     SuperNumber sub(int i, int c) const 215.         SuperNumber ret;2

61、16.         assert(high >= i);   / 保證可截取217.218.         i = high - i + 1;    / 從高位數(shù)起的第i個數(shù)位的下標219.      

62、60;  if(i >= c) 220.             ret.high = c;221.             while(c >= 1) ret.datac- = datai-;222.   

63、       else 223.             ret.high = i;224.             while(i >= 1) 225.      

64、0;          ret.datai = datai;226.                 i-;227.             228.     

65、     229.         / 過濾前導0230.         while(ret.dataret.high = 0) ret.high-;231.         return ret;232.     2

66、33.234.     / I/O235.     friend istream& operator>>(istream& in, SuperNumber& s) 236.         char t256;237.         in&#

67、160;>> t;238.         s.setToStr(t);239.         return in;240.     241.     friend ostream& operator<<(ostream& out, const S

68、uperNumber& s) 242.         return out << s.toString(10);243.     244. private:245.     enum MAX_SIZE=256;        / 最大十進制位數(shù)246.  &

69、#160;  / 須注意，使用data0存儲最高位所在下標是自己的一點小聰明，后來在247.     / 調(diào)試的時候發(fā)現(xiàn)這是一個極大的錯誤，不過對于此題目來說可以應付248.     char dataMAX_SIZE;        / 數(shù)據(jù)的內(nèi)部表示，字符串形式的十進制249.         

70、                        / 其中data0存儲最高位所在下標，data1250.                     &#

71、160;           / 存儲數(shù)據(jù)的最低位，也就是個位251.     int high;252. ;主函數(shù)：1. int main(int argc, char *argv) 2.     freopen("in.txt", "r", stdin);3.4.     SuperNumberTest st;5.6. /    st.run();7.8.     / g和n都是超過2127的素數(shù)。它們在DH算法中公開9.     SuperNumber g,