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