1 /*==============================================================================
  2 |
  3 |  NAME
  4 |
  5 |      ppBigInt.h
  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.1 - A Program for Computing Primitive Polynomials.
 17 |     Copyright (C) 1999-2021 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 
 61 class 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 
 85 class 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 
109 class 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 
127 class 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 
148 class 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 
169 class 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 
224 class 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.
429 BigInt 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 
444 const bool testBit( const ppuint n, const int bitNum ) ;
445 
446 #endif // __PP_BIGINT_H__ --- End of wrapper for header file.