chiark - git - mdw - catacomb-perl/blob - t/mp.t

   1 # -*-mode: perl; comment-column: 68-*-
   2 use Test;
   3 BEGIN { plan tests => 121; }
   4 use Catacomb qw(:const mp);
   5
   6 # Addition
   7 ok mp("5") + mp("4") == mp("9");                                    #t    1
   8 ok mp("5") + mp("-4") == mp("1");                                   #t    2
   9 ok mp("-5") + mp("4") == mp("-1");                                  #t    3
  10 ok mp("-5") + mp("-4") == mp("-9");                                 #t    4
  11 ok mp("0xffffffff") + mp("1") == mp("0x100000000");                 #t    5
  12
  13 # Subtraction
  14 ok mp("5") - mp("4") == mp("1");                                    #t    6
  15 ok mp("5") - mp("-4") == mp("9");                                   #t    7
  16 ok mp("-5") - mp("4") == mp("-9");                                  #t    8
  17 ok mp("-5") - mp("-4") == mp("-1");                                 #t    9
  18 ok mp("4") - mp("5") == mp("-1");                                   #t   10
  19 ok mp("4") - mp("-5") == mp("9");                                   #t   11
  20 ok mp("-4") - mp("5") == mp("-9");                                  #t   12
  21 ok mp("-4") - mp("-5") == mp("1");                                  #t   13
  22
  23 # Squaring
  24 ok mp("5")->sqr() == mp("25");                                      #t   14
  25 ok mp("-5")->sqr() == mp("25");                                     #t   15
  26 ok mp("56309812098453")->sqr()==mp("3170794938563083851364993209"); #t   16
  27
  28 # Multiplication
  29 ok mp("5") * mp("4") == mp("20");                                   #t   17
  30 ok mp("5") * mp("-4") == mp("-20");                                 #t   18
  31 ok mp("-5") * mp("4") == mp("-20");                                 #t   19
  32 ok mp("-5") * mp("-4") == mp("20");                                 #t   20
  33 ok mp("0x10000") * mp("0x10000") == mp("0x100000000");              #t   21
  34
  35 # Division
  36 sub divtest {
  37   my ($x, $y, $q, $r) = @_;
  38   my ($qq, $rr) = Catacomb::MP::div($x, $y);
  39   ok $qq == $q && $rr == $r;
  40 }
  41 divtest "9", "4", "2", "1";                                         #t   22
  42 divtest "-9", "4", "-3", "3";                                       #t   23
  43 divtest "9", "-4", "-3", "-3";                                      #t   24
  44 divtest "-9", "-4", "2", "-1";                                      #t   25
  45 divtest                                                             #t   26
  46   "-3", "6277101735386680763835789423207666416083908700390324961279",
  47   "-1", "6277101735386680763835789423207666416083908700390324961276";
  48 divtest                                                             #t   27
  49   "3131675836296406071791252329528905062261497366991742517193",
  50   "1110875761630725856340142297645383444629395595869672555585",
  51   "2", "909924313034954359110967734238138173002706175252397406023";
  52 divtest                                                             #t   28
  53   "3131675836296406071791252329528905062261497366991742517193", "53",
  54   "59088223326347284373419855274130284193613157867768726739", "26";
  55 ok mp("-9") / mp("-4") == mp("2");                                  #t   29
  56 ok mp("-9") % mp("-4") == mp("-1");                                 #t   30
  57
  58 # Exponentiation
  59 ok mp("4") ** mp("0") == mp("1");                                   #t   31
  60 ok mp("4") ** mp("1") == mp("4");                                   #t   32
  61 ok mp("7") ** mp("2") == mp("49");                                  #t   33
  62 ok mp("3") ** mp("64") == mp("3433683820292512484657849089281");    #t   34
  63
  64 # Bit ops tests
  65 ok ~mp("6") == mp("-7");                                            #t   35
  66 ok ~mp("-7") == mp("6");                                            #t   36
  67
  68 ok +(mp("5") & mp("3")) == mp("1");                                 #t   37
  69 ok +(mp("5") | mp("3")) == mp("7");                                 #t   38
  70 ok +(mp("5") ^ mp("3")) == mp("6");                                 #t   39
  71 ok +(mp("45") | mp("-7")) == mp("-3");                              #t   40
  72 ok +(mp("0x343cd5") ^ mp("-0x6a49c")) == mp("-0x32984f");           #t   41
  73
  74 ok +(mp("-1") >> 5) == mp("-1");                                    #t   42
  75 ok +(mp("1") >> 5) == mp("0");                                      #t   43
  76 ok +(mp("-6") >> 2) == mp("-2");                                    #t   44
  77 ok +(mp("5") >> 0) == mp("5");                                      #t   45
  78 ok +(mp("-4") >> 0) == mp("-4");                                    #t   46
  79 ok +(mp("7") >> 2) == mp("1");                                      #t   47
  80 ok +(mp("-7") >> 2) == mp("-2");                                    #t   48
  81 ok +(mp("-7") >> 20) == mp("-1");                                   #t   49
  82
  83 ok +(mp("-1") << 5) == mp("-32");                                   #t   50
  84 ok +(mp("5") << 0) == mp("5");                                      #t   51
  85 ok +(mp("-4") << 0) == mp("-4");                                    #t   52
  86 ok +(mp("7") << 2) == mp("28");                                     #t   53
  87 ok +(mp("-7") << 2) == mp("-28");                                   #t   54
  88 ok +(mp("0xc0000000") << 1) == mp("0x180000000");                   #t   55
  89 ok +(mp("-0xc0000000") << 1) == mp("-0x180000000");                 #t   56
  90 ok +(mp("-1") << 32) == mp("-0x100000000");                         #t   57
  91
  92 ok mp("0")->setbit2c(40) == mp("0x10000000000");                    #t   58
  93 ok mp("0x87348")->setbit2c(40) == mp("0x10000087348");              #t   59
  94 ok mp("5")->setbit2c(1) == mp("7");                                 #t   60
  95 ok mp("7")->setbit2c(1) == mp("7");                                 #t   61
  96 ok mp("-3")->setbit2c(1) == mp("-1");                               #t   62
  97
  98 ok mp("0x10000000000")->clearbit2c(40) == mp("0");                  #t   63
  99 ok mp("0x87348")->clearbit2c(40) == mp("0x87348");                  #t   64
 100 ok mp("5")->clearbit2c(1) == mp("5");                               #t   65
 101 ok mp("7")->clearbit2c(1) == mp("5");                               #t   66
 102 ok mp("-1")->clearbit2c(1) == mp("-3");                             #t   67
 103
 104 # Negation
 105 ok -mp("0") == mp("0");                                             #t   68
 106 ok -mp("15") == mp("-15");                                          #t   69
 107 ok -mp("-15") == mp("15");                                          #t   70
 108
 109 # Extraction of even powers
 110 sub oddtest {
 111   my ($x, $s, $t) = @_;
 112   my ($ss, $tt) = mp($x)->odd();
 113   ok $ss == $s && $tt == $t;
 114 }
 115 oddtest "1", 0, "1";                                                #t   71
 116 oddtest "2", 1, "1";                                                #t   72
 117 oddtest "4", 2, "1";                                                #t   73
 118 oddtest "12", 2, "3";                                               #t   74
 119 oddtest "0x10000000000000", 52, "1";                                #t   75
 120 oddtest "0x10000000400000", 22, "0x40000001";                       #t   76
 121
 122 # Integer square root
 123 ok mp("0")->sqrt() == mp("0");                                      #t   77
 124 ok mp("1")->sqrt() == mp("1");                                      #t   78
 125 ok mp("4")->sqrt() == mp("2");                                      #t   79
 126 ok mp("9")->sqrt() == mp("3");                                      #t   80
 127 ok mp("16")->sqrt() == mp("4");                                     #t   81
 128 ok mp("99")->sqrt() == mp("9");                                     #t   82
 129 ok mp("100")->sqrt() == mp("10");                                   #t   83
 130 ok mp("101")->sqrt() == mp("10");                                   #t   84
 131 ok mp("120")->sqrt() == mp("10");                                   #t   85
 132 ok mp("121")->sqrt() == mp("11");                                   #t   86
 133 ok mp("10106623487257186586")->sqrt() == mp("3179091613");          #t   87
 134 ok mp("14565040310136678240")->sqrt() == mp("3816417208");          #t   88
 135
 136 # Greatest common divisor
 137
 138 ok Catacomb::MP::gcd("16", "12") == mp("4");                        #t   89
 139 ok mp("90980984098081324")->modinv("4398082908043") ==              #t   90
 140   mp("58497120524729235");
 141
 142 sub gcdtest {
 143   my ($u, $v, $g, $x, $y) = @_;
 144   my ($gg, $xx, $yy) = Catacomb::MP::gcd($u, $v);
 145   ok $g == $gg && $x == $xx && $y == $yy;
 146 }
 147 gcdtest "16", "12", "4", "-11", "15";                               #t   91
 148 gcdtest "12", "16", "4", "-1", "1";                                 #t   92
 149 gcdtest "693", "609", "21", "-7", "8";                              #t   93
 150 gcdtest                                                             #t   94
 151   "4398082908043", "90980984098081324",
 152   "1", "-32483863573352089", "1570292150447";
 153
 154 gcdtest "16", "-12", "4", "-11", "-15";                             #t   95
 155 gcdtest "-16", "12", "4", "11", "15";                               #t   96
 156 gcdtest "-12", "-16", "4", "1", "-1";                               #t   97
 157 gcdtest "-12", "16", "4", "1", "1";                                 #t   98
 158 gcdtest "-693", "609", "21", "7", "8";                              #t   99
 159 gcdtest "693", "-609", "21", "-7", "-8";                            #t  100
 160
 161 gcdtest "15", "0", "15", "1", "0";                                  #t  101
 162 gcdtest "0", "15", "15", "0", "1";                                  #t  102
 163 gcdtest "-5", "0", "5", "-1", "0";                                  #t  103
 164 gcdtest "0", "-5", "5", "0", "-1";                                  #t  104
 165 gcdtest "0", "0", "0", "0", "0";                                    #t  105
 166
 167 gcdtest                                                             #t  106
 168   "829561629303257626084392170900075",
 169   "32498098450983560651904114638965",
 170   "5",
 171   "-29340810037249902802634060204608",
 172   "748967211613630574419802053172497";
 173
 174 # Jacobi symbol
 175 ok mp("5")->jac("4") == 1;                                          #t  107
 176 ok mp("7")->jac("6") == -1;                                         #t  108
 177 ok mp("27")->jac("15") == 0;                                        #t  109
 178 ok mp("98729378979237498798347932749951")                           #t  110
 179   ->jac("2132498039840981") == 1;
 180
 181 # Modular square-root
 182 sub modsqrttest {
 183   my ($p, $x, $r) = @_;
 184   my $rr = mp($p)->modsqrt($x);
 185   ok $rr == $r || $rr == mp($p) - $r;
 186 }
 187 modsqrttest "3", "1", "1";                                          #t  111
 188 modsqrttest "5", "4", "3";                                          #t  112
 189 modsqrttest                                                         #t  113
 190  "13391974640168007623", "9775592058107450692", "3264570455655810730";
 191
 192 # Factorial
 193 ok +Catacomb::MP->factorial(0) == mp("1");                          #t  114
 194 ok +Catacomb::MP->factorial(5) == mp("120");                        #t  115
 195 ok +Catacomb::MP->factorial(30) ==                                  #t  116
 196   mp("265252859812191058636308480000000");
 197
 198 # Parsing
 199 sub parsetest {
 200   my ($str, $rx, $x, $r) = @_;
 201   my ($xx, $rr) = Catacomb::MP->fromstring($str, $rx);
 202   ok defined($x) ? ($xx == $x && $rr eq $r) : !defined($xx);
 203 }
 204 parsetest "0", 10, mp("0"), "";                                     #t  117
 205 parsetest "0z", 10, mp("0"), "z";                                   #t  118
 206 parsetest "z", 10, undef, "";                                       #t  119
 207 parsetest "8_27785", 0, mp("191"), "85";                            #t  120
 208 parsetest "8_27785", 10, mp("8"), "_27785";                         #t  121