invert

Get base ^^ -1 (modulo mod).

Parameter mod must be positive.

pure nothrow @nogc @trusted
_Z!(cow)
invert
(
bool cow
)
(
auto ref scope const _Z!(cow) base
,
auto ref scope const _Z!(cow) mod
)

Examples

default construction

Z x = null;
Z y = null;
assert(x == y);
assert(x is y);			 // TODO: is this correct behaviour?
x = y;
y = x;

const Z z = 42;
x = z;

assert(Z.init.dup == Z.init);
assert(Z.init.dup == Z.init.dup);

assert(Z.init.dup !is Z.init);
assert(Z.init.dup !is Z.init.dup);

Z w = null;
w = 42;

@nogc to ASCII generation

import core.memory : pureFree;
const Z w = null;
auto chars = w.toChars;
scope(exit) pureFree(chars.ptr);
assert(chars == `0`);

operate on default-constructed instances

1 Z w;
2 
3 // should be zeroed
4 assert(w._z._mp_alloc == 0);
5 assert(w._z._mp_size == 0);
6 assert(w._z._mp_d is null);
7 
8 assert(w == 0);
9 assert(w == 0L);
10 assert(w == 0UL);
11 assert(w == 0.0f);
12 assert(w == 0.0);
13 
14 assert(w.toString == `0`);
15 assert(w.toHash == 0);
16 assert(w.sizeInBase(10) == 1);
17 assert(w.countOnes == 0);
18 assert(w.isZero);
19 assert(-w == w);
20 assert(abs(w) == w);
21 
22 assert(w.fitsIn!ulong);
23 assert(w.fitsIn!long);
24 assert(w.fitsIn!uint);
25 assert(w.fitsIn!int);
26 assert(w.fitsIn!ushort);
27 assert(w.fitsIn!short);
28 
29 assert(!w.isOdd);
30 assert(w.isEven);
31 assert(!w.isNegative);
32 assert(w.isPositive);
33 assert(w.sgn == 0);
34 
35 w.negate();
36 assert(w is Z.init);		// should be unchanged
37 w.negate();
38 assert(w is Z.init);		// should be unchanged
39 
40 w = -w;
41 assert(w is Z.init);		// should be unchanged
42 
43 w = +w;
44 assert(w is Z.init);		// should be unchanged
45 
46 w.absolute();
47 assert(w is Z.init);		// should be unchanged
48 
49 w.onesComplementSelf();
50 assert(w is Z.init);		// should be unchanged
51 w.onesComplementSelf();
52 assert(w is Z.init);		// should be unchanged
53 
54 static void testSqrt(ulong p, ulong q) @safe pure nothrow @nogc {
55 	const x = p.Z;
56 	assert(sqrt(x)== q);	// l-value first-parameter
57 	assert(sqrt(p.Z) == q);	// r-value first-parameter
58 }
59 testSqrt(1, 1);
60 testSqrt(2, 1);
61 testSqrt(3, 1);
62 testSqrt(4, 2);
63 testSqrt(5, 2);
64 testSqrt(6, 2);
65 testSqrt(7, 2);
66 testSqrt(8, 2);
67 testSqrt(9, 3);
68 testSqrt(16, 4);
69 
70 { bool isExact; assert(root(16.Z, 2, isExact) == 4 && isExact); }
71 { bool isExact; assert(root(17.Z, 2, isExact) == 4 && !isExact); }
72 { bool isExact; assert(root(27.Z, 3, isExact) == 3 && isExact); }
73 { bool isExact; assert(root(28.Z, 3, isExact) == 3 && !isExact); }
74 
75 foreach (const ui; 16 .. 20)
76 {
77 	{
78 		Z u = ui;
79 		Z rem;
80 		const r = rootrem(u, 2, rem); // l-value first-parameter
81 		assert(r == 4);
82 		assert(rem == ui - 16);
83 	}
84 	{
85 		Z rem;
86 		const r = rootrem(ui.Z, 2, rem); // r-value first-parameter
87 		assert(r == 4);
88 		assert(rem == ui - 16);
89 	}
90 }
91 
92 foreach (const ui; 16 .. 20)
93 {
94 	{
95 		Z u = ui;
96 		Z rem;
97 		const r = sqrtrem(u, rem); // l-value first-parameter
98 		assert(r == 4);
99 		assert(rem == ui - 16);
100 	}
101 	{
102 		Z rem;
103 		const r = sqrtrem(ui.Z, rem); // r-value first-parameter
104 		assert(r == 4);
105 		assert(rem == ui - 16);
106 	}
107 }
108 
109 assert(w^^10 == 0);
110 assert(w^^0 == 1);		  // TODO: correct?
111 
112 // change it and check its contents
113 w = 42;
114 assert(w.toString == `42`);
115 assert(w.toHash != 0);	  // should at least be non-zero
116 
117 {
118 	Z p;
119 	p.setBit(5);
120 	assert(p == 32);
121 }
122 {
123 	Z p;
124 	p.clearBit(5);
125 	assert(p == 0);
126 }
127 {
128 	Z p;
129 	p.complementBit(5);
130 	assert(p == 32);
131 }
132 {
133 	Z p;
134 	assert(p.testBit(5) == 0);
135 }
136 {
137 	Z p;
138 	++p;
139 	assert(p == 1);
140 }
141 {
142 	Z p;
143 	--p;
144 	assert(p == -1);
145 }
146 
147 assert(Z.init + Z.init == Z.init);
148 assert(Z.init - Z.init == Z.init);
149 assert(Z.init * Z.init == Z.init);
150 
151 assert(Z.init + 1 == 1);
152 assert(Z.init - 1 == -1);
153 
154 assert(Z.init * 1 == 0);
155 assert(Z.init / 1 == 0);
156 assert(Z.init ^^ 1 == Z.init);
157 assert(Z.init ^^ 0 == 1);
158 
159 assert(1 + Z.init == 1);
160 assert(1 - Z.init == 1);
161 assert(1 * Z.init == 0);

