1// `Add`/`Sub` ops may flip from `BigInt` to its `BigUint` magnitude
2#![allow(clippy::suspicious_arithmetic_impl)]
3
4use alloc::string::String;
5use alloc::vec::Vec;
6use core::cmp::Ordering::{self, Equal};
7use core::default::Default;
8use core::fmt;
9use core::hash;
10use core::ops::{Neg, Not};
11use core::str;
12
13use num_integer::{Integer, Roots};
14use num_traits::{ConstZero, Num, One, Pow, Signed, Zero};
15
16use self::Sign::{Minus, NoSign, Plus};
17
18use crate::big_digit::BigDigit;
19use crate::biguint::to_str_radix_reversed;
20use crate::biguint::{BigUint, IntDigits, U32Digits, U64Digits};
21
22mod addition;
23mod division;
24mod multiplication;
25mod subtraction;
26
27mod arbitrary;
28mod bits;
29mod convert;
30mod power;
31mod serde;
32mod shift;
33
34/// A `Sign` is a [`BigInt`]'s composing element.
35#[derive(PartialEq, PartialOrd, Eq, Ord, Copy, Clone, Debug, Hash)]
36pub enum Sign {
37 Minus,
38 NoSign,
39 Plus,
40}
41
42impl Neg for Sign {
43 type Output = Sign;
44
45 /// Negate `Sign` value.
46 #[inline]
47 fn neg(self) -> Sign {
48 match self {
49 Minus => Plus,
50 NoSign => NoSign,
51 Plus => Minus,
52 }
53 }
54}
55
56/// A big signed integer type.
57pub struct BigInt {
58 sign: Sign,
59 data: BigUint,
60}
61
62// Note: derived `Clone` doesn't specialize `clone_from`,
63// but we want to keep the allocation in `data`.
64impl Clone for BigInt {
65 #[inline]
66 fn clone(&self) -> Self {
67 BigInt {
68 sign: self.sign,
69 data: self.data.clone(),
70 }
71 }
72
73 #[inline]
74 fn clone_from(&mut self, other: &Self) {
75 self.sign = other.sign;
76 self.data.clone_from(&other.data);
77 }
78}
79
80impl hash::Hash for BigInt {
81 #[inline]
82 fn hash<H: hash::Hasher>(&self, state: &mut H) {
83 debug_assert!((self.sign != NoSign) ^ self.data.is_zero());
84 self.sign.hash(state);
85 if self.sign != NoSign {
86 self.data.hash(state);
87 }
88 }
89}
90
91impl PartialEq for BigInt {
92 #[inline]
93 fn eq(&self, other: &BigInt) -> bool {
94 debug_assert!((self.sign != NoSign) ^ self.data.is_zero());
95 debug_assert!((other.sign != NoSign) ^ other.data.is_zero());
96 self.sign == other.sign && (self.sign == NoSign || self.data == other.data)
97 }
98}
99
100impl Eq for BigInt {}
101
102impl PartialOrd for BigInt {
103 #[inline]
104 fn partial_cmp(&self, other: &BigInt) -> Option<Ordering> {
105 Some(self.cmp(other))
106 }
107}
108
109impl Ord for BigInt {
110 #[inline]
111 fn cmp(&self, other: &BigInt) -> Ordering {
112 debug_assert!((self.sign != NoSign) ^ self.data.is_zero());
113 debug_assert!((other.sign != NoSign) ^ other.data.is_zero());
114 let scmp: Ordering = self.sign.cmp(&other.sign);
115 if scmp != Equal {
116 return scmp;
117 }
118
119 match self.sign {
120 NoSign => Equal,
121 Plus => self.data.cmp(&other.data),
122 Minus => other.data.cmp(&self.data),
123 }
124 }
125}
126
127impl Default for BigInt {
128 #[inline]
129 fn default() -> BigInt {
130 Self::ZERO
131 }
132}
133
134impl fmt::Debug for BigInt {
135 fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
136 fmt::Display::fmt(self, f)
137 }
138}
139
140impl fmt::Display for BigInt {
141 fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
142 f.pad_integral(!self.is_negative(), prefix:"", &self.data.to_str_radix(10))
143 }
144}
145
146impl fmt::Binary for BigInt {
147 fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
148 f.pad_integral(!self.is_negative(), prefix:"0b", &self.data.to_str_radix(2))
149 }
150}
151
152impl fmt::Octal for BigInt {
153 fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
154 f.pad_integral(!self.is_negative(), prefix:"0o", &self.data.to_str_radix(8))
155 }
156}
157
158impl fmt::LowerHex for BigInt {
159 fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
160 f.pad_integral(!self.is_negative(), prefix:"0x", &self.data.to_str_radix(16))
161 }
162}
163
164impl fmt::UpperHex for BigInt {
165 fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
166 let mut s: String = self.data.to_str_radix(16);
167 s.make_ascii_uppercase();
168 f.pad_integral(!self.is_negative(), prefix:"0x", &s)
169 }
170}
171
172// !-2 = !...f fe = ...0 01 = +1
173// !-1 = !...f ff = ...0 00 = 0
174// ! 0 = !...0 00 = ...f ff = -1
175// !+1 = !...0 01 = ...f fe = -2
176impl Not for BigInt {
177 type Output = BigInt;
178
179 fn not(mut self) -> BigInt {
180 match self.sign {
181 NoSign | Plus => {
182 self.data += 1u32;
183 self.sign = Minus;
184 }
185 Minus => {
186 self.data -= 1u32;
187 self.sign = if self.data.is_zero() { NoSign } else { Plus };
188 }
189 }
190 self
191 }
192}
193
194impl Not for &BigInt {
195 type Output = BigInt;
196
197 fn not(self) -> BigInt {
198 match self.sign {
199 NoSign => -BigInt::one(),
200 Plus => -BigInt::from(&self.data + 1u32),
201 Minus => BigInt::from(&self.data - 1u32),
202 }
203 }
204}
205
206impl Zero for BigInt {
207 #[inline]
208 fn zero() -> BigInt {
209 Self::ZERO
210 }
211
212 #[inline]
213 fn set_zero(&mut self) {
214 self.data.set_zero();
215 self.sign = NoSign;
216 }
217
218 #[inline]
219 fn is_zero(&self) -> bool {
220 self.sign == NoSign
221 }
222}
223
224impl ConstZero for BigInt {
225 // forward to the inherent const
226 const ZERO: Self = Self::ZERO;
227}
228
229impl One for BigInt {
230 #[inline]
231 fn one() -> BigInt {
232 BigInt {
233 sign: Plus,
234 data: BigUint::one(),
235 }
236 }
237
238 #[inline]
239 fn set_one(&mut self) {
240 self.data.set_one();
241 self.sign = Plus;
242 }
243
244 #[inline]
245 fn is_one(&self) -> bool {
246 self.sign == Plus && self.data.is_one()
247 }
248}
249
250impl Signed for BigInt {
251 #[inline]
252 fn abs(&self) -> BigInt {
253 match self.sign {
254 Plus | NoSign => self.clone(),
255 Minus => BigInt::from(self.data.clone()),
256 }
257 }
258
259 #[inline]
260 fn abs_sub(&self, other: &BigInt) -> BigInt {
261 if *self <= *other {
262 Self::ZERO
263 } else {
264 self - other
265 }
266 }
267
268 #[inline]
269 fn signum(&self) -> BigInt {
270 match self.sign {
271 Plus => BigInt::one(),
272 Minus => -BigInt::one(),
273 NoSign => Self::ZERO,
274 }
275 }
276
277 #[inline]
278 fn is_positive(&self) -> bool {
279 self.sign == Plus
280 }
281
282 #[inline]
283 fn is_negative(&self) -> bool {
284 self.sign == Minus
285 }
286}
287
288trait UnsignedAbs {
289 type Unsigned;
290
291 fn checked_uabs(self) -> CheckedUnsignedAbs<Self::Unsigned>;
292}
293
294enum CheckedUnsignedAbs<T> {
295 Positive(T),
296 Negative(T),
297}
298use self::CheckedUnsignedAbs::{Negative, Positive};
299
300macro_rules! impl_unsigned_abs {
301 ($Signed:ty, $Unsigned:ty) => {
302 impl UnsignedAbs for $Signed {
303 type Unsigned = $Unsigned;
304
305 #[inline]
306 fn checked_uabs(self) -> CheckedUnsignedAbs<Self::Unsigned> {
307 if self >= 0 {
308 Positive(self as $Unsigned)
309 } else {
310 Negative(self.wrapping_neg() as $Unsigned)
311 }
312 }
313 }
314 };
315}
316impl_unsigned_abs!(i8, u8);
317impl_unsigned_abs!(i16, u16);
318impl_unsigned_abs!(i32, u32);
319impl_unsigned_abs!(i64, u64);
320impl_unsigned_abs!(i128, u128);
321impl_unsigned_abs!(isize, usize);
322
323impl Neg for BigInt {
324 type Output = BigInt;
325
326 #[inline]
327 fn neg(mut self) -> BigInt {
328 self.sign = -self.sign;
329 self
330 }
331}
332
333impl Neg for &BigInt {
334 type Output = BigInt;
335
336 #[inline]
337 fn neg(self) -> BigInt {
338 -self.clone()
339 }
340}
341
342impl Integer for BigInt {
343 #[inline]
344 fn div_rem(&self, other: &BigInt) -> (BigInt, BigInt) {
345 // r.sign == self.sign
346 let (d_ui, r_ui) = self.data.div_rem(&other.data);
347 let d = BigInt::from_biguint(self.sign, d_ui);
348 let r = BigInt::from_biguint(self.sign, r_ui);
349 if other.is_negative() {
350 (-d, r)
351 } else {
352 (d, r)
353 }
354 }
355
356 #[inline]
357 fn div_floor(&self, other: &BigInt) -> BigInt {
358 let (d_ui, m) = self.data.div_mod_floor(&other.data);
359 let d = BigInt::from(d_ui);
360 match (self.sign, other.sign) {
361 (Plus, Plus) | (NoSign, Plus) | (Minus, Minus) => d,
362 (Plus, Minus) | (NoSign, Minus) | (Minus, Plus) => {
363 if m.is_zero() {
364 -d
365 } else {
366 -d - 1u32
367 }
368 }
369 (_, NoSign) => unreachable!(),
370 }
371 }
372
373 #[inline]
374 fn mod_floor(&self, other: &BigInt) -> BigInt {
375 // m.sign == other.sign
376 let m_ui = self.data.mod_floor(&other.data);
377 let m = BigInt::from_biguint(other.sign, m_ui);
378 match (self.sign, other.sign) {
379 (Plus, Plus) | (NoSign, Plus) | (Minus, Minus) => m,
380 (Plus, Minus) | (NoSign, Minus) | (Minus, Plus) => {
381 if m.is_zero() {
382 m
383 } else {
384 other - m
385 }
386 }
387 (_, NoSign) => unreachable!(),
388 }
389 }
390
391 fn div_mod_floor(&self, other: &BigInt) -> (BigInt, BigInt) {
392 // m.sign == other.sign
393 let (d_ui, m_ui) = self.data.div_mod_floor(&other.data);
394 let d = BigInt::from(d_ui);
395 let m = BigInt::from_biguint(other.sign, m_ui);
396 match (self.sign, other.sign) {
397 (Plus, Plus) | (NoSign, Plus) | (Minus, Minus) => (d, m),
398 (Plus, Minus) | (NoSign, Minus) | (Minus, Plus) => {
399 if m.is_zero() {
400 (-d, m)
401 } else {
402 (-d - 1u32, other - m)
403 }
404 }
405 (_, NoSign) => unreachable!(),
406 }
407 }
408
409 #[inline]
410 fn div_ceil(&self, other: &Self) -> Self {
411 let (d_ui, m) = self.data.div_mod_floor(&other.data);
412 let d = BigInt::from(d_ui);
413 match (self.sign, other.sign) {
414 (Plus, Minus) | (NoSign, Minus) | (Minus, Plus) => -d,
415 (Plus, Plus) | (NoSign, Plus) | (Minus, Minus) => {
416 if m.is_zero() {
417 d
418 } else {
419 d + 1u32
420 }
421 }
422 (_, NoSign) => unreachable!(),
423 }
424 }
425
426 /// Calculates the Greatest Common Divisor (GCD) of the number and `other`.
427 ///
428 /// The result is always positive.
429 #[inline]
430 fn gcd(&self, other: &BigInt) -> BigInt {
431 BigInt::from(self.data.gcd(&other.data))
432 }
433
434 /// Calculates the Lowest Common Multiple (LCM) of the number and `other`.
435 #[inline]
436 fn lcm(&self, other: &BigInt) -> BigInt {
437 BigInt::from(self.data.lcm(&other.data))
438 }
439
440 /// Calculates the Greatest Common Divisor (GCD) and
441 /// Lowest Common Multiple (LCM) together.
442 #[inline]
443 fn gcd_lcm(&self, other: &BigInt) -> (BigInt, BigInt) {
444 let (gcd, lcm) = self.data.gcd_lcm(&other.data);
445 (BigInt::from(gcd), BigInt::from(lcm))
446 }
447
448 /// Greatest common divisor, least common multiple, and Bézout coefficients.
449 #[inline]
450 fn extended_gcd_lcm(&self, other: &BigInt) -> (num_integer::ExtendedGcd<BigInt>, BigInt) {
451 let egcd = self.extended_gcd(other);
452 let lcm = if egcd.gcd.is_zero() {
453 Self::ZERO
454 } else {
455 BigInt::from(&self.data / &egcd.gcd.data * &other.data)
456 };
457 (egcd, lcm)
458 }
459
460 /// Deprecated, use `is_multiple_of` instead.
461 #[inline]
462 fn divides(&self, other: &BigInt) -> bool {
463 self.is_multiple_of(other)
464 }
465
466 /// Returns `true` if the number is a multiple of `other`.
467 #[inline]
468 fn is_multiple_of(&self, other: &BigInt) -> bool {
469 self.data.is_multiple_of(&other.data)
470 }
471
472 /// Returns `true` if the number is divisible by `2`.
473 #[inline]
474 fn is_even(&self) -> bool {
475 self.data.is_even()
476 }
477
478 /// Returns `true` if the number is not divisible by `2`.
479 #[inline]
480 fn is_odd(&self) -> bool {
481 self.data.is_odd()
482 }
483
484 /// Rounds up to nearest multiple of argument.
485 #[inline]
486 fn next_multiple_of(&self, other: &Self) -> Self {
487 let m = self.mod_floor(other);
488 if m.is_zero() {
489 self.clone()
490 } else {
491 self + (other - m)
492 }
493 }
494 /// Rounds down to nearest multiple of argument.
495 #[inline]
496 fn prev_multiple_of(&self, other: &Self) -> Self {
497 self - self.mod_floor(other)
498 }
499
500 fn dec(&mut self) {
501 *self -= 1u32;
502 }
503
504 fn inc(&mut self) {
505 *self += 1u32;
506 }
507}
508
509impl Roots for BigInt {
510 fn nth_root(&self, n: u32) -> Self {
511 assert!(
512 !(self.is_negative() && n.is_even()),
513 "root of degree {} is imaginary",
514 n
515 );
516
517 BigInt::from_biguint(self.sign, self.data.nth_root(n))
518 }
519
520 fn sqrt(&self) -> Self {
521 assert!(!self.is_negative(), "square root is imaginary");
522
523 BigInt::from_biguint(self.sign, self.data.sqrt())
524 }
525
526 fn cbrt(&self) -> Self {
527 BigInt::from_biguint(self.sign, self.data.cbrt())
528 }
529}
530
531impl IntDigits for BigInt {
532 #[inline]
533 fn digits(&self) -> &[BigDigit] {
534 self.data.digits()
535 }
536 #[inline]
537 fn digits_mut(&mut self) -> &mut Vec<BigDigit> {
538 self.data.digits_mut()
539 }
540 #[inline]
541 fn normalize(&mut self) {
542 self.data.normalize();
543 if self.data.is_zero() {
544 self.sign = NoSign;
545 }
546 }
547 #[inline]
548 fn capacity(&self) -> usize {
549 self.data.capacity()
550 }
551 #[inline]
552 fn len(&self) -> usize {
553 self.data.len()
554 }
555}
556
557/// A generic trait for converting a value to a [`BigInt`]. This may return
558/// `None` when converting from `f32` or `f64`, and will always succeed
559/// when converting from any integer or unsigned primitive, or [`BigUint`].
560pub trait ToBigInt {
561 /// Converts the value of `self` to a [`BigInt`].
562 fn to_bigint(&self) -> Option<BigInt>;
563}
564
565impl BigInt {
566 /// A constant `BigInt` with value 0, useful for static initialization.
567 pub const ZERO: Self = BigInt {
568 sign: NoSign,
569 data: BigUint::ZERO,
570 };
571
572 /// Creates and initializes a [`BigInt`].
573 ///
574 /// The base 2<sup>32</sup> digits are ordered least significant digit first.
575 #[inline]
576 pub fn new(sign: Sign, digits: Vec<u32>) -> BigInt {
577 BigInt::from_biguint(sign, BigUint::new(digits))
578 }
579
580 /// Creates and initializes a [`BigInt`].
581 ///
582 /// The base 2<sup>32</sup> digits are ordered least significant digit first.
583 #[inline]
584 pub fn from_biguint(mut sign: Sign, mut data: BigUint) -> BigInt {
585 if sign == NoSign {
586 data.assign_from_slice(&[]);
587 } else if data.is_zero() {
588 sign = NoSign;
589 }
590
591 BigInt { sign, data }
592 }
593
594 /// Creates and initializes a [`BigInt`].
595 ///
596 /// The base 2<sup>32</sup> digits are ordered least significant digit first.
597 #[inline]
598 pub fn from_slice(sign: Sign, slice: &[u32]) -> BigInt {
599 BigInt::from_biguint(sign, BigUint::from_slice(slice))
600 }
601
602 /// Reinitializes a [`BigInt`].
603 ///
604 /// The base 2<sup>32</sup> digits are ordered least significant digit first.
605 #[inline]
606 pub fn assign_from_slice(&mut self, sign: Sign, slice: &[u32]) {
607 if sign == NoSign {
608 self.set_zero();
609 } else {
610 self.data.assign_from_slice(slice);
611 self.sign = if self.data.is_zero() { NoSign } else { sign };
612 }
613 }
614
615 /// Creates and initializes a [`BigInt`].
616 ///
617 /// The bytes are in big-endian byte order.
618 ///
619 /// # Examples
620 ///
621 /// ```
622 /// use num_bigint::{BigInt, Sign};
623 ///
624 /// assert_eq!(BigInt::from_bytes_be(Sign::Plus, b"A"),
625 /// BigInt::parse_bytes(b"65", 10).unwrap());
626 /// assert_eq!(BigInt::from_bytes_be(Sign::Plus, b"AA"),
627 /// BigInt::parse_bytes(b"16705", 10).unwrap());
628 /// assert_eq!(BigInt::from_bytes_be(Sign::Plus, b"AB"),
629 /// BigInt::parse_bytes(b"16706", 10).unwrap());
630 /// assert_eq!(BigInt::from_bytes_be(Sign::Plus, b"Hello world!"),
631 /// BigInt::parse_bytes(b"22405534230753963835153736737", 10).unwrap());
632 /// ```
633 #[inline]
634 pub fn from_bytes_be(sign: Sign, bytes: &[u8]) -> BigInt {
635 BigInt::from_biguint(sign, BigUint::from_bytes_be(bytes))
636 }
637
638 /// Creates and initializes a [`BigInt`].
639 ///
640 /// The bytes are in little-endian byte order.
641 #[inline]
642 pub fn from_bytes_le(sign: Sign, bytes: &[u8]) -> BigInt {
643 BigInt::from_biguint(sign, BigUint::from_bytes_le(bytes))
644 }
645
646 /// Creates and initializes a [`BigInt`] from an array of bytes in
647 /// two's complement binary representation.
648 ///
649 /// The digits are in big-endian base 2<sup>8</sup>.
650 #[inline]
651 pub fn from_signed_bytes_be(digits: &[u8]) -> BigInt {
652 convert::from_signed_bytes_be(digits)
653 }
654
655 /// Creates and initializes a [`BigInt`] from an array of bytes in two's complement.
656 ///
657 /// The digits are in little-endian base 2<sup>8</sup>.
658 #[inline]
659 pub fn from_signed_bytes_le(digits: &[u8]) -> BigInt {
660 convert::from_signed_bytes_le(digits)
661 }
662
663 /// Creates and initializes a [`BigInt`].
664 ///
665 /// # Examples
666 ///
667 /// ```
668 /// use num_bigint::{BigInt, ToBigInt};
669 ///
670 /// assert_eq!(BigInt::parse_bytes(b"1234", 10), ToBigInt::to_bigint(&1234));
671 /// assert_eq!(BigInt::parse_bytes(b"ABCD", 16), ToBigInt::to_bigint(&0xABCD));
672 /// assert_eq!(BigInt::parse_bytes(b"G", 16), None);
673 /// ```
674 #[inline]
675 pub fn parse_bytes(buf: &[u8], radix: u32) -> Option<BigInt> {
676 let s = str::from_utf8(buf).ok()?;
677 BigInt::from_str_radix(s, radix).ok()
678 }
679
680 /// Creates and initializes a [`BigInt`]. Each `u8` of the input slice is
681 /// interpreted as one digit of the number
682 /// and must therefore be less than `radix`.
683 ///
684 /// The bytes are in big-endian byte order.
685 /// `radix` must be in the range `2...256`.
686 ///
687 /// # Examples
688 ///
689 /// ```
690 /// use num_bigint::{BigInt, Sign};
691 ///
692 /// let inbase190 = vec![15, 33, 125, 12, 14];
693 /// let a = BigInt::from_radix_be(Sign::Minus, &inbase190, 190).unwrap();
694 /// assert_eq!(a.to_radix_be(190), (Sign:: Minus, inbase190));
695 /// ```
696 pub fn from_radix_be(sign: Sign, buf: &[u8], radix: u32) -> Option<BigInt> {
697 let u = BigUint::from_radix_be(buf, radix)?;
698 Some(BigInt::from_biguint(sign, u))
699 }
700
701 /// Creates and initializes a [`BigInt`]. Each `u8` of the input slice is
702 /// interpreted as one digit of the number
703 /// and must therefore be less than `radix`.
704 ///
705 /// The bytes are in little-endian byte order.
706 /// `radix` must be in the range `2...256`.
707 ///
708 /// # Examples
709 ///
710 /// ```
711 /// use num_bigint::{BigInt, Sign};
712 ///
713 /// let inbase190 = vec![14, 12, 125, 33, 15];
714 /// let a = BigInt::from_radix_be(Sign::Minus, &inbase190, 190).unwrap();
715 /// assert_eq!(a.to_radix_be(190), (Sign::Minus, inbase190));
716 /// ```
717 pub fn from_radix_le(sign: Sign, buf: &[u8], radix: u32) -> Option<BigInt> {
718 let u = BigUint::from_radix_le(buf, radix)?;
719 Some(BigInt::from_biguint(sign, u))
720 }
721
722 /// Returns the sign and the byte representation of the [`BigInt`] in big-endian byte order.
723 ///
724 /// # Examples
725 ///
726 /// ```
727 /// use num_bigint::{ToBigInt, Sign};
728 ///
729 /// let i = -1125.to_bigint().unwrap();
730 /// assert_eq!(i.to_bytes_be(), (Sign::Minus, vec![4, 101]));
731 /// ```
732 #[inline]
733 pub fn to_bytes_be(&self) -> (Sign, Vec<u8>) {
734 (self.sign, self.data.to_bytes_be())
735 }
736
737 /// Returns the sign and the byte representation of the [`BigInt`] in little-endian byte order.
738 ///
739 /// # Examples
740 ///
741 /// ```
742 /// use num_bigint::{ToBigInt, Sign};
743 ///
744 /// let i = -1125.to_bigint().unwrap();
745 /// assert_eq!(i.to_bytes_le(), (Sign::Minus, vec![101, 4]));
746 /// ```
747 #[inline]
748 pub fn to_bytes_le(&self) -> (Sign, Vec<u8>) {
749 (self.sign, self.data.to_bytes_le())
750 }
751
752 /// Returns the sign and the `u32` digits representation of the [`BigInt`] ordered least
753 /// significant digit first.
754 ///
755 /// # Examples
756 ///
757 /// ```
758 /// use num_bigint::{BigInt, Sign};
759 ///
760 /// assert_eq!(BigInt::from(-1125).to_u32_digits(), (Sign::Minus, vec![1125]));
761 /// assert_eq!(BigInt::from(4294967295u32).to_u32_digits(), (Sign::Plus, vec![4294967295]));
762 /// assert_eq!(BigInt::from(4294967296u64).to_u32_digits(), (Sign::Plus, vec![0, 1]));
763 /// assert_eq!(BigInt::from(-112500000000i64).to_u32_digits(), (Sign::Minus, vec![830850304, 26]));
764 /// assert_eq!(BigInt::from(112500000000i64).to_u32_digits(), (Sign::Plus, vec![830850304, 26]));
765 /// ```
766 #[inline]
767 pub fn to_u32_digits(&self) -> (Sign, Vec<u32>) {
768 (self.sign, self.data.to_u32_digits())
769 }
770
771 /// Returns the sign and the `u64` digits representation of the [`BigInt`] ordered least
772 /// significant digit first.
773 ///
774 /// # Examples
775 ///
776 /// ```
777 /// use num_bigint::{BigInt, Sign};
778 ///
779 /// assert_eq!(BigInt::from(-1125).to_u64_digits(), (Sign::Minus, vec![1125]));
780 /// assert_eq!(BigInt::from(4294967295u32).to_u64_digits(), (Sign::Plus, vec![4294967295]));
781 /// assert_eq!(BigInt::from(4294967296u64).to_u64_digits(), (Sign::Plus, vec![4294967296]));
782 /// assert_eq!(BigInt::from(-112500000000i64).to_u64_digits(), (Sign::Minus, vec![112500000000]));
783 /// assert_eq!(BigInt::from(112500000000i64).to_u64_digits(), (Sign::Plus, vec![112500000000]));
784 /// assert_eq!(BigInt::from(1u128 << 64).to_u64_digits(), (Sign::Plus, vec![0, 1]));
785 /// ```
786 #[inline]
787 pub fn to_u64_digits(&self) -> (Sign, Vec<u64>) {
788 (self.sign, self.data.to_u64_digits())
789 }
790
791 /// Returns an iterator of `u32` digits representation of the [`BigInt`] ordered least
792 /// significant digit first.
793 ///
794 /// # Examples
795 ///
796 /// ```
797 /// use num_bigint::BigInt;
798 ///
799 /// assert_eq!(BigInt::from(-1125).iter_u32_digits().collect::<Vec<u32>>(), vec![1125]);
800 /// assert_eq!(BigInt::from(4294967295u32).iter_u32_digits().collect::<Vec<u32>>(), vec![4294967295]);
801 /// assert_eq!(BigInt::from(4294967296u64).iter_u32_digits().collect::<Vec<u32>>(), vec![0, 1]);
802 /// assert_eq!(BigInt::from(-112500000000i64).iter_u32_digits().collect::<Vec<u32>>(), vec![830850304, 26]);
803 /// assert_eq!(BigInt::from(112500000000i64).iter_u32_digits().collect::<Vec<u32>>(), vec![830850304, 26]);
804 /// ```
805 #[inline]
806 pub fn iter_u32_digits(&self) -> U32Digits<'_> {
807 self.data.iter_u32_digits()
808 }
809
810 /// Returns an iterator of `u64` digits representation of the [`BigInt`] ordered least
811 /// significant digit first.
812 ///
813 /// # Examples
814 ///
815 /// ```
816 /// use num_bigint::BigInt;
817 ///
818 /// assert_eq!(BigInt::from(-1125).iter_u64_digits().collect::<Vec<u64>>(), vec![1125u64]);
819 /// assert_eq!(BigInt::from(4294967295u32).iter_u64_digits().collect::<Vec<u64>>(), vec![4294967295u64]);
820 /// assert_eq!(BigInt::from(4294967296u64).iter_u64_digits().collect::<Vec<u64>>(), vec![4294967296u64]);
821 /// assert_eq!(BigInt::from(-112500000000i64).iter_u64_digits().collect::<Vec<u64>>(), vec![112500000000u64]);
822 /// assert_eq!(BigInt::from(112500000000i64).iter_u64_digits().collect::<Vec<u64>>(), vec![112500000000u64]);
823 /// assert_eq!(BigInt::from(1u128 << 64).iter_u64_digits().collect::<Vec<u64>>(), vec![0, 1]);
824 /// ```
825 #[inline]
826 pub fn iter_u64_digits(&self) -> U64Digits<'_> {
827 self.data.iter_u64_digits()
828 }
829
830 /// Returns the two's-complement byte representation of the [`BigInt`] in big-endian byte order.
831 ///
832 /// # Examples
833 ///
834 /// ```
835 /// use num_bigint::ToBigInt;
836 ///
837 /// let i = -1125.to_bigint().unwrap();
838 /// assert_eq!(i.to_signed_bytes_be(), vec![251, 155]);
839 /// ```
840 #[inline]
841 pub fn to_signed_bytes_be(&self) -> Vec<u8> {
842 convert::to_signed_bytes_be(self)
843 }
844
845 /// Returns the two's-complement byte representation of the [`BigInt`] in little-endian byte order.
846 ///
847 /// # Examples
848 ///
849 /// ```
850 /// use num_bigint::ToBigInt;
851 ///
852 /// let i = -1125.to_bigint().unwrap();
853 /// assert_eq!(i.to_signed_bytes_le(), vec![155, 251]);
854 /// ```
855 #[inline]
856 pub fn to_signed_bytes_le(&self) -> Vec<u8> {
857 convert::to_signed_bytes_le(self)
858 }
859
860 /// Returns the integer formatted as a string in the given radix.
861 /// `radix` must be in the range `2...36`.
862 ///
863 /// # Examples
864 ///
865 /// ```
866 /// use num_bigint::BigInt;
867 ///
868 /// let i = BigInt::parse_bytes(b"ff", 16).unwrap();
869 /// assert_eq!(i.to_str_radix(16), "ff");
870 /// ```
871 #[inline]
872 pub fn to_str_radix(&self, radix: u32) -> String {
873 let mut v = to_str_radix_reversed(&self.data, radix);
874
875 if self.is_negative() {
876 v.push(b'-');
877 }
878
879 v.reverse();
880 unsafe { String::from_utf8_unchecked(v) }
881 }
882
883 /// Returns the integer in the requested base in big-endian digit order.
884 /// The output is not given in a human readable alphabet but as a zero
885 /// based `u8` number.
886 /// `radix` must be in the range `2...256`.
887 ///
888 /// # Examples
889 ///
890 /// ```
891 /// use num_bigint::{BigInt, Sign};
892 ///
893 /// assert_eq!(BigInt::from(-0xFFFFi64).to_radix_be(159),
894 /// (Sign::Minus, vec![2, 94, 27]));
895 /// // 0xFFFF = 65535 = 2*(159^2) + 94*159 + 27
896 /// ```
897 #[inline]
898 pub fn to_radix_be(&self, radix: u32) -> (Sign, Vec<u8>) {
899 (self.sign, self.data.to_radix_be(radix))
900 }
901
902 /// Returns the integer in the requested base in little-endian digit order.
903 /// The output is not given in a human readable alphabet but as a zero
904 /// based `u8` number.
905 /// `radix` must be in the range `2...256`.
906 ///
907 /// # Examples
908 ///
909 /// ```
910 /// use num_bigint::{BigInt, Sign};
911 ///
912 /// assert_eq!(BigInt::from(-0xFFFFi64).to_radix_le(159),
913 /// (Sign::Minus, vec![27, 94, 2]));
914 /// // 0xFFFF = 65535 = 27 + 94*159 + 2*(159^2)
915 /// ```
916 #[inline]
917 pub fn to_radix_le(&self, radix: u32) -> (Sign, Vec<u8>) {
918 (self.sign, self.data.to_radix_le(radix))
919 }
920
921 /// Returns the sign of the [`BigInt`] as a [`Sign`].
922 ///
923 /// # Examples
924 ///
925 /// ```
926 /// use num_bigint::{BigInt, Sign};
927 ///
928 /// assert_eq!(BigInt::from(1234).sign(), Sign::Plus);
929 /// assert_eq!(BigInt::from(-4321).sign(), Sign::Minus);
930 /// assert_eq!(BigInt::ZERO.sign(), Sign::NoSign);
931 /// ```
932 #[inline]
933 pub fn sign(&self) -> Sign {
934 self.sign
935 }
936
937 /// Returns the magnitude of the [`BigInt`] as a [`BigUint`].
938 ///
939 /// # Examples
940 ///
941 /// ```
942 /// use num_bigint::{BigInt, BigUint};
943 /// use num_traits::Zero;
944 ///
945 /// assert_eq!(BigInt::from(1234).magnitude(), &BigUint::from(1234u32));
946 /// assert_eq!(BigInt::from(-4321).magnitude(), &BigUint::from(4321u32));
947 /// assert!(BigInt::ZERO.magnitude().is_zero());
948 /// ```
949 #[inline]
950 pub fn magnitude(&self) -> &BigUint {
951 &self.data
952 }
953
954 /// Convert this [`BigInt`] into its [`Sign`] and [`BigUint`] magnitude,
955 /// the reverse of [`BigInt::from_biguint()`].
956 ///
957 /// # Examples
958 ///
959 /// ```
960 /// use num_bigint::{BigInt, BigUint, Sign};
961 ///
962 /// assert_eq!(BigInt::from(1234).into_parts(), (Sign::Plus, BigUint::from(1234u32)));
963 /// assert_eq!(BigInt::from(-4321).into_parts(), (Sign::Minus, BigUint::from(4321u32)));
964 /// assert_eq!(BigInt::ZERO.into_parts(), (Sign::NoSign, BigUint::ZERO));
965 /// ```
966 #[inline]
967 pub fn into_parts(self) -> (Sign, BigUint) {
968 (self.sign, self.data)
969 }
970
971 /// Determines the fewest bits necessary to express the [`BigInt`],
972 /// not including the sign.
973 #[inline]
974 pub fn bits(&self) -> u64 {
975 self.data.bits()
976 }
977
978 /// Converts this [`BigInt`] into a [`BigUint`], if it's not negative.
979 #[inline]
980 pub fn to_biguint(&self) -> Option<BigUint> {
981 match self.sign {
982 Plus => Some(self.data.clone()),
983 NoSign => Some(BigUint::ZERO),
984 Minus => None,
985 }
986 }
987
988 #[inline]
989 pub fn checked_add(&self, v: &BigInt) -> Option<BigInt> {
990 Some(self + v)
991 }
992
993 #[inline]
994 pub fn checked_sub(&self, v: &BigInt) -> Option<BigInt> {
995 Some(self - v)
996 }
997
998 #[inline]
999 pub fn checked_mul(&self, v: &BigInt) -> Option<BigInt> {
1000 Some(self * v)
1001 }
1002
1003 #[inline]
1004 pub fn checked_div(&self, v: &BigInt) -> Option<BigInt> {
1005 if v.is_zero() {
1006 return None;
1007 }
1008 Some(self / v)
1009 }
1010
1011 /// Returns `self ^ exponent`.
1012 pub fn pow(&self, exponent: u32) -> Self {
1013 Pow::pow(self, exponent)
1014 }
1015
1016 /// Returns `(self ^ exponent) mod modulus`
1017 ///
1018 /// Note that this rounds like `mod_floor`, not like the `%` operator,
1019 /// which makes a difference when given a negative `self` or `modulus`.
1020 /// The result will be in the interval `[0, modulus)` for `modulus > 0`,
1021 /// or in the interval `(modulus, 0]` for `modulus < 0`
1022 ///
1023 /// Panics if the exponent is negative or the modulus is zero.
1024 pub fn modpow(&self, exponent: &Self, modulus: &Self) -> Self {
1025 power::modpow(self, exponent, modulus)
1026 }
1027
1028 /// Returns the modular multiplicative inverse if it exists, otherwise `None`.
1029 ///
1030 /// This solves for `x` such that `self * x ≡ 1 (mod modulus)`.
1031 /// Note that this rounds like `mod_floor`, not like the `%` operator,
1032 /// which makes a difference when given a negative `self` or `modulus`.
1033 /// The solution will be in the interval `[0, modulus)` for `modulus > 0`,
1034 /// or in the interval `(modulus, 0]` for `modulus < 0`,
1035 /// and it exists if and only if `gcd(self, modulus) == 1`.
1036 ///
1037 /// ```
1038 /// use num_bigint::BigInt;
1039 /// use num_integer::Integer;
1040 /// use num_traits::{One, Zero};
1041 ///
1042 /// let m = BigInt::from(383);
1043 ///
1044 /// // Trivial cases
1045 /// assert_eq!(BigInt::zero().modinv(&m), None);
1046 /// assert_eq!(BigInt::one().modinv(&m), Some(BigInt::one()));
1047 /// let neg1 = &m - 1u32;
1048 /// assert_eq!(neg1.modinv(&m), Some(neg1));
1049 ///
1050 /// // Positive self and modulus
1051 /// let a = BigInt::from(271);
1052 /// let x = a.modinv(&m).unwrap();
1053 /// assert_eq!(x, BigInt::from(106));
1054 /// assert_eq!(x.modinv(&m).unwrap(), a);
1055 /// assert_eq!((&a * x).mod_floor(&m), BigInt::one());
1056 ///
1057 /// // Negative self and positive modulus
1058 /// let b = -&a;
1059 /// let x = b.modinv(&m).unwrap();
1060 /// assert_eq!(x, BigInt::from(277));
1061 /// assert_eq!((&b * x).mod_floor(&m), BigInt::one());
1062 ///
1063 /// // Positive self and negative modulus
1064 /// let n = -&m;
1065 /// let x = a.modinv(&n).unwrap();
1066 /// assert_eq!(x, BigInt::from(-277));
1067 /// assert_eq!((&a * x).mod_floor(&n), &n + 1);
1068 ///
1069 /// // Negative self and modulus
1070 /// let x = b.modinv(&n).unwrap();
1071 /// assert_eq!(x, BigInt::from(-106));
1072 /// assert_eq!((&b * x).mod_floor(&n), &n + 1);
1073 /// ```
1074 pub fn modinv(&self, modulus: &Self) -> Option<Self> {
1075 let result = self.data.modinv(&modulus.data)?;
1076 // The sign of the result follows the modulus, like `mod_floor`.
1077 let (sign, mag) = match (self.is_negative(), modulus.is_negative()) {
1078 (false, false) => (Plus, result),
1079 (true, false) => (Plus, &modulus.data - result),
1080 (false, true) => (Minus, &modulus.data - result),
1081 (true, true) => (Minus, result),
1082 };
1083 Some(BigInt::from_biguint(sign, mag))
1084 }
1085
1086 /// Returns the truncated principal square root of `self` --
1087 /// see [`num_integer::Roots::sqrt()`].
1088 pub fn sqrt(&self) -> Self {
1089 Roots::sqrt(self)
1090 }
1091
1092 /// Returns the truncated principal cube root of `self` --
1093 /// see [`num_integer::Roots::cbrt()`].
1094 pub fn cbrt(&self) -> Self {
1095 Roots::cbrt(self)
1096 }
1097
1098 /// Returns the truncated principal `n`th root of `self` --
1099 /// See [`num_integer::Roots::nth_root()`].
1100 pub fn nth_root(&self, n: u32) -> Self {
1101 Roots::nth_root(self, n)
1102 }
1103
1104 /// Returns the number of least-significant bits that are zero,
1105 /// or `None` if the entire number is zero.
1106 pub fn trailing_zeros(&self) -> Option<u64> {
1107 self.data.trailing_zeros()
1108 }
1109
1110 /// Returns whether the bit in position `bit` is set,
1111 /// using the two's complement for negative numbers
1112 pub fn bit(&self, bit: u64) -> bool {
1113 if self.is_negative() {
1114 // Let the binary representation of a number be
1115 // ... 0 x 1 0 ... 0
1116 // Then the two's complement is
1117 // ... 1 !x 1 0 ... 0
1118 // where !x is obtained from x by flipping each bit
1119 if bit >= u64::from(crate::big_digit::BITS) * self.len() as u64 {
1120 true
1121 } else {
1122 let trailing_zeros = self.data.trailing_zeros().unwrap();
1123 match Ord::cmp(&bit, &trailing_zeros) {
1124 Ordering::Less => false,
1125 Ordering::Equal => true,
1126 Ordering::Greater => !self.data.bit(bit),
1127 }
1128 }
1129 } else {
1130 self.data.bit(bit)
1131 }
1132 }
1133
1134 /// Sets or clears the bit in the given position,
1135 /// using the two's complement for negative numbers
1136 ///
1137 /// Note that setting/clearing a bit (for positive/negative numbers,
1138 /// respectively) greater than the current bit length, a reallocation
1139 /// may be needed to store the new digits
1140 pub fn set_bit(&mut self, bit: u64, value: bool) {
1141 match self.sign {
1142 Sign::Plus => self.data.set_bit(bit, value),
1143 Sign::Minus => bits::set_negative_bit(self, bit, value),
1144 Sign::NoSign => {
1145 if value {
1146 self.data.set_bit(bit, true);
1147 self.sign = Sign::Plus;
1148 } else {
1149 // Clearing a bit for zero is a no-op
1150 }
1151 }
1152 }
1153 // The top bit may have been cleared, so normalize
1154 self.normalize();
1155 }
1156}
1157
1158impl num_traits::FromBytes for BigInt {
1159 type Bytes = [u8];
1160
1161 fn from_be_bytes(bytes: &Self::Bytes) -> Self {
1162 Self::from_signed_bytes_be(digits:bytes)
1163 }
1164
1165 fn from_le_bytes(bytes: &Self::Bytes) -> Self {
1166 Self::from_signed_bytes_le(digits:bytes)
1167 }
1168}
1169
1170impl num_traits::ToBytes for BigInt {
1171 type Bytes = Vec<u8>;
1172
1173 fn to_be_bytes(&self) -> Self::Bytes {
1174 self.to_signed_bytes_be()
1175 }
1176
1177 fn to_le_bytes(&self) -> Self::Bytes {
1178 self.to_signed_bytes_le()
1179 }
1180}
1181
1182#[test]
1183fn test_from_biguint() {
1184 fn check(inp_s: Sign, inp_n: usize, ans_s: Sign, ans_n: usize) {
1185 let inp = BigInt::from_biguint(inp_s, BigUint::from(inp_n));
1186 let ans = BigInt {
1187 sign: ans_s,
1188 data: BigUint::from(ans_n),
1189 };
1190 assert_eq!(inp, ans);
1191 }
1192 check(Plus, 1, Plus, 1);
1193 check(Plus, 0, NoSign, 0);
1194 check(Minus, 1, Minus, 1);
1195 check(NoSign, 1, NoSign, 0);
1196}
1197
1198#[test]
1199fn test_from_slice() {
1200 fn check(inp_s: Sign, inp_n: u32, ans_s: Sign, ans_n: u32) {
1201 let inp = BigInt::from_slice(inp_s, &[inp_n]);
1202 let ans = BigInt {
1203 sign: ans_s,
1204 data: BigUint::from(ans_n),
1205 };
1206 assert_eq!(inp, ans);
1207 }
1208 check(Plus, 1, Plus, 1);
1209 check(Plus, 0, NoSign, 0);
1210 check(Minus, 1, Minus, 1);
1211 check(NoSign, 1, NoSign, 0);
1212}
1213
1214#[test]
1215fn test_assign_from_slice() {
1216 fn check(inp_s: Sign, inp_n: u32, ans_s: Sign, ans_n: u32) {
1217 let mut inp = BigInt::from_slice(Minus, &[2627_u32, 0_u32, 9182_u32, 42_u32]);
1218 inp.assign_from_slice(inp_s, &[inp_n]);
1219 let ans = BigInt {
1220 sign: ans_s,
1221 data: BigUint::from(ans_n),
1222 };
1223 assert_eq!(inp, ans);
1224 }
1225 check(Plus, 1, Plus, 1);
1226 check(Plus, 0, NoSign, 0);
1227 check(Minus, 1, Minus, 1);
1228 check(NoSign, 1, NoSign, 0);
1229}
1230