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