null construction

const Z x = null;
const Z y = null;
assert(x == y);
assert(x is y);	// TODO: this behaviour recently changed. is this correct?
const x = 42.Z;
assert(x.unaryMinus() == -42);   // l-value `this`
assert(42.Z.unaryMinus() == -42); // r-value `this`

convert to string

assert(mpz(	42).toString ==   `42`);
assert(mpz(   -42).toString ==  `-42`);
assert(mpz(`-101`).toString == `-101`);

assert(mpz(-42).toDecimalString == `-42`);
assert(mpz( 42).toDecimalString ==  `42`);

assert(mpz( 0).toHex == `0`);
assert(mpz( 1).toHex == `1`);
assert(mpz( 9).toHex == `9`);
assert(mpz(10).toHex == `A`);
assert(mpz(14).toHex == `E`);
assert(mpz(15).toHex == `F`);
assert(mpz(16).toHex == `10`);

assert(mpz(-42).absUnsign!ulong == 42);
assert(mpz( 42).absUnsign!ulong == 42);
ubyte[int.sizeof] storage;
const ubyte[1] expected = [2];
assert(storage[0] == 0);
const storage2 =  2.Z.serialize(storage, WordOrder.mostSignificantWordFirst, 1, WordEndianess.littleEndian, 0);
assert(storage2.ptr == storage.ptr);
assert(storage2 == expected);
auto prime = 33_391.Z;
for (int i = 0; i < 20; ++i)
{
	prime = nextPrime(prime);
	for (auto order = WordOrder.min; order < WordOrder.max; ++order)
	{
		for (auto endianess = WordEndianess.min; endianess < WordEndianess.max; ++endianess)
		{
			ubyte[] data = prime.serialize!(ubyte)(order, endianess, 0);
			const samePrime = Z(data, order, 1, endianess, 0);
			assert(prime == samePrime);
		}
	}
}

opBinary with r-value right-hand-side

const Z a = 42;
{
	const Z b = a + 1.Z;	// r-value `rhs`
	assert(b == 43);
}

{
	const Z b = a - 1.Z;	// r-value `rhs`
	assert(b == 41);
}

{
	const Z b = a * 2.Z;	// r-value `rhs`
	assert(b == 84);
}

{
	const Z b = a / 2.Z;	// r-value `rhs`
	assert(b == 21);
}

