1 use crate::big_digit::{self, BigDigit};
2
3 use alloc::string::String;
4 use alloc::vec::Vec;
5 use core::cmp;
6 use core::cmp::Ordering;
7 use core::default::Default;
8 use core::fmt;
9 use core::hash;
10 use core::mem;
11 use core::str;
12
13 use num_integer::{Integer, Roots};
14 use num_traits::{ConstZero, Num, One, Pow, ToPrimitive, Unsigned, Zero};
15
16 mod addition;
17 mod division;
18 mod multiplication;
19 mod subtraction;
20
21 mod arbitrary;
22 mod bits;
23 mod convert;
24 mod iter;
25 mod monty;
26 mod power;
27 mod serde;
28 mod shift;
29
30 pub(crate) use self::convert::to_str_radix_reversed;
31 pub use self::iter::{U32Digits, U64Digits};
32
33 /// A big unsigned integer type.
34 pub struct BigUint {
35 data: Vec<BigDigit>,
36 }
37
38 // Note: derived `Clone` doesn't specialize `clone_from`,
39 // but we want to keep the allocation in `data`.
40 impl Clone for BigUint {
41 #[inline]
clone(&self) -> Self42 fn clone(&self) -> Self {
43 BigUint {
44 data: self.data.clone(),
45 }
46 }
47
48 #[inline]
clone_from(&mut self, other: &Self)49 fn clone_from(&mut self, other: &Self) {
50 self.data.clone_from(&other.data);
51 }
52 }
53
54 impl hash::Hash for BigUint {
55 #[inline]
hash<H: hash::Hasher>(&self, state: &mut H)56 fn hash<H: hash::Hasher>(&self, state: &mut H) {
57 debug_assert!(self.data.last() != Some(&0));
58 self.data.hash(state);
59 }
60 }
61
62 impl PartialEq for BigUint {
63 #[inline]
eq(&self, other: &BigUint) -> bool64 fn eq(&self, other: &BigUint) -> bool {
65 debug_assert!(self.data.last() != Some(&0));
66 debug_assert!(other.data.last() != Some(&0));
67 self.data == other.data
68 }
69 }
70 impl Eq for BigUint {}
71
72 impl PartialOrd for BigUint {
73 #[inline]
partial_cmp(&self, other: &BigUint) -> Option<Ordering>74 fn partial_cmp(&self, other: &BigUint) -> Option<Ordering> {
75 Some(self.cmp(other))
76 }
77 }
78
79 impl Ord for BigUint {
80 #[inline]
cmp(&self, other: &BigUint) -> Ordering81 fn cmp(&self, other: &BigUint) -> Ordering {
82 cmp_slice(&self.data[..], &other.data[..])
83 }
84 }
85
86 #[inline]
cmp_slice(a: &[BigDigit], b: &[BigDigit]) -> Ordering87 fn cmp_slice(a: &[BigDigit], b: &[BigDigit]) -> Ordering {
88 debug_assert!(a.last() != Some(&0));
89 debug_assert!(b.last() != Some(&0));
90
91 match Ord::cmp(&a.len(), &b.len()) {
92 Ordering::Equal => Iterator::cmp(a.iter().rev(), b.iter().rev()),
93 other => other,
94 }
95 }
96
97 impl Default for BigUint {
98 #[inline]
default() -> BigUint99 fn default() -> BigUint {
100 Self::ZERO
101 }
102 }
103
104 impl fmt::Debug for BigUint {
fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result105 fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
106 fmt::Display::fmt(self, f)
107 }
108 }
109
110 impl fmt::Display for BigUint {
fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result111 fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
112 f.pad_integral(true, "", &self.to_str_radix(10))
113 }
114 }
115
116 impl fmt::LowerHex for BigUint {
fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result117 fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
118 f.pad_integral(true, "0x", &self.to_str_radix(16))
119 }
120 }
121
122 impl fmt::UpperHex for BigUint {
fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result123 fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
124 let mut s = self.to_str_radix(16);
125 s.make_ascii_uppercase();
126 f.pad_integral(true, "0x", &s)
127 }
128 }
129
130 impl fmt::Binary for BigUint {
fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result131 fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
132 f.pad_integral(true, "0b", &self.to_str_radix(2))
133 }
134 }
135
136 impl fmt::Octal for BigUint {
fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result137 fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
138 f.pad_integral(true, "0o", &self.to_str_radix(8))
139 }
140 }
141
142 impl Zero for BigUint {
143 #[inline]
zero() -> BigUint144 fn zero() -> BigUint {
145 Self::ZERO
146 }
147
148 #[inline]
set_zero(&mut self)149 fn set_zero(&mut self) {
150 self.data.clear();
151 }
152
153 #[inline]
is_zero(&self) -> bool154 fn is_zero(&self) -> bool {
155 self.data.is_empty()
156 }
157 }
158
159 impl ConstZero for BigUint {
160 // forward to the inherent const
161 const ZERO: Self = Self::ZERO; // BigUint { data: Vec::new() };
162 }
163
164 impl One for BigUint {
165 #[inline]
one() -> BigUint166 fn one() -> BigUint {
167 BigUint { data: vec![1] }
168 }
169
170 #[inline]
set_one(&mut self)171 fn set_one(&mut self) {
172 self.data.clear();
173 self.data.push(1);
174 }
175
176 #[inline]
is_one(&self) -> bool177 fn is_one(&self) -> bool {
178 self.data[..] == [1]
179 }
180 }
181
182 impl Unsigned for BigUint {}
183
184 impl Integer for BigUint {
185 #[inline]
div_rem(&self, other: &BigUint) -> (BigUint, BigUint)186 fn div_rem(&self, other: &BigUint) -> (BigUint, BigUint) {
187 division::div_rem_ref(self, other)
188 }
189
190 #[inline]
div_floor(&self, other: &BigUint) -> BigUint191 fn div_floor(&self, other: &BigUint) -> BigUint {
192 let (d, _) = division::div_rem_ref(self, other);
193 d
194 }
195
196 #[inline]
mod_floor(&self, other: &BigUint) -> BigUint197 fn mod_floor(&self, other: &BigUint) -> BigUint {
198 let (_, m) = division::div_rem_ref(self, other);
199 m
200 }
201
202 #[inline]
div_mod_floor(&self, other: &BigUint) -> (BigUint, BigUint)203 fn div_mod_floor(&self, other: &BigUint) -> (BigUint, BigUint) {
204 division::div_rem_ref(self, other)
205 }
206
207 #[inline]
div_ceil(&self, other: &BigUint) -> BigUint208 fn div_ceil(&self, other: &BigUint) -> BigUint {
209 let (d, m) = division::div_rem_ref(self, other);
210 if m.is_zero() {
211 d
212 } else {
213 d + 1u32
214 }
215 }
216
217 /// Calculates the Greatest Common Divisor (GCD) of the number and `other`.
218 ///
219 /// The result is always positive.
220 #[inline]
gcd(&self, other: &Self) -> Self221 fn gcd(&self, other: &Self) -> Self {
222 #[inline]
223 fn twos(x: &BigUint) -> u64 {
224 x.trailing_zeros().unwrap_or(0)
225 }
226
227 // Stein's algorithm
228 if self.is_zero() {
229 return other.clone();
230 }
231 if other.is_zero() {
232 return self.clone();
233 }
234 let mut m = self.clone();
235 let mut n = other.clone();
236
237 // find common factors of 2
238 let shift = cmp::min(twos(&n), twos(&m));
239
240 // divide m and n by 2 until odd
241 // m inside loop
242 n >>= twos(&n);
243
244 while !m.is_zero() {
245 m >>= twos(&m);
246 if n > m {
247 mem::swap(&mut n, &mut m)
248 }
249 m -= &n;
250 }
251
252 n << shift
253 }
254
255 /// Calculates the Lowest Common Multiple (LCM) of the number and `other`.
256 #[inline]
lcm(&self, other: &BigUint) -> BigUint257 fn lcm(&self, other: &BigUint) -> BigUint {
258 if self.is_zero() && other.is_zero() {
259 Self::ZERO
260 } else {
261 self / self.gcd(other) * other
262 }
263 }
264
265 /// Calculates the Greatest Common Divisor (GCD) and
266 /// Lowest Common Multiple (LCM) together.
267 #[inline]
gcd_lcm(&self, other: &Self) -> (Self, Self)268 fn gcd_lcm(&self, other: &Self) -> (Self, Self) {
269 let gcd = self.gcd(other);
270 let lcm = if gcd.is_zero() {
271 Self::ZERO
272 } else {
273 self / &gcd * other
274 };
275 (gcd, lcm)
276 }
277
278 /// Deprecated, use `is_multiple_of` instead.
279 #[inline]
divides(&self, other: &BigUint) -> bool280 fn divides(&self, other: &BigUint) -> bool {
281 self.is_multiple_of(other)
282 }
283
284 /// Returns `true` if the number is a multiple of `other`.
285 #[inline]
is_multiple_of(&self, other: &BigUint) -> bool286 fn is_multiple_of(&self, other: &BigUint) -> bool {
287 if other.is_zero() {
288 return self.is_zero();
289 }
290 (self % other).is_zero()
291 }
292
293 /// Returns `true` if the number is divisible by `2`.
294 #[inline]
is_even(&self) -> bool295 fn is_even(&self) -> bool {
296 // Considering only the last digit.
297 match self.data.first() {
298 Some(x) => x.is_even(),
299 None => true,
300 }
301 }
302
303 /// Returns `true` if the number is not divisible by `2`.
304 #[inline]
is_odd(&self) -> bool305 fn is_odd(&self) -> bool {
306 !self.is_even()
307 }
308
309 /// Rounds up to nearest multiple of argument.
310 #[inline]
next_multiple_of(&self, other: &Self) -> Self311 fn next_multiple_of(&self, other: &Self) -> Self {
312 let m = self.mod_floor(other);
313 if m.is_zero() {
314 self.clone()
315 } else {
316 self + (other - m)
317 }
318 }
319 /// Rounds down to nearest multiple of argument.
320 #[inline]
prev_multiple_of(&self, other: &Self) -> Self321 fn prev_multiple_of(&self, other: &Self) -> Self {
322 self - self.mod_floor(other)
323 }
324
dec(&mut self)325 fn dec(&mut self) {
326 *self -= 1u32;
327 }
328
inc(&mut self)329 fn inc(&mut self) {
330 *self += 1u32;
331 }
332 }
333
334 #[inline]
fixpoint<F>(mut x: BigUint, max_bits: u64, f: F) -> BigUint where F: Fn(&BigUint) -> BigUint,335 fn fixpoint<F>(mut x: BigUint, max_bits: u64, f: F) -> BigUint
336 where
337 F: Fn(&BigUint) -> BigUint,
338 {
339 let mut xn = f(&x);
340
341 // If the value increased, then the initial guess must have been low.
342 // Repeat until we reverse course.
343 while x < xn {
344 // Sometimes an increase will go way too far, especially with large
345 // powers, and then take a long time to walk back. We know an upper
346 // bound based on bit size, so saturate on that.
347 x = if xn.bits() > max_bits {
348 BigUint::one() << max_bits
349 } else {
350 xn
351 };
352 xn = f(&x);
353 }
354
355 // Now keep repeating while the estimate is decreasing.
356 while x > xn {
357 x = xn;
358 xn = f(&x);
359 }
360 x
361 }
362
363 impl Roots for BigUint {
364 // nth_root, sqrt and cbrt use Newton's method to compute
365 // principal root of a given degree for a given integer.
366
367 // Reference:
368 // Brent & Zimmermann, Modern Computer Arithmetic, v0.5.9, Algorithm 1.14
nth_root(&self, n: u32) -> Self369 fn nth_root(&self, n: u32) -> Self {
370 assert!(n > 0, "root degree n must be at least 1");
371
372 if self.is_zero() || self.is_one() {
373 return self.clone();
374 }
375
376 match n {
377 // Optimize for small n
378 1 => return self.clone(),
379 2 => return self.sqrt(),
380 3 => return self.cbrt(),
381 _ => (),
382 }
383
384 // The root of non-zero values less than 2ⁿ can only be 1.
385 let bits = self.bits();
386 let n64 = u64::from(n);
387 if bits <= n64 {
388 return BigUint::one();
389 }
390
391 // If we fit in `u64`, compute the root that way.
392 if let Some(x) = self.to_u64() {
393 return x.nth_root(n).into();
394 }
395
396 let max_bits = bits / n64 + 1;
397
398 #[cfg(feature = "std")]
399 let guess = match self.to_f64() {
400 Some(f) if f.is_finite() => {
401 use num_traits::FromPrimitive;
402
403 // We fit in `f64` (lossy), so get a better initial guess from that.
404 BigUint::from_f64((f.ln() / f64::from(n)).exp()).unwrap()
405 }
406 _ => {
407 // Try to guess by scaling down such that it does fit in `f64`.
408 // With some (x * 2ⁿᵏ), its nth root ≈ (ⁿ√x * 2ᵏ)
409 let extra_bits = bits - (f64::MAX_EXP as u64 - 1);
410 let root_scale = Integer::div_ceil(&extra_bits, &n64);
411 let scale = root_scale * n64;
412 if scale < bits && bits - scale > n64 {
413 (self >> scale).nth_root(n) << root_scale
414 } else {
415 BigUint::one() << max_bits
416 }
417 }
418 };
419
420 #[cfg(not(feature = "std"))]
421 let guess = BigUint::one() << max_bits;
422
423 let n_min_1 = n - 1;
424 fixpoint(guess, max_bits, move |s| {
425 let q = self / s.pow(n_min_1);
426 let t = n_min_1 * s + q;
427 t / n
428 })
429 }
430
431 // Reference:
432 // Brent & Zimmermann, Modern Computer Arithmetic, v0.5.9, Algorithm 1.13
sqrt(&self) -> Self433 fn sqrt(&self) -> Self {
434 if self.is_zero() || self.is_one() {
435 return self.clone();
436 }
437
438 // If we fit in `u64`, compute the root that way.
439 if let Some(x) = self.to_u64() {
440 return x.sqrt().into();
441 }
442
443 let bits = self.bits();
444 let max_bits = bits / 2 + 1;
445
446 #[cfg(feature = "std")]
447 let guess = match self.to_f64() {
448 Some(f) if f.is_finite() => {
449 use num_traits::FromPrimitive;
450
451 // We fit in `f64` (lossy), so get a better initial guess from that.
452 BigUint::from_f64(f.sqrt()).unwrap()
453 }
454 _ => {
455 // Try to guess by scaling down such that it does fit in `f64`.
456 // With some (x * 2²ᵏ), its sqrt ≈ (√x * 2ᵏ)
457 let extra_bits = bits - (f64::MAX_EXP as u64 - 1);
458 let root_scale = (extra_bits + 1) / 2;
459 let scale = root_scale * 2;
460 (self >> scale).sqrt() << root_scale
461 }
462 };
463
464 #[cfg(not(feature = "std"))]
465 let guess = BigUint::one() << max_bits;
466
467 fixpoint(guess, max_bits, move |s| {
468 let q = self / s;
469 let t = s + q;
470 t >> 1
471 })
472 }
473
cbrt(&self) -> Self474 fn cbrt(&self) -> Self {
475 if self.is_zero() || self.is_one() {
476 return self.clone();
477 }
478
479 // If we fit in `u64`, compute the root that way.
480 if let Some(x) = self.to_u64() {
481 return x.cbrt().into();
482 }
483
484 let bits = self.bits();
485 let max_bits = bits / 3 + 1;
486
487 #[cfg(feature = "std")]
488 let guess = match self.to_f64() {
489 Some(f) if f.is_finite() => {
490 use num_traits::FromPrimitive;
491
492 // We fit in `f64` (lossy), so get a better initial guess from that.
493 BigUint::from_f64(f.cbrt()).unwrap()
494 }
495 _ => {
496 // Try to guess by scaling down such that it does fit in `f64`.
497 // With some (x * 2³ᵏ), its cbrt ≈ (∛x * 2ᵏ)
498 let extra_bits = bits - (f64::MAX_EXP as u64 - 1);
499 let root_scale = (extra_bits + 2) / 3;
500 let scale = root_scale * 3;
501 (self >> scale).cbrt() << root_scale
502 }
503 };
504
505 #[cfg(not(feature = "std"))]
506 let guess = BigUint::one() << max_bits;
507
508 fixpoint(guess, max_bits, move |s| {
509 let q = self / (s * s);
510 let t = (s << 1) + q;
511 t / 3u32
512 })
513 }
514 }
515
516 /// A generic trait for converting a value to a [`BigUint`].
517 pub trait ToBigUint {
518 /// Converts the value of `self` to a [`BigUint`].
to_biguint(&self) -> Option<BigUint>519 fn to_biguint(&self) -> Option<BigUint>;
520 }
521
522 /// Creates and initializes a [`BigUint`].
523 ///
524 /// The digits are in little-endian base matching `BigDigit`.
525 #[inline]
biguint_from_vec(digits: Vec<BigDigit>) -> BigUint526 pub(crate) fn biguint_from_vec(digits: Vec<BigDigit>) -> BigUint {
527 BigUint { data: digits }.normalized()
528 }
529
530 impl BigUint {
531 /// A constant `BigUint` with value 0, useful for static initialization.
532 pub const ZERO: Self = BigUint { data: Vec::new() };
533
534 /// Creates and initializes a [`BigUint`].
535 ///
536 /// The base 2<sup>32</sup> digits are ordered least significant digit first.
537 #[inline]
new(digits: Vec<u32>) -> BigUint538 pub fn new(digits: Vec<u32>) -> BigUint {
539 let mut big = Self::ZERO;
540
541 cfg_digit_expr!(
542 {
543 big.data = digits;
544 big.normalize();
545 },
546 big.assign_from_slice(&digits)
547 );
548
549 big
550 }
551
552 /// Creates and initializes a [`BigUint`].
553 ///
554 /// The base 2<sup>32</sup> digits are ordered least significant digit first.
555 #[inline]
from_slice(slice: &[u32]) -> BigUint556 pub fn from_slice(slice: &[u32]) -> BigUint {
557 let mut big = Self::ZERO;
558 big.assign_from_slice(slice);
559 big
560 }
561
562 /// Assign a value to a [`BigUint`].
563 ///
564 /// The base 2<sup>32</sup> digits are ordered least significant digit first.
565 #[inline]
assign_from_slice(&mut self, slice: &[u32])566 pub fn assign_from_slice(&mut self, slice: &[u32]) {
567 self.data.clear();
568
569 cfg_digit_expr!(
570 self.data.extend_from_slice(slice),
571 self.data.extend(slice.chunks(2).map(u32_chunk_to_u64))
572 );
573
574 self.normalize();
575 }
576
577 /// Creates and initializes a [`BigUint`].
578 ///
579 /// The bytes are in big-endian byte order.
580 ///
581 /// # Examples
582 ///
583 /// ```
584 /// use num_bigint::BigUint;
585 ///
586 /// assert_eq!(BigUint::from_bytes_be(b"A"),
587 /// BigUint::parse_bytes(b"65", 10).unwrap());
588 /// assert_eq!(BigUint::from_bytes_be(b"AA"),
589 /// BigUint::parse_bytes(b"16705", 10).unwrap());
590 /// assert_eq!(BigUint::from_bytes_be(b"AB"),
591 /// BigUint::parse_bytes(b"16706", 10).unwrap());
592 /// assert_eq!(BigUint::from_bytes_be(b"Hello world!"),
593 /// BigUint::parse_bytes(b"22405534230753963835153736737", 10).unwrap());
594 /// ```
595 #[inline]
from_bytes_be(bytes: &[u8]) -> BigUint596 pub fn from_bytes_be(bytes: &[u8]) -> BigUint {
597 if bytes.is_empty() {
598 Self::ZERO
599 } else {
600 let mut v = bytes.to_vec();
601 v.reverse();
602 BigUint::from_bytes_le(&v)
603 }
604 }
605
606 /// Creates and initializes a [`BigUint`].
607 ///
608 /// The bytes are in little-endian byte order.
609 #[inline]
from_bytes_le(bytes: &[u8]) -> BigUint610 pub fn from_bytes_le(bytes: &[u8]) -> BigUint {
611 if bytes.is_empty() {
612 Self::ZERO
613 } else {
614 convert::from_bitwise_digits_le(bytes, 8)
615 }
616 }
617
618 /// Creates and initializes a [`BigUint`]. The input slice must contain
619 /// ascii/utf8 characters in [0-9a-zA-Z].
620 /// `radix` must be in the range `2...36`.
621 ///
622 /// The function `from_str_radix` from the `Num` trait provides the same logic
623 /// for `&str` buffers.
624 ///
625 /// # Examples
626 ///
627 /// ```
628 /// use num_bigint::{BigUint, ToBigUint};
629 ///
630 /// assert_eq!(BigUint::parse_bytes(b"1234", 10), ToBigUint::to_biguint(&1234));
631 /// assert_eq!(BigUint::parse_bytes(b"ABCD", 16), ToBigUint::to_biguint(&0xABCD));
632 /// assert_eq!(BigUint::parse_bytes(b"G", 16), None);
633 /// ```
634 #[inline]
parse_bytes(buf: &[u8], radix: u32) -> Option<BigUint>635 pub fn parse_bytes(buf: &[u8], radix: u32) -> Option<BigUint> {
636 let s = str::from_utf8(buf).ok()?;
637 BigUint::from_str_radix(s, radix).ok()
638 }
639
640 /// Creates and initializes a [`BigUint`]. Each `u8` of the input slice is
641 /// interpreted as one digit of the number
642 /// and must therefore be less than `radix`.
643 ///
644 /// The bytes are in big-endian byte order.
645 /// `radix` must be in the range `2...256`.
646 ///
647 /// # Examples
648 ///
649 /// ```
650 /// use num_bigint::{BigUint};
651 ///
652 /// let inbase190 = &[15, 33, 125, 12, 14];
653 /// let a = BigUint::from_radix_be(inbase190, 190).unwrap();
654 /// assert_eq!(a.to_radix_be(190), inbase190);
655 /// ```
from_radix_be(buf: &[u8], radix: u32) -> Option<BigUint>656 pub fn from_radix_be(buf: &[u8], radix: u32) -> Option<BigUint> {
657 convert::from_radix_be(buf, radix)
658 }
659
660 /// Creates and initializes a [`BigUint`]. Each `u8` of the input slice is
661 /// interpreted as one digit of the number
662 /// and must therefore be less than `radix`.
663 ///
664 /// The bytes are in little-endian byte order.
665 /// `radix` must be in the range `2...256`.
666 ///
667 /// # Examples
668 ///
669 /// ```
670 /// use num_bigint::{BigUint};
671 ///
672 /// let inbase190 = &[14, 12, 125, 33, 15];
673 /// let a = BigUint::from_radix_be(inbase190, 190).unwrap();
674 /// assert_eq!(a.to_radix_be(190), inbase190);
675 /// ```
from_radix_le(buf: &[u8], radix: u32) -> Option<BigUint>676 pub fn from_radix_le(buf: &[u8], radix: u32) -> Option<BigUint> {
677 convert::from_radix_le(buf, radix)
678 }
679
680 /// Returns the byte representation of the [`BigUint`] in big-endian byte order.
681 ///
682 /// # Examples
683 ///
684 /// ```
685 /// use num_bigint::BigUint;
686 ///
687 /// let i = BigUint::parse_bytes(b"1125", 10).unwrap();
688 /// assert_eq!(i.to_bytes_be(), vec![4, 101]);
689 /// ```
690 #[inline]
to_bytes_be(&self) -> Vec<u8>691 pub fn to_bytes_be(&self) -> Vec<u8> {
692 let mut v = self.to_bytes_le();
693 v.reverse();
694 v
695 }
696
697 /// Returns the byte representation of the [`BigUint`] in little-endian byte order.
698 ///
699 /// # Examples
700 ///
701 /// ```
702 /// use num_bigint::BigUint;
703 ///
704 /// let i = BigUint::parse_bytes(b"1125", 10).unwrap();
705 /// assert_eq!(i.to_bytes_le(), vec![101, 4]);
706 /// ```
707 #[inline]
to_bytes_le(&self) -> Vec<u8>708 pub fn to_bytes_le(&self) -> Vec<u8> {
709 if self.is_zero() {
710 vec![0]
711 } else {
712 convert::to_bitwise_digits_le(self, 8)
713 }
714 }
715
716 /// Returns the `u32` digits representation of the [`BigUint`] ordered least significant digit
717 /// first.
718 ///
719 /// # Examples
720 ///
721 /// ```
722 /// use num_bigint::BigUint;
723 ///
724 /// assert_eq!(BigUint::from(1125u32).to_u32_digits(), vec![1125]);
725 /// assert_eq!(BigUint::from(4294967295u32).to_u32_digits(), vec![4294967295]);
726 /// assert_eq!(BigUint::from(4294967296u64).to_u32_digits(), vec![0, 1]);
727 /// assert_eq!(BigUint::from(112500000000u64).to_u32_digits(), vec![830850304, 26]);
728 /// ```
729 #[inline]
to_u32_digits(&self) -> Vec<u32>730 pub fn to_u32_digits(&self) -> Vec<u32> {
731 self.iter_u32_digits().collect()
732 }
733
734 /// Returns the `u64` digits representation of the [`BigUint`] ordered least significant digit
735 /// first.
736 ///
737 /// # Examples
738 ///
739 /// ```
740 /// use num_bigint::BigUint;
741 ///
742 /// assert_eq!(BigUint::from(1125u32).to_u64_digits(), vec![1125]);
743 /// assert_eq!(BigUint::from(4294967295u32).to_u64_digits(), vec![4294967295]);
744 /// assert_eq!(BigUint::from(4294967296u64).to_u64_digits(), vec![4294967296]);
745 /// assert_eq!(BigUint::from(112500000000u64).to_u64_digits(), vec![112500000000]);
746 /// assert_eq!(BigUint::from(1u128 << 64).to_u64_digits(), vec![0, 1]);
747 /// ```
748 #[inline]
to_u64_digits(&self) -> Vec<u64>749 pub fn to_u64_digits(&self) -> Vec<u64> {
750 self.iter_u64_digits().collect()
751 }
752
753 /// Returns an iterator of `u32` digits representation of the [`BigUint`] ordered least
754 /// significant digit first.
755 ///
756 /// # Examples
757 ///
758 /// ```
759 /// use num_bigint::BigUint;
760 ///
761 /// assert_eq!(BigUint::from(1125u32).iter_u32_digits().collect::<Vec<u32>>(), vec![1125]);
762 /// assert_eq!(BigUint::from(4294967295u32).iter_u32_digits().collect::<Vec<u32>>(), vec![4294967295]);
763 /// assert_eq!(BigUint::from(4294967296u64).iter_u32_digits().collect::<Vec<u32>>(), vec![0, 1]);
764 /// assert_eq!(BigUint::from(112500000000u64).iter_u32_digits().collect::<Vec<u32>>(), vec![830850304, 26]);
765 /// ```
766 #[inline]
iter_u32_digits(&self) -> U32Digits<'_>767 pub fn iter_u32_digits(&self) -> U32Digits<'_> {
768 U32Digits::new(self.data.as_slice())
769 }
770
771 /// Returns an iterator of `u64` digits representation of the [`BigUint`] ordered least
772 /// significant digit first.
773 ///
774 /// # Examples
775 ///
776 /// ```
777 /// use num_bigint::BigUint;
778 ///
779 /// assert_eq!(BigUint::from(1125u32).iter_u64_digits().collect::<Vec<u64>>(), vec![1125]);
780 /// assert_eq!(BigUint::from(4294967295u32).iter_u64_digits().collect::<Vec<u64>>(), vec![4294967295]);
781 /// assert_eq!(BigUint::from(4294967296u64).iter_u64_digits().collect::<Vec<u64>>(), vec![4294967296]);
782 /// assert_eq!(BigUint::from(112500000000u64).iter_u64_digits().collect::<Vec<u64>>(), vec![112500000000]);
783 /// assert_eq!(BigUint::from(1u128 << 64).iter_u64_digits().collect::<Vec<u64>>(), vec![0, 1]);
784 /// ```
785 #[inline]
iter_u64_digits(&self) -> U64Digits<'_>786 pub fn iter_u64_digits(&self) -> U64Digits<'_> {
787 U64Digits::new(self.data.as_slice())
788 }
789
790 /// Returns the integer formatted as a string in the given radix.
791 /// `radix` must be in the range `2...36`.
792 ///
793 /// # Examples
794 ///
795 /// ```
796 /// use num_bigint::BigUint;
797 ///
798 /// let i = BigUint::parse_bytes(b"ff", 16).unwrap();
799 /// assert_eq!(i.to_str_radix(16), "ff");
800 /// ```
801 #[inline]
to_str_radix(&self, radix: u32) -> String802 pub fn to_str_radix(&self, radix: u32) -> String {
803 let mut v = to_str_radix_reversed(self, radix);
804 v.reverse();
805 unsafe { String::from_utf8_unchecked(v) }
806 }
807
808 /// Returns the integer in the requested base in big-endian digit order.
809 /// The output is not given in a human readable alphabet but as a zero
810 /// based `u8` number.
811 /// `radix` must be in the range `2...256`.
812 ///
813 /// # Examples
814 ///
815 /// ```
816 /// use num_bigint::BigUint;
817 ///
818 /// assert_eq!(BigUint::from(0xFFFFu64).to_radix_be(159),
819 /// vec![2, 94, 27]);
820 /// // 0xFFFF = 65535 = 2*(159^2) + 94*159 + 27
821 /// ```
822 #[inline]
to_radix_be(&self, radix: u32) -> Vec<u8>823 pub fn to_radix_be(&self, radix: u32) -> Vec<u8> {
824 let mut v = convert::to_radix_le(self, radix);
825 v.reverse();
826 v
827 }
828
829 /// Returns the integer in the requested base in little-endian digit order.
830 /// The output is not given in a human readable alphabet but as a zero
831 /// based u8 number.
832 /// `radix` must be in the range `2...256`.
833 ///
834 /// # Examples
835 ///
836 /// ```
837 /// use num_bigint::BigUint;
838 ///
839 /// assert_eq!(BigUint::from(0xFFFFu64).to_radix_le(159),
840 /// vec![27, 94, 2]);
841 /// // 0xFFFF = 65535 = 27 + 94*159 + 2*(159^2)
842 /// ```
843 #[inline]
to_radix_le(&self, radix: u32) -> Vec<u8>844 pub fn to_radix_le(&self, radix: u32) -> Vec<u8> {
845 convert::to_radix_le(self, radix)
846 }
847
848 /// Determines the fewest bits necessary to express the [`BigUint`].
849 #[inline]
bits(&self) -> u64850 pub fn bits(&self) -> u64 {
851 if self.is_zero() {
852 return 0;
853 }
854 let zeros: u64 = self.data.last().unwrap().leading_zeros().into();
855 self.data.len() as u64 * u64::from(big_digit::BITS) - zeros
856 }
857
858 /// Strips off trailing zero bigdigits - comparisons require the last element in the vector to
859 /// be nonzero.
860 #[inline]
normalize(&mut self)861 fn normalize(&mut self) {
862 if let Some(&0) = self.data.last() {
863 let len = self.data.iter().rposition(|&d| d != 0).map_or(0, |i| i + 1);
864 self.data.truncate(len);
865 }
866 if self.data.len() < self.data.capacity() / 4 {
867 self.data.shrink_to_fit();
868 }
869 }
870
871 /// Returns a normalized [`BigUint`].
872 #[inline]
normalized(mut self) -> BigUint873 fn normalized(mut self) -> BigUint {
874 self.normalize();
875 self
876 }
877
878 /// Returns `self ^ exponent`.
pow(&self, exponent: u32) -> Self879 pub fn pow(&self, exponent: u32) -> Self {
880 Pow::pow(self, exponent)
881 }
882
883 /// Returns `(self ^ exponent) % modulus`.
884 ///
885 /// Panics if the modulus is zero.
modpow(&self, exponent: &Self, modulus: &Self) -> Self886 pub fn modpow(&self, exponent: &Self, modulus: &Self) -> Self {
887 power::modpow(self, exponent, modulus)
888 }
889
890 /// Returns the modular multiplicative inverse if it exists, otherwise `None`.
891 ///
892 /// This solves for `x` in the interval `[0, modulus)` such that `self * x ≡ 1 (mod modulus)`.
893 /// The solution exists if and only if `gcd(self, modulus) == 1`.
894 ///
895 /// ```
896 /// use num_bigint::BigUint;
897 /// use num_traits::{One, Zero};
898 ///
899 /// let m = BigUint::from(383_u32);
900 ///
901 /// // Trivial cases
902 /// assert_eq!(BigUint::zero().modinv(&m), None);
903 /// assert_eq!(BigUint::one().modinv(&m), Some(BigUint::one()));
904 /// let neg1 = &m - 1u32;
905 /// assert_eq!(neg1.modinv(&m), Some(neg1));
906 ///
907 /// let a = BigUint::from(271_u32);
908 /// let x = a.modinv(&m).unwrap();
909 /// assert_eq!(x, BigUint::from(106_u32));
910 /// assert_eq!(x.modinv(&m).unwrap(), a);
911 /// assert!((a * x % m).is_one());
912 /// ```
modinv(&self, modulus: &Self) -> Option<Self>913 pub fn modinv(&self, modulus: &Self) -> Option<Self> {
914 // Based on the inverse pseudocode listed here:
915 // https://en.wikipedia.org/wiki/Extended_Euclidean_algorithm#Modular_integers
916 // TODO: consider Binary or Lehmer's GCD algorithms for optimization.
917
918 assert!(
919 !modulus.is_zero(),
920 "attempt to calculate with zero modulus!"
921 );
922 if modulus.is_one() {
923 return Some(Self::zero());
924 }
925
926 let mut r0; // = modulus.clone();
927 let mut r1 = self % modulus;
928 let mut t0; // = Self::zero();
929 let mut t1; // = Self::one();
930
931 // Lift and simplify the first iteration to avoid some initial allocations.
932 if r1.is_zero() {
933 return None;
934 } else if r1.is_one() {
935 return Some(r1);
936 } else {
937 let (q, r2) = modulus.div_rem(&r1);
938 if r2.is_zero() {
939 return None;
940 }
941 r0 = r1;
942 r1 = r2;
943 t0 = Self::one();
944 t1 = modulus - q;
945 }
946
947 while !r1.is_zero() {
948 let (q, r2) = r0.div_rem(&r1);
949 r0 = r1;
950 r1 = r2;
951
952 // let t2 = (t0 - q * t1) % modulus;
953 let qt1 = q * &t1 % modulus;
954 let t2 = if t0 < qt1 {
955 t0 + (modulus - qt1)
956 } else {
957 t0 - qt1
958 };
959 t0 = t1;
960 t1 = t2;
961 }
962
963 if r0.is_one() {
964 Some(t0)
965 } else {
966 None
967 }
968 }
969
970 /// Returns the truncated principal square root of `self` --
971 /// see [Roots::sqrt](https://docs.rs/num-integer/0.1/num_integer/trait.Roots.html#method.sqrt)
sqrt(&self) -> Self972 pub fn sqrt(&self) -> Self {
973 Roots::sqrt(self)
974 }
975
976 /// Returns the truncated principal cube root of `self` --
977 /// see [Roots::cbrt](https://docs.rs/num-integer/0.1/num_integer/trait.Roots.html#method.cbrt).
cbrt(&self) -> Self978 pub fn cbrt(&self) -> Self {
979 Roots::cbrt(self)
980 }
981
982 /// Returns the truncated principal `n`th root of `self` --
983 /// see [Roots::nth_root](https://docs.rs/num-integer/0.1/num_integer/trait.Roots.html#tymethod.nth_root).
nth_root(&self, n: u32) -> Self984 pub fn nth_root(&self, n: u32) -> Self {
985 Roots::nth_root(self, n)
986 }
987
988 /// Returns the number of least-significant bits that are zero,
989 /// or `None` if the entire number is zero.
trailing_zeros(&self) -> Option<u64>990 pub fn trailing_zeros(&self) -> Option<u64> {
991 let i = self.data.iter().position(|&digit| digit != 0)?;
992 let zeros: u64 = self.data[i].trailing_zeros().into();
993 Some(i as u64 * u64::from(big_digit::BITS) + zeros)
994 }
995
996 /// Returns the number of least-significant bits that are ones.
trailing_ones(&self) -> u64997 pub fn trailing_ones(&self) -> u64 {
998 if let Some(i) = self.data.iter().position(|&digit| !digit != 0) {
999 let ones: u64 = self.data[i].trailing_ones().into();
1000 i as u64 * u64::from(big_digit::BITS) + ones
1001 } else {
1002 self.data.len() as u64 * u64::from(big_digit::BITS)
1003 }
1004 }
1005
1006 /// Returns the number of one bits.
count_ones(&self) -> u641007 pub fn count_ones(&self) -> u64 {
1008 self.data.iter().map(|&d| u64::from(d.count_ones())).sum()
1009 }
1010
1011 /// Returns whether the bit in the given position is set
bit(&self, bit: u64) -> bool1012 pub fn bit(&self, bit: u64) -> bool {
1013 let bits_per_digit = u64::from(big_digit::BITS);
1014 if let Some(digit_index) = (bit / bits_per_digit).to_usize() {
1015 if let Some(digit) = self.data.get(digit_index) {
1016 let bit_mask = (1 as BigDigit) << (bit % bits_per_digit);
1017 return (digit & bit_mask) != 0;
1018 }
1019 }
1020 false
1021 }
1022
1023 /// Sets or clears the bit in the given position
1024 ///
1025 /// Note that setting a bit greater than the current bit length, a reallocation may be needed
1026 /// to store the new digits
set_bit(&mut self, bit: u64, value: bool)1027 pub fn set_bit(&mut self, bit: u64, value: bool) {
1028 // Note: we're saturating `digit_index` and `new_len` -- any such case is guaranteed to
1029 // fail allocation, and that's more consistent than adding our own overflow panics.
1030 let bits_per_digit = u64::from(big_digit::BITS);
1031 let digit_index = (bit / bits_per_digit).to_usize().unwrap_or(usize::MAX);
1032 let bit_mask = (1 as BigDigit) << (bit % bits_per_digit);
1033 if value {
1034 if digit_index >= self.data.len() {
1035 let new_len = digit_index.saturating_add(1);
1036 self.data.resize(new_len, 0);
1037 }
1038 self.data[digit_index] |= bit_mask;
1039 } else if digit_index < self.data.len() {
1040 self.data[digit_index] &= !bit_mask;
1041 // the top bit may have been cleared, so normalize
1042 self.normalize();
1043 }
1044 }
1045 }
1046
1047 impl num_traits::FromBytes for BigUint {
1048 type Bytes = [u8];
1049
from_be_bytes(bytes: &Self::Bytes) -> Self1050 fn from_be_bytes(bytes: &Self::Bytes) -> Self {
1051 Self::from_bytes_be(bytes)
1052 }
1053
from_le_bytes(bytes: &Self::Bytes) -> Self1054 fn from_le_bytes(bytes: &Self::Bytes) -> Self {
1055 Self::from_bytes_le(bytes)
1056 }
1057 }
1058
1059 impl num_traits::ToBytes for BigUint {
1060 type Bytes = Vec<u8>;
1061
to_be_bytes(&self) -> Self::Bytes1062 fn to_be_bytes(&self) -> Self::Bytes {
1063 self.to_bytes_be()
1064 }
1065
to_le_bytes(&self) -> Self::Bytes1066 fn to_le_bytes(&self) -> Self::Bytes {
1067 self.to_bytes_le()
1068 }
1069 }
1070
1071 pub(crate) trait IntDigits {
digits(&self) -> &[BigDigit]1072 fn digits(&self) -> &[BigDigit];
digits_mut(&mut self) -> &mut Vec<BigDigit>1073 fn digits_mut(&mut self) -> &mut Vec<BigDigit>;
normalize(&mut self)1074 fn normalize(&mut self);
capacity(&self) -> usize1075 fn capacity(&self) -> usize;
len(&self) -> usize1076 fn len(&self) -> usize;
1077 }
1078
1079 impl IntDigits for BigUint {
1080 #[inline]
digits(&self) -> &[BigDigit]1081 fn digits(&self) -> &[BigDigit] {
1082 &self.data
1083 }
1084 #[inline]
digits_mut(&mut self) -> &mut Vec<BigDigit>1085 fn digits_mut(&mut self) -> &mut Vec<BigDigit> {
1086 &mut self.data
1087 }
1088 #[inline]
normalize(&mut self)1089 fn normalize(&mut self) {
1090 self.normalize();
1091 }
1092 #[inline]
capacity(&self) -> usize1093 fn capacity(&self) -> usize {
1094 self.data.capacity()
1095 }
1096 #[inline]
len(&self) -> usize1097 fn len(&self) -> usize {
1098 self.data.len()
1099 }
1100 }
1101
1102 /// Convert a `u32` chunk (len is either 1 or 2) to a single `u64` digit
1103 #[inline]
u32_chunk_to_u64(chunk: &[u32]) -> u641104 fn u32_chunk_to_u64(chunk: &[u32]) -> u64 {
1105 // raw could have odd length
1106 let mut digit = chunk[0] as u64;
1107 if let Some(&hi) = chunk.get(1) {
1108 digit |= (hi as u64) << 32;
1109 }
1110 digit
1111 }
1112
1113 cfg_32_or_test!(
1114 /// Combine four `u32`s into a single `u128`.
1115 #[inline]
1116 fn u32_to_u128(a: u32, b: u32, c: u32, d: u32) -> u128 {
1117 u128::from(d) | (u128::from(c) << 32) | (u128::from(b) << 64) | (u128::from(a) << 96)
1118 }
1119 );
1120
1121 cfg_32_or_test!(
1122 /// Split a single `u128` into four `u32`.
1123 #[inline]
1124 fn u32_from_u128(n: u128) -> (u32, u32, u32, u32) {
1125 (
1126 (n >> 96) as u32,
1127 (n >> 64) as u32,
1128 (n >> 32) as u32,
1129 n as u32,
1130 )
1131 }
1132 );
1133
1134 cfg_digit!(
1135 #[test]
1136 fn test_from_slice() {
1137 fn check(slice: &[u32], data: &[BigDigit]) {
1138 assert_eq!(BigUint::from_slice(slice).data, data);
1139 }
1140 check(&[1], &[1]);
1141 check(&[0, 0, 0], &[]);
1142 check(&[1, 2, 0, 0], &[1, 2]);
1143 check(&[0, 0, 1, 2], &[0, 0, 1, 2]);
1144 check(&[0, 0, 1, 2, 0, 0], &[0, 0, 1, 2]);
1145 check(&[-1i32 as u32], &[-1i32 as BigDigit]);
1146 }
1147
1148 #[test]
1149 fn test_from_slice() {
1150 fn check(slice: &[u32], data: &[BigDigit]) {
1151 assert_eq!(
1152 BigUint::from_slice(slice).data,
1153 data,
1154 "from {:?}, to {:?}",
1155 slice,
1156 data
1157 );
1158 }
1159 check(&[1], &[1]);
1160 check(&[0, 0, 0], &[]);
1161 check(&[1, 2], &[8_589_934_593]);
1162 check(&[1, 2, 0, 0], &[8_589_934_593]);
1163 check(&[0, 0, 1, 2], &[0, 8_589_934_593]);
1164 check(&[0, 0, 1, 2, 0, 0], &[0, 8_589_934_593]);
1165 check(&[-1i32 as u32], &[(-1i32 as u32) as BigDigit]);
1166 }
1167 );
1168
1169 #[test]
test_u32_u128()1170 fn test_u32_u128() {
1171 assert_eq!(u32_from_u128(0u128), (0, 0, 0, 0));
1172 assert_eq!(
1173 u32_from_u128(u128::MAX),
1174 (u32::MAX, u32::MAX, u32::MAX, u32::MAX)
1175 );
1176
1177 assert_eq!(u32_from_u128(u32::MAX as u128), (0, 0, 0, u32::MAX));
1178
1179 assert_eq!(u32_from_u128(u64::MAX as u128), (0, 0, u32::MAX, u32::MAX));
1180
1181 assert_eq!(
1182 u32_from_u128((u64::MAX as u128) + u32::MAX as u128),
1183 (0, 1, 0, u32::MAX - 1)
1184 );
1185
1186 assert_eq!(u32_from_u128(36_893_488_151_714_070_528), (0, 2, 1, 0));
1187 }
1188
1189 #[test]
test_u128_u32_roundtrip()1190 fn test_u128_u32_roundtrip() {
1191 // roundtrips
1192 let values = vec![
1193 0u128,
1194 1u128,
1195 u64::MAX as u128 * 3,
1196 u32::MAX as u128,
1197 u64::MAX as u128,
1198 (u64::MAX as u128) + u32::MAX as u128,
1199 u128::MAX,
1200 ];
1201
1202 for val in &values {
1203 let (a, b, c, d) = u32_from_u128(*val);
1204 assert_eq!(u32_to_u128(a, b, c, d), *val);
1205 }
1206 }
1207