OLD | NEW |
1 // Copyright (c) 2015, the Dart project authors. Please see the AUTHORS file | 1 // Copyright (c) 2015, the Dart project authors. Please see the AUTHORS file |
2 // for details. All rights reserved. Use of this source code is governed by a | 2 // for details. All rights reserved. Use of this source code is governed by a |
3 // BSD-style license that can be found in the LICENSE file. | 3 // BSD-style license that can be found in the LICENSE file. |
4 | 4 |
5 import "package:expect/expect.dart"; | 5 import "package:expect/expect.dart"; |
6 | 6 |
7 import "dart:math" show pow; | 7 import "dart:math" show pow; |
8 | 8 |
9 var smallNumber = 1234567890; // is 31-bit integer. | 9 var smallNumber = 1234567890; // is 31-bit integer. |
10 var mediumNumber = 1234567890123456; // is 53-bit integer | 10 var mediumNumber = 1234567890123456; // is 53-bit integer |
11 var bigNumber = 590295810358705600000; // is > 64-bit integer, exact as double. | 11 var bigNumber = 590295810358705600000; // is > 64-bit integer, exact as double. |
12 | 12 |
13 testModPow() { | 13 testModPow() { |
14 test(x, e, m, expectedResult) { | 14 test(x, e, m, expectedResult) { |
15 // Check that expected result is correct, using an unoptimized version. | 15 // Check that expected result is correct, using an unoptimized version. |
16 assert(() { | 16 assert(() { |
17 if (1 is double) return true; // Don't have bignums. | 17 if (1 is double) return true; // Don't have bignums. |
18 slowModPow(x, e, m) { | 18 slowModPow(x, e, m) { |
19 var r = 1; | 19 var r = 1; |
20 while (e > 0) { | 20 while (e > 0) { |
21 if (e.isOdd) r = (r * x) % m; | 21 if (e.isOdd) r = (r * x) % m; |
22 e >>= 1; | 22 e >>= 1; |
23 x = (x * x) % m; | 23 x = (x * x) % m; |
24 } | 24 } |
25 return r; | 25 return r; |
26 } | 26 } |
27 | |
28 return slowModPow(x, e, m) == expectedResult; | 27 return slowModPow(x, e, m) == expectedResult; |
29 }); | 28 }); |
30 var result = x.modPow(e, m); | 29 var result = x.modPow(e, m); |
31 Expect.equals(expectedResult, result, "$x.modPow($e, $m)"); | 30 Expect.equals(expectedResult, result, "$x.modPow($e, $m)"); |
32 } | 31 } |
33 | 32 |
34 test(10, 20, 1, 0); | 33 test(10, 20, 1, 0); |
35 test(1234567890, 1000000001, 19, 11); | 34 test(1234567890, 1000000001, 19, 11); |
36 test(1234567890, 19, 1000000001, 122998977); | 35 test(1234567890, 19, 1000000001, 122998977); |
37 test(19, 1234567890, 1000000001, 619059596); | 36 test(19, 1234567890, 1000000001, 619059596); |
38 test(19, 1000000001, 1234567890, 84910879); | 37 test(19, 1000000001, 1234567890, 84910879); |
39 test(1000000001, 19, 1234567890, 872984351); | 38 test(1000000001, 19, 1234567890, 872984351); |
40 test(1000000001, 1234567890, 19, 0); | 39 test(1000000001, 1234567890, 19, 0); |
41 test(12345678901234567890, 10000000000000000001, 19, 2); | 40 test(12345678901234567890, 10000000000000000001, 19, 2); |
42 test(12345678901234567890, 19, 10000000000000000001, 3239137215315834625); | 41 test(12345678901234567890, 19, 10000000000000000001, 3239137215315834625); |
43 test(19, 12345678901234567890, 10000000000000000001, 4544207837373941034); | 42 test(19, 12345678901234567890, 10000000000000000001, 4544207837373941034); |
44 test(19, 10000000000000000001, 12345678901234567890, 11135411705397624859); | 43 test(19, 10000000000000000001, 12345678901234567890, 11135411705397624859); |
45 test(10000000000000000001, 19, 12345678901234567890, 2034013733189773841); | 44 test(10000000000000000001, 19, 12345678901234567890, 2034013733189773841); |
46 test(10000000000000000001, 12345678901234567890, 19, 1); | 45 test(10000000000000000001, 12345678901234567890, 19, 1); |
47 test(12345678901234567890, 19, 10000000000000000001, 3239137215315834625); | 46 test(12345678901234567890, 19, 10000000000000000001, 3239137215315834625); |
48 test(12345678901234567890, 10000000000000000001, 19, 2); | 47 test(12345678901234567890, 10000000000000000001, 19, 2); |
49 test(123456789012345678901234567890, 123456789012345678901234567891, | 48 test(123456789012345678901234567890, |
50 123456789012345678901234567899, 116401406051033429924651549616); | 49 123456789012345678901234567891, |
51 test(123456789012345678901234567890, 123456789012345678901234567899, | 50 123456789012345678901234567899, |
52 123456789012345678901234567891, 123456789012345678901234567890); | 51 116401406051033429924651549616); |
53 test(123456789012345678901234567899, 123456789012345678901234567890, | 52 test(123456789012345678901234567890, |
54 123456789012345678901234567891, 35088523091000351053091545070); | 53 123456789012345678901234567899, |
55 test(123456789012345678901234567899, 123456789012345678901234567891, | 54 123456789012345678901234567891, |
56 123456789012345678901234567890, 18310047270234132455316941949); | 55 123456789012345678901234567890); |
57 test(123456789012345678901234567891, 123456789012345678901234567899, | 56 test(123456789012345678901234567899, |
58 123456789012345678901234567890, 1); | 57 123456789012345678901234567890, |
59 test(123456789012345678901234567891, 123456789012345678901234567890, | 58 123456789012345678901234567891, |
60 123456789012345678901234567899, 40128068573873018143207285483); | 59 35088523091000351053091545070); |
| 60 test(123456789012345678901234567899, |
| 61 123456789012345678901234567891, |
| 62 123456789012345678901234567890, |
| 63 18310047270234132455316941949); |
| 64 test(123456789012345678901234567891, |
| 65 123456789012345678901234567899, |
| 66 123456789012345678901234567890, |
| 67 1); |
| 68 test(123456789012345678901234567891, |
| 69 123456789012345678901234567890, |
| 70 123456789012345678901234567899, |
| 71 40128068573873018143207285483); |
| 72 |
61 } | 73 } |
62 | 74 |
63 testModInverse() { | 75 testModInverse() { |
64 test(x, m, expectedResult) { | 76 test(x, m, expectedResult) { |
65 //print("$x op $m == $expectedResult"); | 77 //print("$x op $m == $expectedResult"); |
66 // Check that expectedResult is an inverse. | 78 // Check that expectedResult is an inverse. |
67 assert(expectedResult < m); | 79 assert(expectedResult < m); |
68 // The 1 % m handles the m = 1 special case. | 80 // The 1 % m handles the m = 1 special case. |
69 // This test may overflow if we don't have bignums, so only run on VM. | 81 // This test may overflow if we don't have bignums, so only run on VM. |
70 assert(1 is double || (((x % m) * expectedResult) - 1) % m == 0); | 82 assert(1 is double || (((x % m) * expectedResult) - 1) % m == 0); |
(...skipping 57 matching lines...) Expand 10 before | Expand all | Expand 10 after Loading... |
128 | 140 |
129 // Test that gcd of value and other (non-negative) is expectedResult. | 141 // Test that gcd of value and other (non-negative) is expectedResult. |
130 // Tests all combinations of positive and negative values and order of | 142 // Tests all combinations of positive and negative values and order of |
131 // operands, so use positive values and order is not important. | 143 // operands, so use positive values and order is not important. |
132 test(value, other, expectedResult) { | 144 test(value, other, expectedResult) { |
133 // Check for bug in test. | 145 // Check for bug in test. |
134 assert(expectedResult == 0 || value % expectedResult == 0); | 146 assert(expectedResult == 0 || value % expectedResult == 0); |
135 assert(expectedResult == 0 || other % expectedResult == 0); | 147 assert(expectedResult == 0 || other % expectedResult == 0); |
136 callCombos(value, other, (a, b) { | 148 callCombos(value, other, (a, b) { |
137 var result = a.gcd(b); | 149 var result = a.gcd(b); |
138 | |
139 /// Check that the result is a divisor. | 150 /// Check that the result is a divisor. |
140 Expect.equals(0, result == 0 ? a : a % result, "$result | $a"); | 151 Expect.equals(0, result == 0 ? a : a % result, "$result | $a"); |
141 Expect.equals(0, result == 0 ? b : b % result, "$result | $b"); | 152 Expect.equals(0, result == 0 ? b : b % result, "$result | $b"); |
142 // Check for bug in test. If assert fails, the expected value is too low, | 153 // Check for bug in test. If assert fails, the expected value is too low, |
143 // and the gcd call has found a greater common divisor. | 154 // and the gcd call has found a greater common divisor. |
144 assert(result >= expectedResult); | 155 assert(result >= expectedResult); |
145 Expect.equals(expectedResult, result, "$a.gcd($b)"); | 156 Expect.equals(expectedResult, result, "$a.gcd($b)"); |
146 }); | 157 }); |
147 } | 158 } |
148 | 159 |
149 // Test that gcd of value and other (non-negative) throws. | 160 // Test that gcd of value and other (non-negative) throws. |
150 testThrows(value, other) { | 161 testThrows(value, other) { |
151 callCombos(value, other, (a, b) { | 162 callCombos(value, other, (a, b) { |
152 Expect.throws(() => a.gcd(b), null, "$a.gcd($b)"); | 163 Expect.throws(() => a.gcd(b), null, "$a.gcd($b)"); |
153 }); | 164 }); |
154 } | 165 } |
155 | 166 |
156 testThrows(2.5, 5); // Not a method on double. | 167 testThrows(2.5, 5); // Not a method on double. |
157 testThrows(5, 2.5); // Not accepting non-int arguments. | 168 testThrows(5, 2.5); // Not accepting non-int arguments. |
158 | 169 |
159 // Format: | 170 // Format: |
160 // test(value1, value2, expectedResult); | 171 // test(value1, value2, expectedResult); |
161 test(1, 1, 1); // both are 1 | 172 test(1, 1, 1); // both are 1 |
162 test(1, 2, 1); // one is 1 | 173 test(1, 2, 1); // one is 1 |
163 test(3, 5, 1); // coprime. | 174 test(3, 5, 1); // coprime. |
164 test(37, 37, 37); // Same larger prime. | 175 test(37, 37, 37); // Same larger prime. |
165 | 176 |
166 test(9999, 7272, 909); // Larger numbers | 177 test(9999, 7272, 909); // Larger numbers |
167 | 178 |
168 test(0, 1000, 1000); // One operand is zero. | 179 test(0, 1000, 1000); // One operand is zero. |
169 test(0, 0, 0); // Both operands are zero. | 180 test(0, 0, 0); // Both operands are zero. |
170 | 181 |
171 // Multiplying both operands by a number multiplies result by same number. | 182 // Multiplying both operands by a number multiplies result by same number. |
172 test(693, 609, 21); | 183 test(693, 609, 21); |
173 test(693 << 5, 609 << 5, 21 << 5); | 184 test(693 << 5, 609 << 5, 21 << 5); |
174 test(693 * 937, 609 * 937, 21 * 937); | 185 test(693 * 937, 609 * 937, 21 * 937); |
175 test(693 * pow(2, 32), 609 * pow(2, 32), 21 * pow(2, 32)); | 186 test(693 * pow(2, 32), 609 * pow(2, 32), 21 * pow(2, 32)); |
176 test(693 * pow(2, 52), 609 * pow(2, 52), 21 * pow(2, 52)); | 187 test(693 * pow(2, 52), 609 * pow(2, 52), 21 * pow(2, 52)); |
177 test(693 * pow(2, 53), 609 * pow(2, 53), 21 * pow(2, 53)); // Regression. | 188 test(693 * pow(2, 53), 609 * pow(2, 53), 21 * pow(2, 53)); // Regression. |
178 test(693 * pow(2, 99), 609 * pow(2, 99), 21 * pow(2, 99)); | 189 test(693 * pow(2, 99), 609 * pow(2, 99), 21 * pow(2, 99)); |
179 | 190 |
180 test(1234567890, 19, 1); | 191 test(1234567890, 19, 1); |
181 test(1234567890, 1000000001, 1); | 192 test(1234567890, 1000000001, 1); |
182 test(19, 1000000001, 19); | 193 test(19, 1000000001, 19); |
183 | 194 |
184 test(0x3FFFFFFF, 0x3FFFFFFF, 0x3FFFFFFF); | 195 test(0x3FFFFFFF, 0x3FFFFFFF, 0x3FFFFFFF); |
185 test(0x3FFFFFFF, 0x40000000, 1); | 196 test(0x3FFFFFFF, 0x40000000, 1); |
186 | 197 |
187 test(pow(2, 54), pow(2, 53), pow(2, 53)); | 198 test(pow(2, 54), pow(2, 53), pow(2, 53)); |
188 | 199 |
189 test((pow(2, 52) - 1) * pow(2, 14), (pow(2, 26) - 1) * pow(2, 22), | 200 test((pow(2, 52) - 1) * pow(2, 14), |
190 (pow(2, 26) - 1) * pow(2, 14)); | 201 (pow(2, 26) - 1) * pow(2, 22), |
| 202 (pow(2, 26) - 1) * pow(2, 14)); |
191 } | 203 } |
192 | 204 |
193 main() { | 205 main() { |
194 testModPow(); // //# modPow: ok | 206 testModPow(); // //# modPow: ok |
195 testModInverse(); | 207 testModInverse(); |
196 testGcd(); | 208 testGcd(); |
197 } | 209 } |
| 210 |
OLD | NEW |