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