Chinaunix

标题: 一个十进制大数运算类，支持加减乘除模、n次乘方、n次开方等运算 [打印本页]

---

作者: yuxh    时间: 2006-08-18 13:08
标题: 一个十进制大数运算类，支持加减乘除模、n次乘方、n次开方等运算
花了点时间写了这么个东西，目前只支持正整数的运算。
还有很多重要的功能，如素性的检测等还没有完成。
增加了负数 --20060823

decnum.h

1. #include <stdio.h>
   
2. #include <math.h>
   
3. #include <iostream>
   
4. 
   
5. using namespace std;
   
6. 
   
7. class decnum
   
8. {
   
9.     friend decnum pow(const decnum& x, int n);
   
10.     friend decnum root(const decnum& x, int n);
    
11.     friend decnum div(const decnum& x, const decnum& y, decnum& r);
    
12.     friend decnum abs(const decnum& x);
    
13.     friend bool operator==(const decnum& x, const decnum&y);
    
14.     friend bool operator!=(const decnum& x, const decnum&y);
    
15.     friend bool operator>(const decnum& x, const decnum&y);
    
16.     friend bool operator<(const decnum& x, const decnum&y);
    
17.     friend bool operator>=(const decnum& x, const decnum&y);
    
18.     friend bool operator<=(const decnum& x, const decnum&y);
    
19.     friend ostream& operator<<(ostream&os, const decnum& x);
    
20. 
    
21. public:
    
22.     decnum() : cap(0), num(0), sign(0), val(NULL) { }
    
23.     decnum(const char *v, int n)
    
24.     {
    
25.         int i, j;
    
26.         val = new char[n];
    
27.         if(v[0] == '-') {
    
28.             sign = 1;
    
29.             v++;
    
30.             n--;
    
31.         }
    
32.         else {
    
33.             sign = 0;
    
34.             if(v[0] == '+')
    
35.                 v++;
    
36.         }
    
37.         for(i = 0; i < n && v[i] == '0'; i++);
    
38.         for(j=0; i<n; i++, j++)
    
39.             if(v[n-1-i] >= '0' && v[n-1-i] <= '9')
    
40.                 val[j] = v[n-1-i] - '0';
    
41.             else
    
42.                 break;
    
43.         num = j;
    
44.         cap = n;
    
45.     }
    
46.     decnum(const decnum& x)
    
47.     {
    
48.         val = new char[x.num];
    
49.         memcpy(val, x.val, x.num);
    
50.         sign = x.sign;
    
51.         num = x.num;
    
52.         cap = x.num;
    
53.     }
    
54.     decnum(int x)
    
55.     {
    
56.         if(x==0) {
    
57.             cap = num = 0;
    
58.             val = NULL;
    
59.             return;
    
60.         }
    
61.         if(x < 0) {
    
62.             sign = 1;
    
63.             x = -x;
    
64.         }
    
65.         else
    
66.             sign = 0;
    
67.         char temp[20];
    
68.         sprintf(temp, "%d", x);
    
69.         int n = strlen(temp);
    
70.         num = cap = n;
    
71.         val = new char[n];
    
72.         for(int i=0; i<n; i++)
    
73.             val[i] = temp[n-1-i] - '0';
    
74.     }
    
75.     decnum(long long x)
    
76.     {
    
77.         if(x==0) {
    
78.             cap = num = 0;
    
79.             val = NULL;
    
80.             return;
    
81.         }
    
82.         if(x < 0) {
    
83.             sign = 1;
    
84.             x = -x;
    
85.         }
    
86.         else
    
87.             sign = 0;
    
88.         char temp[20];
    
89.         sprintf(temp, "%lld", x);
    
90.         int n = strlen(temp);
    
91.         num = cap = n;
    
92.         val = new char[n];
    
93.         for(int i=0; i<n; i++)
    
94.             val[i] = temp[n-1-i] - '0';
    
95.     }
    
96.     ~decnum() { delete[] val; }
    
97. 
    
98.     int size() const { return num; }
    
99. 
    
100.     decnum&
     
101.     operator=(const decnum& x)
     
102.     {
     
103.         if (this != &x) {
     
104.             if(cap < x.num) {
     
105.                 delete[] val;
     
106.                 val = new char[x.num];
     
107.                 cap = x.num;
     
108.             }
     
109.             memcpy(val, x.val, x.num);
     
110.             num = x.num;
     
111.             sign = x.sign;
     
112.         }
     
113.         return *this;
     
114.     }
     
115.     decnum&
     
116.     operator=(int x)
     
117.     {
     
118.         *this = decnum(x);
     
119.         return *this;
     
120.     }
     
121.     decnum&
     
122.     operator=(long long x)
     
123.     {
     
124.         *this = decnum(x);
     
125.         return *this;
     
126.     }
     
127. 
     
128.     decnum& abs()
     
129.     {
     
130.         sign = 0;
     
131.         return *this;
     
132.     }
     
133.     decnum& operator+=(const decnum& x);
     
134.     decnum& operator-=(const decnum& x);
     
135.     decnum& operator*=(const decnum& x);
     
136.     decnum& operator/=(const decnum& x);
     
137.     decnum& operator%=(const decnum& x);
     
138.     decnum  operator+(const decnum& x) const;
     
139.     decnum  operator-(const decnum& x) const;
     
140.     decnum  operator*(const decnum& x) const;
     
141.     decnum  operator/(const decnum& x) const;
     
142.     decnum  operator%(const decnum& x) const;
     
143. 
     
144.     bool ispow(int n, decnum& r) const;
     
145.     bool ispow() const;
     
146. private:
     
147.     int  cap;
     
148.     int  num;
     
149.     int  sign;
     
150.     char *val;
     
151. private:
     
152.     char root_1(int n);
     
153.     decnum& absadd(const decnum& x);
     
154.     decnum& abssub(const decnum& x);
     
155.     bool absge(const decnum& x);
     
156. };
     
157. 
     

复制代码

decnum.cpp

1. 
   
2. #include "decnum.h"
   
3. 
   
4. decnum&
   
5. decnum::absadd(const decnum& x)
   
6. {
   
7.     int i, max;
   
8.     char carry = 0, ch;
   
9. 
   
10.     if(x.num == 0) return *this;
    
11.     if(num < x.num)
    
12.         max = x.num + 1;
    
13.     else
    
14.         max = num + 1;
    
15.     if(max > cap)
    
16.     {
    
17.         cap = max;
    
18.         char *newval = new char[cap];
    
19.         memcpy(newval, val, num);
    
20.         memset(newval+num, 0, cap - num);
    
21.         delete[] val;
    
22.         val = newval;
    
23.     }
    
24.     else
    
25.     {
    
26.         memset(val+num, 0, max - num);
    
27.     }
    
28.     num = max-1;
    
29.     for(i=0; i<x.num; i++) {
    
30.         ch = val[i] + x.val[i] + carry;
    
31.         if(ch > 9) {
    
32.             carry = 1;
    
33.             val[i] = ch - 10;
    
34.         }
    
35.         else {
    
36.             carry = 0;
    
37.             val[i] = ch;
    
38.         }
    
39.     }
    
40.     for(; i<=num && carry == 1; i++) {
    
41.         ch = val[i] + 1;
    
42.         if(ch > 9) {
    
43.             carry = 1;
    
44.             val[i] = ch - 10;
    
45.         }
    
46.         else {
    
47.             carry = 0;
    
48.             val[i] = ch;
    
49.         }
    
50.     }
    
51.     if(i>num) num = i;
    
52.     return *this;
    
53. }
    
54. 
    
55. decnum&
    
56. decnum::abssub(const decnum& x)
    
57. {
    
58.     if(x.num == 0) return *this;
    
59.     int i;
    
60.     char carry = 0, ch;
    
61.     for(i=0; i<x.num; i++) {
    
62.         ch = val[i] - x.val[i] - carry;
    
63.         if(ch < 0) {
    
64.             carry = 1;
    
65.             val[i] = ch + 10;
    
66.         }
    
67.         else {
    
68.             carry = 0;
    
69.             val[i] = ch;
    
70.         }
    
71.     }
    
72.     for(; i<num && carry == 1; i++) {
    
73.         ch = val[i] - 1;
    
74.         if(ch < 0) {
    
75.             carry = 1;
    
76.             val[i] = ch + 10;
    
77.         }
    
78.         else {
    
79.             carry = 0;
    
80.             val[i] = ch;
    
81.         }
    
82.     }
    
83.     for(i=num; i>0 && val[i-1] == 0; i--);
    
84.     num = i;
    
85.     return *this;
    
86. }
    
87. 
    
88. bool
    
89. decnum::absge(const decnum& x)
    
90. {
    
91.     if(num > x.num) return true;
    
92.     if(num < x.num) return false;
    
93.     for(int i=num-1; i >= 0; i--)
    
94.         if(val[i] > x.val[i])
    
95.             return true;
    
96.         else if(val[i] < x.val[i])
    
97.             return false;
    
98.     return true;
    
99. }
    
