![[BACK]](/cvsweb/icons/back.gif){kind=icon}
Return to bignum.h CVS log ![[TXT]](/cvsweb/icons/text.gif){kind=icon}
![[DIR]](/cvsweb/icons/dir.gif){kind=icon}
Up to [Research Unix] / researchv10no / cmd / cfront / libC / bignum|
Return to bignum.h CVS log | Up to [Research Unix] / researchv10no / cmd / cfront / libC / bignum |
1.1 root 1: //
2: // C++ multiple precision integer arithmetic library.
3: //
4:
5: #ifndef BIGNUM_H
6: #define BIGNUM_H
7: #include <stream.h>
8:
9: typedef void (*OutFn)(char);
10:
11: class INT_REP {
12:
13: short refcnt; // Reference count.
14: long *wt; // First unused space.
15: long *beg; // Start of allocated memory.
16: long *last; // End of allocated memory.
17:
18: INT_REP (INT_REP *); // Duplicate INT_REP.
19:
20: void More (); // Realloc.
21: void Zero(); // Zero out everything.
22: void Print(iostream &); // Print using iostream.
23: void Print(OutFn, int); // Print using user supplied fn.
24: void Prt(); // Print internal representation.
25: void Chsign (); // Change sign.
26: void StripZero(); // Strip redundant zeros.
27: void StripMinus(); // Strip redundant -1's.
28: int Twos();
29:
30: int Length() { return (wt-beg); }
31: int isNegative() { return ((wt > beg) && (*(wt-1) < 0)); }
32: int isZero () { return (wt == beg); }
33: int isNonzero () { return (wt != beg); }
34: int isOdd () { return (*beg & 0x1); } // Assuming positive.
35: int isEven () { return (!(*beg & 0x1)); } // Assuming positive.
36: void SetZero () { wt = beg; }
37: void Putc(long c) { if (wt==last) More(); *wt++ = c; }
38: void Alterc(int c, long *p) { if (p == last) More(); *p++ = c; if (p > wt) wt = p; }
39:
40: void FillDec(char *, char *);
41: void FillHex(char *, char *);
42: void FillOct(char *, char *);
43: void FillLong(unsigned long);
44:
45: INT_REP *PutDec();
46: INT_REP *PutHex();
47: INT_REP *PutOct();
48:
49: int Store(char *, int, int);
50:
51: int Comp(INT_REP *);
52: long Trunc(int &);
53: INT_REP *Add(INT_REP *);
54: INT_REP *Sub(INT_REP *);
55: INT_REP *Mult(INT_REP *);
56: INT_REP *DivMod(INT_REP *, int);
57: INT_REP *Div(INT_REP *b) { return DivMod(b,0); }
58: INT_REP *Mod(INT_REP *b) { return DivMod(b,1); }
59: INT_REP *Exp(INT_REP *b);
60: INT_REP *GCD(INT_REP *b);
61:
62: INT_REP *And(INT_REP *);
63: INT_REP *Or(INT_REP *);
64: INT_REP *Xor(INT_REP *);
65: INT_REP *Not();
66: INT_REP *LeftShift(long);
67: INT_REP *RightShift(long);
68: INT_REP *LeftShift(INT_REP *);
69: INT_REP *RightShift(INT_REP *);
70:
71: public :
72:
73: static void IRMorehd ();
74:
75: INT_REP (int, int = 1); // Create INT_REP of specified size.
76: INT_REP (long); // Create INT_REP of long.
77: INT_REP (char *); // Create INT_REP from ascii representation.
78: ~INT_REP ();
79:
80: friend class INT;
81: friend INT_REP *IRAllocRep ();
82: friend INT operator >> (INT b, long a);
83: friend INT operator << (INT b, long a);
84: };
85:
86: extern INT_REP ZeroRep;
87:
88: class INT {
89: INT_REP *rep;
90:
91: INT Reset (INT_REP *newrep)
92: {
93: rep->refcnt--;
94: if (rep->refcnt == 0)
95: delete rep;
96: rep = newrep;
97: rep->refcnt++;
98: return (*this);
99: }
100:
101: void Print(iostream &i) // Print decimal representation on iostream.
102: { rep->Print(i); }
103:
104: public :
105:
106: INT(long i) // Initialized to i.
107: { rep = new INT_REP (i); if (rep) rep->refcnt++; }
108: INT () // Initialized to zero.
109: { rep = &ZeroRep; rep->refcnt++; }
110: INT (INT_REP *r) // For return values from INT_REP operations.
111: { rep = r; if(r) r->refcnt++; }
112: INT (INT &a) // For assignment.
113: { rep = a.rep; if(rep) rep->refcnt++; }
114: INT (char *s) // Character representation, in decimal, octal or hex.
115: { rep = new INT_REP (s); if(rep) rep->refcnt++; }
116: ~INT ()
117: { rep->refcnt--; if(rep->refcnt == 0) delete rep; }
118:
119: // Assignment operators.
120: INT operator= (INT &a) { return (Reset (a.rep)); }
121: INT operator+= (INT &a) { return (Reset (rep->Add(a.rep))); }
122: INT operator-= (INT &a) { return (Reset (rep->Sub(a.rep))); }
123: INT operator*= (INT &a) { return (Reset (rep->Mult(a.rep))); }
124: INT operator/= (INT &a) { return (Reset (rep->Div(a.rep))); }
125: INT operator%= (INT &a) { return (Reset (rep->Mod(a.rep))); }
126: INT operator|= (INT &a) { return (Reset (rep->Or(a.rep))); }
127: INT operator&= (INT &a) { return (Reset (rep->And(a.rep))); }
128: INT operator^= (INT &a) { return (Reset (rep->Xor(a.rep))); }
129: INT operator<<= (INT &a) { return (Reset (rep->LeftShift(a.rep))); }
130: INT operator>>= (INT &a) { return (Reset (rep->RightShift(a.rep))); }
131:
132: // Increment/decrement.
133: INT operator++ () { INT_REP orep(1l); return (Reset (rep->Add(&orep))); }
134: INT operator-- () { INT_REP orep(-1l); return (Reset (rep->Add(&orep))); }
135:
136: // Binary arithmetic operators.
137: INT operator + (INT b) { return INT(rep->Add(b.rep)); }
138: INT operator - (INT b) { return INT(rep->Sub(b.rep)); }
139: INT operator * (INT b) { return INT(rep->Mult(b.rep)); }
140: INT operator / (INT b) { return INT(rep->Div(b.rep)); }
141: INT operator % (INT b) { return INT(rep->Mod(b.rep)); }
142:
143: // Logical operators.
144: int operator <= (INT b) { return (rep->Comp(b.rep) == 1 ? 0 : 1); }
145: int operator >= (INT b) { return (rep->Comp(b.rep) == -1 ? 0 : 1); }
146: int operator < (INT b) { return (rep->Comp(b.rep) == -1 ? 1 : 0); }
147: int operator > (INT b) { return (rep->Comp(b.rep) == 1 ? 1 : 0); }
148: int operator == (INT b) { return (rep->Comp(b.rep) == 0 ? 1 : 0); }
149: int operator != (INT b) { return (rep->Comp(b.rep) == 0 ? 0 : 1); }
150: int operator ! () { return (rep->isZero() ? 1 : 0); }
151: int operator || (INT b)
152: { return (rep->isNonzero()>0 ? 1 : (b.rep->isNonzero()>0 ? 1 : 0)); }
153: int operator && (INT b)
154: { return (rep->isZero() ? 0 : (b.rep->isZero() ? 0 : 1)); }
155:
156: // Bitwise operators.
157: INT operator >> (INT b) { return INT(rep->RightShift(b.rep)); }
158: INT operator << (INT b) { return INT(rep->LeftShift(b.rep)); }
159: INT operator | (INT b) { return INT(rep->Or(b.rep)); }
160: INT operator & (INT b) { return INT(rep->And(b.rep)); }
161: INT operator ^ (INT b) { return INT(rep->Xor(b.rep)); }
162: INT operator ~ () { return INT(rep->Not()); }
163:
164: // Miscellaneous.
165: INT operator - () // Unary minus.
166: { INT_REP *b = new INT_REP(rep); b->Chsign(); return INT(b); }
167: INT Exp (INT b) // Exponentiate this to the given power.
168: { return INT(rep->Exp(b.rep)); }
169: INT GCD (INT b) // GCD of this and parameter.
170: { return INT(rep->GCD(b.rep)); }
171: long Long(int &error) // Convert this to signed long;
172: { return (rep->Trunc(error)); } // if bits are lost, error will be nonzero.
173: operator void * ()
174: { return (rep->isZero() ? (void *)0 : (void *)rep); }
175:
176: // Output.
177: int Dec (char *buf, int buflen = -1) { return (rep->Store (buf, buflen, 0)); }
178: int Oct (char *buf, int buflen = -1) { return (rep->Store (buf, buflen, 1)); }
179: int Hex (char *buf, int buflen = -1) { return (rep->Store (buf, buflen, 2)); }
180: void Dec (OutFn fn) { rep->Print (fn, 0); }
181: void Oct (OutFn fn) { rep->Print (fn, 1); }
182: void Hex (OutFn fn) { rep->Print (fn, 2); }
183: friend iostream & operator << (iostream &i, INT n)
184: { n.Print(i); return(i); }
185: #ifdef DEBUG
186: void Prt() // Print internal representation.
187: { rep->Prt(); }
188: #endif DEBUG
189:
190: // Friends.
191: friend INT operator >> (INT b, long a);
192: friend INT operator << (INT b, long a);
193:
194: };
195:
196:
197: /* Mixed long and INT functions. */
198:
199: // Binary arithmetic operators.
200: inline INT operator + (long a, INT b) { return (INT(a) + b); }
201: inline INT operator + (INT b, long a) { return (INT(a) + b); }
202: inline INT operator - (long a, INT b) { return (INT(a) - b); }
203: inline INT operator - (INT b, long a) { return (INT(a) - b); }
204: inline INT operator * (long a, INT b) { return (INT(a) * b); }
205: inline INT operator * (INT b, long a) { return (INT(a) * b); }
206: inline INT operator / (long a, INT b) { return (INT(a) / b); }
207: inline INT operator / (INT b, long a) { return (INT(a) / b); }
208: inline INT operator % (long a, INT b) { return (INT(a) % b); }
209: inline INT operator % (INT b, long a) { return (INT(a) % b); }
210:
211: // Logical operators.
212: inline int operator <= (long a, INT b) { return (INT(a) <= b); }
213: inline int operator <= (INT b, long a) { return (INT(a) <= b); }
214: inline int operator >= (long a, INT b) { return (INT(a) >= b); }
215: inline int operator >= (INT b, long a) { return (INT(a) >= b); }
216: inline int operator < (long a, INT b) { return (INT(a) < b); }
217: inline int operator < (INT b, long a) { return (INT(a) < b); }
218: inline int operator > (long a, INT b) { return (INT(a) > b); }
219: inline int operator > (INT b, long a) { return (INT(a) > b); }
220: inline int operator == (long a, INT b) { return (INT(a) == b); }
221: inline int operator == (INT b, long a) { return (INT(a) == b); }
222: inline int operator != (long a, INT b) { return (INT(a) != b); }
223: inline int operator != (INT b, long a) { return (INT(a) != b); }
224: inline int operator || (long a, INT b) { return (a ? 1 : (b ? 1 : 0)); }
225: inline int operator || (INT b, long a) { return (b ? 1 : (a ? 1 : 0)); }
226: inline int operator && (long a, INT b) { return (a==0 ? 0 : (b ? 1 : 0)); }
227: inline int operator && (INT b, long a) { return (!b ? 0 : (a==0 ? 0 : 1)); }
228:
229: // Bitwise operators.
230: inline INT operator >> (long a, INT b) { return (INT(a)>>b); }
231: inline INT operator >> (INT b, long a) { return INT(b.rep->RightShift(a)); }
232: inline INT operator << (long a, INT b) { return (INT(a)<<b); }
233: inline INT operator << (INT b, long a) { return INT(b.rep->LeftShift(a)); }
234: inline INT operator | (long a, INT b) { return (INT(a) | b); }
235: inline INT operator | (INT b, long a) { return (INT(a) | b); }
236: inline INT operator & (long a, INT b) { return (INT(a) & b); }
237: inline INT operator & (INT b, long a) { return (INT(a) & b); }
238: inline INT operator ^ (long a, INT b) { return (INT(a) ^ b); }
239: inline INT operator ^ (INT b, long a) { return (INT(a) ^ b); }
240:
241: // Miscellaneous functions.
242: overload Exp;
243: overload GCD;
244: inline INT Exp (long a, INT b) { return (INT(a).Exp(b)); }
245: inline INT Exp (INT b, long a) { return (b.Exp(INT(a))); }
246: inline INT GCD (long a, INT b) { return (b.GCD(INT(a))); }
247: inline INT GCD (INT b, long a) { return (b.GCD(INT(a))); }
248:
249: #endif BIGNUM_H
This archive runs on limited infrastructure. Preserving old code on modern bandwidth. Automated agents are requested to crawl responsibly.