OLD | NEW |
| (Empty) |
1 // Copyright (c) 2014, 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 library math_test; | |
6 import "package:expect/expect.dart"; | |
7 import 'dart:math'; | |
8 import 'package:math/math.dart'; | |
9 | |
10 // See gcd_test.dart first. This file contains only the tests that need Bigint | |
11 // or would fail in dart2js compatibility mode. | |
12 | |
13 class BigintTest { | |
14 // 8 random primes less within [2^60, 2^64] | |
15 final int p1 = 6714601027348841563; | |
16 final int p2 = 13464639003769154407; | |
17 final int p3 = 9519493673324441563; | |
18 final int p4 = 7064784879742017229; | |
19 final int p5 = 18364232533526122157; | |
20 final int p6 = 2099437422495963203; | |
21 final int p7 = 10166792634765954647; | |
22 final int p8 = 2745073355742392083; | |
23 | |
24 void testGcdWithBigints() { | |
25 Expect.equals(pow(2, 63)*3, gcd(pow(2, 64)*3*5, pow(2, 63)*3*7)); | |
26 // 595056260442243647 is the first prime after 2**64 / 31. | |
27 Expect.equals(595056260442243647, | |
28 gcd(31*595056260442243647, 37*595056260442243647)); | |
29 Expect.equals(p2, gcd(p1*p2, p2*p3)); | |
30 Expect.equals(1, gcd(p1*p2, p3*p4)); | |
31 | |
32 // Negatives | |
33 Expect.equals(pow(2, 63)*3, gcd(-pow(2, 64)*3*5, pow(2, 63)*3*7)); | |
34 Expect.equals(pow(2, 63)*3, gcd(pow(2, 64)*3*5, -pow(2, 63)*3*7)); | |
35 Expect.equals(pow(2, 63)*3, gcd(-pow(2, 64)*3*5, -pow(2, 63)*3*7)); | |
36 Expect.equals(1, gcd(-p1, p2)); | |
37 Expect.equals(1, gcd(p1, -p2)); | |
38 Expect.equals(1, gcd(-p1, -p2)); | |
39 } | |
40 | |
41 void testGcdextWithBigints() { | |
42 Expect.listEquals([pow(2, 63)*3, -2, 3], | |
43 gcdext(pow(2, 64)*3*5, pow(2, 63)*3*7)); | |
44 // 595056260442243647 is the first prime after 2**64 / 31. | |
45 Expect.listEquals([595056260442243647, 6, -5], | |
46 gcdext(31*595056260442243647, 37*595056260442243647)); | |
47 Expect.listEquals([1, 970881267037344823, -970881267037344822], | |
48 gcdext(73786976294838206473, 73786976294838206549)); | |
49 Expect.listEquals([1, 796993873408264695, -397448151389712212], | |
50 gcdext(p1, p2)); | |
51 Expect.listEquals([1, -397448151389712212, 796993873408264695], | |
52 gcdext(p2, p1)); | |
53 | |
54 // Negatives | |
55 Expect.listEquals([1, -796993873408264695, -397448151389712212], | |
56 gcdext(-p1, p2)); | |
57 Expect.listEquals([1, 796993873408264695, 397448151389712212], | |
58 gcdext(p1, -p2)); | |
59 Expect.listEquals([1, -796993873408264695, 397448151389712212], | |
60 gcdext(-p1, -p2)); | |
61 } | |
62 | |
63 void testInvertWithBigints() { | |
64 // 9223372036854775837 is the first prime after 2^63. | |
65 Expect.equals(2093705452366034115, invert(1000, 9223372036854775837)); | |
66 Expect.equals(970547769322117497, invert(1000000, 9223372036854775837)); | |
67 | |
68 Expect.equals(796993873408264695, invert(p1, p2)); | |
69 Expect.equals(2302612976619580647501352961102487476, invert(p3*p4, p5*p6)); | |
70 | |
71 Expect.throws(() => invert(p1 * p2, p2 * p3), | |
72 (e) => e is IntegerDivisionByZeroException); | |
73 | |
74 // Negatives | |
75 Expect.equals(12667645130360889712, invert(-p1, p2)); | |
76 Expect.equals(796993873408264695, invert(p1, -p2)); | |
77 Expect.equals(12667645130360889712, invert(-p1, -p2)); | |
78 } | |
79 | |
80 void testLcmWithBigints() { | |
81 Expect.equals(pow(2, 64)*3*5*7, lcm(pow(2, 64)*3*5, pow(2,63)*3*7)); | |
82 // 595056260442243647 is the first prime after 2**64 / 31. | |
83 Expect.equals(31*37*595056260442243647, | |
84 lcm(31*595056260442243647, 37*595056260442243647)); | |
85 | |
86 Expect.equals(p1 * p2, lcm(p1, p2)); | |
87 Expect.equals(p1 * p2 * p3, lcm(p1 * p2, p2 * p3)); | |
88 Expect.equals(p4 * p5, lcm(p4 * p5, p4)); | |
89 | |
90 // Negative | |
91 Expect.equals(p1 * p2, lcm(-p1, p2)); | |
92 Expect.equals(p1 * p2, lcm(p1, -p2)); | |
93 Expect.equals(p1 * p2, lcm(-p1, -p2)); | |
94 } | |
95 | |
96 void testPowmodWithBigints() { | |
97 // A modulus value greater than 94906265 can result in an intermediate step | |
98 // evaluating to a bigint (base * base). | |
99 // 9079837958533 is the first prime after 2**48 / 31. | |
100 Expect.equals(1073741824, powmod(pow(2, 30), 1, 9079837958533)); | |
101 Expect.equals(9079822119301, powmod(pow(2, 30), 2, 9079837958533)); | |
102 Expect.equals(8370475851674, powmod(pow(2, 30), 3, 9079837958533)); | |
103 Expect.equals(5725645469433, powmod(pow(2, 30), 4, 9079837958533)); | |
104 | |
105 // bigint base | |
106 Expect.equals(10435682577172878912, powmod(p1, 31, p2)); | |
107 Expect.equals(2171334335785523204, powmod(p1 * p2, 5, p3)); | |
108 Expect.equals(2075559997960884603, powmod(p1 * 120, 8, p2)); | |
109 | |
110 // bigint exponent | |
111 Expect.equals(236325130834703514, powmod(pow(2, 64), p1, p4)); | |
112 Expect.equals(1733635560285390571, powmod(1000000, p5, p6)); | |
113 | |
114 // bigint modulus | |
115 Expect.equals(4740839599282053976, powmod(p7, p8, p1)); | |
116 Expect.equals(13037487407831899228197227177643459429, | |
117 powmod(p2, p3, p4 * p5)); | |
118 | |
119 // Negative | |
120 Expect.equals(3028956426596275495, powmod(-p1, 31, p2)); | |
121 Expect.equals(5719988737977477486, powmod(p1, -31, p2)); | |
122 Expect.equals(10435682577172878912, powmod(p1, 31, -p2)); | |
123 Expect.equals(7744650265791676921, powmod(-p1, -31, p2)); | |
124 Expect.equals(3028956426596275495, powmod(-p1, 31, -p2)); | |
125 Expect.equals(5719988737977477486, powmod(p1, -31, -p2)); | |
126 Expect.equals(7744650265791676921, powmod(-p1, -31, -p2)); | |
127 } | |
128 | |
129 testMain() { | |
130 // Source for expected values is Wolfram Alpha (presumably just GMP). | |
131 testGcdWithBigints(); | |
132 testGcdextWithBigints(); | |
133 testInvertWithBigints(); | |
134 testLcmWithBigints(); | |
135 testPowmodWithBigints(); | |
136 } | |
137 } | |
138 | |
139 main() { | |
140 new BigintTest().testMain(); | |
141 } | |
OLD | NEW |