100. 
     
101. decnum&
     
102. decnum::operator+=(const decnum& x)
     
103. {
     
104.     if(x.sign == sign)
     
105.         return absadd(x);
     
106.     else if(absge(x))
     
107.         return abssub(x);
     
108.     else {
     
109.         decnum tmp(*this);
     
110.         *this = x;
     
111.         return abssub(tmp);
     
112.     }
     
113. }
     
114. 
     
115. decnum&
     
116. decnum::operator-=(const decnum& x)
     
117. {
     
118.     if(x.sign != sign)
     
119.         return absadd(x);
     
120.     else if(absge(x))
     
121.         return abssub(x);
     
122.     else {
     
123.         decnum tmp(*this);
     
124.         *this = x;
     
125.         return abssub(tmp);
     
126.     }
     
127. }
     
128. 
     
129. decnum&
     
130. decnum::operator*=(const decnum& x)
     
131. {
     
132.     if(num == 0) return *this;
     
133.     if(x.num == 0) {
     
134.         num = 0;
     
135.         return *this;
     
136.     }
     
137.     if(sign == x.sign)
     
138.         sign = 0;
     
139.     else
     
140.         sign = 1;
     
141.     int mul, i, n, newcap, max;
     
142.     char ch, carry;
     
143.     char *newval = new char[num + x.num];
     
144.     newcap = num + x.num;
     
145.     memset(newval, 0, num + x.num);
     
146. 
     
147.     decnum a, b;
     
148.     char *ptr;
     
149.     for(i=0; i<num && val[i] == 0; i++);
     
150.     int na = i;
     
151.     a.val = val + i;
     
152.     a.num = num - i;
     
153.     for(i=0; i<num && x.val[i] == 0; i++);
     
154.     int nb = i;
     
155.     b.val = x.val + i;
     
156.     b.num = x.num - i;
     
157.     ptr = newval + na + nb;
     
158. 
     
159.     for(n=0; n <= a.num + b.num - 2; n++) {
     
160.         mul = 0;
     
161.         if(n > b.num - 1)
     
162.             i = n - b.num + 1;
     
163.         else
     
164.             i=0;
     
165.         max = n < a.num-1 ? n : a.num-1;
     
166.         for(; i<=max; i++)
     
167.             mul += a.val[i]*b.val[n-i];
     
168.         carry = 0;
     
169.         for(i=n; mul > 0 || carry > 0; mul /= 10, i++) {
     
170.             ch = ptr[i] + mul % 10 + carry;
     
171.             if(ch > 9) {
     
172.                 carry = 1;
     
173.                 ptr[i] = ch - 10;
     
174.             }
     
175.             else
     
176.             {
     
177.                 carry = 0;
     
178.                 ptr[i] = ch;
     
179.             }
     
180.         }
     
181.     }
     
182.     for(i=a.num + b.num; i>0 && ptr[i-1] == 0; i--);
     
183.     num = i + na + nb;
     
184.     if(cap >= num) {
     
185.         memcpy(val, newval, num);
     
186.         delete[] newval;
     
187.     }
     
188.     else {
     
189.         cap = newcap;
     
190.         delete[] val;
     
191.         val = newval;
     
192.     }
     
193.     a.val = b.val = NULL;
     
194.     return *this;
     
195. }
     
196. 
     
197. decnum&
     
198. decnum::operator/=(const decnum& x)
     
199. {
     
200.     char ch, carry, fac;
     
201.     decnum tmp;
     
202.     int i;
     
203.     if(x.num == 0) return *this;
     
204.     if(num < x.num) {
     
205.         num = 0;
     
206.         return *this;
     
207.     }
     
208.     if(sign == x.sign)
     
209.         sign = 0;
     
210.     else
     
211.         sign = 1;
     
212.     char *newval = new char[num - x.num + 1];
     
213.     memset(newval, 0, num - x.num + 1);
     
214.     carry = 0;
     
215.     fac = x.val[x.num-1] + 1;
     
216.     tmp.val = val + num - x.num + 1;
     
217.     tmp.cap = tmp.num = x.num -1;
     
218.     for(i=num-1; i>= x.num-1; i--) {
     
219.         tmp.val--;
     
220.         tmp.num++;
     
221.         ch = (carry * 10 + val[i]) / fac;
     
222.         tmp  -= x * ch;
     
223.         while(tmp >= x) {
     
224.             tmp -= x;
     
225.             ch++;
     
226.         }
     
227.         newval[i-x.num+1] = ch;
     
228.         carry = val[i];
     
229.     }
     
230.     tmp.val = NULL;
     
231.     for(i=num-x.num+1; i>0 && newval[i-1] == 0; i--);
     
232.     num = i;
     
233.     delete[] val;
     
234.     val = newval;
     
235.     return *this;
     
236. }
     
237. 
     
238. decnum&
     
239. decnum::operator%=(const decnum& x)
     
240. {
     
241.     char ch, carry, fac;
     
242.     decnum tmp;
     
243.     int i;
     
244.     if(x.num == 0) return *this;
     
245.     if(num < x.num) return *this;
     
246. 
     
247.     carry = 0;
     
248.     fac = x.val[x.num-1] + 1;
     
249.     tmp.val = val + num - x.num + 1;
     
250.     tmp.num = x.num - 1;
     
251.     for(i=num-1; i>= x.num-1; i--) {
     
252.         tmp.val--;
     
253.         tmp.num++;
     
254.         ch = (carry * 10 + val[i]) / fac;
     
255.         tmp  -= x * ch;
     
256.         while(tmp >= x) {
     
257.             tmp -= x;
     
258.             ch++;
     
259.         }
     
260.         carry = val[i];
     
261.     }
     
262.     tmp.val = NULL;
     
263.     num = tmp.num;
     
264.     return *this;
     
265. }
     
266. 
     
267. decnum
     
268. decnum::operator+(const decnum& x) const
     
269. {
     
270.     decnum tmp = *this;
     
271.     return tmp += x;
     
272. }
     
273. 
     
274. decnum
     
275. decnum::operator-(const decnum& x) const
     
276. {
     
277.     decnum tmp = *this;
     
278.     return tmp -= x;
     
279. }
     
280. 
     
281. decnum
     
282. decnum::operator*(const decnum& x) const
     
283. {
     
284.     decnum tmp = *this;
     
285.     return tmp *= x;
     
286. }
     
287. 
     
288. decnum
     
289. decnum::operator/(const decnum& x) const
     
290. {
     
291.     decnum tmp = *this;
     
292.     return tmp /= x;
     
293. }
     
294. 
     
295. decnum
     
296. decnum::operator%(const decnum& x) const
     
297. {
     
298.     decnum tmp = *this;
     
299.     return tmp %= x;
     
300. }
     
301. 
     
302. decnum abs(const decnum& x)
     
303. {
     
304.     decnum tmp(x);
     
305.     tmp.sign = 0;
     
306.     return tmp;
     
307. }
     
308. 
     
309. decnum pow(const decnum& x, int n)
     
310. {
     
311.     decnum tmp(1), fac(x);
     
312.     for(; n>0; n>>=1) {
     
313.         if(n&0x01)
     
314.             tmp *= fac;
     
315.         fac *= fac;
     
316.     }
     
317.     return tmp;
     
318. }
     
319. 
     
320. char decnum::root_1(int n)
     
321. {
     
322.     char r = (int)(pow(1+val[num-1], 1.0/n) * pow(10,(num-1.0)/n));
     
323.     for(; r>0 && pow(decnum(r), n) > *this; r--);
     
324.     return r;
     
325. }
     
326. 
     
327. bool decnum::ispow(int n, decnum& r) const
     
328. {
     
329.     if(num == 0) {
     
330.         r.num = 0;
     
331.         return true;
     
332.     }
     
333.     if(sign == 1 && (n&1 == 0)) {
     
334.         r.num = 0;
     
335.         return false;
     
336.     }
     
337.     decnum tmp, p;
     
338.     r.cap = r.num = (num+n-1) / n;
     
339.     r.val = new char[r.num];
     
340.     r.sign = sign;
     
341.     memset(r.val, 0, r.num);
     
342.     tmp.val = val + (r.num-1)*n;
     
343.     tmp.num = num - (r.num-1)*n;
     
344.     r.val[r.num-1] = tmp.root_1(n);
     
345. 
     
346.     tmp.val = new char[r.num+1];
     
347.     tmp.cap = r.num+1;
     
348.     int v;
     
349.     p = pow(r, n);
     
350.     if(p == *this) return true;
     
351.     for(int i=r.num-2; i>=0; i--) {
     
352.         memset(tmp.val, 0, i+1);
     
353.         tmp.val[i] = 1;
     
354.         tmp.num = i+1;
     
355.         tmp += r;
     
356.         p = (*this - p) / (pow(tmp, n) - p);
     
357.         if(p.num > 1)
     
358.             v = 9;
     
359.         else if(p.num > 0)
     
360.             v = p.val[0];
     
361.         else
     
362.             v = 0;
     
363.         for(; v>=0; v--) {
     
364.             r.val[i] = v;
     
365.             p = pow(r, n);
     
366.             if(p == *this)
     
367.                 return true;
     
368.             if(p < *this)
     
369.                 break;
     
370.         }
     
371.     }
     
372.     return false;
     
373. }
     
