1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
251
252
253
254
255
256
257
258
259
260
261
262
263
264
265
266
267
268
269
270
271
272
273
274
275
276
277
278
279
280
281
282
283
284
285
286
287
288
289
290
291
292
293
294
295
296
297
298
299
300
301
302
303
304
305
306
307
308
309
310
311
312
313
314
315
316
317
318
319
320
321
322
323
324
325
326
|
/* Test suite for the library. First, it ``tests'' that all the constructs it
* uses compile successfully. Then, its output to stdout is compared to the
* expected output automatically extracted from slash-slash comments below.
*
* NOTE: For now, the test suite expects a 32-bit system. On others, some tests
* may fail, and it may be ineffective at catching bugs. TODO: Remedy this. */
#include "BigIntegerLibrary.hh"
#include <string>
#include <iostream>
using namespace std;
// Evaluate expr and print the result or "error" as appropriate.
#define TEST(expr) do {\
cout << "Line " << __LINE__ << ": ";\
try {\
cout << (expr);\
} catch (const char *err) {\
cout << "error";\
}\
cout << endl;\
} while (0)
const BigUnsigned &check(const BigUnsigned &x) {
unsigned int l = x.getLength();
if (l != 0 && x.getBlock(l-1) == 0)
cout << "check: Unzapped number!" << endl;
if (l > x.getCapacity())
cout << "check: Capacity inconsistent with length!" << endl;
return x;
}
const BigInteger &check(const BigInteger &x) {
if (x.getSign() == 0 && !x.getMagnitude().isZero())
cout << "check: Sign should not be zero!" << endl;
if (x.getSign() != 0 && x.getMagnitude().isZero())
cout << "check: Sign should be zero!" << endl;
check(x.getMagnitude());
return x;
}
short pathologicalShort = ~((unsigned short)(~0) >> 1);
int pathologicalInt = ~((unsigned int)(~0) >> 1);
long pathologicalLong = ~((unsigned long)(~0) >> 1);
int main() {
try {
BigUnsigned z(0), one(1), ten(10);
TEST(z); //0
TEST(1); //1
TEST(10); //10
// TODO: Comprehensively test the general and special cases of each function.
// === Default constructors ===
TEST(check(BigUnsigned())); //0
TEST(check(BigInteger())); //0
// === Block-array constructors ===
BigUnsigned::Blk myBlocks[3];
myBlocks[0] = 3;
myBlocks[1] = 4;
myBlocks[2] = 0;
BigUnsigned bu(myBlocks, 3);
TEST(check(bu)); //17179869187
TEST(check(BigInteger(myBlocks, 3))); //17179869187
TEST(check(BigInteger(bu ))); //17179869187
// For nonzero magnitude, reject zero and invalid signs.
TEST(check(BigInteger(myBlocks, 3, BigInteger::positive))); //17179869187
TEST(check(BigInteger(myBlocks, 3, BigInteger::negative))); //-17179869187
TEST(check(BigInteger(myBlocks, 3, BigInteger::zero ))); //error
TEST(check(BigInteger(bu, BigInteger::positive))); //17179869187
TEST(check(BigInteger(bu, BigInteger::negative))); //-17179869187
TEST(check(BigInteger(bu, BigInteger::zero ))); //error
// For zero magnitude, force the sign to zero without error.
BigUnsigned::Blk myZeroBlocks[1];
myZeroBlocks[0] = 0;
TEST(check(BigInteger(myZeroBlocks, 1, BigInteger::positive))); //0
TEST(check(BigInteger(myZeroBlocks, 1, BigInteger::negative))); //0
TEST(check(BigInteger(myZeroBlocks, 1, BigInteger::zero ))); //0
// === BigUnsigned conversion limits ===
TEST(BigUnsigned(0).toUnsignedLong()); //0
TEST(BigUnsigned(4294967295U).toUnsignedLong()); //4294967295
TEST(stringToBigUnsigned("4294967296").toUnsignedLong()); //error
TEST(BigUnsigned(0).toLong()); //0
TEST(BigUnsigned(2147483647).toLong()); //2147483647
TEST(BigUnsigned(2147483648U).toLong()); //error
// int is the same as long on a 32-bit system
TEST(BigUnsigned(0).toUnsignedInt()); //0
TEST(BigUnsigned(4294967295U).toUnsignedInt()); //4294967295
TEST(stringToBigUnsigned("4294967296").toUnsignedInt()); //error
TEST(BigUnsigned(0).toInt()); //0
TEST(BigUnsigned(2147483647).toInt()); //2147483647
TEST(BigUnsigned(2147483648U).toInt()); //error
TEST(BigUnsigned(0).toUnsignedShort()); //0
TEST(BigUnsigned(65535).toUnsignedShort()); //65535
TEST(BigUnsigned(65536).toUnsignedShort()); //error
TEST(BigUnsigned(0).toShort()); //0
TEST(BigUnsigned(32767).toShort()); //32767
TEST(BigUnsigned(32768).toShort()); //error
// === BigInteger conversion limits ===
TEST(BigInteger(-1).toUnsignedLong()); //error
TEST(BigInteger(0).toUnsignedLong()); //0
TEST(BigInteger(4294967295U).toUnsignedLong()); //4294967295
TEST(stringToBigInteger("4294967296").toUnsignedLong()); //error
TEST(stringToBigInteger("-2147483649").toLong()); //error
TEST(stringToBigInteger("-2147483648").toLong()); //-2147483648
TEST(BigInteger(-2147483647).toLong()); //-2147483647
TEST(BigInteger(0).toLong()); //0
TEST(BigInteger(2147483647).toLong()); //2147483647
TEST(BigInteger(2147483648U).toLong()); //error
// int is the same as long on a 32-bit system
TEST(BigInteger(-1).toUnsignedInt()); //error
TEST(BigInteger(0).toUnsignedInt()); //0
TEST(BigInteger(4294967295U).toUnsignedInt()); //4294967295
TEST(stringToBigInteger("4294967296").toUnsignedInt()); //error
TEST(stringToBigInteger("-2147483649").toInt()); //error
TEST(stringToBigInteger("-2147483648").toInt()); //-2147483648
TEST(BigInteger(-2147483647).toInt()); //-2147483647
TEST(BigInteger(0).toInt()); //0
TEST(BigInteger(2147483647).toInt()); //2147483647
TEST(BigInteger(2147483648U).toInt()); //error
TEST(BigInteger(-1).toUnsignedShort()); //error
TEST(BigInteger(0).toUnsignedShort()); //0
TEST(BigInteger(65535).toUnsignedShort()); //65535
TEST(BigInteger(65536).toUnsignedShort()); //error
TEST(BigInteger(-32769).toShort()); //error
TEST(BigInteger(-32768).toShort()); //-32768
TEST(BigInteger(-32767).toShort()); //-32767
TEST(BigInteger(0).toShort()); //0
TEST(BigInteger(32767).toShort()); //32767
TEST(BigInteger(32768).toShort()); //error
// === Negative BigUnsigneds ===
// ...during construction
TEST(BigUnsigned(short(-1))); //error
TEST(BigUnsigned(pathologicalShort)); //error
TEST(BigUnsigned(-1)); //error
TEST(BigUnsigned(pathologicalInt)); //error
TEST(BigUnsigned(long(-1))); //error
TEST(BigUnsigned(pathologicalLong)); //error
// ...during subtraction
TEST(BigUnsigned(5) - BigUnsigned(6)); //error
TEST(stringToBigUnsigned("314159265358979323") - stringToBigUnsigned("314159265358979324")); //error
TEST(check(BigUnsigned(5) - BigUnsigned(5))); //0
TEST(check(stringToBigUnsigned("314159265358979323") - stringToBigUnsigned("314159265358979323"))); //0
TEST(check(stringToBigUnsigned("4294967296") - BigUnsigned(1))); //4294967295
// === BigUnsigned addition ===
TEST(check(BigUnsigned(0) + 0)); //0
TEST(check(BigUnsigned(0) + 1)); //1
// Ordinary carry
TEST(check(stringToBigUnsigned("8589934591" /* 2^33 - 1*/)
+ stringToBigUnsigned("4294967298" /* 2^32 + 2 */))); //12884901889
// Creation of a new block
TEST(check(BigUnsigned(0xFFFFFFFFU) + 1)); //4294967296
// === BigUnsigned subtraction ===
TEST(check(BigUnsigned(1) - 0)); //1
TEST(check(BigUnsigned(1) - 1)); //0
TEST(check(BigUnsigned(2) - 1)); //1
// Ordinary borrow
TEST(check(stringToBigUnsigned("12884901889")
- stringToBigUnsigned("4294967298"))); //8589934591
// Borrow that removes a block
TEST(check(stringToBigUnsigned("4294967296") - 1)); //4294967295
// === BigUnsigned multiplication and division ===
BigUnsigned a = check(BigUnsigned(314159265) * 358979323);
TEST(a); //112776680263877595
TEST(a / 123); //916883579381118
TEST(a % 123); //81
TEST(BigUnsigned(5) / 0); //error
// === Block accessors ===
BigUnsigned b;
TEST(b); //0
TEST(b.getBlock(0)); //0
b.setBlock(1, 314);
// Did b grow properly? And did we zero intermediate blocks?
TEST(check(b)); //1348619730944
TEST(b.getLength()); //2
TEST(b.getBlock(0)); //0
TEST(b.getBlock(1)); //314
// Did b shrink properly?
b.setBlock(1, 0);
TEST(check(b)); //0
BigUnsigned bb(314);
bb.setBlock(1, 159);
// Make sure we used allocateAndCopy, not allocate
TEST(bb.getBlock(0)); //314
TEST(bb.getBlock(1)); //159
// Blocks beyond the number should be zero regardless of whether they are
// within the capacity.
bb.add(1, 2);
TEST(bb.getBlock(0)); //3
TEST(bb.getBlock(1)); //0
TEST(bb.getBlock(2)); //0
TEST(bb.getBlock(314159)); //0
// === Bit accessors ===
TEST(BigUnsigned(0).bitLength()); //0
TEST(BigUnsigned(1).bitLength()); //1
TEST(BigUnsigned(4095).bitLength()); //12
TEST(BigUnsigned(4096).bitLength()); //13
// 5 billion is between 2^32 (about 4 billion) and 2^33 (about 8 billion).
TEST(stringToBigUnsigned("5000000000").bitLength()); //33
// 25 is binary 11001.
BigUnsigned bbb(25);
TEST(bbb.getBit(4)); //1
TEST(bbb.getBit(3)); //1
TEST(bbb.getBit(2)); //0
TEST(bbb.getBit(1)); //0
TEST(bbb.getBit(0)); //1
TEST(bbb.bitLength()); //5
// Effectively add 2^32.
bbb.setBit(32, true);
TEST(bbb); //4294967321
bbb.setBit(31, true);
bbb.setBit(32, false);
TEST(check(bbb)); //2147483673
// === Combining BigUnsigned, BigInteger, and primitive integers ===
BigUnsigned p1 = BigUnsigned(3) * 5;
TEST(p1); //15
/* In this case, we would like g++ to implicitly promote the BigUnsigned to a
* BigInteger, but it seems to prefer converting the -5 to a BigUnsigned, which
* causes an error. If I take out constructors for BigUnsigned from signed
* primitive integers, the BigUnsigned(3) becomes ambiguous, and if I take out
* all the constructors but BigUnsigned(unsigned long), g++ uses that
* constructor and gets a wrong (positive) answer. Thus, I think we'll just
* have to live with this cast. */
BigInteger p2 = BigInteger(BigUnsigned(3)) * -5;
TEST(p2); //-15
// === Test some previous bugs ===
{
/* Test that BigInteger division sets the sign to zero.
* Bug reported by David Allen. */
BigInteger num(3), denom(5), quotient;
num.divideWithRemainder(denom, quotient);
check(quotient);
num = 5;
num.divideWithRemainder(denom, quotient);
check(num);
}
{
/* Test that BigInteger subtraction sets the sign properly.
* Bug reported by Samuel Larkin. */
BigInteger zero(0), three(3), ans;
ans = zero - three;
TEST(check(ans).getSign()); //-1
}
{
/* Test that BigInteger multiplication shifts bits properly on systems
* where long is bigger than int. (Obviously, this would only catch the
* bug when run on such a system.)
* Bug reported by Mohand Mezmaz. */
BigInteger f=4; f*=3;
TEST(check(f)); //12
}
{
/* Test that bitwise XOR allocates the larger length.
* Bug reported by Sriram Sankararaman. */
BigUnsigned a(0), b(3), ans;
ans = a ^ b;
TEST(ans); //3
}
{
/* Test that an aliased multiplication works.
* Bug reported by Boris Dessy. */
BigInteger num(5);
num *= num;
TEST(check(num)); //25
}
{
/* Test that BigUnsignedInABase(std::string) constructor rejects digits
* too big for the specified base.
* Bug reported by Niakam Kazemi. */
TEST(BigUnsignedInABase("f", 10)); //error
}
} catch (const char *err) {
cout << "UNCAUGHT ERROR: " << err << endl;
}
return 0;
}
|