{
	const Z b = a % 10.Z;	// r-value `rhs`
	assert(b == 2);
}
1 const _ = (cast(uint)42).Z;
2 const a = 42.Z;
3 const b = 43UL.Z;
4 const c = 43.0.Z;
5 const z = 0.Z;
6 
7 // `opOpAssign` with `Unsigned`
8 auto w = 42.Z;
9 assert(w == 42);
10 
11 w += 100UL;
12 assert(w == 142);
13 
14 w -= 100.Z;
15 assert(w == 42);
16 
17 w += 100UL;
18 assert(w == 142);
19 
20 w -= 100UL;
21 assert(w == 42);
22 
23 w *= 100UL;
24 assert(w == 4200);
25 
26 w /= 100UL;
27 assert(w == 42);
28 
29 w %= 10UL;
30 assert(w == 2);
31 
32 w ^^= 6UL;
33 assert(w == 64);
34 
35 w = 42;
36 assert(w == 42);
37 
38 w += 100;
39 assert(w == 142);
40 
41 w -= 100;
42 assert(w == 42);
43 
44 w *= 100;
45 assert(w == 4200);
46 
47 w /= 100;
48 assert(w == 42);
49 
50 w *= 100;
51 assert(w == 4200);
52 
53 w /= -100;
54 assert(w == -42);
55 
56 w *= -1;
57 assert(w == 42);
58 
59 w %= 10;
60 assert(w == 2);
61 
62 w = 2;
63 w ^^= 6;
64 assert(w == 64);
65 
66 w = 32.0;
67 assert(w == 32);
68 
69 w = 42UL;
70 assert(w == 42);
71 
72 w /= 2.Z;
73 assert(w == 21);
74 
75 w /= -2.Z;
76 assert(w == -10);
77 
78 w *= -2.Z;
79 assert(w == 20);
80 
81 w %= 3.Z;
82 assert(w == 2);
83 
84 w *= -1.Z;
85 assert(w == -2);
86 
87 w /= -1.Z;
88 assert(w == 2);
89 
90 // equality
91 assert(z == 0);
92 assert(z == cast(uint)0);
93 assert(z == 0L);
94 assert(z == 0UL);
95 assert(z == 0.0f);
96 assert(z == 0.0);
97 
98 // eval cast
99 
100 assert(a);
101 assert(cast(ulong)a == a);
102 assert(cast(ulong)a == 42);
103 assert(cast(long)a == a);
104 assert(cast(long)a == 42);
105 assert(cast(double)a == 42.0);
106 
107 // binary
108 
109 assert(`0b11`.Z == 3);
110 assert(`0B11`.Z == 3);
111 assert(Z.fromBinaryString(`11`) == 3);
112 assert(Z.fromBinaryString(`0b11`) == 3);
113 assert(Z.fromBinaryString(`0B11`) == 3);
114 
115 // octal
116 
117 assert(`07`.Z == 7);
118 assert(`010`.Z == 8);
119 
120 // hexadecimal
121 
122 assert(`0x10`.Z == 16);
123 assert(`0X10`.Z == 16);
124 assert(Z(`10`, 16) == 16);
125 assert(Z.fromHexString(`10`) == 16);
126 assert(Z.fromHexString(`0x10`) == 16);
127 assert(Z.fromHexString(`0X10`) == 16);
128 
129 // decimal
130 
131 assert(`101`.Z == 101);
132 assert(`101`.Z == 101);
133 
134 const ic = 101UL.Z;
135 
136 assert(a == a.dup);
137 assert(ic == ic.dup);
138 
139 // equality
140 
141 assert(a == a);
142 assert(a == 42.Z);
143 assert(a == 42.0);
144 assert(a == 42);
145 assert(a == cast(uint)42);
146 assert(a == 42UL);
147 assert(_ == 42);
148 assert(c == 43.0);
149 
150 // non-equality
151 
152 assert(a != b);
153 
154 // less than
155 
156 assert(a < b);
157 assert(a < 43.Z);
158 assert(a < 43);
159 assert(a < cast(uint)43);
160 assert(a < 43UL);
161 assert(a < 43.0);
162 
163 assert(-1.Z < 0.Z);
164 assert(-1.Z < 0L);
165 assert(-1.Z < 0UL);
166 assert(-1.Z < 0.0);
167 
168 // greater than
169 
170 assert(b > a);
171 assert(b > 42.Z);
172 assert(b > 42);
173 assert(b > cast(uint)42);
174 assert(b > 42UL);
175 assert(b > 42.0);
176 
177 assert(+1.Z > 0.Z);
178 assert(+1.Z > 0L);
179 assert(+1.Z > 0UL);
180 assert(+1.Z > 0.0);
181 
182 // absolute value
183 
184 assert(abs(a) == a);		// free function
185 assert(a.abs == a);		 // UFCS
186 assert(abs(-42.Z) == 42);
187 assert(abs(-a) == a);
188 
189 // absolute value comparison
190 
191 assert(cmpabs(-43.Z,  44.Z) == -1);
192 assert(cmpabs(-43.Z, -44.Z) == -1);
193 assert(cmpabs(-44.Z, -43.Z) == +1);
194 assert(cmpabs(-43.Z, -43.Z) ==  0);
195 
196 assert(cmpabs(-43.Z,  44.0) == -1);
197 assert(cmpabs(-43.Z, -44.0) == -1);
198 assert(cmpabs(-44.Z, -43.0) == +1);
199 assert(cmpabs(-43.Z, -43.0) ==  0);
200 
201 assert(cmpabs(-43.Z, 44) == -1);
202 assert(cmpabs( 43.Z, 44) == -1);
203 assert(cmpabs(-44.Z, 43) == +1);
204 assert(cmpabs( 44.Z, 43) == +1);
205 assert(cmpabs(-43.Z, 43) ==  0);
206 
207 Z _43 = 43;
208 Z _4 = 4;
209 Z _24 = 24;
210 
211 // next prime
212 assert(nextPrime(_4) == 5);
213 assert(nextPrime(24.Z) == 29);
214 
215 assert(nextPrime(_24) == 29);
216 assert(nextPrime(24.Z) == 29);
217 assert(24.Z.nextPrime() == 29);
218 
219 assert(nextPrime(_43) == 47);
220 assert(nextPrime(43.Z) == 47);
221 assert(43.Z.nextPrime() == 47);
222 
223 // greatest common divisor
224 
225 assert(gcd(43.Z,  44.Z) == 1);
226 assert(gcd(4.Z, 24.Z) == 4);
227 assert(gcd(6.Z, 24.Z) == 6);
228 assert(gcd(10.Z, 100.Z) == 10);
229 
230 assert(gcd(43.Z,  44) == 1);
231 assert(gcd(4.Z, 24) == 4);
232 assert(gcd(6.Z, 24) == 6);
233 assert(gcd(10.Z, 100) == 10);
234 
235 assert(gcd(_43,  44) == 1);
236 assert(gcd(_4, 24) == 4);
237 assert(gcd(_4, _24) == 4);
238 assert(gcd(_4, 24.Z) == 4);
239 
240 // least common multiple
241 
242 assert(lcm(43.Z,  44.Z) == 1892);
243 assert(lcm(4.Z, 24.Z) == 24);
244 assert(lcm(6.Z, 24.Z) == 24);
245 assert(lcm(10.Z, 100.Z) == 100);
246 
247 assert(lcm(43.Z,  44) == 1892);
248 assert(lcm(4.Z, 24) == 24);
249 assert(lcm(6.Z, 24) == 24);
250 assert(lcm(10.Z, 100) == 100);
251 
252 assert(lcm(_43,  44) == 1892);
253 assert(lcm(_4, 24) == 24);
254 assert(lcm(_4, _24) == 24);
255 assert(lcm(_4, 24.Z) == 24);
256 
257 // negated value
258 
259 assert(-a == -42);
260 assert(-(-a) == a);
261 
262 auto n = 42.Z;
263 n.negate();
264 assert(n == -42);
265 n.negate();
266 assert(n == 42);
267 n.negate();
268 assert(n == -42);
269 n.absolute();
270 assert(n == 42);
271 n.absolute();
272 assert(n == 42);
273 
274 n.onesComplementSelf();
275 assert(n == -43);
276 assert(onesComplement(n) == 42);
277 assert(onesComplement(-43.Z) == 42);
278 assert(com(n) == 42);
279 assert(com(-43.Z) == 42);
280 
281 /*TODO: figure out why this call doesn’t trigger a warn-unused warning when
282  * the functions below returning `S` above does */
283 onesComplement(42.Z);
284 static if (false) {
285 	struct S(T) {
286 		T x;
287 		T* xp;						// this prevents diagnostics
288 	}
289 	static S!int f()() @safe pure nothrow @nogc { return typeof(return).init; }
290 	static S!int g()(scope S!int x) @safe pure nothrow @nogc { return x; }
291 	static const(S!int) h1()(scope const(S!int) x) @safe pure nothrow @nogc { return x; }
292 	static S!int h2()(scope const(S!int) _) @safe pure nothrow @nogc { return typeof(return).init; }
293 	g(S!int(32));
294 	f();
295 	h1(S!int(32));
296 	h2(S!int(32));
297 }
298 
299 // addition
300 
301 assert(a + b == b + a);	 // commutative
302 assert(a + 43.Z == b + a);
303 assert(a - 43.Z == -(43.Z - a));
304 assert(a + 0 == a);
305 assert(a + 1 != a);
306 assert(0 + a == a);
307 assert(1 + a != a);
308 assert(a + 0UL == a);
309 assert(a + 1UL != a);
310 assert(a + b == 42 + 43);
311 assert(1 + a == 43);
312 assert(a + (-1) == 41);
313 assert(1UL + a == 43);
314 assert(a + 1 == 1 + a);	   // commutative
315 assert(a + (-1) == (-1) + a); // commutative
316 assert(1UL + a == a + 1UL);   // commutative
317 
318 // subtraction
319 
320 assert(a - 2 == 40);
321 assert(2 - a == -40);
322 assert(-2 - a == -44);
323 assert(a - 2 == -(2 - a));	 // commutative
324 assert(a - (-2) == 44);
325 assert(44UL - 42.Z == 2);
326 
327 // multiplication
328 
329 assert(a * 1UL == a);
330 assert(a * 1 == a);
331 assert(1 * a == a);
332 assert(1UL * a == a);
333 assert((-1) * a == -a);
334 assert(a * 2 != a);
335 assert(a * -2 == -(2*a));
336 assert(a * b == b * a);
337 assert(a * b == 42UL * 43UL);
338 
339 // division
340 
341 assert(27.Z / 3.Z == 9);
342 assert(27.Z /   3  == 9);
343 
344 assert(27.Z / 10.Z  == 2);
345 assert(27.Z /   10   == 2);
346 assert(27.Z /   10UL == 2);
347 
348 assert(27.Z % 10UL == 7);
349 
350 assert(27.Z / -3   == -9);
351 assert(27.Z /  3UL ==  9);
352 
353 assert(27.Z / -10   == -2);
354 
355 assert(28   /  3.Z ==  9);
356 assert(28UL /  3.Z ==  9);
357 
358 assert(28   / -3.Z == -9);
359 assert(28UL / -3.Z == -9);
360 
361 // modulo/remainder
362 
363 assert(27.Z % 3.Z == 0);
364 assert(27.Z % 10.Z == 7);
365 
366 assert(27.Z % 3 == 0);
367 assert(-27.Z % 3 == 0);
368 
369 assert(27.Z % 10 == 7);
370 assert(27.Z % 10 == 7);
371 
372 assert(28   % 3.Z == 1);
373 assert(28UL % 3.Z == 1);
374 
375 assert( 28.Z  % -3 == -1); // negative divisor gives negative remainder according to https://en.wikipedia.org/wiki/Remainder
376 assert(-28.Z  %  3 == 1);  // dividend sign doesn't affect remainder
377 
378 assert( 28.Z  % -3.Z == -1);
379 assert(-28.Z  %  3.Z == 2);
380 assert( 28  % -3.Z == 1);
381 assert(-28  %  3.Z == -1);
382 
383 // modulo/remainder
384 
385 const one = 1.Z;
386 const two = 2.Z;
387 const three = 3.Z;
388 const four = 4.Z;
389 const five = 5.Z;
390 const six = 6.Z;
391 assert(six % one == 0);
392 assert(six % two == 0);
393 assert(six % three == 0);
394 assert(six % four == 2);
395 assert(six % five == 1);
396 assert(six % six == 0);
397 
398 // subtraction
399 
400 assert(six - one == 5);
401 assert(six - 1UL == 5);
402 assert(six - 1 == 5);
403 assert(1 - six == -5);
404 assert(1L - six == -5);
405 assert(1UL - six == -5);
406 
407 // exponentiation
408 assert(0.Z^^0 == 1);
409 assert(3.Z^^3 == 27);
410 assert(3.Z^^3L == 27);
411 assert(2.Z^^8 == 256);
412 assert(2.Z^^8L == 256);
413 assert(2.Z^^8UL == 256);
414 
415 assert(Z.pow(2UL, 8UL) == 256);
416 assert(Z.pow(2UL, 8) == 256);
417 assert(Z.pow(2UL, 8) == 256);
418 assert(Z.pow(2, 8) == 256);
419 assert(Z.pow(-2, 8) == 256);
420 assert(Z.pow(-2, 7) == -128);
421 
422 // disallow power exponent to be an `MpZ`
423 assert(!__traits(compiles, 2^^8.Z == 256));
424 assert(!__traits(compiles, 2L^^8.Z == 256));
425 assert(!__traits(compiles, 2UL^^8.Z == 256));
426 
427 // exponentiation plus modulus
428 
429 assert(2.Z.powm(8.Z, 8.Z) == 0.Z);
430 assert(2.Z.powm(3.Z, 16.Z) == 8.Z);
431 assert(3.Z.powm(3.Z, 16.Z) == 11.Z);
432 
433 assert(2.Z.powm(8, 8.Z) == 0.Z);
434 assert(2.Z.powm(3, 16.Z) == 8.Z);
435 assert(3.Z.powm(3, 16.Z) == 11.Z);
436 
437 // modular multiplicative inverse
438 assert(3.Z.invert(26.Z) == 9.Z); // r-value `base`
439 assert(3.Z.invert(-26.Z) == 9.Z); // r-value `base`
440 {
441 	auto base = 3.Z;
442 	assert(base.invert(26.Z) == 9.Z); // l-value `base` and r-value `mod`
443 }
444 {
445 	auto base = 3.Z;
446 	auto mod = 26.Z;
447 	assert(base.invert(mod) == 9.Z); // l-value `base` and l-value `mod
448 }
449 
450 // bitwise and, or and xor
451 
452 {
453 	foreach (immutable i; 0 .. 10)
454 	{
455 		foreach (immutable j; 0 .. 10)
456 		{
457 			assert((i.Z & j.Z) == (i & j));
458 			assert((i.Z | j.Z) == (i | j));
459 			assert((i.Z ^ j.Z) == (i ^ j));
460 
461 			Z x = null;
462 
463 			x = i.Z;
464 			x &= j.Z;
465 			assert(x == (i & j));
466 
467 			x = i.Z;
468 			x |= j.Z;
469 			assert(x == (i | j));
470 
471 			x = i.Z;
472 			x ^= j.Z;
473 			assert(x == (i ^ j));
474 		}
475 	}
476 }
477 
478 // swap
479 
480 auto x = 42.Z;
481 auto y = 43.Z;
482 
483 assert(x == 42);
484 assert(y == 43);
485 
486 x.swap(y);
487 
488 assert(y == 42);
489 assert(x == 43);
490 
491 swap(x, y);
492 
493 assert(x == 42);
494 assert(y == 43);
495 
496 assert(null.Z.fromString("42") == 42.Z);
497 assert(null.Z.fromString("42") < 43.Z);
498 assert(null.Z.fromString("42") > 41.Z);
499 assert(null.Z.fromString("42") == 42);
500 assert(null.Z.fromString("11", 2) == 3);
501 assert(null.Z.fromString("7", 8) == 7);
502 assert(null.Z.fromString("7") == 7);
503 assert(null.Z.fromString("e", 16) == 14);
504 assert(null.Z.fromString("f", 16) == 15);
505 assert(null.Z.fromString("0xe") == 14);
506 assert(null.Z.fromString("0xf") == 15);
507 assert(null.Z.fromString("10", 16) == 16);
508 assert(null.Z.fromString("10", 32) == 32);
509 
510 // odd and even
511 
512 assert(0.Z.isEven);
513 assert(1.Z.isOdd);
514 assert(2.Z.isEven);
515 assert(3.Z.isOdd);
516 
517 assert((-1).Z.isOdd);
518 assert((-2).Z.isEven);
519 assert((-3).Z.isOdd);
520 
521 assert("300000000000000000000000000000000000000".Z.isEven);
522 assert("300000000000000000000000000000000000001".Z.isOdd);
523 assert("300000000000000000000000000000000000002".Z.isEven);
524 assert("300000000000000000000000000000000000003".Z.isOdd);
525 
526 // negative and positive
527 
528 assert(0.Z.isPositive);
529 assert(1.Z.isPositive);
530 assert(2.Z.isPositive);
531 assert(3.Z.isPositive);
532 // TODO: assert(!(-1.Z.isPositive));
533 // TODO: assert(!(-2.Z.isPositive));
534 // TODO: assert(!(-3.Z.isPositive));
535 // TODO: assert(-1.Z.isNegative);
536 // TODO: assert(-2.Z.isNegative);
537 // TODO: assert(-3.Z.isNegative);
538 // TODO: assert(!(1.Z.isNegative));
539 // TODO: assert(!(2.Z.isNegative));
540 // TODO: assert(!(3.Z.isNegative));
541 
542 foreach (const p; 1 .. 10)
543 {
544 	assert((p^^2).Z.isPerfectSquare);
545 	assert(!(p^^2 + 1).Z.isPerfectSquare);
546 	foreach (const q; 2 .. 5)
547 		assert((p^^q).Z.isPerfectPower);
548 }
549 
550 foreach (const d; 1UL .. 10UL)
551 {
552 	assert( d.Z.isDivisibleBy(d));
553 	assert( d.Z.isDivisibleBy(d.Z));
554 	assert(!d.Z.isDivisibleBy(d + 1));
555 	assert(!d.Z.isDivisibleBy((d + 1).Z));
556 }
557 assert( 1.Z.isDivisibleBy(1.Z));
558 assert( 2.Z.isDivisibleBy(1.Z));
559 assert(!1.Z.isDivisibleBy(2.Z));
560 assert(!3.Z.isDivisibleBy(2.Z));
561 assert( 100.Z.isDivisibleBy(10.Z));
562 assert( 100.Z.isDivisibleBy(10UL));
563 
564 assert((-1).Z.isNegative);
565 assert((-2).Z.isNegative);
566 assert((-3).Z.isNegative);
567 
568 // sign function (sgn)
569 
570 assert(long.min.Z.sgn == -1);
571 assert(int.min.Z.sgn  == -1);
572 assert(-2.Z.sgn == -1);
573 assert(-1.Z.sgn == -1);
574 assert( 0.Z.sgn ==  0);
575 assert( 1.Z.sgn ==  1);
576 assert( 2.Z.sgn ==  1);
577 assert(int.max.Z.sgn  == 1);
578 assert(long.max.Z.sgn == 1);
579 
580 assert(!long.min.Z.isZero);
581 assert(!int.min.Z.isZero);
582 assert(!(-2).Z.isZero);
583 assert(!(-1).Z.isZero);
584 assert( 0.Z.isZero);
585 assert(! 1.Z.isZero);
586 assert(! 2.Z.isZero);
587 assert(!int.max.Z.isZero);
588 assert(!long.max.Z.isZero);
589 
590 assert(!long.min.Z.isOne);
591 assert(!int.min.Z.isOne);
592 assert(!(-2).Z.isOne);
593 assert(!(-1).Z.isOne);
594 assert(!0.Z.isOne);
595 assert( 1.Z.isOne);
596 assert(! 2.Z.isOne);
597 assert(!int.max.Z.isOne);
598 assert(!long.max.Z.isOne);
599 
600 assert(0.Z.populationCount == 0);
601 assert(1.Z.populationCount == 1);
602 assert(2.Z.populationCount == 1);
603 assert(3.Z.populationCount == 2);
604 assert(4.Z.populationCount == 1);
605 assert(5.Z.populationCount == 2);
606 assert(6.Z.populationCount == 2);
607 assert(7.Z.populationCount == 3);
608 
609 // TODO
610 // {
611 //	 Z g = null;
612 //	 assert(!b.testBit(0));
613 //	 g.setBit(0);
614 //	 assert(b.testBit(0));
615 //	 g.clearBit(0);
616 //	 assert(!b.testBit(0));
617 // }
618 
619 // fits in type
620 
621 foreach (Integral; AliasSeq!(short, int, long,
622 							 ushort, uint, ulong))
623 {
624 	assert(Integral.min.Z.fitsIn!Integral);
625 	assert(Integral.max.Z.fitsIn!Integral);
626 }
627 
628 // TODO
629 // assert(short.min.Z.fitsIn!short);
630 // assert(short.max.Z.fitsIn!short);
631 // assert(ushort.min.Z.fitsIn!ushort);
632 // assert(ushort.max.Z.fitsIn!ushort);
633 
634 // limb count
635 
636 assert(0.Z.limbCount == 0);
637 assert(1.Z.limbCount == 1);
638 assert(2.Z.limbCount == 1);
639 
640 assert(Z.pow(2UL, 32UL).limbCount == 1);
641 
642 assert(Z.pow(2UL, 63UL).limbCount == 1);
643 assert(Z.pow(2UL, 63UL + 1).limbCount == 2);
644 
645 assert(Z.pow(2UL, 127UL).limbCount == 2);
646 assert(Z.pow(2UL, 127UL + 1).limbCount == 3);
647 
648 assert(Z.pow(2UL, 255UL).limbCount == 4);
649 assert(Z.pow(2UL, 255UL + 1).limbCount == 5);

