1/*==============================================================================
2|
3| NAME
4|
5| ppBigInt.hpp
6|
7| DESCRIPTION
8|
9| Header for non-negative multiple precision integer arithmetic classes.
10|
11| User manual and technical documentation are described in detail in my web page at
12| http://seanerikoconnor.freeservers.com/Mathematics/AbstractAlgebra/PrimitivePolynomials/overview.html
13|
14| LEGAL
15|
16| Primpoly Version 16.3 - A Program for Computing Primitive Polynomials.
17| Copyright (C) 1999-2024 by Sean Erik O'Connor. All Rights Reserved.
18|
19| This program is free software: you can redistribute it and/or modify
20| it under the terms of the GNU General Public License as published by
21| the Free Software Foundation, either version 3 of the License, or
22| (at your option) any later version.
23|
24| This program is distributed in the hope that it will be useful,
25| but WITHOUT ANY WARRANTY; without even the implied warranty of
26| MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
27| GNU General Public License for more details.
28|
29| You should have received a copy of the GNU General Public License
30| along with this program. If not, see http://www.gnu.org/licenses/.
31|
32| The author's address is seanerikoconnor!AT!gmail!DOT!com
33| with the !DOT! replaced by . and the !AT! replaced by @
34|
35==============================================================================*/
36
37// Wrap this header file to prevent duplication if it is included
38// accidentally more than once.
39#ifndef __PP_BIGINT_H__
40#define __PP_BIGINT_H__
41
42
43/*=============================================================================
44|
45| NAME
46|
47| BigIntMathError General math error, including internal memory errors.
48| BigIntUnderflow Underflow.
49| BigIntOverflow Overflow.
50| BigIntZeroDivide Zero divide.
51| BigIntRangeError Input range error.
52| BigIntDomainError Input domain error, i.e. log(-1).
53|
54| DESCRIPTION
55|
56| Exception classes for the BigInt class
57| derived from the STL exception class runtime_error.
58|
59+============================================================================*/
60
61class BigIntMathError : public runtime_error
62{
63 public:
64 // Throw with error message, file name and line number.
65 BigIntMathError( const string & description, const string & file, const int & line )
66 : runtime_error( description + " in file " + file + " at line " + to_string(line) )
67 {
68 } ;
69
70 // Throw with an error message.
71 BigIntMathError( const string & description )
72 : runtime_error( description )
73 {
74 } ;
75
76 // Default throw with no error message.
77 BigIntMathError()
78 : runtime_error( "BigInt math error: " )
79 {
80 } ;
81
82} ; // end class BigIntMathError
83
84
85class BigIntRangeError : public BigIntMathError
86{
87 public:
88 // Throw with error message, file name and line number.
89 BigIntRangeError( const string & description, const string & file, const int & line )
90 : BigIntMathError( description + " in file " + file + " at line " + to_string(line) )
91 {
92 } ;
93
94 // Throw with an error message.
95 BigIntRangeError( const string & description )
96 : BigIntMathError( description )
97 {
98 } ;
99
100 // Default throw with no error message.
101 BigIntRangeError()
102 : BigIntMathError( "BigInt range error: " )
103 {
104 } ;
105
106} ; // end class BigIntRangeError
107
108
109class BigIntDomainError : public BigIntMathError
110{
111 public:
112 // Throw with an error message.
113 BigIntDomainError( const string & description )
114 : BigIntMathError( description )
115 {
116 } ;
117
118 // Default throw with no error message.
119 BigIntDomainError()
120 : BigIntMathError( "BigInt domain error: " )
121 {
122 } ;
123
124} ; // end class BigIntDomainError
125
126
127class BigIntOverflow : public BigIntMathError
128{
129 public:
130 // Throw with error message, file name and line number.
131 BigIntOverflow( const string & description, const string & file, const int & line )
132 : BigIntMathError( description + " in file " + file + " at line " + to_string(line) )
133 {
134 } ;
135
136 BigIntOverflow( const string & description )
137 : BigIntMathError( description )
138 {
139 } ;
140
141 BigIntOverflow()
142 : BigIntMathError( "BigInt overflow. " )
143 {
144 }
145} ;
146
147
148class BigIntUnderflow : public BigIntMathError
149{
150 public:
151 // Throw with error message, file name and line number.
152 BigIntUnderflow( const string & description, const string & file, const int & line )
153 : BigIntMathError( description + " in file " + file + " at line " + to_string(line) )
154 {
155 } ;
156
157 BigIntUnderflow( const string & description )
158 : BigIntMathError( description )
159 {
160 } ;
161
162 BigIntUnderflow()
163 : BigIntMathError( "BigInt underflow. " )
164 {
165 }
166} ;
167
168
169class BigIntZeroDivide : public BigIntMathError
170{
171 public:
172 // Throw with error message, file name and line number.
173 BigIntZeroDivide( const string & description, const string & file, const int & line )
174 : BigIntMathError( description + " in file " + file + " at line " + to_string(line) )
175 {
176 } ;
177
178 BigIntZeroDivide( const string & description )
179 : BigIntMathError( description )
180 {
181 } ;
182
183 BigIntZeroDivide()
184 : BigIntMathError( "BigInt zero divide. " )
185 {
186 }
187} ;
188
189
190/*=============================================================================
191|
192| NAME
193|
194| BigInt
195|
196| DESCRIPTION
197|
198| Class for arbitrary precision non-negative integer arithmetic using any base.
199|
200| We support the basic operations + - * /
201| Also the C-like operators += -= *= /= ++ -- where some have mixed BigInt and integer
202| Comparisions < > <= >= == != where some have mixed BigInt and integer
203| I/O operations << >>
204| Conversion from ordinary integers, to ordinary integers (can throw an overflow exception)
205| Conversions to and from strings
206| Bit masking & shifting << bit test and num bits
207| power (not in BigInt class)
208| ceil( lg() )
209|
210| We throw one of the following exceptions,
211|
212| BigIntMathError General math error.
213| BigIntRangeError Range error on input.
214| BigIntUnderflow Underflow.
215| BigIntOverflow Overflow.
216| BigIntZeroDivide Zero divide.
217|
218| NOTES
219|
220| The member functions and friends are documented in detail ppBigInt.cpp
221|
222+============================================================================*/
223
224class BigInt
225{
226 public:
227 //-----------------< Basic mathematical operations >------------------
228
229 // *** Constructors.
230
231 // Default constructor.
232 // e.g. BigInt u ;
233 BigInt() ;
234
235 // Destructor.
236 ~BigInt() ;
237
238 // Constructor from unsigned integers.
239 // Use explicit on these one argument constructors to prevent the compiler doing any
240 // implicit conversions from integers to BigInts. This should have been the C++ language default.
241 explicit BigInt( const ppuint d ) ;
242 explicit BigInt( const ppuint32 d ) ;
243
244 // Constructor from decimal number string.
245 // e.g. string s = "314159" ; BigInt w( s ) ;
246 explicit BigInt( const string & s ) ;
247
248 // Copy constructor.
249 // e.g. BigInt u ; BigInt v( u ) ;
250 BigInt( const BigInt & u ) ;
251
252 // Assignment.
253 // e.g. BigInt u( "123" ) ; BigInt v ; v = u ;
254 BigInt & operator=( const BigInt & n ) ;
255
256 // Conversion to int.
257 // e.g. BigInt( w ) = "123" ; ppuint u = static_cast<int>( w ) ;
258 operator ppuint() const ;
259
260
261 // *** Input and output operators.
262
263 // e.g. ostringstream os ; os << u ;
264 friend ostream & operator<<( ostream & out, const BigInt & u ) ;
265
266 // e.g. istringstream is ; is >> u ;
267 friend istream & operator>>( istream & in, BigInt & u ) ;
268
269 // u + v and other additions.
270 friend const BigInt operator+( const BigInt & u, const BigInt & v ) ;
271
272 friend const BigInt operator+( const BigInt & u, const ppuint d ) ;
273
274 BigInt & operator+=( const BigInt & u ) ;
275
276 BigInt & operator+=( const ppuint d ) ;
277
278 // ++u and other increments.
279 BigInt & operator++() ;
280
281 const BigInt operator++( int ) ;
282
283 // u - v and other subtractions.
284 friend const BigInt operator-( const BigInt & u, const BigInt & v ) ;
285
286 friend const BigInt operator-( const BigInt & u, const ppuint d ) ;
287
288 BigInt & operator-=( const BigInt & u ) ;
289
290 BigInt & operator-=( const ppuint d ) ;
291
292 // --u and other decrements
293 BigInt & operator--() ;
294
295 BigInt operator--( int ) ;
296
297 // u * v, and other multiplies.
298 friend const BigInt operator*( const BigInt & u, const BigInt & v ) ;
299
300 friend const BigInt operator*( const BigInt & u, const ppuint d ) ;
301
302 BigInt & operator*=( const BigInt & u ) ;
303
304 BigInt & operator*=( ppuint d ) ;
305
306 // | u / v |, and other integer divides.
307 // -- --
308 friend const BigInt operator/( const BigInt & u, const BigInt & v ) ;
309
310 friend const BigInt operator/( const BigInt & u, const ppuint d ) ;
311
312 BigInt & operator/=( const BigInt & u ) ;
313
314 BigInt & operator/=( ppuint d ) ;
315
316 // u % v, and other integer moduli.
317 friend BigInt operator%( const BigInt & u, const BigInt & v ) ;
318
319 friend ppuint operator%( const BigInt & u, const ppuint d ) ;
320
321 // -- --
322 // | lg() |
323 int ceilLg() ;
324
325 // Comparisions including
326 // ==, == d, !=, != d, >, > d,
327 // <, < d, >=, >= d, <=, <= d,
328 friend bool operator==( const BigInt & u, const BigInt & v ) ;
329 friend bool operator==( const BigInt & u, const ppuint d ) ;
330 friend bool operator!=( const BigInt & u, const BigInt & v ) ;
331 friend bool operator!=( const BigInt & u, const ppuint d ) ;
332 friend bool operator> ( const BigInt & u, const BigInt & v ) ;
333 friend bool operator> ( const BigInt & u, const ppuint d ) ;
334 friend bool operator< ( const BigInt & u, const BigInt & v ) ;
335 friend bool operator< ( const BigInt & u, const ppuint d ) ;
336 friend bool operator>=( const BigInt & u, const BigInt & v ) ;
337 friend bool operator>=( const BigInt & u, const ppuint d ) ;
338 friend bool operator<=( const BigInt & u, const BigInt & v ) ;
339 friend bool operator<=( const BigInt & u, const ppuint d ) ;
340
341 // Bit masking, testing and setting.
342 friend BigInt operator& ( const BigInt & u, const BigInt & v ) ;
343
344 friend BigInt operator<<( const BigInt & u, ppuint n ) ;
345
346 const bool testBit( const int bitNum ) const ;
347
348 //-----------------< Helper functions >-------------------------------
349
350 // Conversion to decimal number string.
351 // e.g. BigInt u( "123" ) ; string s = u.toString() ;
352 string toString() const ;
353
354 // Helper functions for division and mod.
355 friend void divMod( const BigInt & u, const BigInt & v,
356 BigInt & q, BigInt & r ) ;
357
358 friend void divMod( const BigInt & u, const ppuint d,
359 BigInt & q, ppuint & r ) ;
360
361 // Highest bit number in a BigInt, 0 is smallest bit.
362 int maxBitNumber() const ;
363
364 // Used by the PolyParser and main for input range checking, so we use a class function
365 // not requiring us to instantiate a BigInt object.
366 static const ppuint getBase() ;
367
368 //-----------------< Unit Test Functions >----------------------------
369
370 friend const ppuint getDigit( const BigInt & u, const int n ) ;
371
372 friend const int getNumDigits( const BigInt & u ) ;
373
374 friend void setBase( const BigInt & u, const ppuint base ) ;
375
376 friend void printNumber( const BigInt & u, ostream & out ) ;
377
378 friend void printNumber( const BigInt & u ) ;
379
380 // Class variables shared among all classes.
381 // We use static functions instead of static variables to work
382 // around the C++ static member initialization order problem.
383 private:
384 // Base of the number system (a power of 2) and
385 // corresponding number of bits per digit.
386 static ppuint & base_() ;
387
388 // Pointer to number system base. Used for unit testing only.
389 static ppuint * pbase ;
390
391 static int & numBitsPerDigit_() ;
392
393 // Private data for member functions only.
394 private:
395 // Numbers are n-place quantities with base b digits,
396 // 2
397 // where b is guaranteed to fit into a digit and
398 // b is a power of 2.
399 //
400 // (u . . . u )
401 // n-1 0
402 //
403 // For programming ease, digits are stored in a vector of
404 // length n with the least significant digit at digit[ 0 ],
405 //
406 // +----+----+----+------+------+
407 // | u | u | u | | u |
408 // | 0 | 1 | 2 | ... | n-1 |
409 // +----+----+----+------+------+
410 //
411 vector<ppuint> digit_ ;
412} ;
413
414
415/*=============================================================================
416|
417| NAME
418|
419| power
420|
421| DESCRIPTION
422|
423| n
424| Does p for low precision p and n and high precision result.
425|
426+============================================================================*/
427
428// Don't quite fit into BigInt class.
429BigInt power( ppuint p, ppuint n ) ;
430
431
432/*=============================================================================
433|
434| NAME
435|
436| testBit
437|
438| DESCRIPTION
439|
440| Bit test for low precision integers.
441|
442+============================================================================*/
443
444const bool testBit( const ppuint n, const int bitNum ) ;
445
446#endif // __PP_BIGINT_H__ --- End of wrapper for header file.