374. 
     
375. bool decnum::ispow() const
     
376. {
     
377.     decnum r, dec2("2", 1);
     
378.     if(ispow(2, r)) return true;
     
379.     for(int n=3; r > dec2; n+=2) {
     
380.         if(ispow(n, r)) return true;
     
381.     }
     
382.     return false;
     
383. }
     
384. 
     
385. decnum
     
386. root(const decnum& x, int n)
     
387. {
     
388.     decnum r;
     
389.     x.ispow(n, r);
     
390.     return r;
     
391. }
     
392. 
     
393. decnum
     
394. div(const decnum& x, const decnum& y, decnum& r)
     
395. {
     
396.     char ch, carry, fac;
     
397.     decnum d = x, tmp;
     
398.     int i;
     
399.     if(y.num == 0) return x;
     
400.     if(d.num < y.num) {
     
401.         r = x;
     
402.         d = 0;
     
403.         return d;
     
404.     }
     
405.     char *newval = new char[d.num - y.num + 1];
     
406.     memset(newval, 0, d.num - y.num + 1);
     
407.     carry = 0;
     
408.     fac = y.val[y.num-1] + 1;
     
409.     tmp.val = d.val + d.num - y.num + 1;
     
410.     tmp.num = y.num - 1;
     
411.     for(i=d.num-1; i>= y.num-1; i--) {
     
412.         tmp.val--;
     
413.         tmp.num++;
     
414.         ch = (carry * 10 + d.val[i]) / fac;
     
415.         tmp  -= y * ch;
     
416.         while(tmp >= y) {
     
417.             tmp -= y;
     
418.             ch++;
     
419.         }
     
420.         newval[i-y.num+1] = ch;
     
421.         carry = d.val[i];
     
422.     }
     
423.     r = tmp;
     
424.     tmp.val = NULL;
     
425.     for(i=d.num-y.num+1; i>0 && newval[i-1] == 0; i--);
     
426.     d.num = i;
     
427.     delete[] d.val;
     
428.     d.val = newval;
     
429.     return d;
     
430. }
     
431. 
     
432. bool operator==(const decnum& x, const decnum&y)
     
433. {
     
434.     if(x.sign != y.sign) return false;
     
435.     if(x.num != y.num) return false;
     
436.     for(int i=0; i < x.num; i++)
     
437.         if(x.val[i] != y.val[i])
     
438.             return false;
     
439.     return true;
     
440. }
     
441. 
     
442. bool operator!=(const decnum& x, const decnum&y)
     
443. {
     
444.     return !(x==y);
     
445. }
     
446. 
     
447. bool operator>(const decnum& x, const decnum&y)
     
448. {
     
449.     if(x.sign > y.sign) return false;
     
450.     if(x.sign < y.sign) return true;
     
451.     bool retval = (x.sign == 0);
     
452.     if(x.num > y.num) return retval;
     
453.     if(x.num < y.num) return !retval;
     
454.     for(int i=x.num-1; i >= 0; i--)
     
455.         if(x.val[i] > y.val[i])
     
456.             return retval;
     
457.         else if(x.val[i] < y.val[i])
     
458.             return !retval;
     
459.     return false;
     
460. }
     
461. 
     
462. bool operator<(const decnum& x, const decnum&y)
     
463. {
     
464.     return y > x;
     
465. }
     
466. 
     
467. bool operator>=(const decnum& x, const decnum&y)
     
468. {
     
469.     if(x.sign > y.sign) return false;
     
470.     if(x.sign < y.sign) return true;
     
471.     bool retval = (x.sign == 0);
     
472.     if(x.num > y.num) return retval;
     
473.     if(x.num < y.num) return !retval;
     
474.     for(int i=x.num-1; i >= 0; i--)
     
475.         if(x.val[i] > y.val[i])
     
476.             return retval;
     
477.         else if(x.val[i] < y.val[i])
     
478.             return !retval;
     
479.     return true;
     
480. }
     
481. 
     
482. bool operator<=(const decnum& x, const decnum&y)
     
483. {
     
484.     return y >= x;
     
485. }
     
486. 
     
487. ostream& operator<<(ostream&os, const decnum& x)
     
488. {
     
489.     if(x.size() == 0)
     
490.         os << 0;
     
491.     else {
     
492.         if(x.sign == 1)
     
493.             os << "-";
     
494.         for(int i = x.size()-1; i>=0; i--)
     
495.             os << (int)x.val[i];
     
496.     }
     
497.     return os;
     
498. }
     
499. 
     

复制代码

[ 本帖最后由 yuxh 于 2006-8-23 18:11 编辑 ]

---

作者: flw    时间: 2006-08-18 13:16
传说中的沙发？

---

作者: zengjin8310    时间: 2006-08-18 13:18
8错， 对我搞科学计算有用， 测试过效率么？

---

作者: zengjin8310    时间: 2006-08-18 13:21
最好再加上超高精度的浮点数的混合运算支持

---

作者: yuxh    时间: 2006-08-18 13:26
这个本来是为大素数的测试用的，这些是要用到的基本运算
可惜我的工作与加密算法无关，纯粹是业余爱好，代码也是业余水平的。
就效率而言，比较慢的就是求n次方根这个了：
root(x, n)
设x有m位，则算法应该是O(m^3*log(m)/n)的
检测一个数是否是某个数的整数次幂:
ispow()
这个就差不多是O(m^3*log(m)^2)的了

[ 本帖最后由 yuxh 于 2006-8-22 11:17 编辑 ]

---

作者: 默难    时间: 2006-08-18 15:00
支持原创
顶一下吧

---

作者: aple_smx    时间: 2006-08-19 15:25
提示: 作者被禁止或删除 内容自动屏蔽

---

作者: mirnshi    时间: 2006-08-21 15:02
接口为10进制, 内部的进制采用unsigned long或unsigned short，是不是更能借助逻辑运算，提高效率？

---

作者: hqxyn    时间: 2006-08-22 10:29
标题: 回复 1楼 yuxh 的帖子
来凑凑热闹
decimal.h
/***************************************************************************
                          decimal.h  -  description
                             -------------------
    begin                : Wed Jan 9 2002
    copyright            : (C) 2002 by Xian Yining
    email                : hqxyn@yahoo.com.cn
***************************************************************************/

/***************************************************************************
*                                                                         *
*   This program is free software; you can redistribute it and/or modify  *
*   it under the terms of the GNU General Public License as published by  *
*   the Free Software Foundation; either version 2 of the License, or     *
*   (at your option) any later version.                                   *
*                                                                         *
***************************************************************************/
#ifndef DECIMAL_H
#define DECIMAL_H

#ifndef __USE_GNU
#define __USE_GNU
#endif
/*
#ifndef __USE_ISOC99
#define __USE_ISOC99
#endif
*/
#include <typeinfo>
#include <iostream>
#include <string>
#include <limits>

const unsigned DECIMAL_DEFAULT_PRE = 20,DECIMAL_DEFAULT_DEC = 6;

class decimal
{
public :
        enum Sign {PLUS=1,MINUS=-1};
        enum Stat {NOINIT=-1,OK,UPFLOW,DOWNFLOW,OVERDIGITS};
        enum Pre  {DOUBLE_PRECISION=std::numeric_limits<double>::digits10,LDOUBLE_PRECISION=std::numeric_limits<long double>::digits10};