generators

assert(Z.mersennePrime(15) == 2^^15 - 1);
assert(Z.mersennePrime(15UL) == 2^^15 - 1);

left shift

assert(1.Z << 1.Z == 2^^1);
assert(1.Z << 2.Z == 2^^2);
assert(1.Z << 32.Z == 2UL^^32);
assert(1.Z << 63.Z == 2UL^^63);
assert(16.Z << -3.Z == 2); // `16 << -3` becomes `16 >> 3`

assert(1.Z << 1U == 2^^1);
assert(1.Z << 2U == 2^^2);
assert(1.Z << 32U == 2UL^^32);
assert(1.Z << 63U == 2UL^^63);
assert(16.Z << -3 == 2); // `16 << -3` becomes `16 >> 3`

Z a;
a = 1;
a <<= 1u;
assert(a == 2^^1);
a = 1;
a <<= 2u;
assert(a == 2^^2);
a = 1;
a <<= 32u;
assert(a == 2UL^^32);
a = 1;
a <<= 63u;
assert(a == 2UL^^63);
a = 16;
a <<= -3;
assert(a == 2);

Z b;
a = 1;
b = 1;
a <<= b;
assert(a == 2^^1);
a = 1;
b = 2;
a <<= b;
assert(a == 2^^2);
a = 1;
b = 32;
a <<= b;
assert(a == 2UL^^32);
a = 1;
b = 63;
a <<= b;
assert(a == 2UL^^63);
a = 16;
b = -3;
a <<= b;
assert(a == 2);

