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