        //构造函数
        decimal(void):sn(PLUS),val("0",exp(0),st(OK),pre(DECIMAL_DEFAULT_PRE),dec(DECIMAL_DEFAULT_DEC) {}
        decimal(const std::string &,const unsigned int p=DECIMAL_DEFAULT_PRE,const unsigned int d=DECIMAL_DEFAULT_DEC) ;
        decimal(const char* cstr,const unsigned int p=DECIMAL_DEFAULT_PRE,const unsigned int d=DECIMAL_DEFAULT_DEC) ;
        decimal(const int,const unsigned int p=DECIMAL_DEFAULT_PRE,const unsigned int d=DECIMAL_DEFAULT_DEC) ;
        decimal(const unsigned int,const unsigned int p=DECIMAL_DEFAULT_PRE,const unsigned int d=DECIMAL_DEFAULT_DEC) ;
        decimal(const long,const unsigned int p=DECIMAL_DEFAULT_PRE,const unsigned int d=DECIMAL_DEFAULT_DEC) ;
        decimal(const long long,const unsigned int p=DECIMAL_DEFAULT_PRE,const unsigned int d=DECIMAL_DEFAULT_DEC) ;
        decimal(const unsigned long,const unsigned int p=DECIMAL_DEFAULT_PRE,const unsigned int d=DECIMAL_DEFAULT_DEC) ;
        decimal(const unsigned long long,const unsigned int p=DECIMAL_DEFAULT_PRE,const unsigned int d=DECIMAL_DEFAULT_DEC) ;
        decimal(const double,const unsigned int p=DECIMAL_DEFAULT_PRE,const unsigned int d=DECIMAL_DEFAULT_DEC) ;
        decimal(const long double,const unsigned int p=DECIMAL_DEFAULT_PRE,const unsigned int d=DECIMAL_DEFAULT_DEC) ;
        decimal(const decimal& d):sn(d.sn),val(d.val),exp(d.exp),st(d.st),pre(d.pre),dec(d.dec) {}
        virtual ~decimal(){}
        //赋值
        decimal& operator=(const decimal& ;
        //算术运算
        decimal& operator +=(const decimal& ;
        decimal& operator -=(const decimal& ;
        decimal& operator *=(const decimal& ;
        decimal& operator /=(const decimal& ;
//        decimal& operator %=(const decimal& ;

        //比较运算符
        bool le(const decimal& const ;
        bool eq(const decimal& const ;
        bool gt(const decimal& const ;
       
        decimal& operator-(void) {sn=((sn==PLUS)?MINUSLUS);return *this;}
        decimal& operator+(void) {return *this;}
        //杂项函数
        virtual std::string toString() const;
        virtual std::string toShortStr() const;
        virtual std::string toString(const unsigned int len,const int de) const;
                                                                //在len长度内转为十进小数字符串，超常则返回‘＊’串
        virtual std::string toEString(const unsigned int len=0) const;        //在len长度内转为科学表示法字符串，超常则返回‘＊’串
        bool ok() const {return (st==OK)?true:false;}                //数字是否有效
        bool zero() const {return (val=="0")?true:false ;}        //数字是否为0
        virtual decimal& round(int r) ;
        virtual decimal& round() ;        //按dec指定的位数四舍五入
       
        Sign getSn() const {return sn;}
        const std::string &getVal() const {return val;}
        int getExp() const {return exp;}
        Stat getSt() const {return st;}
        unsigned getPre() const {return pre;}
        unsigned getDec() const {return dec;}
/****************
*   内部子程序   *
****************/
protected :
        decimal& decReg() ;
       
        decimal& decAdd(const decimal&);
        decimal& decSub(const decimal&);
        decimal& decMulti(const decimal&) ;
        decimal& decDiv(const decimal&);

        void valDiv(std::string& s1,const std::string& s2,const unsigned len) ;
        char valMult(std::string& s1,const std::string& s2) ;
        void valAdd(std::string& s1,int &p1,const std::string& s2,int p2) ;
        int valSub(std::string& s1,int &e1,const std::string& s2,const int e2);
       
        int digitAdd(char& c1,const char c2,const int car=0) ;
        int digitSub(char& c1,const char c2,const int b=0) ;
        char digitMult(char& c1,const char c2,const char m) ;
       
        int valCmp(const std::string& s1,const int e1,const std::string& s2,const int e2) const;
       
        void setSn(Sign s) {sn=s;}
        void setVal(const std::string &s) {val=s;}
        void setExp(int i) {exp=i;}
        void setSt(Stat s) {st=s;}
        void setPre(unsigned u) {pre=u;}
        void setDec(unsigned u) {dec=u;}
private :
        Sign                sn;        //符号
        std::string        val;        //有效尾数
        int                 exp;        //小数点位置（指数）
        //以下为辅助参数
        Stat                st;        //状态
        unsigned int        pre;        //精度(最大有效数字位数)
        unsigned int        dec;        //保留小数位数
       
};

/*******************
*   协作函数       *
*******************/
decimal round(const decimal& ,const int) ;
//算术运算
decimal operator +(const decimal&,const decimal&) ;
decimal operator -(const decimal&,const decimal&) ;
decimal operator *(const decimal&,const decimal&) ;
decimal operator /(const decimal&,const decimal&) ;
//        friend decimal& operator %(const decimal&,const decimal&) ;
//比较运算符
bool operator  <(const decimal&,const decimal&) ;
bool operator <=(const decimal&,const decimal&) ;
bool operator ==(const decimal&,const decimal&) ;
bool operator >=(const decimal&,const decimal&) ;
bool operator  >(const decimal&,const decimal&) ;
bool operator !=(const decimal&,const decimal&) ;
//流
std:stream& operator <<(std:stream&,const decimal&) ;
//unsigned int midDigits(const decimal& ,const decimal& ) ;

#endif //DECIMAL_H

[ 本帖最后由 hqxyn 于 2006-8-22 19:54 编辑 ]

---

作者: hqxyn    时间: 2006-08-22 10:31
标题: 回复 9楼 hqxyn 的帖子
money.h
/***************************************************************************
                          decimal.cpp  -  description
                             -------------------
    begin                : Wed Jan 9 2002
    copyright            : (C) 2002 by Xian Yining
    email                : hqxyn@yahoo.com.cn
***************************************************************************/

/***************************************************************************
*                                                                         *
*   This program is free software; you can redistribute it and/or modify  *
*   it under the terms of the GNU General Public License as published by  *
*   the Free Software Foundation; either version 2 of the License, or     *
*   (at your option) any later version.                                   *
*                                                                         *
***************************************************************************/
#ifndef _MONEY_H
#define _MONEY_H

#include "decimal.h"

const int MONEY_DEFAULT_DEC = 2;

class money : public decimal {
public :
money():decimal(0,DECIMAL_DEFAULT_PRE,MONEY_DEFAULT_DEC) {};
money(const char* cstr,const unsigned int p=DECIMAL_DEFAULT_PRE)
                :decimal(cstr,p,MONEY_DEFAULT_DEC) {round();} ;
money(const int i,const unsigned int p=DECIMAL_DEFAULT_PRE)
                :decimal(i,p,MONEY_DEFAULT_DEC){round();} ;
money(const unsigned int ui,const unsigned int p=DECIMAL_DEFAULT_PRE)
                :decimal(ui,p,MONEY_DEFAULT_DEC){round();} ;
money(const long l,const unsigned int p=DECIMAL_DEFAULT_PRE)
                :decimal(l,p,MONEY_DEFAULT_DEC){round();} ;
money(const long long ll,const unsigned int p=DECIMAL_DEFAULT_PRE)
                :decimal(ll,p,MONEY_DEFAULT_DEC){round();} ;
money(const unsigned long ul,const unsigned int p=DECIMAL_DEFAULT_PRE)
                :decimal(ul,p,MONEY_DEFAULT_DEC){round();} ;
money(const unsigned long long ull,const unsigned int p=DECIMAL_DEFAULT_PRE)
                :decimal(ull,p,MONEY_DEFAULT_DEC){round();} ;
money(const double db,const unsigned int p=DECIMAL_DEFAULT_PRE)
                :decimal(db,p,MONEY_DEFAULT_DEC){round();} ;
money(const long double ld,const unsigned int p=DECIMAL_DEFAULT_PRE)
                :decimal(ld,p,MONEY_DEFAULT_DEC){round();} ;
money(const decimal& d)
                :decimal(0,d.getPre(),MONEY_DEFAULT_DEC) {
                setSn(d.getSn());
                setVal(d.getVal());
                setExp(d.getExp());
                round();}
//赋值d.toEString().c_str()

money& operator=(const decimal& d) {
        //精度定义(pre)和保留小数位数(dec)在变量定义时确定，?新值时不变。
        setSn(d.getSn());
        setVal(d.getVal());
        setExp(d.getExp());
        if (getVal().size()>getPre()) {setSt(OVERDIGITS);}
        else setSt(d.getSt());
        round();
        return *this;
}
};
#endif //_MONEY_H

[ 本帖最后由 hqxyn 于 2006-8-22 10:38 编辑 ]

---

作者: hqxyn    时间: 2006-08-22 10:35
标题: 回复 10楼 hqxyn 的帖子
decimal.cpp
/***************************************************************************
                          decimal.cpp  -  description
                             -------------------
    begin                : Wed Jan 9 2002
    copyright            : (C) 2002 by Xian Yining
    email                : hqxyn@yahoo.com.cn
***************************************************************************/

/***************************************************************************
*                                                                         *
*   This program is free software; you can redistribute it and/or modify  *
*   it under the terms of the GNU General Public License as published by  *
*   the Free Software Foundation; either version 2 of the License, or     *
*   (at your option) any later version.                                   *
*                                                                         *
***************************************************************************/
#include <iostream>
#include <string>

#undef __DEBUG__
//#define __DEBUG__

#include "decimal.h"
unsigned int midDigits(const decimal& ,const decimal& ) ;

/***********
* 构造函数 *
***********/
decimal::decimal(const std::string &s,const unsigned int p,const unsigned int d) {
        decimal x(s.c_str(),p,d);
        sn=x.sn;
        val=x.val;
        exp=x.exp;
        st=x.st;
        pre=x.pre;
        dec=x.dec;
        this->decReg();
        if (val.size()>p) {st=OVERDIGITS;/*throw*/ ;}
}
decimal::decimal(const char* ci,const unsigned int p,const unsigned int d) {
        char c[strlen(ci)+1];
        unsigned j=0;
        int i;
        strcpy(c,ci);
#ifdef __DEBUG__
std::cout<<"char*:c="<<c<<"\n";
#endif
        //消前后空格
        for ( i=strlen(c)-1;i>=0;--i ) {
                if ( c!=' ' ) break;
                c='\0';
        }
        for ( j=0;j<strlen(c); ) {
                if (c[j]!=' ') break;
                ++j;
        }
        //判符号
        if ( c[j]=='+' ) {sn=PLUS;++j;}
        else {
                if ( c[j]=='-' ) {sn=MINUS;++j;}
                else sn=PLUS;
        }
        //去前导‘0’
        while (j<strlen(c+j)) {if (c[j]!='0') break;++j;}
#ifdef __DEBUG__
std::cout<<"char*:j="<<c+j<<"\n";
#endif
        char *fp=c+j;        //尾数数组指针
#ifdef __DEBUG__
std::cout<<"char*:fp="<<fp<<"\n";
#endif
        char *ep=NULL;        //指数数组指针
        char *dp=NULL;        //小数数组指针
        st=OK;
        for ( j=0;j<strlen(fp) && fp[j]!='\0'; ) {        //取尾数整数部分
                switch(fp[j]) {
                  case '0':case '1':case '2':case '3':case '4':case '5':case '6':case '7':case '8':case '9':++j;break;
                  case '.':dp=fp+j+1;fp[j]='\0';break;
                  case 'E':case 'e':ep=fp+j+1;fp[j]='\0';break;
                  default:st=NOINIT;fp[j]='\0';

                  }
        }
#ifdef __DEBUG__
std::cout<<"char*:fp2="<<fp<<"\n";
#endif
        if ( dp!=NULL ) {        //取尾数小数部分
                for (j=0;j<strlen(dp) && dp[j]!='\0'{
                        switch(dp[j]) {
                          case '0':case '1':case '2':case '3':case '4':case '5':case '6':case '7':case '8':case '9':++j;break;
                          case 'E':case 'e':ep=dp+j+1;dp[j]='\0';break;
                          default:st=NOINIT;dp[j]='\0';
                          }
                }
        }
#ifdef __DEBUG__
std::cout<<"char*:fp3="<<ep<<"\n";
#endif
        if ( ep!=NULL ) {
                switch(ep[0]) {        //检查指数首字符
                  case '+':case '-':
                  case '0':case '1':case '2':case '3':case '4':case '5':case '6':case '7':case '8':case '9':break;
                  default:st=NOINIT;
                }
        }
#ifdef __DEBUG__
std::cout<<"char*:fp4="<<fp<<"\n";
#endif
        if ( ep!=NULL ) {        //取指数部分
                for (j=1;j<strlen(ep){
                        switch(ep[j]) {
                          case '0':case '1':case '2':case '3':case '4':case '5':case '6':case '7':case '8':case '9':++j;break;
                          default:st=NOINIT;
                          }
#ifdef __DEBUG__
std::cout<<"char*:fp5c="<<fp[j]<<"\n";
#endif

                }
        }
#ifdef __DEBUG__
std::cout<<"char*:fp5="<<fp<<"\n";
#endif
        if (fp!=NULL ) {
                val=fp;
        }
        exp=0;
        if (dp!=NULL) {
                val.append(dp);
                exp-=strlen(dp);
        }
        if (ep!=NULL) {
#ifdef __DEBUG__
std::cout<<"char*:*ep="<<atoi(ep)<<"\n";
#endif
                exp+=atoi(ep);
        }
        dec=d;
        pre=p;
        this->decReg();
        if (val.size()>p) {st=OVERDIGITS;/*throw*/ ;}
}
decimal::decimal(const int v,const unsigned int p,const unsigned int d) {
        char c[std::numeric_limits<int>::digits10+2];
        sprintf(c,"%i",v);
#ifdef __DEBUG__
std::cout<<"int:c="<<c<<"\n";
#endif
        if (c[0]=='-') {sn=MINUS;val=c+1;}
        else {sn=PLUS;val=c;}
        pre=p;
        dec=d;
        exp=0;
        st=OK;
        this->decReg();
        if (val.size()>p) {st=OVERDIGITS;/*throw*/ ;}
}
decimal::decimal(const unsigned int v,const unsigned int p,const unsigned int d) {
        char c[std::numeric_limits<unsigned int>::digits10+2];
        sprintf(c,"%u",v);
#ifdef __DEBUG__
std::cout<<"Uint:c="<<c<<"\n";
#endif
        sn=PLUS;
        val=c;
        pre=p;
        dec=d;
        exp=0;
        st=OK;
        this->decReg();
        if (val.size()>p) {st=OVERDIGITS;/*throw*/ ;}
}
decimal::decimal(const long v,const unsigned int p,const unsigned int d) {
        char c[std::numeric_limits<long>::digits10+2];
        sprintf(c,"%li",v);
#ifdef __DEBUG__
std::cout<<"long:c="<<c<<"\n";
#endif
        if (c[0]=='-') {sn=MINUS;val=c+1;}
        else {sn=PLUS;val=c;}
        pre=p;
        dec=d;
        exp=0;
        st=OK;
        this->decReg();
        if (val.size()>p) {st=OVERDIGITS;/*throw*/ ;}
}
decimal::decimal(const long long v,const unsigned int p,const unsigned int d) {
        char c[std::numeric_limits<long long>::digits10+2];
        sprintf(c,"%lli",v);
#ifdef __DEBUG__
std::cout<<"long long:c="<<c<<"\n";
#endif
        if (c[0]=='-') {sn=MINUS;val=c+1;}
        else {sn=PLUS;val=c;}
        pre=p;
        dec=d;
        exp=0;
        st=OK;
        this->decReg();
        if (val.size()>p) {st=OVERDIGITS;/*throw*/ ;}
}
decimal::decimal(const unsigned long v,const unsigned int p,const unsigned int d) {
        char c[std::numeric_limits<unsigned int>::digits10+2];
        sprintf(c,"%lu",v);
#ifdef __DEBUG__
std::cout<<"Ulong:c="<<c<<"\n";
#endif
        val=c;
        sn=PLUS;
        pre=p;
        dec=d;
        exp=0;
        st=OK;
        this->decReg();
        if (val.size()>p) {st=OVERDIGITS;/*throw*/ ;}
}

decimal::decimal(const unsigned long long v,const unsigned int p,const unsigned int d) {
        char c[std::numeric_limits<unsigned long long>::digits10+2];
        sprintf(c,"%llu",v);
#ifdef __DEBUG__
std::cout<<"UUlong:c="<<c<<"\n";
#endif
        val=c;
        sn=PLUS;
        pre=p;
        dec=d;
        exp=0;
        st=OK;
        this->decReg();
        if (val.size()>p) {st=OVERDIGITS;/*throw*/ ;}
}
decimal::decimal(const double v,const unsigned int p,const unsigned int d) {
        char c[std::numeric_limits<double>::digits10+std::numeric_limits<int>::digits10+1];

        char t[10],s[15]="%.";
       
        sprintf(t,"%u",std::numeric_limits<double>::digits10);
        strcat(s,t);
        strcat(s,"E";
       
        sprintf(c,s,v);
#ifdef __DEBUG__
std::cout<<"double:c="<<c<<"\n";
#endif
        char *tE=strchr(c,'E');
        if ( tE!=NULL ) {        //取指数
                exp=atoi(tE+1);
                *tE='\0';
        }
        else exp=0;
       
//        for (unsigned u=strlen(c)-1;u>0 && c=='0';c='\0',u--) {}
       
        char *tD=strchr(c,'.');
       
        if ( tD!=NULL ) {        //将尾数变为整数，并相应调整指数
                char *px=tD;
                for (;*(px+1)!='\0';*px = *(px+1),--exp,++px) {}
                *px='\0';
        }

        if (c[0]=='-') {sn=MINUS;val=c+1;}
        else {sn=PLUS;val=c;}
        pre=p;
        dec=d;
        st=OK;
        this->decReg();
        if (val.size()>p) {st=OVERDIGITS;/*throw*/ ;}
}
decimal::decimal(const long double v,const unsigned int p,const unsigned int d) {
        char c[std::numeric_limits<long double>::digits10+std::numeric_limits<int>::digits10+1];

        char t[10],s[15]="%.";
       
        sprintf(t,"%u",std::numeric_limits<long double>::digits10);
        strcat(s,t);
        strcat(s,"LE";
       
        sprintf(c,s,v);
#ifdef __DEBUG__
std::cout<<"long double:c="<<c<<"\n";
#endif
        char *tE=strchr(c,'E');
        if ( tE!=NULL ) {        //取指数
                exp=atoi(tE+1);
                *tE='\0';
        }
        else exp=0;
       
//        for (unsigned u=strlen(c)-1;u>0 && c=='0';c='\0',u--) {}
       
        char *tD=strchr(c,'.');
       
        if ( tD!=NULL ) {        //将尾数变为整数，并相应调整指数
                char *px=tD;
                for (;*(px+1)!='\0';*px = *(px+1),--exp,++px) {}
                *px='\0';
        }
       
        if (c[0]=='-') {sn=MINUS;val=c+1;}
        else {sn=PLUS;val=c;}
        pre=p;
        dec=d;
        st=OK;
        this->decReg();
        if (val.size()>p) {st=OVERDIGITS;/*throw*/ ;}
}
/************
* 赋值操作符 *
************/
decimal& decimal:perator=(const decimal& d) {
        //精度定义(pre)和保留小数位数(dec)在变量定义时确定，?新值时不变。
#ifdef __DEBUG__
std::cout<<"in decimal[=]:"<<*this<<";;"<<d<<"\n";
#endif
        sn=d.sn;
        val=d.val;
        exp=d.exp;
        if (val.size()>pre) {st=OVERDIGITS;/*throw*/ ;}
        else st=d.st;
        return *this;
}
/**************
*  算术运算符  *
**************/
decimal& decimal:perator +=(const decimal& d2) {
        if (sn==d2.sn) {
                valAdd(val,exp,d2.val,d2.exp);
        }
        else {
                if (valCmp(val,exp,d2.val,d2.exp)<0) {
                        std::string t=d2.val;
                        int et=d2.exp;
                        valSub(t,et,val,exp);val=t;exp=et;sn=d2.sn;
                }
                else valSub(val,exp,d2.val,d2.exp);
        }
        return this->decReg();
}
decimal& decimal:perator -=(const decimal& d2) {
        if (sn==d2.sn) {
                if (valCmp(val,exp,d2.val,d2.exp)<0) {
                        std::string t=d2.val;
                        int et=d2.exp;
                        valSub(t,et,val,exp);val=t;exp=et;
                        sn=(d2.sn==PLUS)?MINUSLUS;
                }
                else valSub(val,exp,d2.val,d2.exp);
        }
        else {
                valAdd(val,exp,d2.val,d2.exp);
        }
        return this->decReg();
}
decimal& decimal:perator *=(const decimal& d2) {
        sn=(sn==d2.sn)?PLUS:MINUS;
        exp+=d2.exp;
        valMult(val,d2.val);
        return this->decReg();
}
decimal& decimal:perator /=(const decimal& d2) {
        if (d2.zero()) {st=UPFLOW;return *this;}
        sn=(sn==d2.sn)?PLUS:MINUS;
        int te1,te2;
        te1=exp+val.size();te2=d2.exp+d2.val.size();
        te1-=te2;
        valDiv(val,d2.val,pre+1);
        exp=-val.size()+1+te1;
        return this->decReg();
}
decimal operator +(const decimal& d1,const decimal& d2) {
        decimal d(0,midDigits(d1,d2),(d1.getDec()>=d2.getDec())?d1.getDec():d2.getDec());
        d=d1;
#ifdef __DEBUG__
        std::cout<<"[+]:d="<<d<<"d.pre="<<d.getPre()<<"\n";
#endif
        return d+=d2;
}
decimal operator -(const decimal& d1,const decimal& d2) {
        decimal d(0,midDigits(d1,d2),(d1.getDec()>=d2.getDec())?d1.getDec():d2.getDec());
        d=d1;
#ifdef __DEBUG__
        std::cout<<"[-]:d="<<d<<"d.pre="<<d.getPre()<<"\n";
#endif
        return d-=d2;
}
decimal operator *(const decimal& d1,const decimal& d2) {
        decimal d(0,d1.getPre()+d2.getPre(),d1.getDec()+d2.getDec());
        d=d1;
#ifdef __DEBUG__
        std::cout<<"

:d="<<d<<"d.pre="<<d.getPre()<<"\n";
#endif
        return d*=d2;
}
decimal operator /(const decimal& d1,const decimal& d2) {
        decimal d(0,d1.getPre()+d2.getPre(),d1.getDec()+d2.getDec());
        d=d1;
#ifdef __DEBUG__
        std::cout<<"[/]:d="<<d<<"d.pre="<<d.getPre()<<"\n";
#endif
        return d/=d2;
}
/**********************
*    比较运算符       *
*********************/

bool decimal::le(const decimal& d2) const {
        if (sn==decimal:LUS && d2.sn==decimal::MINUS) return false;
        if (sn==decimal::MINUS && d2.sn==decimal:LUS) return true;
        int r=decimal::valCmp(val,exp,d2.val,d2.exp);
        if (sn==decimal:LUS && r<0) return true;
        if (sn==decimal::MINUS && r>0) return true;
        return false;
}
bool decimal::eq(const decimal& d2) const {
        if ((sn==decimal::MINUS && d2.sn==decimal:LUS) || (sn==decimal:LUS && d2.sn==decimal::MINUS)) return false;
        int r=decimal::valCmp(val,exp,d2.val,d2.exp);
        if (r==0) return true;
        return false;
}
bool decimal::gt(const decimal& d2) const {
        if (this->sn==decimal::MINUS && d2.sn==decimal:LUS) return false;
        if (this->sn==decimal:LUS && d2.sn==decimal::MINUS) return true;
        int r=decimal::valCmp(val,exp,d2.val,d2.exp);
        if (this->sn==decimal:LUS && r>0) return true;
        if (this->sn==decimal::MINUS && r<0) return true;
        return false;
}

bool operator <(const decimal& d1,const decimal& d2) {
        return d1.le(d2);
}
bool operator ==(const decimal& d1,const decimal& d2) {
        return d1.eq(d2);
}
bool operator  >(const decimal& d1,const decimal& d2) {
        return d1.gt(d2);
}
bool operator <=(const decimal& d1,const decimal& d2) {
        return !(d1>d2);
}
bool operator >=(const decimal& d1,const decimal& d2) {
        return !(d1<d2);
}
bool operator !=(const decimal& d1,const decimal& d2) {
        return !(d1==d2);
}

/*****************
*   输入输出流   *
****************/
std:stream &operator <<(std:stream &os,const decimal& d) {
#ifdef __DEBUG__
        os<<"ok="<<d.ok();
        os<<",sign="<<((d.getSn()==decimal:LUS)?'+'d.getSn()==decimal::MINUS)?'-':'?'));
        os<<",val="<<d.getVal();
        os<<",exp="<<d.getExp();
        os<<",pre="<<d.getPre();
        os<<",dec="<<d.getDec();
        os<<"\n";
#endif
        os<<d.toString(0,d.getDec());
        return os;
}
/*
std::istream& operator >>(std::istream& is,decimal& d) {
        std::string s;
        std::cin>>s;
        decimal dx(s.c_str());
        d=dx;
        return is;
}
*/
/**************
*  杂函数     *
**************/
std::string decimal::toEString(const unsigned len) const {
        std::string s="";
        s.append((sn==decimal::MINUS)?"-"sn==decimal::PLUS)?" ":"?");
        s.append(val);
        s.append("E";
        char c[50];
        sprintf(c,"%i",exp);
        s.append(c);
        if (len != 0 && len<s.size()) s.assign(len,'*');
        return s;
}
std::string decimal::toShortStr() const{
        std::string s=toString();
        if (s.find('.')==std::string::npos) return s;
        int c=0;
        for (uint u=s.length()-1;u>0;--u){
                if (s=='0') ++c;
                else break;
        }
        if (s[s.length()-1-c]=='.') ++c;
        s=s.substr(0,s.length()-c);
        return s;
}

std::string decimal::toString() const{
        return toString(0,getDec());
}
std::string decimal::toString(const unsigned int len,const int de) const {
        std::string s="";
        if ( ! this->ok() ) return s.append((len==0)?1:len,'*');        //数字无效
        s.append((sn==decimal::MINUS)?"-"sn==decimal::PLUS)?" ":"?");
        if (exp>=0) {        //整数
                s.append(val).append(exp,'0').append(1,'.').append(de,'0');
        }
        else {
                if (-exp>=val.size()) {        //纯小数
                        s.append("0.".append(-exp-val.size(),'0').append(val);
                }
                else {
                        s.append(val.substr(0,val.size()+exp));
                        s.append(1,'.');
                        std::string x=val.substr(val.size()+exp);
                        s.append(x);        //带小数
                        s.append((de>x.size())?de-x.size():0,'0');
                }
        }
        if (len != 0 && len<s.size()) s.assign(len,'*');
        return s;
}
decimal& decimal::round() {
        return round(dec);
}
decimal& decimal::round(int r) {
        if (r<-exp) {        //末位属于舍入位
                std::string x="5";
                int e=-(r+1);
                valAdd(val,exp,x,e);
                int i=-exp-r;
                if ((val.size()-i)<=0) val="0";
                else val=val.substr(0,val.size()-i);
                exp+=i;
        }
        return this->decReg();
}

decimal round(const decimal& d,const int dec) {
        decimal dx(0,d.getPre(),dec);
        dx=d;
        dx.round(dec);
        return dx;
}

/****************
*   内部子程序   *
****************/

void decimal::valDiv(std::string& s1,const std::string& s2,const unsigned len) {
        std::string s(len,'0');        //商
        int ed=s2.size()-s1.size();        //商的小数位数
        std::string t1=s1,t2=s2;
        int et1;        //被除数对位指数,把两数首位对齐
        et1=ed;
        unsigned int i;        //商数循环
        int c;        //借位
        for (i=0;i<len;++i,++et1) {
                int j=1;
                for (j=1;j<=10;++j) {
                        if (valCmp(t1,et1,s2,0)<0) {
                        --j;
                        break;
                        }
                        c=valSub(t1,et1,s2,0) ;
                }
                s=char(j+4;
        }
        s1=s;
}
char decimal::valMult(std::string& s1,const std::string& s2) {
        std::string s="0";
        int es=0;
        for (unsigned int i=0;i<s2.size();++i) {        //乘数从末尾向前循环
                char c1,c2=s2[s2.size()-1-i],m='0';
                int j;
                std::string pn(s1.size()+1,'0');
                for (j=s1.size()-1;j>=0;--j) {        //被乘数乘以当前乘数位
                        c1=s1[j];
                        m=digitMult(c1,c2,m);
                        pn[j+1]=c1;
                }
                es=-i;
                pn[0]=m;
                valAdd(s,es,pn,0);
        }
        if (s[0]!='0') s1=s;
        else s1=s.substr(1);
        return '0';
}
int decimal::valSub(std::string& s1,int &e1,const std::string& s2,const int e2) {
        //计算差的位数
        //std::cout<<"s1="<<s1<<",e1="<<e1<<",s2"<<s2<<",e2="<<e2<<"\n";
        int li1,ld1,li2,ld2,li,ld;
        li1= s1.size()+e1;
        if ( e1>=0 ) {
                li1=s1.size()+e1;
                ld1=0;
        }
        else {
                if (li1<0) li1=0;
                ld1=-e1;
        }
        li2=s2.size()+e2;
        if ( e2>=0 ) {
                ld2=0;
        }
        else {
                if (li2<0) li2=0;
                ld2=-e2;
        }
        li=(li1>=li2)?li1:li2;        //整数位数
        ld=(ld1>=ld2)?ld1:ld2;        //小数位数
        std::string s(li+ld,'0');
        int qb1,        //第一串首位权数
            qe1,        //第一串末位权数
            qb2,        //第二串首位权数
            qe2;        //第二串末位权数
        qe1=li-e1-1;qb1=qe1-s1.size()+1;
        qe2=li-e2-1;qb2=qe2-s2.size()+1;
        char c1,c2;
        int m=0,j;
        for (j=li+ld-1;j>=0;--j) {
                c1=(j>=qb1 && j<=qe1)?s1[j-qb1]:'0';
                c2=(j>=qb2 && j<=qe2)?s2[j-qb2]:'0';
                m=digitSub(c1,c2,m);
                s[j]=c1;
        }
        s[0]=c1;
        s1=s;e1=-ld;
        return m;
}
void decimal::valAdd(std::string& s1,int &e1,const std::string& s2,const int e2) {
        //计算和的位数
        int li1,ld1,li2,ld2,li,ld;
        li1= s1.size()+e1;
        if ( e1>=0 ) {
                li1=s1.size()+e1;
                ld1=0;
        }
        else {
                if (li1<0) li1=0;
                ld1=-e1;
        }
        li2=s2.size()+e2;
        if ( e2>=0 ) {
                ld2=0;
        }
        else {
                if (li2<0) li2=0;
                ld2=-e2;
        }
        li=(li1>=li2)?li1:li2;        //整数位数
        ld=(ld1>=ld2)?ld1:ld2;        //小数位数
        std::string s(li+ld+1,'0');
        int qb1,        //第一串首位权数
            qe1,        //第一串末位权数
            qb2,        //第二串首位权数
            qe2;        //第二串末位权数
        qe1=li-e1;qb1=qe1-s1.size()+1;
        qe2=li-e2;qb2=qe2-s2.size()+1;
        char c1,c2;
        int m=0,j;
        for (j=li+ld;j>0;--j) {
                c1=(j>=qb1 && j<=qe1)?s1[j-qb1]:'0';
                c2=(j>=qb2 && j<=qe2)?s2[j-qb2]:'0';
                m=digitAdd(c1,c2,m);
                s[j]=c1;
        }
        if (m>0) {s[0]='1';s1=s;}
        else s1=s.substr(1);
        e1=-ld;
}
int decimal::digitAdd(char& c1,const char c2,const int car) {
        int i=c1+c2-48+car;
        int c=0;
        if (i>57) {i-=10;c=1;}
        c1=char(i);return c;
}
int decimal::digitSub(char& c1,const char c2,const int b) {
        int c=(c1>=c2+b)?0:1;
        int i=c1+(c*10)-c2+48-b;
        c1=char(i);
        return c;
}
char decimal::digitMult(char& c1,const char c2,const char m) {
        int i=(c1-4*(c2-4+(m-4;
        c1=i%10+48;
        return char(i/10+4;
}
int decimal::valCmp(const std::string& s1,const int e1,const std::string& s2,const int e2) const {
        unsigned int h1,h2;        //第一有效位的位置
        //去掉前导0
        for (h1=0;h1<s1.size() && (s1[h1]=='0');++h1) {}
        for (h2=0;h2<s2.size() && (s2[h2]=='0');++h2) {}
        if ( (h1<s1.size()) && ((s1.size()-h1+e1)>(s2.size()-h2+e2)) ) return 1;
        if ( ((s1.size()-h1+e1)<(s2.size()-h2+e2)) && (h1<s1.size()) ) return -1;
        int i,j;
        for (i=s1.size()-h1,j=s2.size()-h2;i>0 && j>0;--i,--j,++h1,++h2) {

                if (s1[h1]<s2[h2]) return -1;
                if (s1[h1]>s2[h2]) return 1;
        }
        if (i>j) {
                for (;i>0 && s1[h1]=='0';--i,++h1) {}
                return (i==0)?0:1;
        }
        if (i<j) {
                for (;j>0 && s2[h2]=='0';--j,++h2) {}
                return (j==0)?0:-1;
        }
        return 0;
}

decimal& decimal::decReg() {
        //消去前0和尾0，调整指数exp
        unsigned int b,e;
        for (b=0;b<val.size()-1 && val=='0';++b){}
        for (e=val.size()-1;e>b && val[e]=='0';--e,++exp){}
        if (b!=0 || e!=val.size()-1) val=val.substr(b,e-b+1);
        if (val.size()==1 && val[0]=='0') {exp=0;sn=PLUS;}        //值为“零”,指数应为0,符号认定为正
        return *this;
}
unsigned int midDigits(const decimal& d1,const decimal& d2) {
        //计算和或差中间变量的位数
        int li1,ld1,li2,ld2,li,ld;
        li1= d1.getVal().size()+d1.getExp();
        if ( d1.getExp()>=0 ) {
                li1=d1.getVal().size()+d1.getExp();
                ld1=0;
        }
        else {
                if (li1<0) li1=0;
                ld1=-d1.getExp();
        }
        li2=d2.getVal().size()+d2.getExp();
        if ( d2.getExp()>=0 ) {
                ld2=0;
        }
        else {
                if (li2<0) li2=0;
                ld2=-d2.getExp();
        }
        li=(li1>=li2)?li1:li2;        //整数位数
        ld=(ld1>=ld2)?ld1:ld2;        //小数位数
        return li+ld+1;
}

[ 本帖最后由 hqxyn 于 2006-8-22 19:55 编辑 ]

---

作者: flw    时间: 2006-08-22 10:36

原帖由 mirnshi 于 2006-8-21 15:02 发表
接口为10进制, 内部的进制采用unsigned long或unsigned short，是不是更能借助逻辑运算，提高效率？

我也这样想。
考虑到 unsigned int 在 32 位机上可以表示超过 10 亿的整数，因此倘若采用万进制来进行内部表示的话，效率应该会高很多。
至于加减法，可以直接用亿进制来进一步提高速度。

---

作者: hqxyn    时间: 2006-08-22 10:56
标题: 回复 12楼 flw 的帖子
开始我也曾用long long型作内部表示，但出于以下考虑，还是放弃了
1）要能表示”任意“大小的十进浮点数。
2）算术运算不能带来误差（用二进制数表示十进制小数总会有舍入误差）。
当然用字符型处理数值效率确实低，但这样作的最直接用途是处理货币类应用，并不是科学计算，也就将就了。

---

作者: yuxh    时间: 2006-08-22 12:30
我写这个类的目的是想实现判断一个数是否是素数, 其中第一步就是判断这个数是否某个数的整数次幂
所以我关心的是运算的效率,而不是把它扩展成浮点数形式等更适用的情况
由于在推导一些公式时就是用10进制来考虑的,所以写的代码里也是用10进制数表示的,其实,对代码作一些相应的改动,是很方便换成16进制或别的基进制,(也可以扩展成浮点数的形式,但对我的应用来说,意义不大).

[ 本帖最后由 yuxh 于 2006-8-22 12:38 编辑 ]

dec.JPG (48.31 KB, 下载次数: 57)

下载附件

2006-08-22 12:38 上传

基本运算的说明

---

作者: yuxh    时间: 2006-08-22 13:04
贴一段测试代码给大家玩玩

1. #include "decnum.h"
   
2. 
   
3. int main()
   
4. {
   
5.     decnum x, y, r;
   
6.     char *line = NULL;
   
7.     size_t  n = 0;
   
8.     int read;
   
9. 
   
10.     cout << "input x:" << endl;
    
11.     if((read = (int)getline(&line, &n, stdin)) != -1) {
    
12.         x = decnum(line, read-1);
    
13.     }
    
14.     else
    
15.         exit(-1);
    
16. 
    
17.     cout << "input y:" << endl;
    
18.     if((read = (int)getline(&line, &n, stdin)) != -1) {
    
19.         y = decnum(line, read-1);
    
20.     }
    
21.     else
    
22.         exit(-1);
    
23. 
    
24.     cout << "x = " << x << endl;
    
25.     cout << "y = " << y << endl;
    
26.     cout << "x * y =" << x * y << endl;
    
27.     cout << "x / y =" << x / y << endl;
    
28.     cout << "x % y =" << x % y << endl;
    
29.     cout << "div(x, y) =" << div(x , y, r) << endl;
    
30.     cout << "mod(x, y) =" << r << endl;
    
31.     cout << "y ^ 2 =" << pow(y, 2) << endl;
    
32.     cout << "x ^ 1/2 =" << root(x, 2) << endl;
    
33.     cout << "x is pow = " << x.ispow() << endl;
    
34. 
    
35.     return 0;
    
36. }

复制代码

input x:
12934891238741902347120934871230948712390487123904871239047812390847123094871230948712309487123904871230947123980471203948712309487120394712398471239048713256129834712903847120394781239084712930487231094712394087123094123481203333333333333333333333333333333333333333333888888888888888888888888888888888888888888888888222222222222222222222222222222222222221094387123908471293048721903487123908412903471290384712398471239847213984712938471209384172093847129834712093847123904123471290384712398471209348712093847120938471297340129341
input y:
87123904781239084712309487123094871230948712390487123
x = 12934891238741902347120934871230948712390487123904871239047812390847123094871230948712309487123904871230947123980471203948712309487120394712398471239048713256129834712903847120394781239084712930487231094712394087123094123481203333333333333333333333333333333333333333333888888888888888888888888888888888888888888888888222222222222222222222222222222222222221094387123908471293048721903487123908412903471290384712398471239847213984712938471209384172093847129834712093847123904123471290384712398471209348712093847120938471297340129341
y = 87123904781239084712309487123094871230948712390487123
x * y =1126938232639833173075933852454844491172426928514059866807740841770815249456423275828974308682129087476539239375374114934208988211619943619716558347499808789403504191997992053251495407207133672212198009872845450749525122406765537233683189166639249361344448037097903846536903047332910602617949715068386039572749284661323652396812507276858460341917936752512602597008627491342253724797935606421392773895578442187710885039658694980497445673861077574294718176507864939038642062979105391800654254681231524754223749316701123751673470225808955075291647887679573776980478625133783450814975943
x / y =148465467327484275048232812439334306695533671227089122007816650126394502951501427671718661140385906942393209068225081817296775831986299773922335101921640962699307587052445014486841122328740344708845214812651256032481988250472736002705523700302442398432754627409724200156670159012028113430398315975429449502269548763370786332836604219524721316400456079938591537603272259855595623013801608933716962712146970686555106278637839124034044858476557783789374654839217122223912234300207
x % y =79300951666803804539185154310166594060311523590394880
div(x, y) =148465467327484275048232812439334306695533671227089122007816650126394502951501427671718661140385906942393209068225081817296775831986299773922335101921640962699307587052445014486841122328740344708845214812651256032481988250472736002705523700302442398432754627409724200156670159012028113430398315975429449502269548763370786332836604219524721316400456079938591537603272259855595623013801608933716962712146970686555106278637839124034044858476557783789374654839217122223912234300207
mod(x, y) =79300951666803804539185154310166594060311523590394880
y ^ 2 =7590574784330414645380746230930586484532745231159928445672223588351361500455337820516206371351345228817129
x ^ 1/2 =3596510981318130543477927424759527967760623382196876121688918127992258229306117726707700713885454867164034990294666943466289844107281148419105171980209085534883218753821511324570335831894205011649807156193955342866243572062280023407886590191390520013437462254313721
x is pow = 0

---

作者: 思一克    时间: 2006-08-22 13:09
yuxh 弄了一个伟大的工程呀

---

作者: yuxh    时间: 2006-08-22 13:12

原帖由 思一克 于 2006-8-22 13:09 发表
yuxh 弄了一个伟大的工程呀

只是玩玩,呵呵~万里长征才走了第一步哇~

---

作者: xiaomiao    时间: 2006-08-22 15:16
提示: 作者被禁止或删除 内容自动屏蔽

---

作者: aple_smx    时间: 2006-08-22 15:29
提示: 作者被禁止或删除 内容自动屏蔽

---

作者: rushrush    时间: 2006-08-22 15:46
http://www.swox.com/gmp/

---

作者: 醉卧水云间    时间: 2006-08-22 16:42
AKS早有人测试过了，不灵。

---

作者: xiaomiao    时间: 2006-08-22 18:17
提示: 作者被禁止或删除 内容自动屏蔽

---

作者: yuxh    时间: 2006-08-23 18:17
增加了负数，但负数不支持取余(%)及相应的带余除法(div)
并用它解决了醉卧水云间 的pell方程的问题

---

作者: assiss    时间: 2006-08-23 18:29
你测试过你的大数库效率吗？
我曾经仔细优化我自己写的C大数库函数，但始终没有GMP的速度快。看GMP的代码，优化到了汇编地步。实在是恐怖。

---

作者: zengjin8310    时间: 2006-08-24 08:29

原帖由 yuxh 于 2006-8-22 12:30 发表
我写这个类的目的是想实现判断一个数是否是素数, 其中第一步就是判断这个数是否某个数的整数次幂
所以我关心的是运算的效率,而不是把它扩展成浮点数形式等更适用的情况
由于在推导一些公式时就是用10进制来考虑的,所以写的代码里也是用10进制数表示的,其实,对代码作一些相应的改动,是很方便换成16进制或别的基进制,(也可以扩展成浮点数的形式,但对我的应用来说,意义不大).

费马定理？  可以参考java RSA公私钥的生成算法， 我没研究过， 你看看那个素数寻找算法是不是比你的好

---

作者: zengjin8310    时间: 2006-08-24 08:32

原帖由 xiaomiao 于 2006-8-22 15:16 发表
搞科学计算最好不用C/C++，传统的用Fortran,现代流行的用Matlab,后者矩阵运算功能超级强大

matlab这个主要是给应用的人用， 科学计算是研究的东西跟matlab里面那一堆工具箱里面的算法实现类似的东西。 如果入门级科学计算matlab可以， 骨灰级的你不懂操作系统，不懂C/C++，lisp你给我试试看你能研究个啥

---

作者: ggggfjeicfh    时间: 2008-07-29 13:24
2^1000000用lisp一下就能算出来

---

作者: zhry0203203    时间: 2009-05-18 21:47
标题: 美中不足
美中不足。整个代码都没有注释。
别人很难看懂啊。

---

作者: zxrjkl    时间: 2010-04-29 12:52
2^4000000000 gmp 0.5s搞定；
科学计算在不太重视效率时可以用其他软件，但要重视效率时（如一算一星期时）
必须靠C/C++和汇编；
gmp的速度真的很可怕

---

作者: sling120    时间: 2010-04-29 14:40
mark

---

欢迎光临 Chinaunix (http://bbs.chinaunix.net/)

Powered by Discuz! X3.2