right shift

1 assert(0x4.Z >> 1.Z == 0x2);
2 assert(0x4.Z >> 2.Z == 0x1);
3 assert(0x4.Z >> 3.Z == 0x0);
4 assert(0x123456789ABCDEF.Z >> 4.Z == 0x123456789ABCDEuL);
5 assert(0xABCDEF.Z >> 8.Z == 0xABCD);
6 assert(0x1234ABCDEF.Z >> 32.Z == 0x12);
7 assert(2.Z >> -3.Z == 16); // `2 >> -3` becomes `2 << 3`
8 
9 assert(0x4.Z >> 1 == 0x2);
10 assert(0x4.Z >> 2 == 0x1);
11 assert(0x4.Z >> 3 == 0x0);
12 assert(0x123456789ABCDEF.Z >> 4 == 0x123456789ABCDEuL);
13 assert(0xABCDEF.Z >> 8 == 0xABCD);
14 assert(0x1234ABCDEF.Z >> 32 == 0x12);
15 assert(2.Z >> -3 == 16);
16 
17 Z a, b;
18 a = 4;
19 a >>= 1;
20 assert(a == 0x2);
21 a = 4;
22 a >>= 2;
23 assert(a == 0x1);
24 a = 4;
25 a >>= 3;
26 assert(a == 0x0);
27 a = 0x123456789ABCDEF;
28 a >>= 4;
29 assert(a == 0x123456789ABCDEuL);
30 a = 0xABCDEF;
31 a >>= 8;
32 assert(a == 0xABCD);
33 a = 0x1234ABCDEF;
34 a >>= 32;
35 assert(a == 0x12);
36 a = 2;
37 a >>= -3;
38 assert(a == 16);
39 
40 a = 4;
41 b = 1;
42 a >>= b;
43 assert(a == 0x2);
44 a = 4;
45 b = 2;
46 a >>= b;
47 assert(a == 0x1);
48 a = 4;
49 b = 3;
50 a >>= b;
51 assert(a == 0x0);
52 a = 0x123456789ABCDEF;
53 b = 4;
54 a >>= b;
55 assert(a == 0x123456789ABCDEuL);
56 a = 0xABCDEF;
57 b = 8;
58 a >>= b;
59 assert(a == 0xABCD);
60 a = 0x1234ABCDEF;
61 b = 32;
62 a >>= b;
63 assert(a == 0x12);
64 a = 2;
65 b = -3;
66 a >>= b;
67 assert(a == 16);

