1use std::{
2 cmp::Ordering,
3 ops::{Add, Div, Mul, Neg, Sub},
4};
5
6use crate::common::cast::Cast;
7
8use super::big_uint::BigUint;
9
10#[derive(Debug, PartialEq, Clone, Eq, Default)]
11pub struct BigInt {
12 pub sign: Sign,
13 pub value: BigUint,
14}
15
16#[derive(Debug, PartialEq, Clone, Copy, Eq)]
17pub enum Sign {
18 Positive = 1,
19 Negative = -1,
20}
21
22impl Default for Sign {
23 fn default() -> Self {
24 Self::Positive
25 }
26}
27
28impl BigInt {
29 pub const ZERO: BigInt = BigInt {
30 sign: Sign::Positive,
31 value: BigUint::ZERO,
32 };
33
34 fn normalize(&mut self) {
35 self.value.normalize();
36 if self.value.is_zero() {
37 self.sign = Sign::Positive;
38 }
39 }
40
41 pub fn is_zero(&self) -> bool {
42 self.value.is_zero()
43 }
44
45 pub fn new(sign: Sign, value: BigUint) -> BigInt {
46 BigInt { sign, value }
47 }
48
49 pub fn from_u64(n: u64) -> Self {
50 BigInt {
51 sign: Sign::Positive,
52 value: BigUint { value: [n].cast() },
53 }
54 }
55
56 pub fn abs(self) -> BigInt {
57 match self.sign {
58 Sign::Positive => self,
59 Sign::Negative => BigInt {
60 sign: Sign::Positive,
61 value: self.value,
62 },
63 }
64 }
65
66 pub fn from_i64(n: i64) -> Self {
67 let sign = if n < 0 {
68 Sign::Negative
69 } else {
70 Sign::Positive
71 };
72 BigInt {
73 sign,
74 value: BigUint {
75 value: [(n * sign as i64) as u64].cast(),
76 },
77 }
78 }
79
80 pub fn div_mod(&self, d: &Self) -> (BigInt, BigInt) {
81 if d.is_zero() {
82 panic!("attempt to divide by zero");
83 }
84
85 let sign = match self.sign == d.sign {
86 true => Sign::Positive,
87 false => Sign::Negative,
88 };
89
90 let (q, r) = self.value.div_mod(&d.value);
91 (BigInt { sign, value: q }, BigInt { sign, value: r })
92 }
93}
94
95impl Add for &BigInt {
96 type Output = BigInt;
97
98 fn add(self, other: Self) -> Self::Output {
99 match self.sign == other.sign {
100 true => BigInt {
101 sign: self.sign,
102 value: &self.value + &other.value,
103 },
104 false => match self.value.cmp(&other.value) {
105 Ordering::Equal => BigInt::ZERO,
106 Ordering::Greater => BigInt {
107 sign: self.sign,
108 value: &self.value - &other.value,
109 },
110 Ordering::Less => BigInt {
111 sign: other.sign,
112 value: &other.value - &self.value,
113 },
114 },
115 }
116 }
117}
118
119impl Sub for BigInt {
120 type Output = BigInt;
121
122 fn sub(self, other: Self) -> Self::Output {
123 self.add(&-other)
124 }
125}
126
127impl Neg for BigInt {
128 type Output = BigInt;
129
130 fn neg(mut self) -> Self::Output {
131 if self.value.is_zero() {
132 return self;
133 }
134 self.sign = if self.sign == Sign::Positive {
135 Sign::Negative
136 } else {
137 Sign::Positive
138 };
139 self
140 }
141}
142
143impl PartialOrd for Sign {
144 fn partial_cmp(&self, other: &Self) -> Option<Ordering> {
145 Some(self.cmp(other))
146 }
147}
148
149impl Ord for Sign {
150 fn cmp(&self, other: &Self) -> Ordering {
151 (*self as i8).cmp(&(*other as i8))
152 }
153}
154
155impl PartialOrd for BigInt {
156 fn partial_cmp(&self, other: &Self) -> Option<Ordering> {
157 Some(self.cmp(other))
158 }
159}
160
161impl Ord for BigInt {
162 fn cmp(&self, other: &Self) -> Ordering {
163 if self.sign != other.sign {
164 return self.sign.cmp(&other.sign);
165 }
166
167 self.value.cmp(&other.value)
168 }
169}
170
171impl Mul for &BigInt {
172 type Output = BigInt;
173
174 fn mul(self, other: Self) -> Self::Output {
175 if self.is_zero() || other.is_zero() {
176 return BigInt::ZERO;
177 }
178 let value = &self.value * &other.value;
179 let sign = match self.sign == other.sign {
180 true => Sign::Positive,
181 false => Sign::Negative,
182 };
183 let mut result = BigInt { sign, value };
184 result.normalize();
185 result
186 }
187}
188
189impl Div for &BigInt {
190 type Output = BigInt;
191
192 fn div(self, d: Self) -> Self::Output {
193 if d.is_zero() {
194 panic!("attempt to divide by zero");
195 }
196
197 let sign = match self.sign == d.sign {
198 true => Sign::Positive,
199 false => Sign::Negative,
200 };
201
202 let value = &self.value / &d.value;
203 BigInt { sign, value }
204 }
205}
206
207#[cfg(test)]
208mod test {
209 use std::cmp::Ordering;
210
211 use wasm_bindgen_test::wasm_bindgen_test;
212
213 use crate::{big_numbers::big_uint::BigUint, common::cast::Cast};
214
215 use super::{BigInt, Sign};
216
217 #[test]
218 #[wasm_bindgen_test]
219 fn test_ord() {
220 let a = BigInt::from_u64(1);
221 let b = BigInt::from_u64(1);
222 assert_eq!(a.cmp(&b), Ordering::Equal);
223
224 let a = BigInt::from_u64(1);
225 let b = BigInt::from_u64(2);
226 assert_eq!(a.cmp(&b), Ordering::Less);
227
228 let a = BigInt::from_u64(1);
229 let b = BigInt::from_i64(-2);
230 assert_eq!(a.cmp(&b), Ordering::Greater);
231
232 let a = BigInt {
233 sign: Sign::Positive,
234 value: BigUint {
235 value: [1, 2].cast(),
236 },
237 };
238 let b = BigInt {
239 sign: Sign::Positive,
240 value: BigUint {
241 value: [2, 1].cast(),
242 },
243 };
244 assert_eq!(a.cmp(&b), Ordering::Greater);
245 }
246
247 #[test]
248 #[wasm_bindgen_test]
249 fn test_add_same_sign() {
250 let a = BigInt::from_u64(1);
251 let b = BigInt::from_u64(2);
252 let result = &a + &b;
253 assert_eq!(&result, &BigInt::from_u64(3));
254
255 let a = BigInt::from_i64(-1);
256 let b = BigInt::from_i64(-2);
257 let result = &a + &b;
258 assert_eq!(&result, &BigInt::from_i64(-3));
259
260 let a = BigInt::from_u64(1);
261 let b = BigInt {
262 sign: Sign::Positive,
263 value: BigUint {
264 value: [2, 4].cast(),
265 },
266 };
267 let result = &a + &b;
268 assert_eq!(
269 &result,
270 &BigInt {
271 sign: Sign::Positive,
272 value: BigUint {
273 value: [3, 4].cast()
274 }
275 }
276 );
277
278 let a = BigInt::from_u64(1 << 63);
279 let b = BigInt::from_u64(1 << 63);
280 let result = &a + &b;
281 assert_eq!(
282 &result,
283 &BigInt {
284 sign: Sign::Positive,
285 value: BigUint {
286 value: [0, 1].cast()
287 }
288 }
289 );
290 }
291
292 #[test]
293 #[wasm_bindgen_test]
294 fn test_add_different_sign() {
295 let a = BigInt::from_u64(1 << 63);
296 let b = BigInt {
297 sign: Sign::Negative,
298 value: BigUint {
299 value: [1 << 63].cast(),
300 },
301 };
302 let result = &a + &b;
303 assert_eq!(&result, &BigInt::ZERO);
304
305 let a = BigInt::from_u64(3);
306 let b = BigInt::from_i64(-2);
307 let result = &a + &b;
308 assert_eq!(&result, &BigInt::from_u64(1));
309 let result = &b + &a;
310 assert_eq!(&result, &BigInt::from_u64(1));
311
312 let a = BigInt {
313 sign: Sign::Positive,
314 value: BigUint {
315 value: [0, 1].cast(),
316 },
317 };
318 let b = BigInt::from_i64(-1);
319 let result = &a + &b;
320 assert_eq!(&result, &BigInt::from_u64(u64::MAX));
321 }
322
323 #[test]
324 #[wasm_bindgen_test]
325 fn test_add_overflow() {
326 let a = BigInt {
327 sign: Sign::Positive,
328 value: BigUint {
329 value: [u64::MAX, 0, 1].cast(),
330 },
331 };
332 let b = BigInt {
333 sign: Sign::Positive,
334 value: BigUint {
335 value: [u64::MAX, u64::MAX].cast(),
336 },
337 };
338 let result = &a + &b;
339 assert_eq!(
340 &result,
341 &BigInt {
342 sign: Sign::Positive,
343 value: BigUint {
344 value: [u64::MAX - 1, 0, 2].cast()
345 }
346 }
347 );
348 let result = &b + &a;
349 assert_eq!(
350 &result,
351 &BigInt {
352 sign: Sign::Positive,
353 value: BigUint {
354 value: [u64::MAX - 1, 0, 2].cast()
355 }
356 }
357 );
358 }
359
360 #[test]
361 #[wasm_bindgen_test]
362 fn test_sub_same_sign() {
363 let a = BigInt::from_u64(1 << 63);
364 let b = BigInt::from_u64(1 << 63);
365 let result = a - b;
366 assert_eq!(&result, &BigInt::ZERO);
367
368 let a = BigInt::from_u64(3);
369 let b = BigInt::from_u64(2);
370 let result = a.clone() - b.clone();
371 assert_eq!(&result, &BigInt::from_u64(1));
372 let result = b - a;
373 assert_eq!(&result, &BigInt::from_i64(-1));
374
375 let a = BigInt {
376 sign: Sign::Positive,
377 value: BigUint {
378 value: [0, 1].cast(),
379 },
380 };
381 let b = BigInt::from_u64(1);
382 let result = a - b;
383 assert_eq!(&result, &BigInt::from_u64(u64::MAX));
384 }
385
386 #[test]
387 #[wasm_bindgen_test]
388 fn test_sub_different_sign() {
389 let a = BigInt::from_u64(1);
390 let b = BigInt::from_i64(-2);
391 let result = a - b;
392 assert_eq!(&result, &BigInt::from_u64(3));
393
394 let a = BigInt::from_i64(-1);
395 let b = BigInt::from_u64(2);
396 let result = a - b;
397 assert_eq!(&result, &BigInt::from_i64(-3));
398
399 let a = BigInt::from_u64(1);
400 let b = BigInt {
401 sign: Sign::Negative,
402 value: BigUint {
403 value: [2, 4].cast(),
404 },
405 };
406 let result = a - b;
407 assert_eq!(
408 &result,
409 &BigInt {
410 sign: Sign::Positive,
411 value: BigUint {
412 value: [3, 4].cast()
413 }
414 }
415 );
416
417 let a = BigInt::from_u64(1 << 63);
418 let b = BigInt {
419 sign: Sign::Negative,
420 value: BigUint {
421 value: [1 << 63].cast(),
422 },
423 };
424 let result = a - b;
425 assert_eq!(
426 &result,
427 &BigInt {
428 sign: Sign::Positive,
429 value: BigUint {
430 value: [0, 1].cast()
431 }
432 }
433 );
434 }
435
436 #[test]
437 #[wasm_bindgen_test]
438 fn test_mul() {
439 let a = BigInt::from_u64(1);
440 let result = &a * &BigInt::ZERO;
441 assert_eq!(&result, &BigInt::ZERO);
442 let result = &BigInt::ZERO * &a;
443 assert_eq!(&result, &BigInt::ZERO);
444
445 let a = BigInt::from_i64(-1);
446 let result = &a * &BigInt::ZERO;
447 assert_eq!(&result, &BigInt::ZERO);
448 let result = &BigInt::ZERO * &a;
449 assert_eq!(&result, &BigInt::ZERO);
450
451 let a = BigInt::from_i64(-1);
452 let b = BigInt::from_i64(-1);
453 let result = &a * &b;
454 assert_eq!(&result, &BigInt::from_u64(1));
455
456 let a = BigInt {
457 sign: Sign::Negative,
458 value: BigUint {
459 value: [1, 2, 3, 4].cast(),
460 },
461 };
462 let b = BigInt {
463 sign: Sign::Negative,
464 value: BigUint {
465 value: [5, 6, 7].cast(),
466 },
467 };
468 let result = &a * &b;
469 assert_eq!(
470 &result,
471 &BigInt {
472 sign: Sign::Positive,
473 value: BigUint {
474 value: [5, 16, 34, 52, 45, 28].cast()
475 }
476 },
477 );
478 let result = &b * &a;
479 assert_eq!(
480 &result,
481 &BigInt {
482 sign: Sign::Positive,
483 value: BigUint {
484 value: [5, 16, 34, 52, 45, 28].cast()
485 }
486 },
487 );
488
489 let a = BigInt {
490 sign: Sign::Negative,
491 value: BigUint {
492 value: [u64::MAX].cast(),
493 },
494 };
495 let b = BigInt {
496 sign: Sign::Negative,
497 value: BigUint {
498 value: [u64::MAX].cast(),
499 },
500 };
501 let result = &a * &b;
502 assert_eq!(
503 &result,
504 &BigInt {
505 sign: Sign::Positive,
506 value: BigUint {
507 value: [1, u64::MAX - 1].cast()
508 }
509 },
510 );
511 let result = &b * &a;
512 assert_eq!(
513 &result,
514 &BigInt {
515 sign: Sign::Positive,
516 value: BigUint {
517 value: [1, u64::MAX - 1].cast()
518 }
519 },
520 );
521
522 let a = BigInt {
523 sign: Sign::Negative,
524 value: BigUint {
525 value: [u64::MAX, u64::MAX, u64::MAX].cast(),
526 },
527 };
528 let b = BigInt {
529 sign: Sign::Negative,
530 value: BigUint {
531 value: [u64::MAX].cast(),
532 },
533 };
534 let result = &a * &b;
535 assert_eq!(
536 &result,
537 &BigInt {
538 sign: Sign::Positive,
539 value: BigUint {
540 value: [1, u64::MAX, u64::MAX, u64::MAX - 1].cast()
541 }
542 },
543 );
544 let result = &b * &a;
545 assert_eq!(
546 &result,
547 &BigInt {
548 sign: Sign::Positive,
549 value: BigUint {
550 value: [1, u64::MAX, u64::MAX, u64::MAX - 1].cast()
551 }
552 },
553 );
554 }
555
556 #[test]
557 #[should_panic(expected = "attempt to divide by zero")]
558 #[wasm_bindgen_test]
559 fn test_div_by_zero() {
560 let a = BigInt::from_u64(1);
561 let _result = &a / &BigInt::ZERO;
562 }
563
564 #[test]
565 #[should_panic(expected = "attempt to divide by zero")]
566 #[wasm_bindgen_test]
567 fn test_div_zero_by_zero() {
568 let _result = &BigInt::ZERO / &BigInt::ZERO;
569 }
570
571 #[test]
572 #[wasm_bindgen_test]
573 fn test_div_simple() {
574 let a = BigInt::from_u64(2);
575 let b = BigInt::from_u64(7);
576 let result = &a / &b;
577 assert_eq!(&result, &BigInt::ZERO);
578
579 let a = BigInt::from_u64(7);
580 let result = &a / &a;
581 assert_eq!(&result, &BigInt::from_u64(1));
582
583 let a = BigInt::from_u64(7);
584 let b = BigInt::from_u64(2);
585 let result = &a / &b;
586 assert_eq!(&result, &BigInt::from_u64(3));
587
588 let a = BigInt {
589 sign: Sign::Positive,
590 value: BigUint {
591 value: [6, 8].cast(),
592 },
593 };
594 let b = BigInt::from_u64(2);
595 let result = &a / &b;
596 assert_eq!(
597 &result,
598 &BigInt {
599 sign: Sign::Positive,
600 value: BigUint {
601 value: [3, 4].cast()
602 }
603 }
604 );
605
606 let a = BigInt {
607 sign: Sign::Positive,
608 value: BigUint {
609 value: [4, 7].cast(),
610 },
611 };
612 let b = BigInt::from_u64(2);
613 let result = &a / &b;
614 assert_eq!(
615 &result,
616 &BigInt {
617 sign: Sign::Positive,
618 value: BigUint {
619 value: [(1 << 63) + 2, 3].cast()
620 }
621 }
622 );
623 }
624
625 #[test]
626 #[wasm_bindgen_test]
627 fn test_div_mod() {
628 let a = BigInt::from_i64(7);
629 let b = BigInt::from_i64(2);
630 let result = a.div_mod(&b);
631 assert_eq!(result, (BigInt::from_i64(3), BigInt::from_i64(1)));
632
633 let a = BigInt::from_i64(-7);
634 let b = BigInt::from_i64(2);
635 let result = a.div_mod(&b);
636 assert_eq!(result, (BigInt::from_i64(-3), BigInt::from_i64(-1)));
637 }
638}