1 // This may look like C code, but it is really -*- C++ -*-
4 Copyright (C) 1988 Free Software Foundation
5 written by Doug Lea (dl@rocky.oswego.edu)
7 This file is part of the GNU C++ Library. This library is free
8 software; you can redistribute it and/or modify it under the terms of
9 the GNU Library General Public License as published by the Free
10 Software Foundation; either version 2 of the License, or (at your
11 option) any later version. This library is distributed in the hope
12 that it will be useful, but WITHOUT ANY WARRANTY; without even the
13 implied warranty of MERCHANTABILITY or FITNESS FOR A PARTICULAR
14 PURPOSE. See the GNU Library General Public License for more details.
15 You should have received a copy of the GNU Library General Public
16 License along with this library; if not, write to the Free Software
17 Foundation, 675 Mass Ave, Cambridge, MA 02139, USA.
28 struct IntRep // internal Integer representations
30 unsigned short len; // current length
31 unsigned short sz; // allocated space (0 means static).
32 short sgn; // 1 means >= 0; 0 means < 0
33 unsigned short s[1]; // represented as ushort array starting here
36 // True if REP is staticly (or manually) allocated,
37 // and should not be deleted by an Integer destructor.
38 #define STATIC_IntRep(rep) ((rep)->sz==0)
40 extern IntRep* Ialloc(IntRep*, const unsigned short *, int, int, int);
41 extern IntRep* Icalloc(IntRep*, int);
42 extern IntRep* Icopy_ulong(IntRep*, unsigned long);
43 extern IntRep* Icopy_long(IntRep*, long);
44 extern IntRep* Icopy(IntRep*, const IntRep*);
45 extern IntRep* Iresize(IntRep*, int);
46 extern IntRep* add(const IntRep*, int, const IntRep*, int, IntRep*);
47 extern IntRep* add(const IntRep*, int, long, IntRep*);
48 extern IntRep* multiply(const IntRep*, const IntRep*, IntRep*);
49 extern IntRep* multiply(const IntRep*, long, IntRep*);
50 extern IntRep* lshift(const IntRep*, long, IntRep*);
51 extern IntRep* lshift(const IntRep*, const IntRep*, int, IntRep*);
52 extern IntRep* bitop(const IntRep*, const IntRep*, IntRep*, char);
53 extern IntRep* bitop(const IntRep*, long, IntRep*, char);
54 extern IntRep* power(const IntRep*, long, IntRep*);
55 extern IntRep* div(const IntRep*, const IntRep*, IntRep*);
56 extern IntRep* mod(const IntRep*, const IntRep*, IntRep*);
57 extern IntRep* div(const IntRep*, long, IntRep*);
58 extern IntRep* mod(const IntRep*, long, IntRep*);
59 extern IntRep* I_compl(const IntRep*, IntRep*);
60 extern IntRep* abs(const IntRep*, IntRep*);
61 extern IntRep* negate(const IntRep*, IntRep*);
62 extern IntRep* pow(const IntRep*, long);
63 extern IntRep* gcd(const IntRep*, const IntRep* y);
64 extern int compare(const IntRep*, const IntRep*);
65 extern int compare(const IntRep*, long);
66 extern int ucompare(const IntRep*, const IntRep*);
67 extern int ucompare(const IntRep*, long);
68 extern char* Itoa(const IntRep* x, int base = 10, int width = 0);
69 extern char* cvtItoa(const IntRep* x, char* fmt, int& fmtlen, int base,
70 int showbase, int width, int align_right,
71 char fillchar, char Xcase, int showpos);
72 extern IntRep* atoIntRep(const char* s, int base = 10);
73 extern long Itolong(const IntRep*);
74 extern double Itodouble(const IntRep*);
75 extern int Iislong(const IntRep*);
76 extern int Iisdouble(const IntRep*);
77 extern long lg(const IntRep*);
79 extern IntRep _ZeroRep, _OneRep, _MinusOneRep;
88 Integer(unsigned long);
90 Integer(const Integer&);
94 void operator = (const Integer&);
95 void operator = (long);
97 // unary operations to self
101 void negate(); // negate in-place
102 void abs(); // absolute-value in-place
103 void complement(); // bitwise complement in-place
105 // assignment-based operations
107 void operator += (const Integer&);
108 void operator -= (const Integer&);
109 void operator *= (const Integer&);
110 void operator /= (const Integer&);
111 void operator %= (const Integer&);
112 void operator <<=(const Integer&);
113 void operator >>=(const Integer&);
114 void operator &= (const Integer&);
115 void operator |= (const Integer&);
116 void operator ^= (const Integer&);
118 void operator += (long);
119 void operator -= (long);
120 void operator *= (long);
121 void operator /= (long);
122 void operator %= (long);
123 void operator <<=(long);
124 void operator >>=(long);
125 void operator &= (long);
126 void operator |= (long);
127 void operator ^= (long);
129 // (constructive binary operations are inlined below)
132 //friend Integer operator <? (const Integer& x, const Integer& y); // min
133 //friend Integer operator >? (const Integer& x, const Integer& y); // max
136 // builtin Integer functions that must be friends
138 friend long lg (const Integer&); // floor log base 2 of abs(x)
139 friend double ratio(const Integer& x, const Integer& y);
140 // return x/y as a double
142 friend Integer gcd(const Integer&, const Integer&);
143 friend int even(const Integer&); // true if even
144 friend int odd(const Integer&); // true if odd
145 friend int sign(const Integer&); // returns -1, 0, +1
147 friend void (setbit)(Integer& x, long b); // set b'th bit of x
148 friend void clearbit(Integer& x, long b); // clear b'th bit
149 friend int testbit(const Integer& x, long b); // return b'th bit
151 // procedural versions of operators
153 friend void abs(const Integer& x, Integer& dest);
154 friend void negate(const Integer& x, Integer& dest);
155 friend void complement(const Integer& x, Integer& dest);
157 friend int compare(const Integer&, const Integer&);
158 friend int ucompare(const Integer&, const Integer&);
159 friend void add(const Integer& x, const Integer& y, Integer& dest);
160 friend void sub(const Integer& x, const Integer& y, Integer& dest);
161 friend void mul(const Integer& x, const Integer& y, Integer& dest);
162 friend void div(const Integer& x, const Integer& y, Integer& dest);
163 friend void mod(const Integer& x, const Integer& y, Integer& dest);
164 friend void divide(const Integer& x, const Integer& y,
165 Integer& q, Integer& r);
166 friend void I_and(const Integer& x, const Integer& y, Integer& dest);
167 friend void I_or(const Integer& x, const Integer& y, Integer& dest);
168 friend void I_xor(const Integer& x, const Integer& y, Integer& dest);
169 friend void lshift(const Integer& x, const Integer& y, Integer& dest);
170 friend void rshift(const Integer& x, const Integer& y, Integer& dest);
171 friend void pow(const Integer& x, const Integer& y, Integer& dest);
173 friend int compare(const Integer&, long);
174 friend int ucompare(const Integer&, long);
175 friend void add(const Integer& x, long y, Integer& dest);
176 friend void sub(const Integer& x, long y, Integer& dest);
177 friend void mul(const Integer& x, long y, Integer& dest);
178 friend void div(const Integer& x, long y, Integer& dest);
179 friend void mod(const Integer& x, long y, Integer& dest);
180 friend void divide(const Integer& x, long y, Integer& q, long& r);
181 friend void I_and(const Integer& x, long y, Integer& dest);
182 friend void I_or(const Integer& x, long y, Integer& dest);
183 friend void I_xor(const Integer& x, long y, Integer& dest);
184 friend void lshift(const Integer& x, long y, Integer& dest);
185 friend void rshift(const Integer& x, long y, Integer& dest);
186 friend void pow(const Integer& x, long y, Integer& dest);
188 friend int compare(long, const Integer&);
189 friend int ucompare(long, const Integer&);
190 friend void add(long x, const Integer& y, Integer& dest);
191 friend void sub(long x, const Integer& y, Integer& dest);
192 friend void mul(long x, const Integer& y, Integer& dest);
193 friend void I_and(long x, const Integer& y, Integer& dest);
194 friend void I_or(long x, const Integer& y, Integer& dest);
195 friend void I_xor(long x, const Integer& y, Integer& dest);
197 // coercion & conversion
199 int fits_in_long() const;
200 int fits_in_double() const;
202 operator long() const;
203 operator double() const;
205 friend char* Itoa(const Integer& x, int base = 10, int width = 0);
206 friend Integer atoI(const char* s, int base = 10);
207 void printon(std::ostream& s, int base = 10, int width = 0) const;
209 friend std::istream& operator >> (std::istream& s, Integer& y);
210 friend std::ostream& operator << (std::ostream& s, const Integer& y);
214 int initialized() const;
215 void error(const char* msg) const;
220 // (These are declared inline)
222 int operator == (const Integer&, const Integer&);
223 int operator == (const Integer&, long);
224 int operator != (const Integer&, const Integer&);
225 int operator != (const Integer&, long);
226 int operator < (const Integer&, const Integer&);
227 int operator < (const Integer&, long);
228 int operator <= (const Integer&, const Integer&);
229 int operator <= (const Integer&, long);
230 int operator > (const Integer&, const Integer&);
231 int operator > (const Integer&, long);
232 int operator >= (const Integer&, const Integer&);
233 int operator >= (const Integer&, long);
234 Integer operator - (const Integer&);
235 Integer operator ~ (const Integer&);
236 Integer operator + (const Integer&, const Integer&);
237 Integer operator + (const Integer&, long);
238 Integer operator + (long, const Integer&);
239 Integer operator - (const Integer&, const Integer&);
240 Integer operator - (const Integer&, long);
241 Integer operator - (long, const Integer&);
242 Integer operator * (const Integer&, const Integer&);
243 Integer operator * (const Integer&, long);
244 Integer operator * (long, const Integer&);
245 Integer operator / (const Integer&, const Integer&);
246 Integer operator / (const Integer&, long);
247 Integer operator % (const Integer&, const Integer&);
248 Integer operator % (const Integer&, long);
249 Integer operator << (const Integer&, const Integer&);
250 Integer operator << (const Integer&, long);
251 Integer operator >> (const Integer&, const Integer&);
252 Integer operator >> (const Integer&, long);
253 Integer operator & (const Integer&, const Integer&);
254 Integer operator & (const Integer&, long);
255 Integer operator & (long, const Integer&);
256 Integer operator | (const Integer&, const Integer&);
257 Integer operator | (const Integer&, long);
258 Integer operator | (long, const Integer&);
259 Integer operator ^ (const Integer&, const Integer&);
260 Integer operator ^ (const Integer&, long);
261 Integer operator ^ (long, const Integer&);
263 Integer abs(const Integer&); // absolute value
264 Integer sqr(const Integer&); // square
266 Integer pow(const Integer& x, const Integer& y);
267 Integer pow(const Integer& x, long y);
268 Integer Ipow(long x, long y); // x to the y as Integer
271 extern char* dec(const Integer& x, int width = 0);
272 extern char* oct(const Integer& x, int width = 0);
273 extern char* hex(const Integer& x, int width = 0);
274 extern Integer sqrt(const Integer&); // floor of square root
275 extern Integer lcm(const Integer& x, const Integer& y); // least common mult
278 typedef Integer IntTmp; // for backward compatibility
280 inline Integer::Integer() :rep(&_ZeroRep) {}
282 inline Integer::Integer(IntRep* r) :rep(r) {}
284 inline Integer::Integer(long y) :rep(Icopy_long(0, y)) {}
286 inline Integer::Integer(unsigned long y) :rep(Icopy_ulong(0, y)) {}
288 inline Integer::Integer(const Integer& y) :rep(Icopy(0, y.rep)) {}
290 inline Integer::~Integer() { if (rep && !STATIC_IntRep(rep)) delete rep; }
292 inline void Integer::operator = (const Integer& y)
294 rep = Icopy(rep, y.rep);
297 inline void Integer::operator = (long y)
299 rep = Icopy_long(rep, y);
302 inline Integer::operator long() const
307 inline int Integer::initialized() const
312 inline int Integer::fits_in_long() const
317 inline Integer::operator double() const
319 return Itodouble(rep);
322 inline int Integer::fits_in_double() const
324 return Iisdouble(rep);
327 // procedural versions
329 inline int compare(const Integer& x, const Integer& y)
331 return compare(x.rep, y.rep);
334 inline int ucompare(const Integer& x, const Integer& y)
336 return ucompare(x.rep, y.rep);
339 inline int compare(const Integer& x, long y)
341 return compare(x.rep, y);
344 inline int ucompare(const Integer& x, long y)
346 return ucompare(x.rep, y);
349 inline int compare(long x, const Integer& y)
351 return -compare(y.rep, x);
354 inline int ucompare(long x, const Integer& y)
356 return -ucompare(y.rep, x);
359 inline void add(const Integer& x, const Integer& y, Integer& dest)
361 dest.rep = add(x.rep, 0, y.rep, 0, dest.rep);
364 inline void sub(const Integer& x, const Integer& y, Integer& dest)
366 dest.rep = add(x.rep, 0, y.rep, 1, dest.rep);
369 inline void mul(const Integer& x, const Integer& y, Integer& dest)
371 dest.rep = multiply(x.rep, y.rep, dest.rep);
374 inline void div(const Integer& x, const Integer& y, Integer& dest)
376 dest.rep = div(x.rep, y.rep, dest.rep);
379 inline void mod(const Integer& x, const Integer& y, Integer& dest)
381 dest.rep = mod(x.rep, y.rep, dest.rep);
384 inline void I_and(const Integer& x, const Integer& y, Integer& dest)
386 dest.rep = bitop(x.rep, y.rep, dest.rep, '&');
389 inline void I_or(const Integer& x, const Integer& y, Integer& dest)
391 dest.rep = bitop(x.rep, y.rep, dest.rep, '|');
394 inline void I_xor(const Integer& x, const Integer& y, Integer& dest)
396 dest.rep = bitop(x.rep, y.rep, dest.rep, '^');
399 inline void lshift(const Integer& x, const Integer& y, Integer& dest)
401 dest.rep = lshift(x.rep, y.rep, 0, dest.rep);
404 inline void rshift(const Integer& x, const Integer& y, Integer& dest)
406 dest.rep = lshift(x.rep, y.rep, 1, dest.rep);
409 inline void pow(const Integer& x, const Integer& y, Integer& dest)
411 dest.rep = power(x.rep, long(y), dest.rep); // not incorrect
414 inline void add(const Integer& x, long y, Integer& dest)
416 dest.rep = add(x.rep, 0, y, dest.rep);
419 inline void sub(const Integer& x, long y, Integer& dest)
421 dest.rep = add(x.rep, 0, -y, dest.rep);
424 inline void mul(const Integer& x, long y, Integer& dest)
426 dest.rep = multiply(x.rep, y, dest.rep);
429 inline void div(const Integer& x, long y, Integer& dest)
431 dest.rep = div(x.rep, y, dest.rep);
434 inline void mod(const Integer& x, long y, Integer& dest)
436 dest.rep = mod(x.rep, y, dest.rep);
439 inline void I_and(const Integer& x, long y, Integer& dest)
441 dest.rep = bitop(x.rep, y, dest.rep, '&');
444 inline void I_or(const Integer& x, long y, Integer& dest)
446 dest.rep = bitop(x.rep, y, dest.rep, '|');
449 inline void I_xor(const Integer& x, long y, Integer& dest)
451 dest.rep = bitop(x.rep, y, dest.rep, '^');
454 inline void lshift(const Integer& x, long y, Integer& dest)
456 dest.rep = lshift(x.rep, y, dest.rep);
459 inline void rshift(const Integer& x, long y, Integer& dest)
461 dest.rep = lshift(x.rep, -y, dest.rep);
464 inline void pow(const Integer& x, long y, Integer& dest)
466 dest.rep = power(x.rep, y, dest.rep);
469 inline void abs(const Integer& x, Integer& dest)
471 dest.rep = abs(x.rep, dest.rep);
474 inline void negate(const Integer& x, Integer& dest)
476 dest.rep = negate(x.rep, dest.rep);
479 inline void complement(const Integer& x, Integer& dest)
481 dest.rep = I_compl(x.rep, dest.rep);
484 inline void add(long x, const Integer& y, Integer& dest)
486 dest.rep = add(y.rep, 0, x, dest.rep);
489 inline void sub(long x, const Integer& y, Integer& dest)
491 dest.rep = add(y.rep, 1, x, dest.rep);
494 inline void mul(long x, const Integer& y, Integer& dest)
496 dest.rep = multiply(y.rep, x, dest.rep);
499 inline void I_and(long x, const Integer& y, Integer& dest)
501 dest.rep = bitop(y.rep, x, dest.rep, '&');
504 inline void I_or(long x, const Integer& y, Integer& dest)
506 dest.rep = bitop(y.rep, x, dest.rep, '|');
509 inline void I_xor(long x, const Integer& y, Integer& dest)
511 dest.rep = bitop(y.rep, x, dest.rep, '^');
517 inline int operator == (const Integer& x, const Integer& y)
519 return compare(x, y) == 0;
522 inline int operator == (const Integer& x, long y)
524 return compare(x, y) == 0;
527 inline int operator != (const Integer& x, const Integer& y)
529 return compare(x, y) != 0;
532 inline int operator != (const Integer& x, long y)
534 return compare(x, y) != 0;
537 inline int operator < (const Integer& x, const Integer& y)
539 return compare(x, y) < 0;
542 inline int operator < (const Integer& x, long y)
544 return compare(x, y) < 0;
547 inline int operator <= (const Integer& x, const Integer& y)
549 return compare(x, y) <= 0;
552 inline int operator <= (const Integer& x, long y)
554 return compare(x, y) <= 0;
557 inline int operator > (const Integer& x, const Integer& y)
559 return compare(x, y) > 0;
562 inline int operator > (const Integer& x, long y)
564 return compare(x, y) > 0;
567 inline int operator >= (const Integer& x, const Integer& y)
569 return compare(x, y) >= 0;
572 inline int operator >= (const Integer& x, long y)
574 return compare(x, y) >= 0;
578 inline void Integer::operator += (const Integer& y)
580 add(*this, y, *this);
583 inline void Integer::operator += (long y)
585 add(*this, y, *this);
588 inline void Integer::operator ++ ()
590 add(*this, 1, *this);
594 inline void Integer::operator -= (const Integer& y)
596 sub(*this, y, *this);
599 inline void Integer::operator -= (long y)
601 sub(*this, y, *this);
604 inline void Integer::operator -- ()
606 add(*this, -1, *this);
611 inline void Integer::operator *= (const Integer& y)
613 mul(*this, y, *this);
616 inline void Integer::operator *= (long y)
618 mul(*this, y, *this);
622 inline void Integer::operator &= (const Integer& y)
624 I_and(*this, y, *this);
627 inline void Integer::operator &= (long y)
629 I_and(*this, y, *this);
632 inline void Integer::operator |= (const Integer& y)
634 I_or(*this, y, *this);
637 inline void Integer::operator |= (long y)
639 I_or(*this, y, *this);
643 inline void Integer::operator ^= (const Integer& y)
645 I_xor(*this, y, *this);
648 inline void Integer::operator ^= (long y)
650 I_xor(*this, y, *this);
655 inline void Integer::operator /= (const Integer& y)
657 div(*this, y, *this);
660 inline void Integer::operator /= (long y)
662 div(*this, y, *this);
666 inline void Integer::operator %= (const Integer& y)
668 *this = *this % y; // mod(*this, y, *this) doesn't work.
671 inline void Integer::operator %= (long y)
673 *this = *this % y; // mod(*this, y, *this) doesn't work.
677 inline void Integer::operator <<= (const Integer& y)
679 lshift(*this, y, *this);
682 inline void Integer::operator <<= (long y)
684 lshift(*this, y, *this);
688 inline void Integer::operator >>= (const Integer& y)
690 rshift(*this, y, *this);
693 inline void Integer::operator >>= (long y)
695 rshift(*this, y, *this);
700 inline Integer operator <? (const Integer& x, const Integer& y)
702 return (compare(x.rep, y.rep) <= 0) ? x : y;
705 inline Integer operator >? (const Integer& x, const Integer& y)
707 return (compare(x.rep, y.rep) >= 0)? x : y;
713 inline void Integer::abs()
718 inline void Integer::negate()
720 ::negate(*this, *this);
724 inline void Integer::complement()
726 ::complement(*this, *this);
730 inline int sign(const Integer& x)
732 return (x.rep->len == 0) ? 0 : ( (x.rep->sgn == 1) ? 1 : -1 );
735 inline int even(const Integer& y)
737 return y.rep->len == 0 || !(y.rep->s[0] & 1);
740 inline int odd(const Integer& y)
742 return y.rep->len > 0 && (y.rep->s[0] & 1);
745 inline char* Itoa(const Integer& y, int base, int width)
747 return Itoa(y.rep, base, width);
752 inline long lg(const Integer& x)
757 // constructive operations
759 inline Integer operator + (const Integer& x, const Integer& y)
761 Integer r; add(x, y, r); return r;
764 inline Integer operator + (const Integer& x, long y)
766 Integer r; add(x, y, r); return r;
769 inline Integer operator + (long x, const Integer& y)
771 Integer r; add(x, y, r); return r;
774 inline Integer operator - (const Integer& x, const Integer& y)
776 Integer r; sub(x, y, r); return r;
779 inline Integer operator - (const Integer& x, long y)
781 Integer r; sub(x, y, r); return r;
784 inline Integer operator - (long x, const Integer& y)
786 Integer r; sub(x, y, r); return r;
789 inline Integer operator * (const Integer& x, const Integer& y)
791 Integer r; mul(x, y, r); return r;
794 inline Integer operator * (const Integer& x, long y)
796 Integer r; mul(x, y, r); return r;
799 inline Integer operator * (long x, const Integer& y)
801 Integer r; mul(x, y, r); return r;
804 inline Integer sqr(const Integer& x)
806 Integer r; mul(x, x, r); return r;
809 inline Integer operator & (const Integer& x, const Integer& y)
811 Integer r; I_and(x, y, r); return r;
814 inline Integer operator & (const Integer& x, long y)
816 Integer r; I_and(x, y, r); return r;
819 inline Integer operator & (long x, const Integer& y)
821 Integer r; I_and(x, y, r); return r;
824 inline Integer operator | (const Integer& x, const Integer& y)
826 Integer r; I_or(x, y, r); return r;
829 inline Integer operator | (const Integer& x, long y)
831 Integer r; I_or(x, y, r); return r;
834 inline Integer operator | (long x, const Integer& y)
836 Integer r; I_or(x, y, r); return r;
839 inline Integer operator ^ (const Integer& x, const Integer& y)
841 Integer r; I_xor(x, y, r); return r;
844 inline Integer operator ^ (const Integer& x, long y)
846 Integer r; I_xor(x, y, r); return r;
849 inline Integer operator ^ (long x, const Integer& y)
851 Integer r; I_xor(x, y, r); return r;
854 inline Integer operator / (const Integer& x, const Integer& y)
856 Integer r; div(x, y, r); return r;
859 inline Integer operator / (const Integer& x, long y)
861 Integer r; div(x, y, r); return r;
864 inline Integer operator % (const Integer& x, const Integer& y)
866 Integer r; mod(x, y, r); return r;
869 inline Integer operator % (const Integer& x, long y)
871 Integer r; mod(x, y, r); return r;
874 inline Integer operator << (const Integer& x, const Integer& y)
876 Integer r; lshift(x, y, r); return r;
879 inline Integer operator << (const Integer& x, long y)
881 Integer r; lshift(x, y, r); return r;
884 inline Integer operator >> (const Integer& x, const Integer& y)
886 Integer r; rshift(x, y, r); return r;
889 inline Integer operator >> (const Integer& x, long y)
891 Integer r; rshift(x, y, r); return r;
894 inline Integer pow(const Integer& x, long y)
896 Integer r; pow(x, y, r); return r;
899 inline Integer Ipow(long x, long y)
901 Integer r(x); pow(r, y, r); return r;
904 inline Integer pow(const Integer& x, const Integer& y)
906 Integer r; pow(x, y, r); return r;
911 inline Integer abs(const Integer& x)
913 Integer r; abs(x, r); return r;
916 inline Integer operator - (const Integer& x)
918 Integer r; negate(x, r); return r;
921 inline Integer operator ~ (const Integer& x)
923 Integer r; complement(x, r); return r;
926 inline Integer atoI(const char* s, int base)
928 Integer r; r.rep = atoIntRep(s, base); return r;
931 inline Integer gcd(const Integer& x, const Integer& y)
933 Integer r; r.rep = gcd(x.rep, y.rep); return r;
936 #endif /* !_Integer_h */