verify compliance with Phobos' BigInt

1 alias bigInt = mpz;
2 alias BigInt = Z;	 // Phobos naming convention
3 
4 {
5 	const BigInt a = "9588669891916142";
6 	const BigInt b = "7452469135154800";
7 	const c = a * b;
8 	assert(c == BigInt("71459266416693160362545788781600"));
9 	auto d = b * a;
10 	assert(d == BigInt("71459266416693160362545788781600"));
11 	assert(d == c);
12 	d = c * BigInt("794628672112");
13 	assert(d == BigInt("56783581982794522489042432639320434378739200"));
14 	auto e = c + d;
15 	assert(e == BigInt("56783581982865981755459125799682980167520800"));
16 	const f = d + c;
17 	assert(f == e);
18 	auto g = f - c;
19 	assert(g == d);
20 	g = f - d;
21 	assert(g == c);
22 	e = 12_345_678;
23 	g = c + e;
24 	const h = g / b;
25 	const i = g % b;
26 	assert(h == a);
27 	assert(i == e);
28 	BigInt j = "-0x9A56_57f4_7B83_AB78";
29 	j ^^= 11UL;
30 	j ^^= 2L;
31 	j ^^= 2;
32 }
33 
34 {
35 	auto b = BigInt("1_000_000_000");
36 
37 	b += 12_345;
38 	assert(b == 1_000_012_345);
39 	b += -12_345;
40 	assert(b == 1_000_000_000);
41 
42 	b -= -12_345;
43 	assert(b == 1_000_012_345);
44 	b -= +12_345;
45 	assert(b == 1_000_000_000);
46 
47 	b += 12_345;
48 	assert(b == 1_000_012_345);
49 
50 	b /= 5UL;
51 	assert(b == 200_002_469);
52 }
53 
54 {
55 	auto x = BigInt("123");
56 	const y = BigInt("321");
57 	x += y;
58 	assert(x == 444);
59 }
60 
61 {
62 	const x = BigInt("123");
63 	const y = BigInt("456");
64 	const BigInt z = x * y;
65 	assert(z == 56_088);
66 }
67 
68 {
69 	auto x = BigInt("123");
70 	x *= 300;
71 	assert(x == 36_900);
72 }
73 
74 {
75 	auto x = BigInt("123");
76 	x *= -1;
77 	assert(x == -123);
78 }
79 
80 {
81 	const x  = BigInt("1_000_000_500");
82 
83 	immutable ulong ul  = 2_000_000UL;
84 	immutable uint ui   = 500_000;
85 	immutable ushort us = 30_000;
86 	immutable ubyte ub  = 50;
87 
88 	immutable long  l = 1_000_000L;
89 	immutable int   i = 500_000;
90 	immutable short s = 30_000;
91 	immutable byte b  = 50;
92 
93 	static assert(is(typeof(x % ul)  == ulong));
94 	static assert(is(typeof(x % ui)  == uint));
95 	static assert(is(typeof(x % us)  == ushort));
96 	static assert(is(typeof(x % ub)  == ubyte));
97 
98 	static assert(is(typeof(x % l)  == long));
99 	static assert(is(typeof(x % i)  == int));
100 	// TODO: static assert(is(typeof(x % s)  == short));
101 	// TODO: static assert(is(typeof(x % b)  == byte));
102 
103 	assert(x % ul == 500);
104 	assert(x % ui == 500);
105 	assert(x % us  == 10_500);
106 	assert(x % ub == 0);
107 
108 	assert(x % l  == 500L);
109 	assert(x % i  == 500);
110 	assert(x % s  == 10_500);
111 	assert(x % b == 0);
112 }
113 
114 {
115 	const x = BigInt("100");
116 	const BigInt y = 123 + x;
117 	assert(y == BigInt("223"));
118 
119 	const BigInt z = 123 - x;
120 	assert(z == BigInt("23"));
121 
122 	// Dividing a built-in integer type by BigInt always results in
123 	// something that fits in a built-in type, so the built-in type is
124 	// returned, not BigInt.
125 	static assert(is(typeof(1000 / x) == int));
126 	assert(1000 / x == 10);
127 }
128 
129 {
130 	auto x = BigInt("1234");
131 	assert(+x  == BigInt(" 1234"));
132 	assert(-x  == BigInt("-1234"));
133 	++x;
134 	assert(x == BigInt("1235"));
135 	--x;
136 	assert(x == BigInt("1234"));
137 }
138 
139 {
140 	const x = BigInt("12345");
141 	const y = BigInt("12340");
142 	immutable int z = 12_345;
143 	immutable int w = 54_321;
144 	assert(x == x);
145 	assert(x != y);
146 	assert(x == y + 5);
147 	assert(x == z);
148 	assert(x != w);
149 }
150 
151 {
152 	// non-zero values are regarded as `true`
153 	const x = BigInt("1");
154 	const y = BigInt("10");
155 	assert(x);
156 	assert(y);
157 
158 	// zero value is regarded as `false`
159 	const z = BigInt("0");
160 	assert(!z);
161 }
162 
163 {
164 	assert(cast(int)BigInt("0") == 0);
165 	assert(cast(ubyte)BigInt("0") == 0);
166 
167 	assert(cast(ubyte)BigInt(255) == 255);
168 	assert(cast(ushort)BigInt(65_535) == 65_535);
169 	assert(cast(uint)BigInt(uint.max) == uint.max);
170 	assert(cast(ulong)BigInt(ulong.max) == ulong.max);
171 
172 	assert(cast(byte)BigInt(-128) == -128);
173 	assert(cast(short)BigInt(-32_768) == -32_768);
174 	assert(cast(int)BigInt(int.min) == int.min);
175 	assert(cast(long)BigInt(long.min) == long.min);
176 
177 	assert(cast(byte)BigInt(127) == 127);
178 	assert(cast(short)BigInt(32_767) == 32_767);
179 	assert(cast(int)BigInt(int.max) == int.max);
180 	assert(cast(long)BigInt(long.max) == long.max);
181 
182 	// TODO:
183 	// import std.conv : to, ConvOverflowException;
184 	// import std.exception : assertThrown;
185 	// assertThrown!ConvOverflowException(BigInt("256").to!ubyte);
186 	// assertThrown!ConvOverflowException(BigInt("-1").to!ubyte);
187 }
188 
189 {
190 	// TODO
191 	// segfaults because with double free
192 	// const(BigInt) x = BigInt("123");
193 	// BigInt y = cast()x;	// cast away const
194 	// assert(y == x);
195 }
196 
197 {
198 	const x = BigInt("100");
199 	const y = BigInt("10");
200 	const int z = 50;
201 	const int w = 200;
202 	assert(y < x);
203 	assert(x > z);
204 	assert(z > y);
205 	assert(x < w);
206 }
207 
208 {
209 	assert(BigInt("12345").toLong() == 12_345);
210 	assert(BigInt("-123450000000000000000000000000").toLong() == long.min);
211 	assert(BigInt("12345000000000000000000000000000").toLong() == long.max);
212 }
213 
214 {
215 	assert(BigInt("12345").toInt() == 12_345);
216 	assert(BigInt("-123450000000000000000000000000").toInt() == int.min);
217 	assert(BigInt("12345000000000000000000000000000").toInt() == int.max);
218 }

Fermats Little Theorem

version (unittestLong)
{
	/*
	  Fermats little theorem: a ^ p ≡ a (mod p) ∀ prime p check Fermats
	  little theorem for a ≤ 100000 and all mersene primes M(p) : p ≤ 127
	*/
	foreach (immutable ulong i; [2, 3, 5, 7, 13, 17, 19, 31, 61, 89, 107, 127])
	{
		foreach (immutable ulong j; 2 .. 100_000)
		{
			const p = Z.mersennePrime(i); // power
			const a = Z(j); // base
			const amp = a % p;
			const b = a.powm(p, p); // result
			assert(b == amp);
		}
	}
}

Meta