1/*==============================================================================
2|
3| NAME
4|
5| ppUnitTest.cpp
6|
7| DESCRIPTION
8|
9| Unit test for exercising all classes and methods.
10| User manual and technical documentation are described in detail in my web page at
11|
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
38/*------------------------------------------------------------------------------
39| Includes |
40------------------------------------------------------------------------------*/
41
42#include <cstdlib> // abort()
43#include <iostream> // Basic stream I/O.
44#include <iomanip> // I/O manipulators.
45#include <new> // set_new_handler()
46#include <cmath> // Basic math functions e.g. sqrt()
47#include <limits> // Numeric limits.
48#include <complex> // Complex data type and operations.
49#include <fstream> // File stream I/O.
50#include <sstream> // String stream I/O.
51#include <vector> // STL vector class.
52#include <string> // STL string class.
53#include <algorithm> // Iterators.
54#include <stdexcept> // Exceptions.
55#include <cassert> // assert()
56#include <array> // array type.
57
58using namespace std ; // So we don't need to say std::vector everywhere.
59
60
61/*------------------------------------------------------------------------------
62| PP Include Files |
63------------------------------------------------------------------------------*/
64
65#include "Primpoly.hpp" // Global functions.
66#include "ppArith.hpp" // Basic arithmetic functions.
67#include "ppBigInt.hpp" // Arbitrary precision integer arithmetic.
68#include "ppOperationCount.hpp" // OperationCount collection for factoring and poly finding.
69#include "ppFactor.hpp" // Prime factorization and Euler Phi.
70#include "ppPolynomial.hpp" // Polynomial operations and mod polynomial operations.
71#include "ppParser.hpp" // Parsing of polynomials and I/O services.
72
73
74#ifdef SELF_CHECK
75#include "ppUnitTest.hpp" // Complete unit test.
76
77/*=============================================================================
78 |
79 | NAME
80 |
81 | UnitTest
82 |
83 | DESCRIPTION
84 |
85 | Constructor for the class with a default file name.
86 |
87 | EXAMPLE
88 |
89 | try
90 | {
91 | UnitTest unitTest ;
92 | if (!unitTest.run())
93 | cerr << "Failed one or more unit tests!" << endl ;
94 | }
95 | catch( UnitTestError & e )
96 | {
97 | cerr << "Failed to run unit test suite at all!" << endl ;
98 | cerr << e.what() << endl ;
99 | }
100 |
101 +============================================================================*/
102
103UnitTest::UnitTest( const char * fileName )
104 : unit_test_log_file_name_( fileName )
105{
106 // Place results into a log file in the current directory.
107 // If the file can't be opened, just print results to the console.
108 fout_.open( unit_test_log_file_name_ ) ;
109
110 // Test this section of code by making the existing file read only:
111 // chmod 000 unitTest.log
112 if (!fout_)
113 {
114 cerr << "Unit test: cannot open output log file " << unit_test_log_file_name_ << endl ;
115 cerr << "Trying standard output to the console instead." << endl ;
116
117 // Test this section of code by changing "/dev/stdout to "/dev/nonsensewonsense/stdout" and recompiling.
118 fout_.open( "/dev/stdout", fstream::out ) ;
119
120 if (fout_.fail())
121 {
122 ostringstream os ;
123 os << "Unit test: cannot open the output log file " << unit_test_log_file_name_
124 << " and unable to log standard output to the console. "
125 << "Skipping the unit test self check" ;
126 throw UnitTestError( os.str(), __FILE__, __LINE__ ) ;
127 }
128 }
129
130 fout_ << "\nBegin unit testing..." ;
131}
132
133
134/*=============================================================================
135 |
136 | NAME
137 |
138 | ~UnitTest
139 |
140 | DESCRIPTION
141 |
142 | Destructor which closes the file.
143 |
144 +============================================================================*/
145
146UnitTest::~UnitTest()
147{
148 fout_.close() ;
149}
150
151
152/*=============================================================================
153|
154| NAME
155|
156| run
157|
158| DESCRIPTION
159|
160| Run all the unit tests. Return the overall test status.
161|
162+============================================================================*/
163
164bool UnitTest::run()
165{
166 bool status = true ;
167
168 try
169 {
170 // A C++ array is more lightweight and faster than a vector for this simple application.
171 array<bool,8> unitTestStatus ;
172 unitTestStatus.fill( true ) ;
173 int i = 0 ;
174
175 // Go thorough all the unit tests in order.
176 unitTestStatus[i++] = unitTestSystemFunctions() ;
177 unitTestStatus[i++] = unitTestBigIntBase10() ;
178 unitTestStatus[i++] = unitTestBigIntDefaultBase() ;
179 unitTestStatus[i++] = unitTestModPArithmetic() ;
180 unitTestStatus[i++] = unitTestFactoring() ;
181 unitTestStatus[i++] = unitTestPolynomials() ;
182 unitTestStatus[i++] = unitTestPolynomialOrder() ;
183 unitTestStatus[i++] = unitTestParser() ;
184
185 // True only if every single test passes.
186 for (i = 0 ; i < unitTestStatus.size() ; ++i)
187 status = status && unitTestStatus[ i ] ;
188 }
189 // One or more unit tests might throw an exception unexpectedly.
190 // This would be a bug since any unit test should catch and handle any exceptions it generates within
191 // the test itself and convert to a proper test status.
192 //
193 // Catch blocks should be in order from more specific to less specific, i.e. up the class hierarchy.
194 catch( PrimpolyError & e )
195 {
196 fout_ << ".........FAIL!\n caught exception type PrimpolyError: [ " << e.what() << " ] " << endl ;
197 status = false ;
198 }
199 catch( ParserError & e )
200 {
201 fout_ << ".........FAIL!\n caught exception type ParserError: [ " << e.what() << " ] " << endl ;
202 status = false ;
203 }
204 catch( FactorError & e )
205 {
206 fout_ << ".........FAIL!" << endl ;
207 fout_ << " caught FactorError: [ " << e.what() << " ] " << endl ;
208 status = false ;
209 }
210 catch( BigIntRangeError & e )
211 {
212 fout_ << ".........FAIL!\n caught exception type BigIntRangeError: [ " << e.what() << " ] " << endl ;
213 status = false ;
214 }
215 catch( BigIntDomainError & e )
216 {
217 fout_ << ".........FAIL!\n caught exception type BigIntDomainError: [ " << e.what() << " ] " << endl ;
218 status = false ;
219 }
220 catch( BigIntUnderflow & e )
221 {
222 fout_ << ".........FAIL!\n caught exception type BigIntUnderflow: [ " << e.what() << " ] " << endl ;
223 status = false ;
224 }
225 catch( BigIntOverflow & e )
226 {
227 fout_ << ".........FAIL!\n caught exception type BigIntOverflow: [ " << e.what() << " ] " << endl ;
228 status = false ;
229 }
230 catch( BigIntZeroDivide & e )
231 {
232 fout_ << ".........FAIL!\n caught exception type BigIntZeroDivide: [ " << e.what() << " ] " << endl ;
233 status = false ;
234 }
235 catch( BigIntMathError & e )
236 {
237 fout_ << ".........FAIL!\n caught exception type BigIntMathError: [ " << e.what() << " ] " << endl ;
238 status = false ;
239 }
240 catch( ArithModPError & e )
241 {
242 fout_ << ".........FAIL!\n caught exception type ArithModPError: [ " << e.what() << " ] " << endl ;
243 status = false ;
244 }
245 catch( PolynomialRangeError & e )
246 {
247 fout_ << ".........FAIL!\n caught exception type PolynomialRangeError: [ " << e.what() << " ] " << endl ;
248 status = false ;
249 }
250 catch( PolynomialError & e )
251 {
252 fout_ << ".........FAIL!\n caught exception type PolynomialError: [ " << e.what() << " ] " << endl ;
253 status = false ;
254 }
255 //
256 // Standard library exceptions.
257 //
258 catch( bad_alloc & e )
259 {
260 fout_ << ".........FAIL!\n caught exception type Caught bad_alloc exception: [ " << e.what() << " ] " << endl ;
261 status = false ;
262 }
263 catch( length_error & e )
264 {
265 fout_ << ".........FAIL!\n caught exception type Caught length_error exception: [ " << e.what() << " ] " << endl ;
266 status = false ;
267 }
268 catch( exception & e )
269 {
270 fout_ << ".........FAIL!\n caught exception type Standard library error: [ " << e.what() << " ] " << endl ;
271 status = false ;
272 }
273 // Catch all other uncaught exceptions, which would otherwise call terminate()
274 // which in turn calls abort() and which would halt this program.
275 //
276 // Limitations:
277 // We can't handle the case where terminate() gets called because the
278 // exception mechanism finds a corrupt stack or catches a destructor
279 // throwing an exception.
280 //
281 // Also we can't catch exceptions which are thrown by initializing or
282 // destructing global variables.
283 catch( ... )
284 {
285 fout_ << ".........FAIL!\n caught exception type uncaught exception" << endl ;
286 status = false ;
287 }
288
289 fout_ << "\nEnd unit testing..." ;
290
291 if (status)
292 fout_ << "\nCONGRATULATIONS! All tests passed!" << endl ;
293 else
294 fout_ << "\nSORRY. One or more unit tests failed!" << endl ;
295
296 fout_.close() ;
297
298 return status ;
299}
300
301
302bool UnitTest::unitTestSystemFunctions()
303{
304 bool status = true ;
305
306 #ifdef DEBUG_PP_FORCE_MEMORY_OVERLOAD
307 // Test resize() exceptions.
308 fout_ << "\nTEST: C++ resize a vector to > max_size dimensions. Did resize throw a length_error exception?" ;
309
310 // 30
311 // Typically 2 - 1.
312 vector<ppuint> testVector ;
313 size_t maxSize = testVector.max_size() ;
314
315 try
316 {
317 // Overload the vector.
318 testVector.resize( maxSize + 1 ) ;
319
320 fout_ << ".........FAIL!" << endl ;
321 fout_ << " resize did not throw an exception " << endl ;
322 status = false ;
323 }
324 catch( length_error & e )
325 {
326 fout_ << ".........PASS!" ;
327 }
328 catch( ... )
329 {
330 fout_ << ".........FAIL!" << endl ;
331 fout_ << " resize did not throw a length_error exception" << endl ;
332 status = false ;
333 }
334 #endif // DEBUG_PP_FORCE_MEMORY_OVERLOAD
335
336 #ifdef DEBUG_PP_FORCE_MEMORY_OVERLOAD
337 fout_ << "\nTEST: C++ overload memory for a vector. Did push_back throw an exception?" ;
338 try
339 {
340 // Overload memory.
341 for (int i = 1 ; i <= maxSize + 1 ; ++i)
342 testVector.push_back( 1000 ) ;
343
344 fout_ << ".........FAIL!" << endl ;
345 fout_ << " push_back did not throw an exception" << endl ;
346 status = false ;
347 }
348 catch( bad_alloc & e )
349 {
350 fout_ << ".........PASS!" ;
351 }
352 catch( ... )
353 {
354 fout_ << ".........FAIL!" << endl ;
355 fout_ << " push_back did not throw a bad_alloc exception" << endl ;
356 status = false ;
357 }
358 #endif // DEBUG_OVERLOADING_MEMORY
359
360 return status ;
361}
362
363
364
365bool UnitTest::unitTestBigIntBase10()
366{
367 bool status = true ;
368
369 // ------------------- Set to base 10 ----------------------
370 ppuint oldBase = 0 ; // Save the old default base.
371 {
372 // Instantiate a BigInt object and set its to base 10 to change the base for all BigInts.
373 BigInt w ;
374 oldBase = BigInt::getBase() ;
375 setBase( w, 10 ) ;
376 }
377
378 #ifdef DEBUG_PP_FORCE_UNIT_TEST_FAIL
379 { BigInt dummy ; setBase( dummy, 11 ) ; }
380 #endif
381
382 fout_ << "\nTEST: BigInt switching from base = " << oldBase << " to new base = " << 10 ;
383 {
384 // Check all BigInts have the new base of 10.
385 if (BigInt::getBase() != 10)
386 {
387 fout_ << ".........FAIL!" << endl ;
388 fout_ << " Current base is not 10 but rather = " << BigInt::getBase() << endl ;
389 status = false ;
390 }
391 else
392 fout_ << ".........PASS!" ;
393 }
394
395 fout_ << "\nTEST: BigInt u default constructor which gives u = 0." ;
396 {
397 BigInt u ;
398 if (getNumDigits(u) != 0)
399 {
400 fout_ << ".........FAIL!" << endl ;
401 fout_ << " u = " ; printNumber( u, fout_ ) ; fout_ << endl ;
402 status = false ;
403 }
404 else
405 fout_ << ".........PASS!" ;
406 }
407
408 fout_ << "\nTEST: Constructor BigInt u( d ) from ppuint d = 1234" ;
409 {
410 ppuint d{ 1234 } ;
411 BigInt u( d ) ;
412 if (getNumDigits( u ) == 4 && getDigit( u, 3 ) == 1 && getDigit( u, 2 ) == 2 && getDigit( u, 1 ) == 3 && getDigit( u, 0 ) == 4)
413 fout_ << ".........PASS!" ;
414 else
415 {
416 fout_ << ".........FAIL!" << endl ;
417 fout_ << " u = " ; printNumber( u, fout_ ) ; fout_ << endl ;
418 status = false ;
419 }
420 }
421
422 fout_ << "\nTEST: Constructor BigInt u( s ) from string s = \"1234\"" ;
423 {
424 string s = "1234" ;
425 BigInt u( s ) ;
426 if (getNumDigits( u ) == 4 && getDigit( u, 3 ) == 1 && getDigit( u, 2 ) == 2 && getDigit( u, 1 ) == 3 && getDigit( u, 0 ) == 4)
427 fout_ << ".........PASS!" ;
428 else
429 {
430 fout_ << ".........FAIL!" << endl ;
431 fout_ << " u = " ; printNumber( u, fout_ ) ; fout_ << endl ;
432 status = false ;
433 }
434 }
435
436 fout_ << "\nTEST: Constructor BigInt u( s ) from INVALID string s = \"12x34\"" ;
437 try
438 {
439 string s = "12x34" ;
440 BigInt u( s ) ;
441 fout_ << ".........FAIL!" << endl ;
442 fout_ << " u = " ; printNumber( u, fout_ ) ; fout_ << endl ;
443 status = false ;
444 }
445 catch( BigIntRangeError & e )
446 {
447 fout_ << ".........PASS!" ;
448 }
449
450 fout_ << "\nTEST: Copy constructor BigInt v( u ) from BigInt u( 123 )" ;
451 {
452 BigInt u( 123u ) ;
453 BigInt v( u ) ;
454
455 if (getNumDigits( u ) != getNumDigits( v ) ||
456 getDigit( u, 0 ) != getDigit( v, 0 ) ||
457 getDigit( u, 1 ) != getDigit( v, 1 ) ||
458 getDigit( u, 2 ) != getDigit( v, 2 ))
459 {
460 fout_ << ".........FAIL!" << endl ;
461 fout_ << " u = " ; printNumber( u, fout_ ) ; fout_ << endl ;
462 fout_ << " v = " ; printNumber( v, fout_ ) ; fout_ << endl ;
463 status = false ;
464 }
465 else
466 fout_ << ".........PASS!" ;
467 }
468
469 fout_ << "\nTEST: Assignment operator v = u from BigInt v and BigInt u( 123 )" ;
470 {
471 BigInt u( 123u ) ;
472 BigInt v ; // Don't use BigInt v = u because that would call the copy constructor.
473 v = u ;
474
475 if (getNumDigits( u ) != getNumDigits( v ) ||
476 getDigit( u, 0 ) != getDigit( v, 0 ) ||
477 getDigit( u, 1 ) != getDigit( v, 1 ) ||
478 getDigit( u, 2 ) != getDigit( v, 2 ))
479 {
480 fout_ << ".........FAIL!" << endl ;
481 fout_ << " u = " ; printNumber( u, fout_ ) ; fout_ << endl ;
482 fout_ << " v = " ; printNumber( v, fout_ ) ; fout_ << endl ;
483 status = false ;
484 }
485 else
486 fout_ << ".........PASS!" ;
487 }
488
489 fout_ << "\nTEST: Implicit casting ppuint d = u from BigInt u( \"01234\" )" ;
490 {
491 BigInt u( "01234" ) ;
492 ppuint d = u ;
493 if (d != static_cast<ppuint>(1234u))
494 {
495 fout_ << ".........FAIL!" << endl ;
496 fout_ << " u = " ; printNumber( u, fout_ ) ; fout_ << endl ;
497 fout_ << " d = " << d << endl ;
498 status = false ;
499 }
500 else
501 fout_ << ".........PASS!" ;
502
503 fout_ << "\nTEST: Explicit casting static_cast< ppuint >( u ) from BigInt u( \"01234\" )" ;
504 if (static_cast< ppuint >( u ) != static_cast< ppuint >( 1234u ))
505 {
506 fout_ << ".........FAIL!" << endl ;
507 fout_ << " u = " << endl ; printNumber( u, fout_ ) ; fout_ << endl ;
508 fout_ << " static_cast< ppuint > u = " << static_cast< ppuint >( u ) << endl ;
509 status = false ;
510 }
511 else
512 fout_ << ".........PASS!" ;
513 }
514
515 fout_ << "\nTEST: Check overflow during ui = static_cast< ppuint >(u) on BigInt u( \"3141592653589793238462643383279\" )" ;
516 try
517 {
518 BigInt u( "3141592653589793238462643383279" ) ;
519 ppuint ui{ static_cast<ppuint>(u) } ;
520
521 fout_ << ".........FAIL!" << endl ;
522 fout_ << " Casting BigInt to ppuint didn't overflow." << endl ;
523 fout_ << " u = " ; printNumber( u, fout_ ) ; fout_ << endl ;
524 fout_ << " ui = " << ui << endl ;
525 status = false ;
526 }
527 catch( BigIntOverflow & e )
528 {
529 // Should overflow!
530 fout_ << ".........PASS!" ;
531 }
532
533 fout_ << "\nTEST: Stream output os << u from BigInt u( \"1234567890\" )" ;
534 {
535 BigInt u( "1234567890" ) ;
536 ostringstream os ;
537 os << u ;
538 if (os.str() != "1234567890")
539 {
540 fout_ << ".........FAIL!" << endl ;
541 fout_ << " u = |" << u << "|" << endl ;
542 fout_ << " os.str() = |" << os.str() << "|" << endl ;
543 status = false ;
544 }
545 else
546 fout_ << ".........PASS!" ;
547 }
548
549 fout_ << "\nTEST: Stream input is >> u for BigInt u where we've loaded the stream is.str( \"314159265358979323846264\" )" ;
550 {
551 BigInt u ;
552 istringstream is ;
553 is.clear() ;
554 is.str( "314159265358979323846264" ) ;
555 is >> u ;
556
557 // Test by streaming out the BigInt and checking its string value.
558 ostringstream os ;
559 os << u ;
560 if (os.str() != "314159265358979323846264" )
561 {
562 fout_ << ".........FAIL!" << endl ;
563 fout_ << " BigInt = |" << u << "| is.str() = |" << is.str() << "|" << endl ;
564 status = false ;
565 }
566 else
567 fout_ << ".........PASS!" ;
568 }
569
570 fout_ << "\nTEST: Equality test BigInt u == ppuint d?" ;
571 {
572 BigInt u( "9" ) ;
573 ppuint d{ 9 } ;
574 if (u == d)
575 fout_ << ".........PASS!" ;
576 else
577 {
578 fout_ << ".........FAIL!" << endl ;
579 fout_ << " u = " ; printNumber( u, fout_ ) ; fout_ << endl ;
580 fout_ << " d = " << d << endl ;
581 status = false ;
582 }
583 }
584
585 fout_ << "\nTEST: Equality test BigInt u == BigInt v" ;
586 {
587 BigInt u( "1234" ) ;
588 BigInt v( "1234" ) ;
589 if (u == v)
590 fout_ << ".........PASS!" ;
591 else
592 {
593 fout_ << ".........FAIL!" << endl ;
594 fout_ << " u = " ; printNumber( u, fout_ ) ; fout_ << endl ;
595 fout_ << " v = " ; printNumber( v, fout_ ) ; fout_ << endl ;
596 status = false ;
597 }
598 }
599
600 fout_ << "\nTEST: BigInt u > BigInt v" ;
601 {
602 BigInt u( "3844035" ) ;
603 BigInt v( "933134" ) ;
604
605 if (u > v)
606 fout_ << ".........PASS!" ;
607 else
608 {
609 fout_ << ".........FAIL!" << endl ;
610 fout_ << " u = " ; printNumber( u, fout_ ) ; fout_ << endl ;
611 fout_ << " v = " ; printNumber( v, fout_ ) ; fout_ << endl ;
612 status = false ;
613 }
614 }
615
616 fout_ << "\nTEST: BigInt u( \"1234\" ) -= ppuint d" ;
617 try
618 {
619 BigInt u( "1234" ) ;
620 ppuint d = static_cast<ppuint>(5u) ;
621 u -= d ;
622
623 if (getNumDigits( u ) != static_cast<ppuint>(4) ||
624 getDigit( u, 3 ) != static_cast<ppuint>(1) || getDigit( u, 2 ) != static_cast<ppuint>(2) ||
625 getDigit( u, 1 ) != static_cast<ppuint>(2) || getDigit( u, 0 ) != static_cast<ppuint>(9)
626 )
627 {
628 fout_ << ".........FAIL!" << endl ;
629 fout_ << " u = " ; printNumber( u, fout_ ) ; fout_ << endl ;
630 fout_ << " d = " << d << endl ;
631 status = false ;
632 }
633 else
634 fout_ << ".........PASS!" ;
635 }
636 catch( BigIntMathError & e )
637 {
638 fout_ << ".........FAIL!" << endl ;
639 fout_ << "BigIntMathError: [ " << e.what() << " ] " << endl ;
640 status = false ;
641 }
642
643 fout_ << "\nTEST: BigInt u -= static_cast<ppuint>(5) underflow" ;
644 {
645 try
646 {
647 BigInt u( "4" ) ;
648 ppuint d = static_cast<ppuint>(5u) ;
649 u -= d ;
650
651 fout_ << ".........FAIL!" << endl ;
652 fout_ << " u = " ; printNumber( u, fout_ ) ; fout_ << endl ;
653 fout_ << " d = " << d << endl ;
654 status = false ;
655 }
656 catch( BigIntUnderflow & e )
657 {
658 // Caught underflow; works correctly.
659 // fout_ << "Underflow: " << e.what() << endl ;
660 fout_ << ".........PASS!" ;
661 }
662 catch( ... )
663 {
664 fout_ << ".........FAIL!" << endl ;
665 fout_ << " Didn't catch a BigIntUnderflow exception" << endl ;
666 status = false ;
667 }
668 }
669
670 fout_ << "\nTEST: BigInt u += ppuint d" ;
671 {
672 BigInt u( "9994" ) ;
673 ppuint d = static_cast<ppuint>(6u) ;
674 u += d ;
675 if (getNumDigits( u ) != 5 ||
676 getDigit( u, 4 ) != 1 ||
677 getDigit( u, 3 ) != 0 || getDigit( u, 2 ) != 0 ||
678 getDigit( u, 1 ) != 0 || getDigit( u, 0 ) != 0
679 )
680 {
681 fout_ << ".........FAIL!" << endl ;
682 fout_ << " u = " ; printNumber( u, fout_ ) ; fout_ << endl ;
683 fout_ << " d = " << d << endl ;
684 status = false ;
685 }
686 else
687 fout_ << ".........PASS!" ;
688 }
689
690 fout_ << "\nTEST: BigInt v = BigInt u * ppuint d" ;
691 {
692 BigInt u( "123" ) ;
693 ppuint d{ 4 } ;
694 BigInt v = u * d ;
695
696 if (getNumDigits( v ) != 3 ||
697 getDigit( v, 2 ) != 4 ||
698 getDigit( v, 1 ) != 9 || getDigit( v, 0 ) != 2
699 )
700 {
701 fout_ << ".........FAIL!" << endl ;
702 fout_ << " u = " ; printNumber( u, fout_ ) ; fout_ << endl ;
703 fout_ << " v = " ; printNumber( v, fout_ ) ; fout_ << endl ;
704 fout_ << " d = " << d << endl ;
705 status = false ;
706 }
707 else
708 fout_ << ".........PASS!" ;
709 }
710
711 fout_ << "\nTEST: BigInt u /= ppuint d" ;
712 {
713 BigInt u( "12" ) ;
714 ppuint d{ 4 } ;
715 u /= d ;
716
717 if (getNumDigits( u ) != 1 || getDigit( u, 0 ) != 3)
718 {
719 fout_ << ".........FAIL!" << endl ;
720 fout_ << " u = " ; printNumber( u, fout_ ) ; fout_ << endl ;
721 fout_ << " d = " << d << endl ;
722 status = false ;
723 }
724 else
725 fout_ << ".........PASS!" ;
726 }
727
728 fout_ << "\nTEST: BigInt u /= ppuint d underflow to zero." ;
729 {
730 BigInt u( "3" ) ;
731 ppuint d{ 4 } ;
732 u /= d ;
733
734 if (getNumDigits( u ) != 1 || getDigit( u, 0 ) != 0)
735 {
736 fout_ << ".........FAIL!" << endl ;
737 fout_ << " u = " ; printNumber( u, fout_ ) ; fout_ << endl ;
738 fout_ << " d = " << d << endl ;
739 status = false ;
740 }
741 else
742 fout_ << ".........PASS!" ;
743 }
744
745 fout_ << "\nTEST: BigInt v = ++BigInt u" ;
746 {
747 BigInt u( "123" ) ;
748 BigInt v = ++u ;
749
750 if (getNumDigits( u ) != 3 || getDigit( u, 2 ) != 1 || getDigit( u, 1 ) != 2 || getDigit( u, 0 ) != 4
751 || (u != v))
752 {
753 fout_ << ".........FAIL!" << endl ;
754 fout_ << " u = " ; printNumber( u, fout_ ) ; fout_ << endl ;
755 fout_ << " v = " ; printNumber( v, fout_ ) ; fout_ << endl ;
756 status = false ;
757 }
758 else
759 fout_ << ".........PASS!" ;
760 }
761
762 fout_ << "\nTEST: BigInt v = --BigInt u" ;
763 {
764 BigInt u( "123" ) ;
765 BigInt v = --u ;
766
767 if (getNumDigits( u ) != 3 ||
768 getDigit( u, 2 ) != 1 || getDigit( u, 1 ) != 2 || getDigit( u, 0 ) != 2 ||
769 (u != v))
770 {
771 fout_ << ".........FAIL!" << endl ;
772 fout_ << " u = " ; printNumber( u, fout_ ) ; fout_ << endl ;
773 fout_ << " v = " ; printNumber( v, fout_ ) ; fout_ << endl ;
774 status = false ;
775 }
776 else
777 fout_ << ".........PASS!" ;
778 }
779
780 fout_ << "\nTEST: BigInt++" ;
781 {
782 BigInt u( "123" ) ;
783 BigInt v = u++ ;
784
785 if (getNumDigits( u ) != 3 ||
786 getDigit( u, 2 ) != 1 || getDigit( u, 1 ) != 2 || getDigit( u, 0 ) != 4
787 )
788 {
789 fout_ << ".........FAIL!" << endl ;
790 fout_ << " ++BigInt failed." << endl ;
791 printNumber( u, fout_ ) ;
792 status = false ;
793 }
794 else if (getNumDigits( v ) != 3 ||
795 getDigit( v, 2 ) != 1 || getDigit( v, 1 ) != 2 || getDigit( v, 0 ) != 3
796 )
797 {
798 fout_ << ".........FAIL!" << endl ;
799 fout_ << " BigInt++ failed." << endl ;
800 printNumber( u, fout_ ) ;
801 status = false ;
802 }
803 else
804 fout_ << ".........PASS!" ;
805 }
806
807 fout_ << "\nTEST: BigInt--" ;
808 {
809 BigInt u( "123" ) ;
810 BigInt v = u-- ;
811
812 if (getNumDigits( u ) != 3 ||
813 getDigit( u, 2 ) != 1 || getDigit( u, 1 ) != 2 || getDigit( u, 0 ) != 2
814 )
815 {
816 fout_ << "\n\tERROR: BigInt-- failed." << endl ;
817 printNumber( u, fout_ ) ;
818 status = false ;
819 }
820 else if (getNumDigits( v ) != 3 ||
821 getDigit( v, 2 ) != 1 || getDigit( v, 1 ) != 2 || getDigit( v, 0 ) != 3
822 )
823 {
824 fout_ << "\n\tERROR: BigInt-- failed." << endl ;
825 printNumber( u, fout_ ) ;
826 status = false ;
827 }
828 else
829 fout_ << ".........PASS!" ;
830 }
831
832 fout_ << "\nTEST: one digit BigInt + ppuint" ;
833 {
834 BigInt u( "3" ) ;
835 ppuint d{ 4 } ;
836 BigInt w = u + d ;
837
838 if (getNumDigits( w ) != 1 || getDigit( w, 0 ) != 7)
839 {
840 fout_ << "\n\tERROR: BigInt + BigInt 3 + 4 = 7 failed." << endl ;
841 printNumber( w, fout_ ) ;
842 status = false ;
843 }
844 else
845 fout_ << ".........PASS!" ;
846 }
847
848 fout_ << "\nTEST: two digit BigInt + ppuint" ;
849 {
850 BigInt u( "3" ) ;
851 ppuint d{ 9 } ;
852 BigInt w = u + d ;
853
854 if (getNumDigits( w ) != 2 || getDigit( w, 1 ) != 1
855 || getDigit( w, 0 ) != 2)
856 {
857 fout_ << "\n\tERROR: BigInt + BigInt 3 + 9 = 12 failed." << endl ;
858 printNumber( w, fout_ ) ;
859 status = false ;
860 }
861 else
862 fout_ << ".........PASS!" ;
863 }
864
865 fout_ << "\nTEST: BigInt + BigInt" ;
866 {
867 BigInt u( "9999" ) ;
868 BigInt v( "999" ) ;
869 BigInt w = u + v ;
870
871 if (getNumDigits( w ) != 5 || getDigit( w, 4 ) != 1
872 || getDigit( w, 3 ) != 0
873 || getDigit( w, 2 ) != 9
874 || getDigit( w, 1 ) != 9
875 || getDigit( w, 0 ) != 8)
876 {
877 fout_ << "\n\tERROR: BigInt + BigInt 9999 + 999 = 10998 failed." << endl ;
878 printNumber( w, fout_ ) ;
879 status = false ;
880 }
881 else
882 fout_ << ".........PASS!" ;
883 }
884
885 fout_ << "\nTEST: BigInt + BigInt" ;
886 {
887 BigInt u( "999" ) ;
888 BigInt v( "9999" ) ;
889 BigInt w = u + v ;
890
891 if (getNumDigits( w ) != 5 || getDigit( w, 4 ) != 1
892 || getDigit( w, 3 ) != 0
893 || getDigit( w, 2 ) != 9
894 || getDigit( w, 1 ) != 9
895 || getDigit( w, 0 ) != 8)
896 {
897 fout_ << "\n\tERROR: BigInt + BigInt 999 + 9999 = 10998 failed." << endl ;
898 printNumber( w, fout_ ) ;
899 status = false ;
900 }
901 else
902 fout_ << ".........PASS!" ;
903 }
904
905 fout_ << "\nTEST: BigInt - BigInt" ;
906 {
907 BigInt u( "103" ) ;
908 BigInt v( "9" ) ;
909 BigInt w = u - v ;
910
911 if (getNumDigits( w ) != 2 || getDigit( w, 1 ) != 9
912 || getDigit( w, 0 ) != 4)
913 {
914 fout_ << "\n\tERROR: BigInt - BigInt 103 - 9 = 94 failed." << endl ;
915 printNumber( w, fout_ ) ;
916 status = false ;
917 }
918 else
919 fout_ << ".........PASS!" ;
920 }
921
922 fout_ << "\nTEST: BigInt - BigInt < 0" ;
923 try
924 {
925 BigInt u( "9" ) ;
926 BigInt v( "103" ) ;
927 BigInt w = u - v ;
928
929 fout_ << "\n\tERROR: BigInt - BigInt 9 - 103 failed didn't catch range exception." << endl ;
930 printNumber( w, fout_ ) ;
931 status = false ;
932 }
933 catch( BigIntUnderflow & e )
934 {
935 // Caught underflow; works correctly.
936 // fout_ << "Underflow: " << e.what() << endl ;
937 fout_ << ".........PASS!" ;
938 }
939
940 fout_ << "\nTEST: BigInt - ppuint" ;
941 {
942 BigInt u( "103" ) ;
943 ppuint d{ 9 } ;
944 BigInt w = u - d ;
945
946 if (getNumDigits( w ) != 2 || getDigit( w, 1 ) != 9
947 || getDigit( w, 0 ) != 4)
948 {
949 fout_ << "\n\tERROR: BigInt - ppuint 103 - 9 = 94 failed." << endl ;
950 printNumber( w, fout_ ) ;
951 status = false ;
952 }
953 else
954 fout_ << ".........PASS!" ;
955 }
956
957 fout_ << "\nTEST: one digit BigInt * BigInt" ;
958 {
959 BigInt u( "3" ) ;
960 BigInt v( "3" ) ;
961 BigInt w = u * v ;
962
963 if (getNumDigits( w ) != 1 || getDigit( w, 0 ) != 9)
964 {
965 fout_ << "\n\tERROR: BigInt * BigInt 3 * 3 = 9 failed." << endl ;
966 printNumber( w, fout_ ) ;
967 status = false ;
968 }
969 else
970 fout_ << ".........PASS!" ;
971 }
972
973 fout_ << "\nTEST: two digit BigInt * BigInt" ;
974 {
975 BigInt u( "3" ) ;
976 BigInt v( "4" ) ;
977 BigInt w = u * v ;
978
979 if (getNumDigits( w ) != 2 || getDigit( w, 1 ) != 1 || getDigit( w, 0 ) != 2)
980 {
981 fout_ << "\n\tERROR: BigInt * BigInt = 3 * 4 = 12 failed." << endl ;
982 printNumber( w, fout_ ) ;
983 status = false ;
984 }
985 else
986 fout_ << ".........PASS!" ;
987 }
988
989 fout_ << "\nTEST: BigInt multidigit *" ;
990 {
991 BigInt w ;
992 BigInt u( "329218104" ) ;
993 BigInt v( "3606" ) ;
994
995 w = u * v ;
996
997 string s = w.toString() ;
998
999 if (s != "1187160483024" )
1000 {
1001 fout_ << "\n\tERROR: BigInt multidigit * failed." << endl ;
1002 fout_ << "u = " ; printNumber( u, fout_ ) ;
1003 fout_ << "v = " ; printNumber( v, fout_ ) ;
1004 fout_ << "w = " ; printNumber( w, fout_ ) ;
1005 status = false ;
1006 }
1007 else
1008 {
1009 fout_ << ".........PASS!" ;
1010 }
1011 }
1012
1013 fout_ << "\nTEST: BigInt multidigit *=" ;
1014 {
1015 BigInt u( "329218104" ) ;
1016 BigInt v( "3606" ) ;
1017
1018 u *= v ;
1019
1020 string s = u.toString() ;
1021
1022 if (s != "1187160483024" )
1023 {
1024 fout_ << "\n\tERROR: BigInt multidigit *= failed." << endl ;
1025 fout_ << "u = " ; printNumber( u, fout_ ) ;
1026 fout_ << "v = " ; printNumber( v, fout_ ) ;
1027 status = false ;
1028 }
1029 else
1030 {
1031 fout_ << ".........PASS!" ;
1032 }
1033 }
1034
1035 fout_ << "\nTEST: BigInt / BigInt one digit divisor." ;
1036 {
1037 BigInt u( "12" ) ;
1038 BigInt v( "4" ) ;
1039 BigInt w = u / v ;
1040
1041 if (getNumDigits( w ) != 1 || getDigit( w, 0 ) != 3)
1042 {
1043 fout_ << "\n\tERROR: BigInt / BigInt = 12/4 = 3 failed." << endl ;
1044 printNumber( w, fout_ ) ;
1045 status = false ;
1046 }
1047 else
1048 fout_ << ".........PASS!" ;
1049 }
1050
1051 fout_ << "\nTEST: BigInt / BigInt multidigit" ;
1052 {
1053 BigInt u( "398765" ) ;
1054 BigInt v( "3457" ) ;
1055 BigInt w = u / v ;
1056
1057 if (getNumDigits( w ) != 3 ||
1058 getDigit( w, 2 ) != 1 || getDigit( w, 1 ) != 1 || getDigit( w, 0 ) != 5)
1059 {
1060 fout_ << "\n\tERROR: BigInt / BigInt = 398765/3457 = 215 failed." << endl ;
1061 printNumber( w, fout_ ) ;
1062 status = false ;
1063 }
1064 else
1065 fout_ << ".........PASS!" ;
1066 }
1067
1068 fout_ << "\nTEST: BigInt / BigInt leading zero digit." ;
1069 {
1070 BigInt u( "120" ) ;
1071 BigInt v( "40" ) ;
1072 BigInt w = u / v ;
1073
1074 if (getNumDigits( w ) != 1 || getDigit( w, 0 ) != 3)
1075 {
1076 fout_ << "\n\tERROR: BigInt / BigInt = 120/40 = 3 failed." << endl ;
1077 printNumber( w, fout_ ) ;
1078 status = false ;
1079 }
1080 else
1081 fout_ << ".........PASS!" ;
1082 }
1083
1084 fout_ << "\nTEST: BigInt / 0 " ;
1085 try
1086 {
1087 BigInt u( "120" ) ;
1088 BigInt v( "0" ) ;
1089 BigInt w = u / v ;
1090
1091 fout_ << "\n\tERROR: BigInt / 0 = 120/0 failed." << endl ;
1092 status = false ;
1093 }
1094 catch( BigIntZeroDivide & e )
1095 {
1096 // Should catch zero divide here.
1097 fout_ << ".........PASS!" ;
1098 }
1099
1100 fout_ << "\nTEST: BigInt % BigInt with u > v" ;
1101 {
1102 BigInt u( "398765" ) ;
1103 BigInt v( "3457" ) ;
1104 BigInt r = u % v ;
1105
1106 if (getNumDigits( r ) != 4 ||
1107 getDigit( r, 3 ) != 1 || getDigit( r, 2 ) != 2 ||
1108 getDigit( r, 1 ) != 1 || getDigit( r, 0 ) != 0)
1109 {
1110 fout_ << "\n\tERROR: BigInt % BigInt = 398765 / 3457 = 1210 failed." << endl ;
1111 printNumber( r, fout_ ) ;
1112 status = false ;
1113 }
1114 else
1115 {
1116 fout_ << ".........PASS!" ;
1117 }
1118 }
1119
1120 fout_ << "\nTEST: BigInt multidigit mod with normalizing constant d = 1" ;
1121 {
1122 BigInt w ;
1123 BigInt u( "1369244731822264511994463394" ) ;
1124 BigInt v( "954901783703457032047844259" ) ;
1125
1126 w = u % v ;
1127
1128 string s{ w.toString() } ;
1129
1130 if (s != "414342948118807479946619135" )
1131 {
1132 fout_ << "\n\tERROR: BigInt multidigit mod failed." << endl ;
1133 fout_ << "u = " ; printNumber( u, fout_ ) ;
1134 fout_ << "v = " ; printNumber( v, fout_ ) ;
1135 fout_ << "w = " ; printNumber( w, fout_ ) ;
1136 status = false ;
1137 }
1138 else
1139 {
1140 fout_ << ".........PASS!" ;
1141 }
1142 }
1143
1144 fout_ << "\nTEST: BigInt % BigInt with u < v" ;
1145 {
1146 BigInt u( "12" ) ;
1147 BigInt v( "34567" ) ;
1148 BigInt r{ u % v } ;
1149
1150 if (getNumDigits( r ) != 2 ||
1151 getDigit( r, 1 ) != 1 || getDigit( r, 0 ) != 2)
1152 {
1153 fout_ << "\n\tERROR: BigInt % BigInt = 12 mod 345 = 12 failed." << endl ;
1154 printNumber( r, fout_ ) ;
1155 status = false ;
1156 }
1157 else
1158 fout_ << ".........PASS!" ;
1159 }
1160
1161 fout_ << "\nTEST: BigInt % ppuint = 314159 / 9 = 5 with ppuint < base " ;
1162 {
1163 BigInt u( "314159" ) ;
1164 ppuint v{ 9u } ;
1165 ppuint r{ u % v } ;
1166
1167 if (r != 5)
1168 {
1169 fout_ << "\n\tERROR: [BigInt u % ppuint v = r]: 314159 / 9 = 5 failed" << endl ;
1170 fout_ << "u = " << u << " v = " << v << " r = " << r << " for base = " << BigInt::getBase() << endl ;
1171 status = false ;
1172 }
1173 else
1174 fout_ << ".........PASS!" ;
1175 }
1176
1177 fout_ << "\nTEST: BigInt % ppuint = 398765 % 11u with ppuint > base = 10 throws error? " ;
1178 try
1179 {
1180 BigInt u( "398765" ) ;
1181 ppuint v{ 11u } ;
1182 ppuint r{ u % v } ;
1183
1184 fout_ << "\n\tERROR: BigInt % ppuint = 398765 % 11 = 4 failed for base = " << BigInt::getBase() << endl ;
1185 fout_ << "\n\tERROR: [BigInt u % ppuint v = r]: 398765 / 11 = 4 failed" << endl ;
1186 fout_ << "u = " << u << " v = " << v << " r = " << r << " for base = " << BigInt::getBase() << endl ;
1187 status = false ;
1188 }
1189 catch( BigIntOverflow & e )
1190 {
1191 fout_ << ".........PASS!" ;
1192 }
1193
1194 fout_ << "\nTEST: BigInt / BigInt low probability if branch." ;
1195 {
1196 BigInt u( "4100" ) ;
1197 BigInt v( "588" ) ;
1198 BigInt w{ u / v } ;
1199
1200 if (w != BigInt("6"))
1201 fout_ << "error" << endl;
1202
1203 if (getNumDigits( w ) != 1 || getDigit( w, 0 ) != 6)
1204 {
1205 fout_ << "\n\tERROR: BigInt / BigInt = 4100/588 = 6 failed." << endl ;
1206 printNumber( w, fout_ ) ;
1207 status = false ;
1208 }
1209 else
1210 fout_ << ".........PASS!" ;
1211 }
1212
1213 fout_ << "\nTEST: Switching back from base " << 10 << " to oldBase " << oldBase ;
1214 BigInt dummy ;
1215 setBase( dummy, oldBase ) ;
1216 if (BigInt::getBase() != oldBase)
1217 {
1218 fout_ << "\n\tERROR: Changing back to default base for all BigInt objects "
1219 << " failed. base = " << BigInt::getBase() << endl ;
1220 status = false ;
1221 }
1222 else
1223 fout_ << ".........PASS!" ;
1224
1225 return status ;
1226}
1227
1228
1229
1230bool UnitTest::unitTestBigIntDefaultBase()
1231{
1232 bool status{ true } ;
1233
1234 fout_ << "\nTEST: Decimal string to BigInt conversion and back to decimal string using default base." ;
1235 {
1236 BigInt x( "3141592653589793238462643383279" ) ;
1237 string s{ x.toString() } ;
1238
1239 if (s != "3141592653589793238462643383279" )
1240 {
1241 fout_ << "\n\tERROR: BigInt default base conversion failed." << endl ;
1242 fout_ << "x = " << x << " " ; printNumber( x, fout_ ) ;
1243 fout_ << " NOT EQUAL TO s = 3141592653589793238462643383279 (decimal digits)" << endl ;
1244 status = false ;
1245 }
1246 else
1247 fout_ << ".........PASS!" ;
1248 }
1249
1250 fout_ << "\nTEST: BigInt z = x * y then x =? z / y multidigit with default base." ;
1251 {
1252 BigInt x( "3141592653589793238462643383279" ) ;
1253 BigInt y( "2718281828459045" ) ;
1254 BigInt z{ x * y } ;
1255 BigInt w{ z / y } ;
1256
1257 if (w != x)
1258 {
1259 fout_ << "\n\tERROR: BigInt z = x * y then x =? z / y multidigit with default base failed." << endl ;
1260 fout_ << "x = " ; printNumber( x, fout_ ) ;
1261 fout_ << "y = " ; printNumber( y, fout_ ) ;
1262 fout_ << "z = " ; printNumber( z, fout_ ) ;
1263 fout_ << "w = " ; printNumber( w, fout_ ) ;
1264 status = false ;
1265 }
1266 else
1267 fout_ << ".........PASS!" ;
1268 }
1269
1270 fout_ << "\nTEST: BigInt testBit" ;
1271 {
1272 BigInt u( "31415926535897932" ) ;
1273
1274 if (u.testBit( 0 ) == false &&
1275 u.testBit( 1 ) == false &&
1276 u.testBit( 2 ) == true &&
1277 u.testBit( 3 ) == true &&
1278 u.testBit( 4 ) == false &&
1279 u.testBit( 5 ) == false &&
1280 u.testBit( 6 ) == true &&
1281 u.testBit( 7 ) == false)
1282 {
1283 fout_ << ".........PASS!" ;
1284 }
1285 else
1286 {
1287 fout_ << "\n\tERROR: BigInt testBit failed." << endl ;
1288 printNumber( u, fout_ ) ;
1289 fout_ << "testBit 0 = " << (u.testBit( 0 ) == true) << endl ;
1290 fout_ << "testBit 1 = " << (u.testBit( 1 ) == true) << endl ;
1291 fout_ << "testBit 2 = " << (u.testBit( 2 ) == true) << endl ;
1292 fout_ << "testBit 3 = " << (u.testBit( 3 ) == true) << endl ;
1293 fout_ << "testBit 4 = " << (u.testBit( 4 ) == true) << endl ;
1294 fout_ << "testBit 5 = " << (u.testBit( 5 ) == true) << endl ;
1295 fout_ << "testBit 6 = " << (u.testBit( 6 ) == true) << endl ;
1296 fout_ << "testBit 7 = " << (u.testBit( 7 ) == true) << endl ;
1297 status = false ;
1298 }
1299 }
1300
1301 fout_ << "\nTEST: testBit()" ;
1302 {
1303 ppuint u{ 0b100101 } ; // Set bits 0, 2 and 5 using C++14 binary literals.
1304
1305 if (testBit( u, 0 ) == true &&
1306 testBit( u, 1 ) == false &&
1307 testBit( u, 2 ) == true &&
1308 testBit( u, 3 ) == false &&
1309 testBit( u, 4 ) == false &&
1310 testBit( u, 5 ) == true &&
1311 testBit( u, 6 ) == false &&
1312 testBit( u, 7 ) == false)
1313 {
1314 fout_ << ".........PASS!" ;
1315 }
1316 else
1317 {
1318 fout_ << "\n\tERROR: ppuint testBit failed for u = " << u << endl ;
1319 fout_ << "testBit 0 = " << (testBit( u, 0 ) == true) << endl ;
1320 fout_ << "testBit 1 = " << (testBit( u, 1 ) == true) << endl ;
1321 fout_ << "testBit 2 = " << (testBit( u, 2 ) == true) << endl ;
1322 fout_ << "testBit 3 = " << (testBit( u, 3 ) == true) << endl ;
1323 fout_ << "testBit 4 = " << (testBit( u, 4 ) == true) << endl ;
1324 fout_ << "testBit 5 = " << (testBit( u, 5 ) == true) << endl ;
1325 fout_ << "testBit 6 = " << (testBit( u, 6 ) == true) << endl ;
1326 fout_ << "testBit 7 = " << (testBit( u, 7 ) == true) << endl ;
1327 status = false ;
1328 }
1329 }
1330
1331 fout_ << "\nTEST: BigInt power( ppuint 2, ppuint 100 )" ;
1332 {
1333 ppuint p{ 2u } ;
1334 int n{ 100 } ;
1335 BigInt u{ power( p, n ) } ;
1336 string s{ u.toString() } ;
1337
1338 BigInt v{ 1u } ;
1339 for (int i = 1 ; i <= n ; ++i)
1340 v *= p ;
1341 string sv{ v.toString() } ;
1342
1343 if (s != sv)
1344 {
1345 fout_ << "\n\tERROR: BigInt power( 2, 100 ) = " << u << endl ;
1346 fout_ << "correct answer = " << v << endl ;
1347 status = false ;
1348 }
1349 else
1350 fout_ << ".........PASS!" ;
1351 }
1352
1353 fout_ << "\nTEST: BigInt ceilLg( 6 )" ;
1354 {
1355 BigInt u{ 6u } ;
1356
1357 int ceilingOfLog2 = u.ceilLg() ;
1358 if (ceilingOfLog2 != 3)
1359 {
1360 fout_ << "\n\tERROR: BigInt ceilingOfLog2( 6 ) = " << ceilingOfLog2 << endl ;
1361 fout_ << "correct answer = 3" << endl ;
1362 status = false ;
1363 }
1364 else
1365 fout_ << ".........PASS!" ;
1366 }
1367
1368 fout_ << "\nTEST: BigInt eval 2 ^ 1198 - 1" ;
1369 {
1370 BigInt largePowerOf2Minus1 = power( 2, 1198 ) - static_cast< BigInt >( 1u ) ;
1371 /// cout << "largePowerOf2Minus1 = " << largePowerOf2Minus1 << endl ;
1372 BigInt f1{ BigInt( 3u ) } ;
1373 BigInt f2{ BigInt( "366994123" ) } ;
1374 BigInt f3{ BigInt( "16659379034607403556537" ) } ;
1375 BigInt f4{ BigInt( "148296291984475077955727317447564721950969097" ) } ;
1376 BigInt f5{ BigInt( "839804700900123195473468092497901750422530587828620063507554515144683510250490874819119570309824866293030799718783" ) } ;
1377 BigInt f6{ BigInt( "188446049896780543200161267236930710150747483597643192594833338774867012035362945326134784314021280857050576738677"
1378 "1290423087216156597588216186445958479269565424431335013281" ) } ;
1379 BigInt product{ f1 * f2 * f3 * f4 * f5 * f6 } ;
1380 bool allFactorsPrime{ isAlmostSurelyPrime( f1 ) && isAlmostSurelyPrime( f2 ) && isAlmostSurelyPrime( f3 ) &&
1381 isAlmostSurelyPrime( f4 ) && isAlmostSurelyPrime( f5 ) && isAlmostSurelyPrime( f6 ) } ;
1382 /// cout << "all factors prime = " << allFactorsPrime << endl ;
1383 /// cout << "product = " << product << endl ;
1384
1385 if (product != largePowerOf2Minus1 || !allFactorsPrime)
1386 {
1387 fout_ << "\nERROR: BigInt eval 2 ^ 1198 - 1 != 3 * 366994123 * 16659379034607403556537 * 148296291984475077955727317447564721950969097 * "
1388 "839804700900123195473468092497901750422530587828620063507554515144683510250490874819119570309824866293030799718783 * "
1389 "18844604989678054320016126723693071015074748359764319259483333877486701203536294532613478431402128085705057673867712"
1390 "90423087216156597588216186445958479269565424431335013281" << endl ;
1391 status = false ;
1392 }
1393 else
1394 fout_ << ".........PASS!" ;
1395 }
1396
1397 return status ;
1398}
1399
1400
1401bool UnitTest::unitTestModPArithmetic()
1402{
1403 volatile bool status{ true } ; // Suppress XCode warning about Dead store: value never read.
1404
1405 fout_ << "\nTEST: ModP 10 = 3 (mod 7)" ;
1406 {
1407 ModP<ppuint,ppsint> modp( 7 ) ;
1408 if (modp( 10 ) != 3)
1409 {
1410 fout_ << ".........FAIL!" << endl ;
1411 fout_ << " ModP modp( 7 ); modp( 10 ) = " << modp( 10 ) << endl ;
1412 status = false ;
1413 }
1414 else
1415 fout_ << ".........PASS!" ;
1416 }
1417
1418 fout_ << "\nTEST: ModP -10 = 4 (mod 7)" ;
1419 {
1420 ModP<ppuint,ppsint> modp( 7 ) ;
1421 if (modp( -10 ) != 4)
1422 {
1423 fout_ << ".........FAIL!" << endl ;
1424 fout_ << " ModP modp( 7 ); modp( -10 ) = " << modp( -10 ) << endl ;
1425 ppsint n = -10 ;
1426 ppsint p = 7 ;
1427 fout_ << "+ + + + + + + +" << endl ;
1428 fout_ << n << endl ;
1429 fout_ << p << endl ;
1430 fout_ << (n % p) << endl ;
1431 fout_ << ( (n % p) + p ) << endl ;
1432 fout_ << "+ + + + + + + +" << endl ;
1433 status = false ;
1434 }
1435 else
1436 fout_ << ".........PASS!" ;
1437 }
1438
1439 fout_ << "\nTEST: ModP( 0 ) throwing ArithModPError" ;
1440 {
1441 try
1442 {
1443 ModP<ppuint,ppsint> modp( 0 ) ;
1444 modp( 10 ) ;
1445
1446 status = false ;
1447 fout_ << ".........FAIL!\n did not catch ArithModPError when p <= 0" << endl ;
1448 }
1449 catch( ArithModPError & e )
1450 {
1451 // Since we cannot debug trace exceptions in XCode, break on this statement so we can see it works OK.
1452 fout_ << ".........PASS!" ;
1453 }
1454 }
1455
1456 fout_ << "\nTEST: ppuint gcd( 85, 25 ) = 5" ;
1457 {
1458 ppuint u{ 85u } ;
1459 ppuint v{ 25u } ;
1460 ppuint g{ gcd( u, v ) } ;
1461 if (g != static_cast<ppuint>(5u))
1462 {
1463 fout_ << ".........FAIL!" << endl ;
1464 fout_ << " ppuint gcd( 85, 25 ) = " << g << endl ;
1465 status = false ;
1466 }
1467 else
1468 fout_ << ".........PASS!" ;
1469 }
1470
1471 fout_ << "\nTEST: BigInt gcd( 779953197883173551166308319545, 1282866356929526866866376009397 ) = 1" ;
1472 {
1473 BigInt u( "779953197883173551166308319545" ) ;
1474 BigInt v( "1282866356929526866866376009397" ) ;
1475 BigInt g = gcd( u, v ) ;
1476 if (g != static_cast<BigInt>( static_cast<ppuint>(1u) ))
1477 {
1478 fout_ << ".........FAIL!" << endl ;
1479 fout_ << " BigInt gcd = " << g << endl ;
1480 status = false ;
1481 }
1482 else
1483 fout_ << ".........PASS!" ;
1484 }
1485
1486 fout_ << "\nTEST: c,r = addMod( a, b, n ) for ppuint type " ;
1487 {
1488 if (8 * sizeof( ppuint ) == 64)
1489 {
1490 fout_ << "of 64 bits " ;
1491 ppuint a = static_cast<ppuint>(18446744073709551614ULL) ; // 2^64-1-1
1492 ppuint b = static_cast<ppuint>(18446744073709551615ULL) ; // 2^64-1
1493 ppuint n = static_cast<ppuint>(18446744073709551615ULL) ; // 2^64-1
1494 ppuint c = static_cast<ppuint>(18446744073709551614ULL) ; // 2^64-1-1
1495 ppuint r = addMod( a, b, n ) ;
1496 if (r != c)
1497 {
1498 fout_ << ".........FAIL!" << endl ;
1499 fout_ << "a = " << a << endl ;
1500 fout_ << "b = " << b << endl ;
1501 fout_ << "n = " << n << endl ;
1502 fout_ << "c = " << c << endl ;
1503 fout_ << "r = " << r << endl ;
1504 status = false ;
1505 }
1506 else
1507 fout_ << ".........PASS!" ;
1508 }
1509 else if (8 * sizeof( ppuint ) == 32)
1510 {
1511 fout_ << "of 32 bits " ;
1512 ppuint a{ static_cast<ppuint>(4294967295u) } ; // 2^32-1
1513 ppuint b{ static_cast<ppuint>(4294967294u) } ; // (2^32-1)-1
1514 ppuint n{ static_cast<ppuint>(4294967295u) } ; // 2^32-1
1515 ppuint c{ static_cast<ppuint>(4294967294u) } ; // (2^32-1)-1
1516 ppuint r{ addMod( a, b, n ) } ;
1517 if (r != c)
1518 {
1519 fout_ << ".........FAIL!" << endl ;
1520 fout_ << "a = " << a << endl ;
1521 fout_ << "b = " << b << endl ;
1522 fout_ << "n = " << n << endl ;
1523 fout_ << "c = " << c << endl ;
1524 fout_ << "r = " << r << endl ;
1525 status = false ;
1526 }
1527 else
1528 fout_ << ".........PASS!" ;
1529 }
1530 }
1531
1532 fout_ << "\nTEST: c,r = timesTwoMod( a, n ) for ppuint type " ;
1533 {
1534 if (8 * sizeof( ppuint ) == 64)
1535 {
1536 fout_ << "of 64 bits " ;
1537 ppuint a = static_cast<ppuint>(18446744073709551614ULL) ; // 2^64-1-1
1538 ppuint n = static_cast<ppuint>(18446744073709551615ULL) ; // 2^64-1
1539 ppuint c = static_cast<ppuint>(18446744073709551613ULL) ; // 2^64-1-2
1540 ppuint r = timesTwoMod( a, n ) ;
1541 if (r != c)
1542 {
1543 fout_ << ".........FAIL!" << endl ;
1544 fout_ << "a = " << a << endl ;
1545 fout_ << "n = " << n << endl ;
1546 fout_ << "c = " << c << endl ;
1547 fout_ << "r = " << r << endl ;
1548 status = false ;
1549 }
1550 else
1551 fout_ << ".........PASS!" ;
1552 }
1553 else if (8 * sizeof( ppuint ) == 32)
1554 {
1555 fout_ << "of 32 bits " ;
1556 ppuint a{ static_cast<ppuint>(4294967294u) } ; // 2^32-1-1
1557 ppuint n{ static_cast<ppuint>(4294967295u) } ; // 2^32-1
1558 ppuint c{ static_cast<ppuint>(4294967293u) } ; // (2^32-1)-2
1559 ppuint r{ timesTwoMod( a, n ) } ;
1560 if (r != c)
1561 {
1562 fout_ << ".........FAIL!" << endl ;
1563 fout_ << "a = " << a << endl ;
1564 fout_ << "n = " << n << endl ;
1565 fout_ << "c = " << c << endl ;
1566 fout_ << "r = " << r << endl ;
1567 status = false ;
1568 }
1569 else
1570 fout_ << ".........PASS!" ;
1571 }
1572 }
1573
1574 fout_ << "\nTEST: c,r = multiplyMod( a, b, n ) for ppuint type " ;
1575 {
1576 if (8 * sizeof( ppuint ) == 64)
1577 {
1578 fout_ << "of 64 bits " ;
1579 ppuint a{ static_cast<ppuint>(18446744073709551614ULL) } ; // 2^64-1-1
1580 ppuint b{ static_cast<ppuint>(18446744073709551614ULL) } ; // 2^64-1-1
1581 ppuint n{ static_cast<ppuint>(18446744073709551615ULL) } ; // 2^64-1
1582 ppuint c{ static_cast<ppuint>(1ULL) } ; // 1
1583 ppuint r{ multiplyMod( a, b, n ) } ;
1584 if (r != c)
1585 {
1586 fout_ << ".........FAIL!" << endl ;
1587 fout_ << "a = " << a << endl ;
1588 fout_ << "b = " << b << endl ;
1589 fout_ << "n = " << n << endl ;
1590 fout_ << "c = " << c << endl ;
1591 fout_ << "r = " << r << endl ;
1592 status = false ;
1593 }
1594 else
1595 fout_ << ".........PASS!" ;
1596 }
1597 else if (8 * sizeof( ppuint ) == 32)
1598 {
1599 fout_ << "of 32 bits " ;
1600 ppuint a{ static_cast<ppuint>(4294967294u) } ; // 2^32-1-1
1601 ppuint b{ static_cast<ppuint>(4294967294u) } ; // 2^32-1-1
1602 ppuint n{ static_cast<ppuint>(4294967295u) } ; // 2^32-1
1603 ppuint c{ static_cast<ppuint>(1u) } ; // 1
1604 ppuint r{ multiplyMod( a, b, n ) } ;
1605 if (r != c)
1606 {
1607 fout_ << ".........FAIL!" << endl ;
1608 fout_ << "a = " << a << endl ;
1609 fout_ << "b = " << b << endl ;
1610 fout_ << "n = " << n << endl ;
1611 fout_ << "c = " << c << endl ;
1612 fout_ << "r = " << r << endl ;
1613 status = false ;
1614 }
1615 else
1616 fout_ << ".........PASS!" ;
1617 }
1618 }
1619
1620 fout_ << "\nTEST: PowerMod ppuint 3^10 = 4 (mod 7)" ;
1621 {
1622 PowerMod<ppuint> powermod( static_cast<ppuint>(7u) ) ;
1623 if (powermod( static_cast<ppuint>(3u), static_cast<ppuint>(10u) ) != static_cast<ppuint>(4u))
1624 {
1625 fout_ << ".........FAIL!" << endl ;
1626 fout_ << " PowerMod powermod( 7 ); powermod( 3, 10 ) = " << powermod( 3, 10 ) << " failed." << endl ;
1627 status = false ;
1628 }
1629 else
1630 fout_ << ".........PASS!" ;
1631 }
1632
1633 fout_ << "\nTEST: c,r = PowerMod( a, b ) modulo n for ppuint type " ;
1634 {
1635 if (8 * sizeof( ppuint ) == 64)
1636 {
1637 fout_ << "of 64 bits " ;
1638 ppuint a{ static_cast<ppuint>(2323123u) } ;
1639 ppuint b{ static_cast<ppuint>(10u) } ;
1640 ppuint n{ static_cast<ppuint>(18446744073709551615ULL) } ; // 2^64-1
1641 ppuint c{ static_cast<ppuint>(17955139022230052569ULL) } ;
1642 PowerMod<ppuint> powermod( n ) ;
1643 ppuint r = powermod( a, b ) ;
1644 if (r != c)
1645 {
1646 fout_ << ".........FAIL!" << endl ;
1647 fout_ << "a = " << a << endl ;
1648 fout_ << "b = " << b << endl ;
1649 fout_ << "n = " << n << endl ;
1650 fout_ << "c = " << c << endl ;
1651 fout_ << "r = " << r << endl ;
1652 status = false ;
1653 }
1654 else
1655 fout_ << ".........PASS!" ;
1656 }
1657 else if (8 * sizeof( ppuint ) == 32)
1658 {
1659 fout_ << "of 32 bits " ;
1660 ppuint a{ static_cast<ppuint>(4294967290u) } ;
1661 ppuint b{ static_cast<ppuint>(10u) } ;
1662 ppuint n{ static_cast<ppuint>(4294967295u) } ; // 2^32-1
1663 ppuint c{ static_cast<ppuint>(9765625u) } ;
1664 PowerMod<ppuint> powermod( n ) ;
1665 ppuint r{ powermod( a, b ) } ;
1666 if (r != c)
1667 {
1668 fout_ << ".........FAIL!" << endl ;
1669 fout_ << "a = " << a << endl ;
1670 fout_ << "b = " << b << endl ;
1671 fout_ << "n = " << n << endl ;
1672 fout_ << "c = " << c << endl ;
1673 fout_ << "r = " << r << endl ;
1674 status = false ;
1675 }
1676 else
1677 fout_ << ".........PASS!" ;
1678 }
1679 }
1680
1681 fout_ << "\nTEST: PowerMod BigInt 3^10 = 4 (mod 7)" ;
1682 PowerMod<BigInt> powermod( static_cast<BigInt>(static_cast<ppuint>(7u)) ) ;
1683 if (powermod( static_cast<BigInt>(static_cast<ppuint>(3u)),
1684 static_cast<BigInt>(static_cast<ppuint>(10u)) ) != static_cast<BigInt>(static_cast<ppuint>(4u)))
1685 {
1686 BigInt three{ 3u } ;
1687 BigInt ten{ 10u } ;
1688 fout_ << "\n\tERROR: PowerMod powermod( 7 ); powermod( 3, 10 ) = " << powermod( three, ten ) << " failed." << endl ;
1689 status = false ;
1690 }
1691 else
1692 fout_ << ".........PASS!" ;
1693
1694 fout_ << "\nTEST: PowerMod with out of range inputs." ;
1695 try
1696 {
1697 PowerMod<BigInt> powermod{ static_cast<BigInt>(static_cast<ppuint>( 7u )) } ;
1698 powermod( static_cast<BigInt>(static_cast<ppuint>( 0u )), static_cast<BigInt>(static_cast<ppuint>( 0u )) ) ;
1699
1700 fout_ << "\n\tERROR: PowerMod on 0^0 didn't throw exception." << endl ;
1701 status = false ;
1702 }
1703 catch( ArithModPError & e )
1704 {
1705 fout_ << ".........PASS!" ;
1706 }
1707
1708 fout_ << "\nTEST: InverseModP 3 * 5 = 1 (mod 7)" ;
1709 InverseModP imodp( 7 ) ;
1710 if (imodp( 3 ) != 5)
1711 {
1712 fout_ << "\n\tERROR: InverseModP imodp( 7 ); imodp( 3 ) = " << imodp( 3 ) << " failed." << endl ;
1713 status = false ;
1714 }
1715 else
1716 fout_ << ".........PASS!" ;
1717
1718 fout_ << "\nTEST: IsPrimitiveRoot. 3 is a primitive root of 7." ;
1719 IsPrimitiveRoot isroot( 7 ) ;
1720 if (isroot( 3 ))
1721 fout_ << ".........PASS!" ;
1722 else
1723 {
1724 fout_ << "\n\tERROR: IsPrimitiveRoot( 7 ) isroot ; isroot( 3 ) = " << isroot( 3 ) << " failed." << endl ;
1725 status = false ;
1726 }
1727
1728 fout_ << "\nTEST: IsPrimitiveRoot. 2 is a primitive root of 11." ;
1729 IsPrimitiveRoot isroot11( 11 ) ;
1730 if (isroot11( 2 ))
1731 fout_ << ".........PASS!" ;
1732 else
1733 {
1734 fout_ << "\n\tERROR: IsPrimitiveRoot( 11 ) isroot11 ; isroot11( 2 ) = " << isroot11( 2 ) << " failed." << endl ;
1735 status = false ;
1736 }
1737
1738 fout_ << "\nTEST: IsPrimitiveRoot. 3 is NOT a primitive root of 11." ;
1739 if (isroot11( 3 ))
1740 {
1741 fout_ << "\n\tERROR: IsPrimitiveRoot( 11 ) isroot11 ; isroot11( 3 ) = " << isroot11( 3 ) << " failed." << endl ;
1742 status = false ;
1743 }
1744 else
1745 fout_ << ".........PASS!" ;
1746
1747 fout_ << "\nTEST: IsPrimitiveRoot. 5 is a primitive root of 65003." ;
1748 IsPrimitiveRoot isroot65003( 65003 ) ;
1749 if (isroot65003( 5 ))
1750 fout_ << ".........PASS!" ;
1751 else
1752 {
1753 fout_ << "\n\tERROR: IsPrimitiveRoot65003( 5 ) should have said true. It failed." << endl ;
1754 status = false ;
1755 }
1756
1757 fout_ << "\nTEST: IsPrimitiveRoot. 8 is NOT a primitive root of 65003." ;
1758 if (isroot65003( 8 ))
1759 {
1760 fout_ << "\n\tERROR: IsPrimitiveRoot65003( 8 ) should have said false. It failed." << endl ;
1761 status = false ;
1762 }
1763 else
1764 fout_ << ".........PASS!" ;
1765
1766 fout_ << "\nTEST: constant coefficient test." ;
1767 ArithModP arith1( 5 ) ;
1768 if (arith1.constCoeffTest( 4, 1, 11 ))
1769 fout_ << ".........PASS!" ;
1770 else
1771 {
1772 fout_ << "\n\tERROR: constant coefficient test failed = " << arith1.constCoeffTest( 4, 1, 11 ) << " failed." << endl ;
1773 status = false ;
1774 }
1775
1776 fout_ << "\nTEST: constant coefficient is primitive root." ;
1777 ArithModP arith2( 7 ) ;
1778 if (arith2.constCoeffIsPrimitiveRoot( 4, 11 ))
1779 fout_ << ".........PASS!" ;
1780 else
1781 {
1782 fout_ << "\n\tERROR: constant coefficient test failed = " << arith1.constCoeffIsPrimitiveRoot( 4, 11 ) << " failed." << endl ;
1783 status = false ;
1784 }
1785
1786 fout_ << "\nTEST: UniformRandomIntegers with range [0, 11)" ;
1787 ppuint range{ 11u } ;
1788 UniformRandomIntegers<ppuint> randum( range ) ;
1789 ppuint ran1{ randum.rand() } ;
1790 if (ran1 >= 0u && ran1 < range)
1791 fout_ << ".........PASS!" ;
1792 else
1793 {
1794 fout_ << "\n\tERROR: random number generator out of range. num = " << ran1 << " not in range [0, " << range << ")" << " failed." << endl ;
1795 status = false ;
1796 }
1797
1798 fout_ << "\nTEST: isProbablyPrime on ppuint prime 97 with random x = 10" ;
1799 if ( isProbablyPrime( static_cast<ppuint>( 97u ), static_cast<ppuint>( 10u ) ) == Primality::ProbablyPrime)
1800 fout_ << ".........PASS!" ;
1801 else
1802 {
1803 fout_ << ".........FAIL!" << endl ;
1804 status = false ;
1805 }
1806
1807 fout_ << "\nTEST: isAlmostSurelyPrime for ppuint prime 97" ;
1808 if ( isAlmostSurelyPrime( static_cast<ppuint>( 97u ) ))
1809 fout_ << ".........PASS!" ;
1810 else
1811 {
1812 fout_ << ".........FAIL!" << endl ;
1813 status = false ;
1814 }
1815
1816 fout_ << "\nTEST: isAlmostSurelyPrime for BigInt prime 97" ;
1817 if ( isAlmostSurelyPrime( static_cast<BigInt>( "97" ) ))
1818 fout_ << ".........PASS!" ;
1819 else
1820 {
1821 fout_ << ".........FAIL!" << endl ;
1822 status = false ;
1823 }
1824
1825 fout_ << "\nTEST: isAlmostSurelyPrime for non-prime BigInt 49" ;
1826 if (isAlmostSurelyPrime( static_cast<BigInt>( 49u ) ))
1827 {
1828 fout_ << ".........FAIL!" << endl ;
1829 status = false ;
1830 }
1831 else
1832 fout_ << ".........PASS!" ;
1833
1834 fout_ << "\nTEST: isAlmostSurelyPrime on the 10000th prime number 104729 of ppuint type" ;
1835 if (isAlmostSurelyPrime( static_cast<ppuint>( 104729u )))
1836 fout_ << ".........PASS!" ;
1837 else
1838 {
1839 fout_ << ".........FAIL!" << endl ;
1840 status = false ;
1841 }
1842
1843 return status ;
1844}
1845
1846
1847bool UnitTest::unitTestFactoring()
1848{
1849 bool status = true ;
1850
1851 fout_ << "\nTEST: Factor table method used on unsigned int 3^20 - 1 = 3486784400 = 2^4 5^2 11^2 61 1181" ;
1852
1853 // 3^20 - 1 = 3486784400 = 2^4 5^2 11^2 61 1181
1854 ppuint num{ 3486784400 } ;
1855 ppuint p{ 3 } ;
1856 ppuint n{ 20 } ;
1857
1858 Factorization<ppuint> f( num, FactoringAlgorithm::FactorTable, p, n ) ;
1859 vector<ppuint> df = f.getDistinctPrimeFactors() ;
1860
1861 if (!(f.multiplicity(0) == 4 && f.primeFactor(0) == 2u && f.primeFactor(0) == df[0] &&
1862 f.multiplicity(1) == 2 && f.primeFactor(1) == 5u && f.primeFactor(1) == df[1] &&
1863 f.multiplicity(2) == 2 && f.primeFactor(2) == 11u && f.primeFactor(2) == df[2] &&
1864 f.multiplicity(3) == 1 && f.primeFactor(3) == 61u && f.primeFactor(2) == df[2] &&
1865 f.multiplicity(4) == 1 && f.primeFactor(4) == 1181u && f.primeFactor(2) == df[2] ))
1866 {
1867 fout_ << "\n\tERROR: Table lookup factoring on unsigned int." << endl ;
1868 status = false ;
1869
1870 fout_ << "\tFactor<ppuint> failed on 337500 = 2^2 3^3 5^5." << endl ;
1871 fout_ << "\tNumber of factors = " << f.numDistinctFactors() << endl ;
1872 fout_ << "\tFactors = " << endl ;
1873 for (unsigned int i = 0 ; i < f.numDistinctFactors() ; ++i)
1874 fout_ << f.primeFactor( i ) << " ^ " << f.multiplicity( i ) << " " ;
1875 fout_ << endl ;
1876 }
1877 else
1878 fout_ << ".........PASS!" ;
1879
1880
1881 fout_ << "\nTEST: Factor table method used on BigInt 3^20 - 1 = 3486784400 = 2^4 5^2 11^2 61 1181" ;
1882
1883 // 3^20 - 1 = 3486784400 = 2^4 5^2 11^2 61 1181
1884 BigInt num1{ 3486784400u } ;
1885 ppuint p1{ 3 } ;
1886 ppuint n1{ 20 } ;
1887
1888 Factorization<BigInt> f1( num1, FactoringAlgorithm::FactorTable, p1, n1 ) ;
1889 vector<BigInt> df1 = f1.getDistinctPrimeFactors() ;
1890
1891 if (!(f1.multiplicity(0) == 4 && f1.primeFactor(0) == static_cast<BigInt>( 2u ) && f1.primeFactor(0) == df[0] &&
1892 f1.multiplicity(1) == 2 && f1.primeFactor(1) == static_cast<BigInt>( 5u ) && f1.primeFactor(1) == df[1] &&
1893 f1.multiplicity(2) == 2 && f1.primeFactor(2) == static_cast<BigInt>( 11u ) && f1.primeFactor(2) == df[2] &&
1894 f1.multiplicity(3) == 1 && f1.primeFactor(3) == static_cast<BigInt>( 61u ) && f1.primeFactor(2) == df[2] &&
1895 f1.multiplicity(4) == 1 && f1.primeFactor(4) == static_cast<BigInt>( 1181u ) && f1.primeFactor(2) == df[2] ))
1896 {
1897 fout_ << "\n\tERROR: Table lookup factoring on unsigned int." << endl ;
1898 status = false ;
1899
1900 fout_ << "\tFactor<BigInt> failed on 337500 = 2^2 3^3 5^5." << endl ;
1901 fout_ << "\tNumber of factors = " << f.numDistinctFactors() << endl ;
1902 fout_ << "\tFactors = " << endl ;
1903 for (unsigned int i = 0 ; i < f.numDistinctFactors() ; ++i)
1904 fout_ << f.primeFactor( i ) << " ^ " << f.multiplicity( i ) << " " ;
1905 fout_ << endl ;
1906 }
1907 else
1908 fout_ << ".........PASS!" ;
1909
1910
1911 fout_ << "\nTEST: Trial division factoring on unsigned int 337500 = 2^2 3^3 5^5." ;
1912
1913 Factorization<ppuint> f2( 337500u, FactoringAlgorithm::TrialDivisionAlgorithm ) ;
1914 vector<ppuint> df2 = f2.getDistinctPrimeFactors() ;
1915
1916 if (!(f2.multiplicity(0) == 2 && f2.primeFactor(0) == 2u && f2.primeFactor(0) == df2[0] &&
1917 f2.multiplicity(1) == 3 && f2.primeFactor(1) == 3u && f2.primeFactor(1) == df2[1] &&
1918 f2.multiplicity(2) == 5 && f2.primeFactor(2) == 5u && f2.primeFactor(2) == df2[2] ))
1919 {
1920 fout_ << "\n\tERROR: Trial division factoring on unsigned int." << endl ;
1921 status = false ;
1922
1923 fout_ << "\tFactor<ppuint> failed on 337500 = 2^2 3^3 5^5." << endl ;
1924 fout_ << "\tNumber of factors = " << f2.numDistinctFactors() << endl ;
1925 fout_ << "\tFactors = " << endl ;
1926 for (unsigned int i = 0 ; i < f2.numDistinctFactors() ; ++i)
1927 fout_ << f2.primeFactor( i ) << " ^ " << f2.multiplicity( i ) << " " ;
1928 fout_ << endl ;
1929 }
1930 else
1931 fout_ << ".........PASS!" ;
1932
1933
1934 fout_ << "\nTEST: Trial division factoriing on BigInt 337500 = 2^2 3^3 5^5." ;
1935
1936 Factorization<BigInt> f3( static_cast<BigInt>("337500"), FactoringAlgorithm::TrialDivisionAlgorithm ) ;
1937 vector<BigInt> df3{ f3.getDistinctPrimeFactors() } ;
1938
1939 if (!(f3.multiplicity(0) == 2u && f3.primeFactor( 0 ) == static_cast<BigInt>( 2u ) && f3.primeFactor( 0 ) == df3[0] &&
1940 f3.multiplicity(1) == 3u && f3.primeFactor( 1 ) == static_cast<BigInt>( 3u ) && f3.primeFactor( 1 ) == df3[1] &&
1941 f3.multiplicity(2) == 5u && f3.primeFactor( 2 ) == static_cast<BigInt>( 5u ) && f3.primeFactor( 2 ) == df3[2] ))
1942 {
1943 fout_ << "\n\tERROR:Factorization<BigInt> failed on 337500 = 2^2 3^3 5^5." << endl ;
1944 status = false ;
1945
1946 fout_ << "Number of factors = " << f3.numDistinctFactors() << endl ;
1947 fout_ << "Factors = " << endl ;
1948 for (unsigned int i = 0 ; i < f3.numDistinctFactors() ; ++i)
1949 fout_ << f3.primeFactor( i ) << " ^ " << f3.multiplicity( i ) << " " ;
1950 fout_ << endl ;
1951 }
1952 else
1953 fout_ << ".........PASS!" ;
1954
1955
1956 fout_ << "\nTEST: Pollard Rho factorization on unsigned int 25852 = 2^2 23 281" ;
1957
1958 Factorization<ppuint> fr( 25852u, FactoringAlgorithm::pollardRhoAlgorithm ) ;
1959 vector<ppuint> dfr = fr.getDistinctPrimeFactors() ;
1960
1961 if ( !(fr.multiplicity(0) == 2 && fr.primeFactor(0) == 2u && fr.primeFactor(0) == dfr[0] &&
1962 fr.multiplicity(1) == 1 && fr.primeFactor(1) == 23u && fr.primeFactor(1) == dfr[1] &&
1963 fr.multiplicity(2) == 1 && fr.primeFactor(2) == 281u && fr.primeFactor(2) == dfr[2] ))
1964 {
1965 fout_ << "\n\tERROR:Factorization<ppuint> failed on 25852 = 2^2 23 281." << endl ;
1966
1967 status = false ;
1968 fout_ << "Number of factors = " << fr.numDistinctFactors() << endl ;
1969 fout_ << "Factors = " << endl ;
1970 for (unsigned int i = 0 ; i < fr.numDistinctFactors() ; ++i)
1971 fout_ << fr.primeFactor( i ) << " ^ " << fr.multiplicity( i ) << " " ;
1972 fout_ << endl ;
1973 }
1974 else
1975 fout_ << ".........PASS!" ;
1976
1977
1978 fout_ << "\nTEST: Pollard Rho factorization on BigInt 25852 = 2^2 23 281" ;
1979
1980 Factorization<BigInt> frb( static_cast<BigInt>( 25852u ), FactoringAlgorithm::pollardRhoAlgorithm ) ;
1981 vector<BigInt> dfrb = frb.getDistinctPrimeFactors() ;
1982
1983 if ( !(frb.multiplicity(0) == 2 && frb.primeFactor(0) == static_cast<BigInt>( 2u ) && frb.primeFactor(0) == dfrb[0] &&
1984 frb.multiplicity(1) == 1 && frb.primeFactor(1) == static_cast<BigInt>( 23u ) && frb.primeFactor(1) == dfrb[1] &&
1985 frb.multiplicity(2) == 1 && frb.primeFactor(2) == static_cast<BigInt>( 281u ) && frb.primeFactor(2) == dfrb[2] ))
1986 {
1987 fout_ << "\n\tERROR:Factorization<BigInt> failed on 25852 = 2^2 23 281." << endl ;
1988
1989 status = false ;
1990 fout_ << "Number of factors = " << frb.numDistinctFactors() << endl ;
1991 fout_ << "Factors = " << endl ;
1992 for (unsigned int i = 0 ; i < frb.numDistinctFactors() ; ++i)
1993 fout_ << frb.primeFactor( i ) << " ^ " << frb.multiplicity( i ) << " " ;
1994 fout_ << endl ;
1995 }
1996 else
1997 fout_ << ".........PASS!" ;
1998
1999
2000 fout_ << "\nTEST: BigInt computation of p^n, r, factors of r, EulerPhi[ p^n - 1]/n for p = 2" ;
2001 {
2002 try
2003 {
2004 ppuint p{ 2u } ;
2005 ppuint n{ 36u } ;
2006
2007 // n
2008 // Create a polynomial of degree n modulo p: x + 1
2009 vector<ppuint> coeff {0} ;
2010 TrialPolynomial f( coeff ) ;
2011 f.initialTrialPoly( n, p ) ;
2012
2013 // We'll do the factorization here.
2014 PolyOrder order( f ) ;
2015
2016 if ( !( order.getMaxNumPoly() == static_cast<BigInt>( "68719476736" ) && order.getR() == static_cast<BigInt>( "68719476735" ) &&
2017 order.getFactorsOfR().primeFactor(0) == static_cast<BigInt>( 3u ) &&
2018 order.getFactorsOfR().multiplicity(0) == 3 &&
2019 order.getFactorsOfR().primeFactor(1) == static_cast<BigInt>( 5u ) &&
2020 order.getFactorsOfR().multiplicity(1) == 1 &&
2021 order.getFactorsOfR().primeFactor(2) == static_cast<BigInt>( 7u ) &&
2022 order.getFactorsOfR().multiplicity(2) == 1 &&
2023 order.getFactorsOfR().primeFactor(3) == static_cast<BigInt>( 13u ) &&
2024 order.getFactorsOfR().multiplicity(3) == 1 &&
2025 order.getFactorsOfR().primeFactor(4) == static_cast<BigInt>( 19u ) &&
2026 order.getFactorsOfR().multiplicity(4) == 1 &&
2027 order.getFactorsOfR().primeFactor(5) == static_cast<BigInt>( 37u ) &&
2028 order.getFactorsOfR().multiplicity(5) == 1 &&
2029 order.getFactorsOfR().primeFactor(6) == static_cast<BigInt>( 73u ) &&
2030 order.getFactorsOfR().multiplicity(6) == 1 &&
2031 order.getFactorsOfR().primeFactor(7) == static_cast<BigInt>(109u ) &&
2032 order.getFactorsOfR().multiplicity(7) == 1 &&
2033 order.getNumPrimPoly() == static_cast<BigInt>( "725594112" )
2034 ))
2035 {
2036 fout_ << "\n\tERROR: BigInt computation of p^n, r, factors of r, EulerPhi[ p^n - 1]/n for p = 2" << endl ;
2037 status = false ;
2038
2039 fout_ << "p = " << p << endl ;
2040 fout_ << "n = " << n << endl ;
2041 fout_ << "max_num_possible_poly = " << order.getMaxNumPoly() << endl ;
2042 fout_ << "r = " << order.getR() << endl ;
2043 fout_ << "r: Number of factors = " << order.getFactorsOfR().numDistinctFactors() << endl ;
2044 fout_ << "Factors = " << endl ;
2045 for (unsigned int i = 0 ; i < order.getFactorsOfR().numDistinctFactors() ; ++i)
2046 fout_ << order.getFactorsOfR().primeFactor( i ) << " ^ " << order.getFactorsOfR().multiplicity( i ) << " " ;
2047 fout_ << endl ;
2048
2049 fout_ << "num_primitive_poly = " << order.getNumPrimPoly() << endl ;
2050 }
2051 else
2052 fout_ << ".........PASS!" ;
2053 }
2054 catch( BigIntMathError & e )
2055 {
2056 fout_ << ".........FAIL!" << endl ;
2057 fout_ << " caught BigIntMathError: [ " << e.what() << " ] " << endl ;
2058 status = false ;
2059 }
2060 catch( FactorError & e )
2061 {
2062 fout_ << ".........FAIL!" << endl ;
2063 fout_ << " caught FactorError: [ " << e.what() << " ] " << endl ;
2064 status = false ;
2065 }
2066 }
2067
2068
2069 fout_ << "\nTEST: Factor Copy constructor" ;
2070 Factorization<BigInt> fact( f3 ) ;
2071 vector<BigInt> dfact = fact.getDistinctPrimeFactors() ;
2072 if (!(fact.multiplicity(0) == 2 && fact.primeFactor(0) == static_cast<BigInt>( 2u ) && fact.primeFactor(0) == dfact[0] &&
2073 fact.multiplicity(1) == 3 && fact.primeFactor(1) == static_cast<BigInt>( 3u ) && fact.primeFactor(1) == dfact[1] &&
2074 fact.multiplicity(2) == 5 && fact.primeFactor(2) == static_cast<BigInt>( 5u ) && fact.primeFactor(2) == dfact[2] ))
2075 {
2076 fout_ << "\n\tERROR: Factor copy constructor failed on 337500 = 2^2 3^3 5^5." << endl ;
2077 status = false ;
2078
2079 fout_ << "Number of factors = " << fact.numDistinctFactors() << endl ;
2080 fout_ << "Factors = " << endl ;
2081 for (unsigned int i = 0 ; i < fact.numDistinctFactors() ; ++i)
2082 fout_ << fact.primeFactor( i ) << " ^ " << fact.multiplicity( i ) << " " ;
2083 fout_ << endl ;
2084 }
2085 else
2086 fout_ << ".........PASS!" ;
2087
2088
2089
2090 fout_ << "\nTEST: Factor assignment operator" ;
2091 Factorization<BigInt> fact1 ;
2092 fact1 = f3 ;
2093 vector<BigInt> dfact1 = fact1.getDistinctPrimeFactors() ;
2094 if (!(fact1.multiplicity(0) == 2 && fact1.primeFactor(0) == static_cast<BigInt>( 2u ) && dfact1[0] == fact1.primeFactor(0) &&
2095 fact1.multiplicity(1) == 3 && fact1.primeFactor(1) == static_cast<BigInt>( 3u ) && dfact1[1] == fact1.primeFactor(1) &&
2096 fact1.multiplicity(2) == 5 && fact1.primeFactor(2) == static_cast<BigInt>( 5u ) && dfact1[2] == fact1.primeFactor(2) ))
2097 {
2098 fout_ << "\n\tERROR: Factor assignment operator failed on 337500 = 2^2 3^3 5^5." << endl ;
2099 status = false ;
2100
2101 fout_ << "Number of factors = " << fact1.numDistinctFactors() << endl ;
2102 fout_ << "Factors = " << endl ;
2103 for (unsigned int i = 0 ; i < fact1.numDistinctFactors() ; ++i)
2104 fout_ << fact1.primeFactor( i ) << " ^ " << fact1.multiplicity( i ) << " " ;
2105 fout_ << endl ;
2106 }
2107 else
2108 fout_ << ".........PASS!" ;
2109
2110 return status ;
2111}
2112
2113
2114bool UnitTest::unitTestPolynomials()
2115{
2116 bool status = true ;
2117
2118 fout_ << "\nTEST: Polynomial() default constructor." ;
2119 {
2120 Polynomial p ;
2121 if (p.deg() != 0)
2122 {
2123 fout_ << "\n\tERROR: Polynomial default constructor failed." << endl ;
2124 status = false ;
2125 }
2126 else
2127 fout_ << ".........PASS!" ;
2128 }
2129
2130 fout_ << "\nTEST: Polynomial() from string." ;
2131 {
2132 Polynomial p( "2x^2 + 1, 3" ) ;
2133 if (p.deg() != 2 || p.modulus() != 3 || p[0] != 1 || p[1] != 0 || p[2] != 2)
2134 {
2135 fout_ << "\n\tERROR: Polynomial p( \"2x^2 + 1, 3\" ) failed." << endl ;
2136 status = false ;
2137 }
2138 else
2139 fout_ << ".........PASS!" ;
2140 }
2141
2142 fout_ << "\nTEST: Polynomial = string." ;
2143 {
2144 Polynomial p ;
2145 p = "2x^2 + 1, 3" ;
2146 if (p.deg() != 2 || p.modulus() != 3 || p[0] != 1 || p[1] != 0 || p[2] != 2)
2147 {
2148 fout_ << "\n\tERROR: Polynomial p = string \"2x^2 + 1, 3\" ) failed." << endl ;
2149 status = false ;
2150 }
2151 else
2152 fout_ << ".........PASS!" ;
2153 }
2154
2155 fout_ << "\nTEST: Polynomial() from string with negative constant should give a parser error." ;
2156 try
2157 {
2158 Polynomial p( "x^4-1, 5" ) ;
2159 fout_ << "\n\tERROR: Polynomial with negative constant failed to throw an exception " << endl ;
2160 status = false ;
2161 }
2162 catch( PolynomialRangeError & e )
2163 {
2164 // Match only the error message.
2165 // The file name and line number where the error occurred may change with different versions of this software.
2166 string trueErrorMessage = "Error in parser converting polynomial from string x^4-1, 5 for p = 2 Error: negative number for a polynomial coefficient = -1 is not allowed. Numbers must be >= 0" ;
2167 if (static_cast<string>(e.what()).find( trueErrorMessage ) == string::npos)
2168 {
2169 fout_ << "\n\tERROR: Incorrect error message = |" << e.what() << "|" << endl ;
2170 status = false ;
2171 }
2172 else
2173 fout_ << ".........PASS!" ;
2174 }
2175
2176 fout_ << "\nTEST: Polynomial() to string." ;
2177 {
2178 Polynomial p ; // ( "2x^2 + 1, 3" )
2179 Polynomial q( p ) ;
2180 p[0] = 1 ; p[2] = 2 ;
2181 p.setModulus( 3 ) ;
2182 string s = p ;
2183 if (s != "2 x ^ 2 + 1, 3")
2184 {
2185 fout_ << "\n\tERROR: Polynomial p( \"2x^2 + 1, 3\" ) to string s = " << s << " failed." << endl ;
2186 status = false ;
2187 }
2188 else
2189 fout_ << ".........PASS!" ;
2190 }
2191
2192 fout_ << "\nTEST: Polynomial() copy constructor." ;
2193 try
2194 {
2195 Polynomial p( "2x^2 + 1, 3" ) ;
2196 Polynomial q( p ) ;
2197 if (static_cast<string>(q) != "2 x ^ 2 + 1, 3")
2198 {
2199 fout_ << "\n\tERROR: Polynomial copy constructor p( q ) = " << q << " failed." << endl ;
2200 status = false ;
2201 }
2202 else
2203 fout_ << ".........PASS!" ;
2204 }
2205 catch( PolynomialRangeError & e )
2206 {
2207 fout_ << "\n\tERROR: PolynomialRangeError error: copy constructor failed [ " << e.what() << " ] " << endl ;
2208 status = false ;
2209 }
2210
2211 fout_ << "\nTEST: Polynomial equality test operator==()." ;
2212 try
2213 {
2214 Polynomial p1( "2x^2 + 1, 3" ) ;
2215 Polynomial p2( "2x^2 + 1, 3" ) ;
2216 if (p1 == p2)
2217 fout_ << ".........PASS!" ;
2218 else
2219 {
2220 fout_ << "\n\tERROR: Polynomial " << p1 << " == " << p2 << " failed." << endl ;
2221 status = false ;
2222 }
2223 }
2224 catch( PolynomialRangeError & e )
2225 {
2226 fout_ << "\n\tERROR: PolynomialRangeError error: operator()== failed [ " << e.what() << " ] " << endl ;
2227 status = false ;
2228 }
2229
2230 fout_ << "\nTEST: Polynomial inequality test operator!=()." ;
2231 try
2232 {
2233 Polynomial p1( "2x^2 + 1, 3" ) ;
2234 Polynomial p2( "2x^2 + x + 1, 3" ) ;
2235 if (p1 != p2)
2236 fout_ << ".........PASS!" ;
2237 else
2238 {
2239 fout_ << "\n\tERROR: Polynomial " << p1 << " != " << p2 << " failed." << endl ;
2240 status = false ;
2241 }
2242 }
2243 catch( PolynomialRangeError & e )
2244 {
2245 fout_ << "\n\tERROR: PolynomialRangeError error: operator()!= failed [ " << e.what() << " ] " << endl ;
2246 status = false ;
2247 }
2248
2249 fout_ << "\nTEST: Polynomial assignment operator." ;
2250 try
2251 {
2252 Polynomial p( "2x^2 + 1, 3" ) ;
2253 Polynomial q ;
2254 q = p ; // If we did Polynomial q = p it would call the copy constructor.
2255 if (static_cast<string>(q) != "2 x ^ 2 + 1, 3")
2256 {
2257 fout_ << "\n\tERROR: Polynomial assignment operator p = q " << q << " failed." << endl ;
2258 status = false ;
2259 }
2260 else
2261 fout_ << ".........PASS!" ;
2262 }
2263 catch( PolynomialRangeError & e )
2264 {
2265 fout_ << "\n\tERROR: PolynomialRangeError error: assignment operator p = q failed [ " << e.what() << " ] " << endl ;
2266 status = false ;
2267 }
2268
2269 fout_ << "\nTEST: Polynomial()[] read only operator." ;
2270 try
2271 {
2272 Polynomial p( "2x^2 + 1, 3" ) ;
2273 if (p[ 0 ] == 1 && p[ 1 ] == 0 && p[ 2 ] == 2)
2274 fout_ << ".........PASS!" ;
2275 else
2276 {
2277 fout_ << "\n\tERROR: Polynomial [] read only failed on reading p[0], p[1], p[2]." << endl ;
2278 status = false ;
2279 }
2280 }
2281 catch( PolynomialRangeError & e )
2282 {
2283 fout_ << "\n\tERROR: Polynomial [] read only failed on reading p[0], p[1], p[2] [ " << e.what() << " ] " << endl ;
2284 status = false ;
2285 }
2286
2287 fout_ << "\nTEST: Polynomial()[] accessing coeff higher than its degree." ;
2288 try
2289 {
2290 const Polynomial p( "2x^2 + 1, 3" ) ;
2291 ppuint z{ p[ 3 ] } ;
2292
2293 fout_ << "\n\tERROR: Polynomial [] failed to throw exception on accessing p[3] = " << z << endl ;
2294 fout_ << "poly = " << p << " deg of p = " << p.deg() << endl ;
2295 status = false ;
2296 }
2297 catch( PolynomialRangeError & e )
2298 {
2299 fout_ << ".........PASS!" ;
2300 }
2301
2302 fout_ << "\nTEST: Polynomial()[] lvalue operator." ;
2303 try
2304 {
2305 Polynomial p( "2x^2 + 1, 3" ) ;
2306 int oldDeg{ p.deg() } ;
2307 p[ 5 ] = 2 ;
2308 p[ 1 ] = 1 ;
2309 int newDeg = p.deg() ;
2310 if (static_cast<string>(p) != "2 x ^ 5 + 2 x ^ 2 + x + 1, 3" || oldDeg != 2 || newDeg != 5)
2311 {
2312 fout_ << "\n\tERROR: Polynomial [] lvalue operator " << p << " failed." << endl ;
2313 status = false ;
2314 }
2315 else
2316 fout_ << ".........PASS!" ;
2317 }
2318 catch( PolynomialRangeError & e )
2319 {
2320 fout_ << "\n\tERROR: Polynomial [] failed [ " << e.what() << " ] " << endl ;
2321 status = false ;
2322 }
2323
2324 fout_ << "\nTEST: Polynomial() += operator." ;
2325 try
2326 {
2327 Polynomial p( "2x^2 + 1, 3" ) ;
2328 Polynomial q( " x^2 + 1, 3" ) ;
2329 p += q ;
2330 if (p.deg() != 1 && static_cast<string>(p) != "2, 3")
2331 {
2332 fout_ << "\n\tERROR: Polynomial += " << p << " failed." << endl ;
2333 status = false ;
2334 }
2335 else
2336 fout_ << ".........PASS!" ;
2337 }
2338 catch( PolynomialRangeError & e )
2339 {
2340 fout_ << "\n\tERROR: Polynomial += failed. [ " << e.what() << " ] " << endl ;
2341 status = false ;
2342 }
2343
2344 fout_ << "\nTEST: Polynomial() += operator." ;
2345 try
2346 {
2347 Polynomial p( "2x^2 + 1, 3" ) ;
2348 Polynomial q( " x^2 + 2, 3" ) ;
2349 p += q ;
2350 if (p.deg() != 0 && static_cast<string>(p) != "0, 3")
2351 {
2352 fout_ << "\n\tERROR: Polynomial += " << p << " failed." << endl ;
2353 status = false ;
2354 }
2355 else
2356 fout_ << ".........PASS!" ;
2357 }
2358 catch( PolynomialRangeError & e )
2359 {
2360 fout_ << "\n\tERROR: Polynomial += failed [ " << e.what() << " ] " << endl ;
2361 status = false ;
2362 }
2363
2364 fout_ << "\nTEST: Polynomial() + operator." ;
2365 try
2366 {
2367 Polynomial p( "2x^2 + 1, 3" ) ;
2368 Polynomial q( " x^2 + 1, 3" ) ;
2369 Polynomial r = p + q ;
2370 if (static_cast<string>(r) != "2, 3")
2371 {
2372 fout_ << "\n\tERROR: Polynomial + " << r << " failed." << endl ;
2373 status = false ;
2374 }
2375 else
2376 fout_ << ".........PASS!" ;
2377 }
2378 catch( PolynomialRangeError & e )
2379 {
2380 fout_ << "\n\tERROR: Polynomial + failed [ " << e.what() << " ] " << endl ;
2381 status = false ;
2382 }
2383
2384 fout_ << "\nTEST: Polynomial * scalar" ;
2385 try
2386 {
2387 Polynomial p( "2x^2 + 1, 3" ) ;
2388 ppuint k{ 2 } ;
2389
2390 Polynomial q = p * k ;
2391 if (static_cast<string>(q) != "x ^ 2 + 2, 3")
2392 {
2393 fout_ << "\n\tERROR: Polynomial * scalar operator " << q << " failed." << endl ;
2394 status = false ;
2395 }
2396 else
2397 fout_ << ".........PASS!" ;
2398 }
2399 catch( PolynomialRangeError & e )
2400 {
2401 fout_ << "\n\tERROR: PolynomialRangeError error: * scalar failed [ " << e.what() << " ] " << endl ;
2402 status = false ;
2403 }
2404
2405
2406 fout_ << "\nTEST: Polynomial evaluation x^4 + 3x + 3 (mod 5)" ;
2407 {
2408 Polynomial p( "x^4 + 3x + 3, 5" ) ;
2409 ppuint f2{ p( 2 ) } ;
2410 ppuint f3{ p( 3 ) } ;
2411 ppuint f0{ p( 0 ) } ;
2412 if (f2 != 0 || f3 != 3 || f0 != 3)
2413 {
2414 fout_ << "\n\tERROR: Polynomial operator() = " << f2 << f3 << f0 << " failed." << endl ;
2415 status = false ;
2416 }
2417 else
2418 fout_ << ".........PASS!" ;
2419 }
2420
2421 fout_ << "\nTEST: Polynomial evaluation x^4 + x + 1 (mod 2)" ;
2422 {
2423 Polynomial p( "x^4 + x + 1, 2" ) ;
2424 ppuint f0{ p( 0 ) } ;
2425 ppuint f1{ p( 1 ) } ;
2426 if (f0 != 1 || f1 != 1)
2427 {
2428 fout_ << "\n\tERROR: Polynomial operator() = " << f0 << f1 << " failed." << endl ;
2429 status = false ;
2430 }
2431 else
2432 fout_ << ".........PASS!" ;
2433 }
2434
2435 fout_ << "\nTEST: Polynomial hasLinearFactor is true" ;
2436 {
2437 Polynomial p( "x^4 + 3x + 3, 5" ) ;
2438 bool linFac = p.hasLinearFactor() ;
2439 if (linFac)
2440 fout_ << ".........PASS!" ;
2441 else
2442 {
2443 fout_ << "\n\tERROR: Polynomial hasLinearFactor = " << linFac << " failed." << endl ;
2444 status = false ;
2445 }
2446 }
2447
2448 fout_ << "\nTEST: Polynomial hasLinearFactor is false" ;
2449 {
2450 Polynomial p( "x^4 + 3x^2 + x + 1, 5" ) ;
2451 bool linFac = p.hasLinearFactor() ;
2452 if (!linFac)
2453 fout_ << ".........PASS!" ;
2454 else
2455 {
2456 fout_ << "\n\tERROR: Polynomial hasLinearFactor = " << linFac << " failed." << endl ;
2457 status = false ;
2458 }
2459 }
2460
2461 fout_ << "\nTEST: Polynomial isInteger" ;
2462 try
2463 {
2464 Polynomial p( "x^4 + 3x + 3, 5" ) ;
2465 bool isInt = p.isInteger() ;
2466 if (!isInt)
2467 fout_ << ".........PASS!" ;
2468 else
2469 {
2470 fout_ << "\n\tERROR: Polynomial " << p << " isInteger = " << isInt << " failed." << endl ;
2471 status = false ;
2472 }
2473
2474 Polynomial q( "3, 5" ) ;
2475 isInt = q.isInteger() ;
2476 if (isInt)
2477 fout_ << ".........PASS!" ;
2478 else
2479 {
2480 fout_ << "\n\tERROR: Polynomial " << q << " isInteger = " << isInt << " failed." << endl ;
2481 status = false ;
2482 }
2483
2484 }
2485 catch( PolynomialRangeError & e )
2486 {
2487 fout_ << "\n\tERROR: PolynomialRangeError error: polynomial operator() failed [ " << e.what() << " ] " << endl ;
2488 status = false ;
2489 }
2490
2491 fout_ << "\nTEST: Polynomial initial and next trial polynomials" ;
2492 try {
2493 TrialPolynomial p ;
2494 p.initialTrialPoly( 4, 5 ) ;
2495
2496 for (int i = 1 ; i <= 3 ; ++i)
2497 {
2498 p.nextTrialPoly() ;
2499 }
2500 if (static_cast<string>(p) == "x ^ 4 + 3, 5")
2501 fout_ << ".........PASS!" ;
2502 else
2503 {
2504 fout_ << "\n\tERROR: Polynomial " << p << " (3rd iteration from x^n initial) failed." << endl ;
2505 status = false ;
2506 }
2507 }
2508 catch( PolynomialRangeError & e )
2509 {
2510 fout_ << "\n\tERROR: PolynomialRangeError error: polynomial operator() failed [ " << e.what() << " ] " << endl ;
2511 status = false ;
2512 }
2513
2514 ////////////////////////////////////////////////////////////////////////
2515 // Test polynomial mod
2516 ////////////////////////////////////////////////////////////////////////
2517
2518 fout_ << "\nTEST: PolyMod constructor from polynomials." ;
2519 try {
2520 Polynomial g( "x^4 + x^2 + 1,2" ) ;
2521 Polynomial f( "x^4 + x + 1,2" ) ;
2522
2523 PolyMod p( g, f ) ;
2524 if (static_cast<string>(p) == "x ^ 2 + x, 2" &&
2525 static_cast<string>( p.getf() ) == "x ^ 4 + x + 1, 2" && p.getModulus() == 2)
2526 fout_ << ".........PASS!" ;
2527 else
2528 {
2529 fout_ << "\n\tERROR: PolyMod constructor from polynomials, g(x) = " << p << " failed." << endl ;
2530 status = false ;
2531 }
2532 }
2533 catch( PolynomialRangeError & e )
2534 {
2535 fout_ << "\n\tERROR: PolynomialRangeError error: [ " << e.what() << " ] " << endl ;
2536 status = false ;
2537 }
2538
2539 fout_ << "\nTEST: PolyMod constructor from string and polynomial." ;
2540 try {
2541 Polynomial f( "x^4 + x^2 + 2x + 3, 5" ) ;
2542 PolyMod p( "x^6 + 2x^2 + 3x + 2, 5", f ) ;
2543
2544 if (static_cast<string>(p) == "3 x ^ 3, 5" &&
2545 static_cast<string>( p.getf() ) == "x ^ 4 + x ^ 2 + 2 x + 3, 5" && p.getModulus() == 5)
2546 fout_ << ".........PASS!" ;
2547 else
2548 {
2549 fout_ << "\n\tERROR: PolyMod constructor from string and polynomial failed." << endl ;
2550 fout_ << "\ng(x) mod f(x), p = " << p << endl ;
2551 fout_ << "\nf(x) = " << f << endl ;
2552 status = false ;
2553 }
2554 }
2555 catch( PolynomialRangeError & e )
2556 {
2557 fout_ << "\n\tERROR: PolynomialRangeError error: [ " << e.what() << " ] " << endl ;
2558 status = false ;
2559 }
2560
2561 fout_ << "\nTEST: PolyMod timesX." ;
2562 try {
2563 Polynomial g( "2x^3 + 4x^2 + 3x, 5" ) ;
2564 Polynomial f( "x^4 + x^2 + 2x + 3, 5" ) ;
2565
2566 PolyMod p( g, f ) ;
2567
2568 p.timesX() ;
2569 if (static_cast<string>(p) == "4 x ^ 3 + x ^ 2 + x + 4, 5" )
2570 fout_ << ".........PASS!" ;
2571 else
2572 {
2573 fout_ << "\n\tERROR: PolyMod timesX " << p << " failed." << endl ;
2574 status = false ;
2575 }
2576 }
2577 catch( PolynomialRangeError & e )
2578 {
2579 fout_ << "\n\tERROR: PolynomialRangeError error: [ " << e.what() << " ] " << endl ;
2580 status = false ;
2581 }
2582
2583 fout_ << "\nTEST: PolyMod autoconvolve." ;
2584 try {
2585 Polynomial t( "4x^3 + x^2 + 3x + 3, 5" ) ;
2586 int k{ 3 } ; int lower{ 1 } ; int upper{ 3 } ;
2587 ppuint c{ autoConvolve( t, k, lower, upper ) } ;
2588
2589 if (c == 3)
2590 fout_ << ".........PASS!" ;
2591 else
2592 {
2593 fout_ << "\n\tERROR: PolyMod autoconvolve = " << c
2594 << " for t = " << t << " deg = " << t.deg() << " failed." << endl ;
2595 status = false ;
2596 }
2597 }
2598 catch( PolynomialRangeError & e )
2599 {
2600 fout_ << "\n\tERROR: PolynomialRangeError autoconvolve [ " << e.what() << " ] " << endl ;
2601 status = false ;
2602 }
2603
2604 fout_ << "\nTEST: PolyMod convolve." ;
2605 try {
2606 Polynomial s( "4x^3 + x^2 + 3x + 3, 5" ) ;
2607 Polynomial t( "4x^3 + x^2 + 3x + 3, 5" ) ;
2608 int k{ 3 } ; int lower{ 1 } ; int upper{ 3 } ;
2609 ppuint c{ convolve( s, t, k, lower, upper ) } ;
2610
2611 if (c == 3)
2612 fout_ << ".........PASS!" ;
2613 else
2614 {
2615 fout_ << "\n\tERROR: PolyMod convolve = " << c
2616 << " for t = " << t << " deg = " << t.deg() << " failed." << endl ;
2617 status = false ;
2618 }
2619 }
2620 catch( PolynomialRangeError & e )
2621 {
2622 fout_ << "\n\tERROR: PolynomialRangeError convolve [ " << e.what() << " ] " << endl ;
2623 status = false ;
2624 }
2625
2626 fout_ << "\nTEST: PolyMod coeffOfSquare." ;
2627 try {
2628 Polynomial g( "4x^3 + x^2 + 3x + 3, 5" ) ;
2629 int n = 4 ;
2630 ppuint c0{ coeffOfSquare( g, 0, n ) } ;
2631 ppuint c1{ coeffOfSquare( g, 1, n ) } ;
2632 ppuint c2{ coeffOfSquare( g, 2, n ) } ;
2633 ppuint c3{ coeffOfSquare( g, 3, n ) } ;
2634 ppuint c4{ coeffOfSquare( g, 4, n ) } ;
2635 ppuint c5{ coeffOfSquare( g, 5, n ) } ;
2636 ppuint c6{ coeffOfSquare( g, 6, n ) } ;
2637
2638 if (c0 == 4 && c1 == 3 && c2 == 0 && c3 == 0 && c4 == 0 && c5 == 3 && c6 == 1)
2639 fout_ << ".........PASS!" ;
2640 else
2641 {
2642 fout_ << "\n\tERROR: PolyMod coeffOfSquare (c0 ... c6) = " << c0 << " " << c1 << " " << c2
2643 << " " << c3 << " " << c4 << " " << c5 << " " << c6 << " failed." << endl ;
2644 status = false ;
2645 }
2646 }
2647 catch( PolynomialRangeError & e )
2648 {
2649 fout_ << "\n\tERROR: PolynomialRangeError coeffOfSquare [ " << e.what() << " ] " << endl ;
2650 status = false ;
2651 }
2652
2653 fout_ << "\nTEST: PolyMod coeffOfProduct." ;
2654 try {
2655 Polynomial s( "4x^3 + x^2 + 4, 5" ) ;
2656 Polynomial t( "3x^2 + x + 2, 5" ) ;
2657 int n = 4 ;
2658 ppuint c0{ coeffOfProduct( s, t, 0, n ) } ;
2659 ppuint c1{ coeffOfProduct( s, t, 1, n ) } ;
2660 ppuint c2{ coeffOfProduct( s, t, 2, n ) } ;
2661 ppuint c3{ coeffOfProduct( s, t, 3, n ) } ;
2662 ppuint c4{ coeffOfProduct( s, t, 4, n ) } ;
2663 ppuint c5{ coeffOfProduct( s, t, 5, n ) } ;
2664 ppuint c6{ coeffOfProduct( s, t, 6, n ) } ;
2665
2666 if (c0 == 3 && c1 == 4 && c2 == 4 && c3 == 4 && c4 == 2 && c5 == 2 && c6 == 0)
2667 fout_ << ".........PASS!" ;
2668 else
2669 {
2670 fout_ << "\n\tERROR: PolyMod coeffOfProduct (c0 ... c6) = " << c0 << " " << c1 << " " << c2
2671 << " " << c3 << " " << c4 << " " << c5 << " " << c6 << " failed." << endl ;
2672 status = false ;
2673 }
2674 }
2675 catch( PolynomialRangeError & e )
2676 {
2677 fout_ << "\n\tERROR: PolynomialRangeError coeffOfProduct [ " << e.what() << " ] " << endl ;
2678 status = false ;
2679 }
2680
2681 fout_ << "\nTEST: PolyMod square." ;
2682 try {
2683 Polynomial g( "4x^3 + x^2 + 4, 5" ) ;
2684 Polynomial f( "x^4 + x^2 + 2x + 3, 5" ) ;
2685
2686 PolyMod p( g, f ) ;
2687
2688 p.square() ;
2689 if (static_cast<string>(p) == "2 x ^ 3 + 4 x ^ 2 + x + 1, 5" )
2690 fout_ << ".........PASS!" ;
2691 else
2692 {
2693 fout_ << "\n\tERROR: PolyMod square " << p << " failed." << endl ;
2694 status = false ;
2695 }
2696 }
2697 catch( PolynomialRangeError & e )
2698 {
2699 fout_ << "\n\tERROR: PolynomialRangeError error [ " << e.what() << " ] " << endl ;
2700 status = false ;
2701 }
2702
2703 fout_ << "\nTEST: PolyMod operator* and implicitly, operator*=" ;
2704 try {
2705 Polynomial s( "4x^3 + x^2 + 4, 5" ) ;
2706 Polynomial t( "3x^2 + x + 2, 5" ) ;
2707 Polynomial f( "x^4 + x^2 + 2x + 3, 5" ) ;
2708
2709 PolyMod smodf( s, f ) ;
2710 PolyMod tmodf( t, f ) ;
2711
2712 PolyMod p = smodf * tmodf ;
2713 if (static_cast<string>(p) == "2 x ^ 3 + 3 x ^ 2 + 4 x + 2, 5" )
2714 fout_ << ".........PASS!" ;
2715 else
2716 {
2717 fout_ << "\n\tERROR: PolyMod operator* " << p << " failed." << endl ;
2718 status = false ;
2719 }
2720 }
2721 catch( PolynomialRangeError & e )
2722 {
2723 fout_ << "\n\tERROR: PolynomialRangeError error [ " << e.what() << " ] " << endl ;
2724 status = false ;
2725 }
2726
2727 fout_ << "\nTEST: PolyMod x_to_power and isInteger()" ;
2728 try {
2729 Polynomial f( "x^4 + x^2 + 2x + 3, 5" ) ;
2730 PolyMod x( "x, 5", f ) ; // g(x) = 0, modulus = 5.
2731
2732 PolyMod p = power( x, static_cast<BigInt>( 156u ) ) ;
2733 if (static_cast<string>(p) == "3, 5" && p.isInteger())
2734 fout_ << ".........PASS!" ;
2735 else
2736 {
2737 fout_ << "\n\tERROR: PolyMod x_to_power = |" << static_cast<string>(p) << "| failed." << endl ;
2738 status = false ;
2739 }
2740 }
2741 catch( PolynomialRangeError & e )
2742 {
2743 fout_ << "\n\tERROR: PolynomialRangeError error: [ " << e.what() << " ] " << endl ;
2744 status = false ;
2745 }
2746
2747 return status ;
2748}
2749
2750
2751bool UnitTest::unitTestPolynomialOrder()
2752{
2753 bool status = true ;
2754
2755 fout_ << "\nTEST: PolyOrder reduced Q-I matrix" ;
2756 try {
2757 Polynomial f( "x^4 + x^2 + 2x + 3, 5" ) ;
2758 PolyOrder order( f ) ;
2759
2760 // Get the fully nullity count. Don't do early out in findNullity().
2761 order.hasMultipleDistinctFactors( false ) ;
2762 string s = order.printQMatrix() ;
2763 string t = "\n( 0 0 0 0 )\n( 0 4 0 0 )\n( 4 0 0 0 )\n( 0 0 4 0 )\n" ;
2764 if (s == t)
2765 fout_ << ".........PASS!" ;
2766 else
2767 {
2768 fout_ << "\n\tERROR: PolyOrder reduced Q-I failed = " << s << endl ;
2769 fout_ << "\n true reduced Q-I = " << t << endl ;
2770 status = false ;
2771 }
2772 }
2773 catch( PolynomialRangeError & e )
2774 {
2775 fout_ << "\n\tERROR: PolynomialRangeError error [ " << e.what() << " ] " << endl ;
2776 status = false ;
2777 }
2778
2779 fout_ << "\nTEST: PolyOrder 3 distinct factors out of 4" ;
2780 try {
2781 Polynomial f( "x^4 + 3 x^3 + 3 x^2 + 3 x + 2, 5" ) ;
2782 PolyOrder order( f ) ;
2783
2784 // Get the fully nullity count. Don't do early out in findNullity().
2785 bool multipleFactors = order.hasMultipleDistinctFactors( false ) ;
2786 if (multipleFactors && order.getNullity() == 3)
2787 fout_ << ".........PASS!" ;
2788 else
2789 {
2790 fout_ << "\n\tERROR: PolyOrder 3 distinct factors out of 4 failed" << endl ;
2791 fout_ << " f( x ) = " << f << endl ;
2792 fout_ << " nullity = " << order.getNullity() << endl ;
2793 fout_ << "\n reduced Q-I matrix " << order.printQMatrix() << endl ;
2794 status = false ;
2795 }
2796 }
2797 catch( PolynomialRangeError & e )
2798 {
2799 fout_ << "\n\tERROR: PolynomialRangeError error [ " << e.what() << " ] " << endl ;
2800 status = false ;
2801 }
2802
2803 fout_ << "\nTEST: PolyOrder, reducible polynomial x^3 + 3 mod 5 with 2 distinct factors" ;
2804 try {
2805 Polynomial f( "x^3 + 3, 5" ) ;
2806 PolyOrder order( f ) ;
2807
2808 // Get the fully nullity count. Don't do early out in findNullity().
2809 bool multipleFactors = order.hasMultipleDistinctFactors( false ) ;
2810
2811 if (multipleFactors && order.getNullity() == 2)
2812 fout_ << ".........PASS!" ;
2813 else
2814 {
2815 fout_ << ".........FAIL!" << endl ;
2816 fout_ << " PolyOrder 2 distinct factors failed" << endl ;
2817 fout_ << " f( x ) = " << f << endl ;
2818 fout_ << " nullity = " << order.getNullity() << endl ;
2819 fout_ << " reduced Q-I matrix " << order.printQMatrix() << endl ;
2820 status = false ;
2821 }
2822 }
2823 catch( PolynomialRangeError & e )
2824 {
2825 fout_ << ".........FAIL!" << endl ;
2826 fout_ << " PolynomialRangeError [ " << e.what() << " ] " << endl ;
2827 status = false ;
2828 }
2829
2830 fout_ << "\nTEST: PolyOrder, irreducible polynomial x^4 + x^2 + 2x + 3 mod 5 (nullity = 1)" ;
2831 try
2832 {
2833 Polynomial f( "x^4 + x^2 + 2x + 3, 5" ) ;
2834 PolyOrder order( f ) ;
2835
2836 // Get the fully nullity count. Don't do early out in findNullity().
2837 bool multipleFactors = order.hasMultipleDistinctFactors( false ) ;
2838
2839 if (multipleFactors == false && order.getNullity() == 1)
2840 fout_ << ".........PASS!" ;
2841 else
2842 {
2843 fout_ << ".........FAIL!" << endl ;
2844 fout_ << " PolyOrder irreducible" << endl ;
2845 fout_ << " f( x ) = " << f << endl ;
2846 fout_ << " nullity = " << order.getNullity() << endl ;
2847 fout_ << " reduced Q-I matrix " << order.printQMatrix() << endl ;
2848 status = false ;
2849 }
2850 }
2851 catch( PolynomialRangeError & e )
2852 {
2853 fout_ << ".........FAIL!" << endl ;
2854 fout_ << " PolynomialRangeError: [ " << e.what() << " ] " << endl ;
2855 status = false ;
2856 }
2857
2858
2859 fout_ << "\nTEST: PolyOrder 1 distinct factor 4 times" ;
2860 {
2861 Polynomial f( "x^4 + 4x^3 + x^2 + 4x + 1, 5" ) ;
2862 PolyOrder order( f ) ;
2863
2864 // Get the fully nullity count. Don't do early out in findNullity().
2865 bool multipleFactors = order.hasMultipleDistinctFactors( false ) ;
2866 if (multipleFactors == false && order.getNullity() == 1)
2867 fout_ << ".........PASS!" ;
2868 else
2869 {
2870 fout_ << "\n\tERROR: PolyOrder 1 distinct factor 4 times" << endl ;
2871 fout_ << " f( x ) = " << f << endl ;
2872 fout_ << " nullity = " << order.getNullity() << endl ;
2873 fout_ << "\n reduced Q-I matrix " << order.printQMatrix() << endl ;
2874 status = false ;
2875 }
2876 }
2877
2878 fout_ << "\nTEST: PolyOrder orderM()" ;
2879 {
2880 Polynomial f( "x^4 + x^2 + 2x + 3, 5" ) ;
2881 PolyOrder order( f ) ;
2882
2883 if (order.orderM())
2884 fout_ << ".........PASS!" ;
2885 else
2886 {
2887 fout_ << "\n\tERROR: PolyOrder orderM failed." << endl ;
2888 status = false ;
2889 }
2890 }
2891
2892 fout_ << "\nTEST: PolyOrder orderR() is true" ;
2893 {
2894 Polynomial f( "x^4 + x^2 + 2x + 3, 5" ) ;
2895 PolyOrder order( f ) ;
2896
2897 ppuint a{ order.orderR() } ;
2898 if (a == 3)
2899 fout_ << ".........PASS!" ;
2900 else
2901 {
2902 fout_ << "\n\tERROR: PolyOrder orderR failed." << endl ;
2903 status = false ;
2904 }
2905 }
2906
2907 fout_ << "\nTEST: PolyOrder orderR() is false" ;
2908 {
2909 Polynomial f( "x^4 + x + 3, 5" ) ;
2910 PolyOrder order( f ) ;
2911
2912 ppuint a{ order.orderR() } ;
2913 if (a == 0)
2914 fout_ << ".........PASS!" ;
2915 else
2916 {
2917 fout_ << "\n\tERROR: PolyOrder orderR failed." << endl ;
2918 status = false ;
2919 }
2920 }
2921
2922 fout_ << "\nTEST: PolyOrder isPrimitive on non-primitive poly" ;
2923 {
2924 Polynomial f( "x^5 + x + 1, 2" ) ;
2925 PolyOrder order( f ) ;
2926
2927 bool isPrimitive = order.isPrimitive() ;
2928 if (!isPrimitive)
2929 fout_ << ".........PASS!" ;
2930 else
2931 {
2932 fout_ << "\n\tERROR: PolyOrder isPrimitive on non-primitive poly" << endl ;
2933 fout_ << " f( x ) = " << f << endl ;
2934 status = false ;
2935 }
2936 }
2937
2938 fout_ << "\nTEST: PolyOrder isPrimitive on primitive poly" ;
2939 {
2940 Polynomial f( "x^4 + x^2 + 2x + 3, 5" ) ;
2941 PolyOrder order( f ) ;
2942
2943 bool isPrimitive = order.isPrimitive() ;
2944 if (isPrimitive)
2945 fout_ << ".........PASS!" ;
2946 else
2947 {
2948 fout_ << "\n\tERROR: PolyOrder isPrimitive on primitive poly" << endl ;
2949 fout_ << " f( x ) = " << f << endl ;
2950 status = false ;
2951 }
2952 }
2953
2954 fout_ << "\nTEST: PolyOrder isPrimitive on primitive poly, part II" ;
2955 {
2956 Polynomial f0( "x^4+4, 5" ) ;
2957 PolyOrder order( f0 ) ;
2958
2959 Polynomial f( "x^4 + x^2 + 2x + 3, 5" ) ;
2960 order.resetPolynomial( f ) ;
2961
2962 bool isPrimitive = order.isPrimitive() ;
2963 if (isPrimitive)
2964 fout_ << ".........PASS!" ;
2965 else
2966 {
2967 fout_ << "\n\tERROR: PolyOrder isPrimitive on primitive poly, part II" << endl ;
2968 fout_ << " f( x ) = " << f << endl ;
2969 status = false ;
2970 }
2971 }
2972
2973 return status ;
2974}
2975
2976
2977bool UnitTest::unitTestParser()
2978{
2979 bool status = true ;
2980
2981 // Create a parser with parse tables.
2982 string s ;
2983 PolyValue v ;
2984 PolyParser< PolySymbol, PolyValue > p ;
2985
2986 fout_ << "\nTEST: Parsing command line options for test polynomial x^4 + 1, 2 with -s -t and -c options." ;
2987 {
2988 #ifdef DEBUG_PP_FORCE_UNIT_TEST_FAIL
2989 const char * argv[ 5 ] { "Primpoly", "-s", "-t", "-c", "x^3 + 1, 2" } ;
2990 const Polynomial truePoly( "x^3 + 1", 2 ) ;
2991 #else
2992 const char * argv[ 5 ] { "Primpoly", "-s", "-t", "-c", "x^4 + 1, 2" } ;
2993 const Polynomial truePoly( "x^4 + 1", 2 ) ;
2994 #endif
2995
2996 p.parseCommandLine( 5, argv ) ;
2997
2998 if (p.test_polynomial_for_primitivity_ && p.print_operation_count_ && p.slow_confirm_ &&
2999 !p.list_all_primitive_polynomials_ && !p.print_help_ &&
3000 p.test_polynomial_ == truePoly)
3001 {
3002 fout_ << ".........PASS!" ;
3003 }
3004 else
3005 {
3006 fout_ << ".........FAIL!" << endl ;
3007 fout_ << " Test polynomial = " << p.test_polynomial_ ; fout_ << " deg = " << p.test_polynomial_.deg() << endl ;
3008 fout_ << " p = " << p.p << " n = " << p.n << endl ;
3009 status = false ;
3010 }
3011 }
3012
3013 fout_ << "\nTEST: parsing constant 0" ;
3014 {
3015 s = "0" ;
3016 #ifdef DEBUG_PP_FORCE_UNIT_TEST_FAIL
3017 s = "2" ;
3018 #endif
3019 v = p.parse( s ) ;
3020 if (!(v.scalar_ == 2 && (v.f_.size()-1) == 0 && v.f_[0] == 0))
3021 {
3022 fout_ << ".........FAIL!" << endl ;
3023 fout_ << " parsing input " << s << endl << " value = " << v << endl ;
3024 status = false ;
3025 }
3026 else
3027 fout_ << ".........PASS!" ;
3028 }
3029
3030 fout_ << "\nTEST: parsing polynomial with a specified modulus: 2 x ^ 3 + 3 x + 4, 5" ;
3031 {
3032 #ifdef DEBUG_PP_FORCE_UNIT_TEST_FAIL
3033 s = "2 x ^ 3 + 3 x + 4, 7" ;
3034 #else
3035 s = "2 x ^ 3 + 3 x + 4, 5" ;
3036 #endif
3037 v = p.parse( s ) ;
3038 if (!(v.scalar_ == 5 && (v.f_.size()-1) == 3 && v.f_[0] == 4 && v.f_[1] == 3 && v.f_[2] == 0 && v.f_[3] == 2))
3039 {
3040 fout_ << ".........FAIL!" << endl ;
3041 fout_ << " parsing input " << s << endl << " value = " << v << endl ;
3042 status = false ;
3043 }
3044 else
3045 fout_ << ".........PASS!" ;
3046 }
3047
3048 fout_ << "\nTEST: parsing polynomial 2x without a modulus, which will be defaulted to p=2: 2x" ;
3049 {
3050 s = "2x" ;
3051 #ifdef DEBUG_PP_FORCE_UNIT_TEST_FAIL
3052 s = "2x,3" ;
3053 #endif
3054 v = p.parse( s ) ;
3055 if (!(v.scalar_ == 2 && (v.f_.size()-1) == 1 && v.f_[0] == 0 && v.f_[1] == 2 ))
3056 {
3057 fout_ << ".........FAIL!" << endl ;
3058 fout_ << " parsing input " << s << endl << " value = " << v << endl ;
3059 status = false ;
3060 }
3061 else
3062 fout_ << ".........PASS!" ;
3063 }
3064
3065 fout_ << "\nTEST: parsing bad syntax x 1" ;
3066 try
3067 {
3068 s = "x 1" ;
3069 #ifdef DEBUG_PP_FORCE_UNIT_TEST_FAIL
3070 s = "x+1" ;
3071 #endif
3072 v = p.parse( s ) ;
3073 if (!(v.scalar_ == 0 && (v.f_.size()-1) == 0 &&
3074 v.f_[0] == 0 && v.f_[1] == 2 ))
3075 {
3076 fout_ << ".........FAIL!" << endl ;
3077 fout_ << " Parser did not throw a parsing error " << endl ;
3078 fout_ << " while parsing input " << s << endl << " value = " << v << endl ;
3079 status = false ;
3080 }
3081 }
3082 catch( ParserError & e )
3083 {
3084 // Match only the error message.
3085 // The file name and line number where the error occurred may change with different versions of this software.
3086 string trueErrorMessage = "Expecting to see x^ or x or x ^ integer in sentence x 1" ;
3087 if (static_cast<string>(e.what()).find( trueErrorMessage ) == string::npos)
3088 {
3089 fout_ << ".........FAIL!" << endl ;
3090 fout_ << " Parser correctly threw a parse error exception while parsing " << s << endl << " value = " << v << endl ;
3091 fout_ << " but the error message was incorrect! error = |" << e.what() << "|" << endl ;
3092 status = false ;
3093 }
3094 else
3095 fout_ << ".........PASS!" ;
3096 }
3097
3098 return status ;
3099}
3100#endif // SELF_CHECK