OLD | NEW |
| (Empty) |
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 | |
3 // BSD-style license that can be found in the LICENSE file. | |
4 | |
5 import "package:expect/expect.dart"; | |
6 | |
7 import "dart:math" show pow; | |
8 | |
9 var smallNumber = 1234567890; // is 31-bit integer. | |
10 var mediumNumber = 1234567890123456; // is 53-bit integer | |
11 var bigNumber = 590295810358705600000; // is > 64-bit integer, exact as double. | |
12 | |
13 testModPow() { | |
14 test(x, e, m, expectedResult) { | |
15 // Check that expected result is correct, using an unoptimized version. | |
16 assert(() { | |
17 if (1 is double) return true; // Don't have bignums. | |
18 slowModPow(x, e, m) { | |
19 var r = 1; | |
20 while (e > 0) { | |
21 if (e.isOdd) r = (r * x) % m; | |
22 e >>= 1; | |
23 x = (x * x) % m; | |
24 } | |
25 return r; | |
26 } | |
27 | |
28 return slowModPow(x, e, m) == expectedResult; | |
29 }); | |
30 var result = x.modPow(e, m); | |
31 Expect.equals(expectedResult, result, "$x.modPow($e, $m)"); | |
32 } | |
33 | |
34 test(10, 20, 1, 0); | |
35 test(1234567890, 1000000001, 19, 11); | |
36 test(1234567890, 19, 1000000001, 122998977); | |
37 test(19, 1234567890, 1000000001, 619059596); | |
38 test(19, 1000000001, 1234567890, 84910879); | |
39 test(1000000001, 19, 1234567890, 872984351); | |
40 test(1000000001, 1234567890, 19, 0); | |
41 test(12345678901234567890, 10000000000000000001, 19, 2); | |
42 test(12345678901234567890, 19, 10000000000000000001, 3239137215315834625); | |
43 test(19, 12345678901234567890, 10000000000000000001, 4544207837373941034); | |
44 test(19, 10000000000000000001, 12345678901234567890, 11135411705397624859); | |
45 test(10000000000000000001, 19, 12345678901234567890, 2034013733189773841); | |
46 test(10000000000000000001, 12345678901234567890, 19, 1); | |
47 test(12345678901234567890, 19, 10000000000000000001, 3239137215315834625); | |
48 test(12345678901234567890, 10000000000000000001, 19, 2); | |
49 test(123456789012345678901234567890, 123456789012345678901234567891, | |
50 123456789012345678901234567899, 116401406051033429924651549616); | |
51 test(123456789012345678901234567890, 123456789012345678901234567899, | |
52 123456789012345678901234567891, 123456789012345678901234567890); | |
53 test(123456789012345678901234567899, 123456789012345678901234567890, | |
54 123456789012345678901234567891, 35088523091000351053091545070); | |
55 test(123456789012345678901234567899, 123456789012345678901234567891, | |
56 123456789012345678901234567890, 18310047270234132455316941949); | |
57 test(123456789012345678901234567891, 123456789012345678901234567899, | |
58 123456789012345678901234567890, 1); | |
59 test(123456789012345678901234567891, 123456789012345678901234567890, | |
60 123456789012345678901234567899, 40128068573873018143207285483); | |
61 } | |
62 | |
63 testModInverse() { | |
64 test(x, m, expectedResult) { | |
65 //print("$x op $m == $expectedResult"); | |
66 // Check that expectedResult is an inverse. | |
67 assert(expectedResult < m); | |
68 // 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. | |
70 assert(1 is double || (((x % m) * expectedResult) - 1) % m == 0); | |
71 | |
72 var result = x.modInverse(m); | |
73 Expect.equals(expectedResult, result, "$x modinv $m"); | |
74 | |
75 if (x > m) { | |
76 x = x % m; | |
77 var result = x.modInverse(m); | |
78 Expect.equals(expectedResult, result, "$x modinv $m"); | |
79 } | |
80 } | |
81 | |
82 testThrows(x, m) { | |
83 // Throws if not co-prime, which is a symmetric property. | |
84 Expect.throws(() => x.modInverse(m), null, "$x modinv $m"); | |
85 Expect.throws(() => m.modInverse(x), null, "$m modinv $x"); | |
86 } | |
87 | |
88 test(1, 1, 0); | |
89 | |
90 testThrows(0, 1000000001); | |
91 testThrows(2, 4); | |
92 testThrows(99, 9); | |
93 testThrows(19, 1000000001); | |
94 testThrows(123456789012345678901234567890, 123456789012345678901234567899); | |
95 | |
96 // Co-prime numbers | |
97 test(1234567890, 19, 11); | |
98 test(1234567890, 1000000001, 189108911); | |
99 test(19, 1234567890, 519818059); | |
100 test(1000000001, 1234567890, 1001100101); | |
101 | |
102 test(12345, 12346, 12345); | |
103 test(12345, 12346, 12345); | |
104 | |
105 test(smallNumber, 137, 42); | |
106 test(137, smallNumber, 856087223); | |
107 test(mediumNumber, 137, 77); | |
108 test(137, mediumNumber, 540686667207353); | |
109 test(bigNumber, 137, 128); // //# bignum: ok | |
110 // Bigger numbers as modulo is tested in big_integer_arith_vm_test.dart. | |
111 // Big doubles are not co-prime, so there is nothing to test for dart2js. | |
112 } | |
113 | |
114 testGcd() { | |
115 // Call testFunc with all combinations and orders of plus/minus | |
116 // value and other. | |
117 callCombos(value, other, testFunc) { | |
118 testFunc(value, other); | |
119 testFunc(value, -other); | |
120 testFunc(-value, other); | |
121 testFunc(-value, -other); | |
122 if (value == other) return; | |
123 testFunc(other, value); | |
124 testFunc(other, -value); | |
125 testFunc(-other, value); | |
126 testFunc(-other, -value); | |
127 } | |
128 | |
129 // Test that gcd of value and other (non-negative) is expectedResult. | |
130 // Tests all combinations of positive and negative values and order of | |
131 // operands, so use positive values and order is not important. | |
132 test(value, other, expectedResult) { | |
133 // Check for bug in test. | |
134 assert(expectedResult == 0 || value % expectedResult == 0); | |
135 assert(expectedResult == 0 || other % expectedResult == 0); | |
136 callCombos(value, other, (a, b) { | |
137 var result = a.gcd(b); | |
138 | |
139 /// Check that the result is a divisor. | |
140 Expect.equals(0, result == 0 ? a : a % result, "$result | $a"); | |
141 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, | |
143 // and the gcd call has found a greater common divisor. | |
144 assert(result >= expectedResult); | |
145 Expect.equals(expectedResult, result, "$a.gcd($b)"); | |
146 }); | |
147 } | |
148 | |
149 // Test that gcd of value and other (non-negative) throws. | |
150 testThrows(value, other) { | |
151 callCombos(value, other, (a, b) { | |
152 Expect.throws(() => a.gcd(b), null, "$a.gcd($b)"); | |
153 }); | |
154 } | |
155 | |
156 testThrows(2.5, 5); // Not a method on double. | |
157 testThrows(5, 2.5); // Not accepting non-int arguments. | |
158 | |
159 // Format: | |
160 // test(value1, value2, expectedResult); | |
161 test(1, 1, 1); // both are 1 | |
162 test(1, 2, 1); // one is 1 | |
163 test(3, 5, 1); // coprime. | |
164 test(37, 37, 37); // Same larger prime. | |
165 | |
166 test(9999, 7272, 909); // Larger numbers | |
167 | |
168 test(0, 1000, 1000); // One operand is zero. | |
169 test(0, 0, 0); // Both operands are zero. | |
170 | |
171 // Multiplying both operands by a number multiplies result by same number. | |
172 test(693, 609, 21); | |
173 test(693 << 5, 609 << 5, 21 << 5); | |
174 test(693 * 937, 609 * 937, 21 * 937); | |
175 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)); | |
177 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)); | |
179 | |
180 test(1234567890, 19, 1); | |
181 test(1234567890, 1000000001, 1); | |
182 test(19, 1000000001, 19); | |
183 | |
184 test(0x3FFFFFFF, 0x3FFFFFFF, 0x3FFFFFFF); | |
185 test(0x3FFFFFFF, 0x40000000, 1); | |
186 | |
187 test(pow(2, 54), pow(2, 53), pow(2, 53)); | |
188 | |
189 test((pow(2, 52) - 1) * pow(2, 14), (pow(2, 26) - 1) * pow(2, 22), | |
190 (pow(2, 26) - 1) * pow(2, 14)); | |
191 } | |
192 | |
193 main() { | |
194 testModPow(); // //# modPow: ok | |
195 testModInverse(); | |
196 testGcd(); | |
197 } | |
OLD | NEW |