| 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 |