tests/exam_I_gcd.cc

   1 #include <cln/integer.h>
   2 #include <cln/integer_io.h>
   3 #include <cln/io.h>
   4
   5 using namespace std;
   6 using namespace cln;
   7
   8 #define ASSERT(expr)  \
   9   if (!(expr)) {                                        \
  10         std::cerr << "Assertion failed! File " << __FILE__ << ", line " << __LINE__ << endl;    \
  11         error = 1;                                      \
  12   }
  13
  14 struct gcd_test {
  15         const char * arg1;
  16         const char * arg2;
  17         const char * result;
  18 };
  19
  20 #define num_elements(array)  (sizeof(array)/sizeof(array[0]))
  21
  22 // Note: This macro differs slightly from the one in "exam.h".
  23 #define DO_BINOP_TEST(typename,type,rtype,opname)  \
  24 static int test_##typename##_##opname (void)                            \
  25 {                                                                       \
  26         int error = 0;                                                  \
  27         for (unsigned int i = 0; i < num_elements(typename##_##opname##_tests); i++) { \
  28                 opname##_test& test = typename##_##opname##_tests[i];   \
  29                 type arg1 = type(test.arg1);                            \
  30                 type arg2 = type(test.arg2);                            \
  31                 rtype computed_result = opname(arg1,arg2);              \
  32                 rtype result = rtype(test.result);                      \
  33                 if (computed_result != result) {                        \
  34                         std::cerr << "Error in " #typename "_" #opname "_tests[" << i << "] !" << endl; \
  35                         std::cerr << "Result should be: " << result << endl;    \
  36                         std::cerr << "Result computed : " << computed_result << endl << endl;   \
  37                         error = 1;                                      \
  38                 }                                                       \
  39         }                                                               \
  40         return error;                                                   \
  41 }
  42
  43 static gcd_test integer_gcd_tests[] = {
  44         { "123456789", "345", "3" },
  45         { "345", "123456789", "3" },
  46         { "10", "0", "10" },
  47         { "0", "10", "10" },
  48         { "2523533737", "855322739", "1" },
  49         { "855322739", "2523533737", "1" },
  50         { "101611479673163974026724715741235467160607959655653420075620", "533177863832047932237026621580126811198495699416238676294977", "1" },
  51         { "30729415811", "323233683197", "31071199" },
  52         { "77874422", "32223899", "1" },
  53         { "974507656412513757857315037382926980395082974811562770185617915360", "-1539496810360685510909469177732386446833404488164283", "1" },
  54         { "2823618260546496405819033080103700734250203999069672146446", "18374686479688400895", "1" }
  55 };
  56
  57 DO_BINOP_TEST(integer,cl_I,cl_I,gcd)
  58
  59 int test_gcd (void)
  60 {
  61         int error = 0;
  62         error |= test_integer_gcd();
  63         return error;
  64 }
  65
  66 int test_xgcd (void)
  67 {
  68         int error = 0;
  69         {
  70                 cl_I a = 77874422;
  71                 cl_I b = 32223899;
  72                 cl_I u;
  73                 cl_I v;
  74                 cl_I g = xgcd(a,b, &u,&v);
  75                 ASSERT(g == 1);
  76                 ASSERT(g == a*u+b*v);
  77                 ASSERT(u == -9206830);
  78                 ASSERT(v == 22249839);
  79         }
  80         {
  81                 cl_I a = "560014183";
  82                 cl_I b = 312839871;
  83                 cl_I u;
  84                 cl_I v;
  85                 cl_I g = xgcd(a,b, &u,&v);
  86                 ASSERT(g == 1);
  87                 ASSERT(g == a*u+b*v);
  88                 ASSERT(u == 77165803);
  89                 ASSERT(v == -138134388);
  90         }
  91         {
  92                 cl_I a = "#x80000000";
  93                 cl_I b = "#x-C0000000";
  94                 cl_I u;
  95                 cl_I v;
  96                 cl_I g = xgcd(a,b, &u,&v);
  97                 ASSERT(g == (cl_I)"#x40000000");
  98                 ASSERT(g == a*u+b*v);
  99                 ASSERT(u == -1);
 100                 ASSERT(v == -1);
 101         }
 102         {
 103                 cl_I a = "974507656412513757857315037382926980395082974811562770185617915360";
 104                 cl_I b = "-1539496810360685510909469177732386446833404488164283";
 105                 cl_I u;
 106                 cl_I v;
 107                 cl_I g = xgcd(a,b, &u,&v);
 108                 ASSERT(g == 1);
 109                 ASSERT(g == a*u+b*v);
 110         }
 111         return error;
 112 }