Struct sp_arithmetic::biguint::BigUint

pub struct BigUint { /* private fields */ }

Simple wrapper around an infinitely large integer, represented as limbs of Single.

Implementations

impl BigUint

pub fn with_capacity(size: usize) -> Self

Create a new instance with size limbs. This prevents any number with zero limbs to be created.

The behavior of the type is undefined with zero limbs.

Examples found in repository

src/biguint.rs (line 195)

	pub fn add(self, other: &Self) -> Self {
		let n = self.len().max(other.len());
		let mut k: Double = 0;
		let mut w = Self::with_capacity(n + 1);

		for j in 0..n {
			let u = Double::from(self.checked_get(j).unwrap_or(0));
			let v = Double::from(other.checked_get(j).unwrap_or(0));
			let s = u + v + k;
			// proof: any number % B will fit into `Single`.
			w.set(j, (s % B) as Single);
			k = s / B;
		}
		// k is always 0 or 1.
		w.set(n, k as Single);
		w
	}

	/// Subtracts `other` from `self`. self and other do not have to have any particular size.
	/// Given that the `n = max{size(self), size(other)}`, it will produce a number of size `n`.
	///
	/// If `other` is bigger than `self`, `Err(B - borrow)` is returned.
	///
	/// Taken from "The Art of Computer Programming" by D.E. Knuth, vol 2, chapter 4.
	pub fn sub(self, other: &Self) -> Result<Self, Self> {
		let n = self.len().max(other.len());
		let mut k = 0;
		let mut w = Self::with_capacity(n);
		for j in 0..n {
			let s = {
				let u = Double::from(self.checked_get(j).unwrap_or(0));
				let v = Double::from(other.checked_get(j).unwrap_or(0));

				if let Some(v2) = u.checked_sub(v).and_then(|v1| v1.checked_sub(k)) {
					// no borrow is needed. u - v - k can be computed as-is
					let t = v2;
					k = 0;

					t
				} else {
					// borrow is needed. Add a `B` to u, before subtracting.
					// PROOF: addition: `u + B < 2*B`, thus can fit in double.
					// PROOF: subtraction: if `u - v - k < 0`, then `u + B - v - k < B`.
					// NOTE: the order of operations is critical to ensure underflow won't happen.
					let t = u + B - v - k;
					k = 1;

					t
				}
			};
			w.set(j, s as Single);
		}

		if k.is_zero() {
			Ok(w)
		} else {
			Err(w)
		}
	}

	/// Multiplies n-limb number `self` with m-limb number `other`.
	///
	/// The resulting number will always have `n + m` limbs.
	///
	/// This function does not strip the output and returns the original allocated `n + m`
	/// limbs. The caller may strip the output if desired.
	///
	/// Taken from "The Art of Computer Programming" by D.E. Knuth, vol 2, chapter 4.
	pub fn mul(self, other: &Self) -> Self {
		let n = self.len();
		let m = other.len();
		let mut w = Self::with_capacity(m + n);

		for j in 0..n {
			if self.get(j) == 0 {
				// Note: `with_capacity` allocates with 0. Explicitly set j + m to zero if
				// otherwise.
				continue
			}

			let mut k = 0;
			for i in 0..m {
				// PROOF: (B−1) × (B−1) + (B−1) + (B−1) = B^2 −1 < B^2. addition is safe.
				let t = mul_single(self.get(j), other.get(i)) +
					Double::from(w.get(i + j)) +
					Double::from(k);
				w.set(i + j, (t % B) as Single);
				// PROOF: (B^2 - 1) / B < B. conversion is safe.
				k = (t / B) as Single;
			}
			w.set(j + m, k);
		}
		w
	}

	/// Divides `self` by a single limb `other`. This can be used in cases where the original
	/// division cannot work due to the divisor (`other`) being just one limb.
	///
	/// Invariant: `other` cannot be zero.
	pub fn div_unit(self, mut other: Single) -> Self {
		other = other.max(1);
		let n = self.len();
		let mut out = Self::with_capacity(n);
		let mut r: Single = 0;
		// PROOF: (B-1) * B + (B-1) still fits in double
		let with_r = |x: Single, r: Single| Double::from(r) * B + Double::from(x);
		for d in (0..n).rev() {
			let (q, rr) = div_single(with_r(self.get(d), r), other);
			out.set(d, q as Single);
			r = rr;
		}
		out
	}

	/// Divides an `n + m` limb self by a `n` limb `other`. The result is a `m + 1` limb
	/// quotient and a `n` limb remainder, if enabled by passing `true` in `rem` argument, both
	/// in the form of an option's `Ok`.
	///
	/// - requires `other` to be stripped and have no leading zeros.
	/// - requires `self` to be stripped and have no leading zeros.
	/// - requires `other` to have at least two limbs.
	/// - requires `self` to have a greater length compared to `other`.
	///
	/// All arguments are examined without being stripped for the above conditions. If any of
	/// the above fails, `None` is returned.`
	///
	/// Taken from "The Art of Computer Programming" by D.E. Knuth, vol 2, chapter 4.
	pub fn div(self, other: &Self, rem: bool) -> Option<(Self, Self)> {
		if other.len() <= 1 || other.msb() == 0 || self.msb() == 0 || self.len() <= other.len() {
			return None
		}
		let n = other.len();
		let m = self.len() - n;

		let mut q = Self::with_capacity(m + 1);
		let mut r = Self::with_capacity(n);

		// PROOF: 0 <= normalizer_bits < SHIFT 0 <= normalizer < B. all conversions are
		// safe.
		let normalizer_bits = other.msb().leading_zeros() as Single;
		let normalizer = 2_u32.pow(normalizer_bits as u32) as Single;

		// step D1.
		let mut self_norm = self.mul(&Self::from(normalizer));
		let mut other_norm = other.clone().mul(&Self::from(normalizer));

		// defensive only; the mul implementation should always create this.
		self_norm.lpad(n + m + 1);
		other_norm.lstrip();

		// step D2.
		for j in (0..=m).rev() {
			// step D3.0 Find an estimate of q[j], named qhat.
			let (qhat, rhat) = {
				// PROOF: this always fits into `Double`. In the context of Single = u8, and
				// Double = u16, think of 255 * 256 + 255 which is just u16::MAX.
				let dividend =
					Double::from(self_norm.get(j + n)) * B + Double::from(self_norm.get(j + n - 1));
				let divisor = other_norm.get(n - 1);
				div_single(dividend, divisor)
			};

			// D3.1 test qhat
			// replace qhat and rhat with RefCells. This helps share state with the closure
			let qhat = RefCell::new(qhat);
			let rhat = RefCell::new(Double::from(rhat));

			let test = || {
				// decrease qhat if it is bigger than the base (B)
				let qhat_local = *qhat.borrow();
				let rhat_local = *rhat.borrow();
				let predicate_1 = qhat_local >= B;
				let predicate_2 = {
					let lhs = qhat_local * Double::from(other_norm.get(n - 2));
					let rhs = B * rhat_local + Double::from(self_norm.get(j + n - 2));
					lhs > rhs
				};
				if predicate_1 || predicate_2 {
					*qhat.borrow_mut() -= 1;
					*rhat.borrow_mut() += Double::from(other_norm.get(n - 1));
					true
				} else {
					false
				}
			};

			test();
			while (*rhat.borrow() as Double) < B {
				if !test() {
					break
				}
			}

			let qhat = qhat.into_inner();
			// we don't need rhat anymore. just let it go out of scope when it does.

			// step D4
			let lhs = Self { digits: (j..=j + n).rev().map(|d| self_norm.get(d)).collect() };
			let rhs = other_norm.clone().mul(&Self::from(qhat));

			let maybe_sub = lhs.sub(&rhs);
			let mut negative = false;
			let sub = match maybe_sub {
				Ok(t) => t,
				Err(t) => {
					negative = true;
					t
				},
			};
			(j..=j + n).for_each(|d| {
				self_norm.set(d, sub.get(d - j));
			});

			// step D5
			// PROOF: the `test()` specifically decreases qhat until it is below `B`. conversion
			// is safe.
			q.set(j, qhat as Single);

			// step D6: add back if negative happened.
			if negative {
				q.set(j, q.get(j) - 1);
				let u = Self { digits: (j..=j + n).rev().map(|d| self_norm.get(d)).collect() };
				let r = other_norm.clone().add(&u);
				(j..=j + n).rev().for_each(|d| {
					self_norm.set(d, r.get(d - j));
				})
			}
		}

		// if requested, calculate remainder.
		if rem {
			// undo the normalization.
			if normalizer_bits > 0 {
				let s = SHIFT as u32;
				let nb = normalizer_bits;
				for d in 0..n - 1 {
					let v = self_norm.get(d) >> nb | self_norm.get(d + 1).overflowing_shl(s - nb).0;
					r.set(d, v);
				}
				r.set(n - 1, self_norm.get(n - 1) >> normalizer_bits);
			} else {
				r = self_norm;
			}
		}

		Some((q, r))
	}

pub fn from_limbs(limbs: &[Single]) -> Self

Raw constructor from custom limbs. If limbs is empty, Zero::zero() implementation is used.

Examples found in repository

src/helpers_128bit.rs (line 54)

pub fn to_big_uint(x: u128) -> biguint::BigUint {
	let (xh, xl) = split(x);
	let (xhh, xhl) = biguint::split(xh);
	let (xlh, xll) = biguint::split(xl);
	let mut n = biguint::BigUint::from_limbs(&[xhh, xhl, xlh, xll]);
	n.lstrip();
	n
}

pub fn len(&self) -> usize

Number of limbs.

Examples found in repository

src/biguint.rs (line 118)

	pub fn get(&self, index: usize) -> Single {
		self.digits[self.len() - 1 - index]
	}

	/// A naive getter for limb at `index`. Note that the order is lsb -> msb.
	pub fn checked_get(&self, index: usize) -> Option<Single> {
		let i = self.len().checked_sub(1)?;
		let j = i.checked_sub(index)?;
		self.digits.get(j).cloned()
	}

	/// A naive setter for limb at `index`. Note that the order is lsb -> msb.
	///
	/// #### Panics
	///
	/// This panics if index is out of range.
	pub fn set(&mut self, index: usize, value: Single) {
		let len = self.digits.len();
		self.digits[len - 1 - index] = value;
	}

	/// returns the least significant limb of the number.
	///
	/// #### Panics
	///
	/// While the constructor of the type prevents this, this can panic if `self` has no digits.
	pub fn lsb(&self) -> Single {
		self.digits[self.len() - 1]
	}

	/// returns the most significant limb of the number.
	///
	/// #### Panics
	///
	/// While the constructor of the type prevents this, this can panic if `self` has no digits.
	pub fn msb(&self) -> Single {
		self.digits[0]
	}

	/// Strips zeros from the left side (the most significant limbs) of `self`, if any.
	pub fn lstrip(&mut self) {
		// by definition, a big-int number should never have leading zero limbs. This function
		// has the ability to cause this. There is nothing to do if the number already has 1
		// limb only. call it a day and return.
		if self.len().is_zero() {
			return
		}
		let index = self.digits.iter().position(|&elem| elem != 0).unwrap_or(self.len() - 1);

		if index > 0 {
			self.digits = self.digits[index..].to_vec()
		}
	}

	/// Zero-pad `self` from left to reach `size` limbs. Will not make any difference if `self`
	/// is already bigger than `size` limbs.
	pub fn lpad(&mut self, size: usize) {
		let n = self.len();
		if n >= size {
			return
		}
		let pad = size - n;
		let mut new_digits = (0..pad).map(|_| 0).collect::<Vec<Single>>();
		new_digits.extend(self.digits.iter());
		self.digits = new_digits;
	}

	/// Adds `self` with `other`. self and other do not have to have any particular size. Given
	/// that the `n = max{size(self), size(other)}`, it will produce a number with `n + 1`
	/// limbs.
	///
	/// This function does not strip the output and returns the original allocated `n + 1`
	/// limbs. The caller may strip the output if desired.
	///
	/// Taken from "The Art of Computer Programming" by D.E. Knuth, vol 2, chapter 4.
	pub fn add(self, other: &Self) -> Self {
		let n = self.len().max(other.len());
		let mut k: Double = 0;
		let mut w = Self::with_capacity(n + 1);

		for j in 0..n {
			let u = Double::from(self.checked_get(j).unwrap_or(0));
			let v = Double::from(other.checked_get(j).unwrap_or(0));
			let s = u + v + k;
			// proof: any number % B will fit into `Single`.
			w.set(j, (s % B) as Single);
			k = s / B;
		}
		// k is always 0 or 1.
		w.set(n, k as Single);
		w
	}

	/// Subtracts `other` from `self`. self and other do not have to have any particular size.
	/// Given that the `n = max{size(self), size(other)}`, it will produce a number of size `n`.
	///
	/// If `other` is bigger than `self`, `Err(B - borrow)` is returned.
	///
	/// Taken from "The Art of Computer Programming" by D.E. Knuth, vol 2, chapter 4.
	pub fn sub(self, other: &Self) -> Result<Self, Self> {
		let n = self.len().max(other.len());
		let mut k = 0;
		let mut w = Self::with_capacity(n);
		for j in 0..n {
			let s = {
				let u = Double::from(self.checked_get(j).unwrap_or(0));
				let v = Double::from(other.checked_get(j).unwrap_or(0));

				if let Some(v2) = u.checked_sub(v).and_then(|v1| v1.checked_sub(k)) {
					// no borrow is needed. u - v - k can be computed as-is
					let t = v2;
					k = 0;

					t
				} else {
					// borrow is needed. Add a `B` to u, before subtracting.
					// PROOF: addition: `u + B < 2*B`, thus can fit in double.
					// PROOF: subtraction: if `u - v - k < 0`, then `u + B - v - k < B`.
					// NOTE: the order of operations is critical to ensure underflow won't happen.
					let t = u + B - v - k;
					k = 1;

					t
				}
			};
			w.set(j, s as Single);
		}

		if k.is_zero() {
			Ok(w)
		} else {
			Err(w)
		}
	}

	/// Multiplies n-limb number `self` with m-limb number `other`.
	///
	/// The resulting number will always have `n + m` limbs.
	///
	/// This function does not strip the output and returns the original allocated `n + m`
	/// limbs. The caller may strip the output if desired.
	///
	/// Taken from "The Art of Computer Programming" by D.E. Knuth, vol 2, chapter 4.
	pub fn mul(self, other: &Self) -> Self {
		let n = self.len();
		let m = other.len();
		let mut w = Self::with_capacity(m + n);

		for j in 0..n {
			if self.get(j) == 0 {
				// Note: `with_capacity` allocates with 0. Explicitly set j + m to zero if
				// otherwise.
				continue
			}

			let mut k = 0;
			for i in 0..m {
				// PROOF: (B−1) × (B−1) + (B−1) + (B−1) = B^2 −1 < B^2. addition is safe.
				let t = mul_single(self.get(j), other.get(i)) +
					Double::from(w.get(i + j)) +
					Double::from(k);
				w.set(i + j, (t % B) as Single);
				// PROOF: (B^2 - 1) / B < B. conversion is safe.
				k = (t / B) as Single;
			}
			w.set(j + m, k);
		}
		w
	}

	/// Divides `self` by a single limb `other`. This can be used in cases where the original
	/// division cannot work due to the divisor (`other`) being just one limb.
	///
	/// Invariant: `other` cannot be zero.
	pub fn div_unit(self, mut other: Single) -> Self {
		other = other.max(1);
		let n = self.len();
		let mut out = Self::with_capacity(n);
		let mut r: Single = 0;
		// PROOF: (B-1) * B + (B-1) still fits in double
		let with_r = |x: Single, r: Single| Double::from(r) * B + Double::from(x);
		for d in (0..n).rev() {
			let (q, rr) = div_single(with_r(self.get(d), r), other);
			out.set(d, q as Single);
			r = rr;
		}
		out
	}

	/// Divides an `n + m` limb self by a `n` limb `other`. The result is a `m + 1` limb
	/// quotient and a `n` limb remainder, if enabled by passing `true` in `rem` argument, both
	/// in the form of an option's `Ok`.
	///
	/// - requires `other` to be stripped and have no leading zeros.
	/// - requires `self` to be stripped and have no leading zeros.
	/// - requires `other` to have at least two limbs.
	/// - requires `self` to have a greater length compared to `other`.
	///
	/// All arguments are examined without being stripped for the above conditions. If any of
	/// the above fails, `None` is returned.`
	///
	/// Taken from "The Art of Computer Programming" by D.E. Knuth, vol 2, chapter 4.
	pub fn div(self, other: &Self, rem: bool) -> Option<(Self, Self)> {
		if other.len() <= 1 || other.msb() == 0 || self.msb() == 0 || self.len() <= other.len() {
			return None
		}
		let n = other.len();
		let m = self.len() - n;

		let mut q = Self::with_capacity(m + 1);
		let mut r = Self::with_capacity(n);

		// PROOF: 0 <= normalizer_bits < SHIFT 0 <= normalizer < B. all conversions are
		// safe.
		let normalizer_bits = other.msb().leading_zeros() as Single;
		let normalizer = 2_u32.pow(normalizer_bits as u32) as Single;

		// step D1.
		let mut self_norm = self.mul(&Self::from(normalizer));
		let mut other_norm = other.clone().mul(&Self::from(normalizer));

		// defensive only; the mul implementation should always create this.
		self_norm.lpad(n + m + 1);
		other_norm.lstrip();

		// step D2.
		for j in (0..=m).rev() {
			// step D3.0 Find an estimate of q[j], named qhat.
			let (qhat, rhat) = {
				// PROOF: this always fits into `Double`. In the context of Single = u8, and
				// Double = u16, think of 255 * 256 + 255 which is just u16::MAX.
				let dividend =
					Double::from(self_norm.get(j + n)) * B + Double::from(self_norm.get(j + n - 1));
				let divisor = other_norm.get(n - 1);
				div_single(dividend, divisor)
			};

			// D3.1 test qhat
			// replace qhat and rhat with RefCells. This helps share state with the closure
			let qhat = RefCell::new(qhat);
			let rhat = RefCell::new(Double::from(rhat));

			let test = || {
				// decrease qhat if it is bigger than the base (B)
				let qhat_local = *qhat.borrow();
				let rhat_local = *rhat.borrow();
				let predicate_1 = qhat_local >= B;
				let predicate_2 = {
					let lhs = qhat_local * Double::from(other_norm.get(n - 2));
					let rhs = B * rhat_local + Double::from(self_norm.get(j + n - 2));
					lhs > rhs
				};
				if predicate_1 || predicate_2 {
					*qhat.borrow_mut() -= 1;
					*rhat.borrow_mut() += Double::from(other_norm.get(n - 1));
					true
				} else {
					false
				}
			};

			test();
			while (*rhat.borrow() as Double) < B {
				if !test() {
					break
				}
			}

			let qhat = qhat.into_inner();
			// we don't need rhat anymore. just let it go out of scope when it does.

			// step D4
			let lhs = Self { digits: (j..=j + n).rev().map(|d| self_norm.get(d)).collect() };
			let rhs = other_norm.clone().mul(&Self::from(qhat));

			let maybe_sub = lhs.sub(&rhs);
			let mut negative = false;
			let sub = match maybe_sub {
				Ok(t) => t,
				Err(t) => {
					negative = true;
					t
				},
			};
			(j..=j + n).for_each(|d| {
				self_norm.set(d, sub.get(d - j));
			});

			// step D5
			// PROOF: the `test()` specifically decreases qhat until it is below `B`. conversion
			// is safe.
			q.set(j, qhat as Single);

			// step D6: add back if negative happened.
			if negative {
				q.set(j, q.get(j) - 1);
				let u = Self { digits: (j..=j + n).rev().map(|d| self_norm.get(d)).collect() };
				let r = other_norm.clone().add(&u);
				(j..=j + n).rev().for_each(|d| {
					self_norm.set(d, r.get(d - j));
				})
			}
		}

		// if requested, calculate remainder.
		if rem {
			// undo the normalization.
			if normalizer_bits > 0 {
				let s = SHIFT as u32;
				let nb = normalizer_bits;
				for d in 0..n - 1 {
					let v = self_norm.get(d) >> nb | self_norm.get(d + 1).overflowing_shl(s - nb).0;
					r.set(d, v);
				}
				r.set(n - 1, self_norm.get(n - 1) >> normalizer_bits);
			} else {
				r = self_norm;
			}
		}

		Some((q, r))
	}

pub fn get(&self, index: usize) -> Single

A naive getter for limb at index. Note that the order is lsb -> msb.

Panics

This panics if index is out of range.

Examples found in repository

src/biguint.rs (line 266)

	pub fn mul(self, other: &Self) -> Self {
		let n = self.len();
		let m = other.len();
		let mut w = Self::with_capacity(m + n);

		for j in 0..n {
			if self.get(j) == 0 {
				// Note: `with_capacity` allocates with 0. Explicitly set j + m to zero if
				// otherwise.
				continue
			}

			let mut k = 0;
			for i in 0..m {
				// PROOF: (B−1) × (B−1) + (B−1) + (B−1) = B^2 −1 < B^2. addition is safe.
				let t = mul_single(self.get(j), other.get(i)) +
					Double::from(w.get(i + j)) +
					Double::from(k);
				w.set(i + j, (t % B) as Single);
				// PROOF: (B^2 - 1) / B < B. conversion is safe.
				k = (t / B) as Single;
			}
			w.set(j + m, k);
		}
		w
	}

	/// Divides `self` by a single limb `other`. This can be used in cases where the original
	/// division cannot work due to the divisor (`other`) being just one limb.
	///
	/// Invariant: `other` cannot be zero.
	pub fn div_unit(self, mut other: Single) -> Self {
		other = other.max(1);
		let n = self.len();
		let mut out = Self::with_capacity(n);
		let mut r: Single = 0;
		// PROOF: (B-1) * B + (B-1) still fits in double
		let with_r = |x: Single, r: Single| Double::from(r) * B + Double::from(x);
		for d in (0..n).rev() {
			let (q, rr) = div_single(with_r(self.get(d), r), other);
			out.set(d, q as Single);
			r = rr;
		}
		out
	}

	/// Divides an `n + m` limb self by a `n` limb `other`. The result is a `m + 1` limb
	/// quotient and a `n` limb remainder, if enabled by passing `true` in `rem` argument, both
	/// in the form of an option's `Ok`.
	///
	/// - requires `other` to be stripped and have no leading zeros.
	/// - requires `self` to be stripped and have no leading zeros.
	/// - requires `other` to have at least two limbs.
	/// - requires `self` to have a greater length compared to `other`.
	///
	/// All arguments are examined without being stripped for the above conditions. If any of
	/// the above fails, `None` is returned.`
	///
	/// Taken from "The Art of Computer Programming" by D.E. Knuth, vol 2, chapter 4.
	pub fn div(self, other: &Self, rem: bool) -> Option<(Self, Self)> {
		if other.len() <= 1 || other.msb() == 0 || self.msb() == 0 || self.len() <= other.len() {
			return None
		}
		let n = other.len();
		let m = self.len() - n;

		let mut q = Self::with_capacity(m + 1);
		let mut r = Self::with_capacity(n);

		// PROOF: 0 <= normalizer_bits < SHIFT 0 <= normalizer < B. all conversions are
		// safe.
		let normalizer_bits = other.msb().leading_zeros() as Single;
		let normalizer = 2_u32.pow(normalizer_bits as u32) as Single;

		// step D1.
		let mut self_norm = self.mul(&Self::from(normalizer));
		let mut other_norm = other.clone().mul(&Self::from(normalizer));

		// defensive only; the mul implementation should always create this.
		self_norm.lpad(n + m + 1);
		other_norm.lstrip();

		// step D2.
		for j in (0..=m).rev() {
			// step D3.0 Find an estimate of q[j], named qhat.
			let (qhat, rhat) = {
				// PROOF: this always fits into `Double`. In the context of Single = u8, and
				// Double = u16, think of 255 * 256 + 255 which is just u16::MAX.
				let dividend =
					Double::from(self_norm.get(j + n)) * B + Double::from(self_norm.get(j + n - 1));
				let divisor = other_norm.get(n - 1);
				div_single(dividend, divisor)
			};

			// D3.1 test qhat
			// replace qhat and rhat with RefCells. This helps share state with the closure
			let qhat = RefCell::new(qhat);
			let rhat = RefCell::new(Double::from(rhat));

			let test = || {
				// decrease qhat if it is bigger than the base (B)
				let qhat_local = *qhat.borrow();
				let rhat_local = *rhat.borrow();
				let predicate_1 = qhat_local >= B;
				let predicate_2 = {
					let lhs = qhat_local * Double::from(other_norm.get(n - 2));
					let rhs = B * rhat_local + Double::from(self_norm.get(j + n - 2));
					lhs > rhs
				};
				if predicate_1 || predicate_2 {
					*qhat.borrow_mut() -= 1;
					*rhat.borrow_mut() += Double::from(other_norm.get(n - 1));
					true
				} else {
					false
				}
			};

			test();
			while (*rhat.borrow() as Double) < B {
				if !test() {
					break
				}
			}

			let qhat = qhat.into_inner();
			// we don't need rhat anymore. just let it go out of scope when it does.

			// step D4
			let lhs = Self { digits: (j..=j + n).rev().map(|d| self_norm.get(d)).collect() };
			let rhs = other_norm.clone().mul(&Self::from(qhat));

			let maybe_sub = lhs.sub(&rhs);
			let mut negative = false;
			let sub = match maybe_sub {
				Ok(t) => t,
				Err(t) => {
					negative = true;
					t
				},
			};
			(j..=j + n).for_each(|d| {
				self_norm.set(d, sub.get(d - j));
			});

			// step D5
			// PROOF: the `test()` specifically decreases qhat until it is below `B`. conversion
			// is safe.
			q.set(j, qhat as Single);

			// step D6: add back if negative happened.
			if negative {
				q.set(j, q.get(j) - 1);
				let u = Self { digits: (j..=j + n).rev().map(|d| self_norm.get(d)).collect() };
				let r = other_norm.clone().add(&u);
				(j..=j + n).rev().for_each(|d| {
					self_norm.set(d, r.get(d - j));
				})
			}
		}

		// if requested, calculate remainder.
		if rem {
			// undo the normalization.
			if normalizer_bits > 0 {
				let s = SHIFT as u32;
				let nb = normalizer_bits;
				for d in 0..n - 1 {
					let v = self_norm.get(d) >> nb | self_norm.get(d + 1).overflowing_shl(s - nb).0;
					r.set(d, v);
				}
				r.set(n - 1, self_norm.get(n - 1) >> normalizer_bits);
			} else {
				r = self_norm;
			}
		}

		Some((q, r))
	}

pub fn checked_get(&self, index: usize) -> Option<Single>

A naive getter for limb at index. Note that the order is lsb -> msb.

Examples found in repository

src/biguint.rs (line 198)

	pub fn add(self, other: &Self) -> Self {
		let n = self.len().max(other.len());
		let mut k: Double = 0;
		let mut w = Self::with_capacity(n + 1);

		for j in 0..n {
			let u = Double::from(self.checked_get(j).unwrap_or(0));
			let v = Double::from(other.checked_get(j).unwrap_or(0));
			let s = u + v + k;
			// proof: any number % B will fit into `Single`.
			w.set(j, (s % B) as Single);
			k = s / B;
		}
		// k is always 0 or 1.
		w.set(n, k as Single);
		w
	}

	/// Subtracts `other` from `self`. self and other do not have to have any particular size.
	/// Given that the `n = max{size(self), size(other)}`, it will produce a number of size `n`.
	///
	/// If `other` is bigger than `self`, `Err(B - borrow)` is returned.
	///
	/// Taken from "The Art of Computer Programming" by D.E. Knuth, vol 2, chapter 4.
	pub fn sub(self, other: &Self) -> Result<Self, Self> {
		let n = self.len().max(other.len());
		let mut k = 0;
		let mut w = Self::with_capacity(n);
		for j in 0..n {
			let s = {
				let u = Double::from(self.checked_get(j).unwrap_or(0));
				let v = Double::from(other.checked_get(j).unwrap_or(0));

				if let Some(v2) = u.checked_sub(v).and_then(|v1| v1.checked_sub(k)) {
					// no borrow is needed. u - v - k can be computed as-is
					let t = v2;
					k = 0;

					t
				} else {
					// borrow is needed. Add a `B` to u, before subtracting.
					// PROOF: addition: `u + B < 2*B`, thus can fit in double.
					// PROOF: subtraction: if `u - v - k < 0`, then `u + B - v - k < B`.
					// NOTE: the order of operations is critical to ensure underflow won't happen.
					let t = u + B - v - k;
					k = 1;

					t
				}
			};
			w.set(j, s as Single);
		}

		if k.is_zero() {
			Ok(w)
		} else {
			Err(w)
		}
	}

pub fn set(&mut self, index: usize, value: Single)

A naive setter for limb at index. Note that the order is lsb -> msb.

Panics

This panics if index is out of range.

Examples found in repository

src/biguint.rs (line 202)

	pub fn add(self, other: &Self) -> Self {
		let n = self.len().max(other.len());
		let mut k: Double = 0;
		let mut w = Self::with_capacity(n + 1);

		for j in 0..n {
			let u = Double::from(self.checked_get(j).unwrap_or(0));
			let v = Double::from(other.checked_get(j).unwrap_or(0));
			let s = u + v + k;
			// proof: any number % B will fit into `Single`.
			w.set(j, (s % B) as Single);
			k = s / B;
		}
		// k is always 0 or 1.
		w.set(n, k as Single);
		w
	}

	/// Subtracts `other` from `self`. self and other do not have to have any particular size.
	/// Given that the `n = max{size(self), size(other)}`, it will produce a number of size `n`.
	///
	/// If `other` is bigger than `self`, `Err(B - borrow)` is returned.
	///
	/// Taken from "The Art of Computer Programming" by D.E. Knuth, vol 2, chapter 4.
	pub fn sub(self, other: &Self) -> Result<Self, Self> {
		let n = self.len().max(other.len());
		let mut k = 0;
		let mut w = Self::with_capacity(n);
		for j in 0..n {
			let s = {
				let u = Double::from(self.checked_get(j).unwrap_or(0));
				let v = Double::from(other.checked_get(j).unwrap_or(0));

				if let Some(v2) = u.checked_sub(v).and_then(|v1| v1.checked_sub(k)) {
					// no borrow is needed. u - v - k can be computed as-is
					let t = v2;
					k = 0;

					t
				} else {
					// borrow is needed. Add a `B` to u, before subtracting.
					// PROOF: addition: `u + B < 2*B`, thus can fit in double.
					// PROOF: subtraction: if `u - v - k < 0`, then `u + B - v - k < B`.
					// NOTE: the order of operations is critical to ensure underflow won't happen.
					let t = u + B - v - k;
					k = 1;

					t
				}
			};
			w.set(j, s as Single);
		}

		if k.is_zero() {
			Ok(w)
		} else {
			Err(w)
		}
	}

	/// Multiplies n-limb number `self` with m-limb number `other`.
	///
	/// The resulting number will always have `n + m` limbs.
	///
	/// This function does not strip the output and returns the original allocated `n + m`
	/// limbs. The caller may strip the output if desired.
	///
	/// Taken from "The Art of Computer Programming" by D.E. Knuth, vol 2, chapter 4.
	pub fn mul(self, other: &Self) -> Self {
		let n = self.len();
		let m = other.len();
		let mut w = Self::with_capacity(m + n);

		for j in 0..n {
			if self.get(j) == 0 {
				// Note: `with_capacity` allocates with 0. Explicitly set j + m to zero if
				// otherwise.
				continue
			}

			let mut k = 0;
			for i in 0..m {
				// PROOF: (B−1) × (B−1) + (B−1) + (B−1) = B^2 −1 < B^2. addition is safe.
				let t = mul_single(self.get(j), other.get(i)) +
					Double::from(w.get(i + j)) +
					Double::from(k);
				w.set(i + j, (t % B) as Single);
				// PROOF: (B^2 - 1) / B < B. conversion is safe.
				k = (t / B) as Single;
			}
			w.set(j + m, k);
		}
		w
	}

	/// Divides `self` by a single limb `other`. This can be used in cases where the original
	/// division cannot work due to the divisor (`other`) being just one limb.
	///
	/// Invariant: `other` cannot be zero.
	pub fn div_unit(self, mut other: Single) -> Self {
		other = other.max(1);
		let n = self.len();
		let mut out = Self::with_capacity(n);
		let mut r: Single = 0;
		// PROOF: (B-1) * B + (B-1) still fits in double
		let with_r = |x: Single, r: Single| Double::from(r) * B + Double::from(x);
		for d in (0..n).rev() {
			let (q, rr) = div_single(with_r(self.get(d), r), other);
			out.set(d, q as Single);
			r = rr;
		}
		out
	}

	/// Divides an `n + m` limb self by a `n` limb `other`. The result is a `m + 1` limb
	/// quotient and a `n` limb remainder, if enabled by passing `true` in `rem` argument, both
	/// in the form of an option's `Ok`.
	///
	/// - requires `other` to be stripped and have no leading zeros.
	/// - requires `self` to be stripped and have no leading zeros.
	/// - requires `other` to have at least two limbs.
	/// - requires `self` to have a greater length compared to `other`.
	///
	/// All arguments are examined without being stripped for the above conditions. If any of
	/// the above fails, `None` is returned.`
	///
	/// Taken from "The Art of Computer Programming" by D.E. Knuth, vol 2, chapter 4.
	pub fn div(self, other: &Self, rem: bool) -> Option<(Self, Self)> {
		if other.len() <= 1 || other.msb() == 0 || self.msb() == 0 || self.len() <= other.len() {
			return None
		}
		let n = other.len();
		let m = self.len() - n;

		let mut q = Self::with_capacity(m + 1);
		let mut r = Self::with_capacity(n);

		// PROOF: 0 <= normalizer_bits < SHIFT 0 <= normalizer < B. all conversions are
		// safe.
		let normalizer_bits = other.msb().leading_zeros() as Single;
		let normalizer = 2_u32.pow(normalizer_bits as u32) as Single;

		// step D1.
		let mut self_norm = self.mul(&Self::from(normalizer));
		let mut other_norm = other.clone().mul(&Self::from(normalizer));

		// defensive only; the mul implementation should always create this.
		self_norm.lpad(n + m + 1);
		other_norm.lstrip();

		// step D2.
		for j in (0..=m).rev() {
			// step D3.0 Find an estimate of q[j], named qhat.
			let (qhat, rhat) = {
				// PROOF: this always fits into `Double`. In the context of Single = u8, and
				// Double = u16, think of 255 * 256 + 255 which is just u16::MAX.
				let dividend =
					Double::from(self_norm.get(j + n)) * B + Double::from(self_norm.get(j + n - 1));
				let divisor = other_norm.get(n - 1);
				div_single(dividend, divisor)
			};

			// D3.1 test qhat
			// replace qhat and rhat with RefCells. This helps share state with the closure
			let qhat = RefCell::new(qhat);
			let rhat = RefCell::new(Double::from(rhat));

			let test = || {
				// decrease qhat if it is bigger than the base (B)
				let qhat_local = *qhat.borrow();
				let rhat_local = *rhat.borrow();
				let predicate_1 = qhat_local >= B;
				let predicate_2 = {
					let lhs = qhat_local * Double::from(other_norm.get(n - 2));
					let rhs = B * rhat_local + Double::from(self_norm.get(j + n - 2));
					lhs > rhs
				};
				if predicate_1 || predicate_2 {
					*qhat.borrow_mut() -= 1;
					*rhat.borrow_mut() += Double::from(other_norm.get(n - 1));
					true
				} else {
					false
				}
			};

			test();
			while (*rhat.borrow() as Double) < B {
				if !test() {
					break
				}
			}

			let qhat = qhat.into_inner();
			// we don't need rhat anymore. just let it go out of scope when it does.

			// step D4
			let lhs = Self { digits: (j..=j + n).rev().map(|d| self_norm.get(d)).collect() };
			let rhs = other_norm.clone().mul(&Self::from(qhat));

			let maybe_sub = lhs.sub(&rhs);
			let mut negative = false;
			let sub = match maybe_sub {
				Ok(t) => t,
				Err(t) => {
					negative = true;
					t
				},
			};
			(j..=j + n).for_each(|d| {
				self_norm.set(d, sub.get(d - j));
			});

			// step D5
			// PROOF: the `test()` specifically decreases qhat until it is below `B`. conversion
			// is safe.
			q.set(j, qhat as Single);

			// step D6: add back if negative happened.
			if negative {
				q.set(j, q.get(j) - 1);
				let u = Self { digits: (j..=j + n).rev().map(|d| self_norm.get(d)).collect() };
				let r = other_norm.clone().add(&u);
				(j..=j + n).rev().for_each(|d| {
					self_norm.set(d, r.get(d - j));
				})
			}
		}

		// if requested, calculate remainder.
		if rem {
			// undo the normalization.
			if normalizer_bits > 0 {
				let s = SHIFT as u32;
				let nb = normalizer_bits;
				for d in 0..n - 1 {
					let v = self_norm.get(d) >> nb | self_norm.get(d + 1).overflowing_shl(s - nb).0;
					r.set(d, v);
				}
				r.set(n - 1, self_norm.get(n - 1) >> normalizer_bits);
			} else {
				r = self_norm;
			}
		}

		Some((q, r))
	}

pub fn lsb(&self) -> Single

returns the least significant limb of the number.

Panics

While the constructor of the type prevents this, this can panic if self has no digits.

pub fn msb(&self) -> Single

returns the most significant limb of the number.

Panics

While the constructor of the type prevents this, this can panic if self has no digits.

Examples found in repository

src/biguint.rs (line 320)

	pub fn div(self, other: &Self, rem: bool) -> Option<(Self, Self)> {
		if other.len() <= 1 || other.msb() == 0 || self.msb() == 0 || self.len() <= other.len() {
			return None
		}
		let n = other.len();
		let m = self.len() - n;

		let mut q = Self::with_capacity(m + 1);
		let mut r = Self::with_capacity(n);

		// PROOF: 0 <= normalizer_bits < SHIFT 0 <= normalizer < B. all conversions are
		// safe.
		let normalizer_bits = other.msb().leading_zeros() as Single;
		let normalizer = 2_u32.pow(normalizer_bits as u32) as Single;

		// step D1.
		let mut self_norm = self.mul(&Self::from(normalizer));
		let mut other_norm = other.clone().mul(&Self::from(normalizer));

		// defensive only; the mul implementation should always create this.
		self_norm.lpad(n + m + 1);
		other_norm.lstrip();

		// step D2.
		for j in (0..=m).rev() {
			// step D3.0 Find an estimate of q[j], named qhat.
			let (qhat, rhat) = {
				// PROOF: this always fits into `Double`. In the context of Single = u8, and
				// Double = u16, think of 255 * 256 + 255 which is just u16::MAX.
				let dividend =
					Double::from(self_norm.get(j + n)) * B + Double::from(self_norm.get(j + n - 1));
				let divisor = other_norm.get(n - 1);
				div_single(dividend, divisor)
			};

			// D3.1 test qhat
			// replace qhat and rhat with RefCells. This helps share state with the closure
			let qhat = RefCell::new(qhat);
			let rhat = RefCell::new(Double::from(rhat));

			let test = || {
				// decrease qhat if it is bigger than the base (B)
				let qhat_local = *qhat.borrow();
				let rhat_local = *rhat.borrow();
				let predicate_1 = qhat_local >= B;
				let predicate_2 = {
					let lhs = qhat_local * Double::from(other_norm.get(n - 2));
					let rhs = B * rhat_local + Double::from(self_norm.get(j + n - 2));
					lhs > rhs
				};
				if predicate_1 || predicate_2 {
					*qhat.borrow_mut() -= 1;
					*rhat.borrow_mut() += Double::from(other_norm.get(n - 1));
					true
				} else {
					false
				}
			};

			test();
			while (*rhat.borrow() as Double) < B {
				if !test() {
					break
				}
			}

			let qhat = qhat.into_inner();
			// we don't need rhat anymore. just let it go out of scope when it does.

			// step D4
			let lhs = Self { digits: (j..=j + n).rev().map(|d| self_norm.get(d)).collect() };
			let rhs = other_norm.clone().mul(&Self::from(qhat));

			let maybe_sub = lhs.sub(&rhs);
			let mut negative = false;
			let sub = match maybe_sub {
				Ok(t) => t,
				Err(t) => {
					negative = true;
					t
				},
			};
			(j..=j + n).for_each(|d| {
				self_norm.set(d, sub.get(d - j));
			});

			// step D5
			// PROOF: the `test()` specifically decreases qhat until it is below `B`. conversion
			// is safe.
			q.set(j, qhat as Single);

			// step D6: add back if negative happened.
			if negative {
				q.set(j, q.get(j) - 1);
				let u = Self { digits: (j..=j + n).rev().map(|d| self_norm.get(d)).collect() };
				let r = other_norm.clone().add(&u);
				(j..=j + n).rev().for_each(|d| {
					self_norm.set(d, r.get(d - j));
				})
			}
		}

		// if requested, calculate remainder.
		if rem {
			// undo the normalization.
			if normalizer_bits > 0 {
				let s = SHIFT as u32;
				let nb = normalizer_bits;
				for d in 0..n - 1 {
					let v = self_norm.get(d) >> nb | self_norm.get(d + 1).overflowing_shl(s - nb).0;
					r.set(d, v);
				}
				r.set(n - 1, self_norm.get(n - 1) >> normalizer_bits);
			} else {
				r = self_norm;
			}
		}

		Some((q, r))
	}

pub fn lstrip(&mut self)

Strips zeros from the left side (the most significant limbs) of self, if any.

Examples found in repository

src/helpers_128bit.rs (line 55)

pub fn to_big_uint(x: u128) -> biguint::BigUint {
	let (xh, xl) = split(x);
	let (xhh, xhl) = biguint::split(xh);
	let (xlh, xll) = biguint::split(xl);
	let mut n = biguint::BigUint::from_limbs(&[xhh, xhl, xlh, xll]);
	n.lstrip();
	n
}

src/biguint.rs (line 340)

	pub fn div(self, other: &Self, rem: bool) -> Option<(Self, Self)> {
		if other.len() <= 1 || other.msb() == 0 || self.msb() == 0 || self.len() <= other.len() {
			return None
		}
		let n = other.len();
		let m = self.len() - n;

		let mut q = Self::with_capacity(m + 1);
		let mut r = Self::with_capacity(n);

		// PROOF: 0 <= normalizer_bits < SHIFT 0 <= normalizer < B. all conversions are
		// safe.
		let normalizer_bits = other.msb().leading_zeros() as Single;
		let normalizer = 2_u32.pow(normalizer_bits as u32) as Single;

		// step D1.
		let mut self_norm = self.mul(&Self::from(normalizer));
		let mut other_norm = other.clone().mul(&Self::from(normalizer));

		// defensive only; the mul implementation should always create this.
		self_norm.lpad(n + m + 1);
		other_norm.lstrip();

		// step D2.
		for j in (0..=m).rev() {
			// step D3.0 Find an estimate of q[j], named qhat.
			let (qhat, rhat) = {
				// PROOF: this always fits into `Double`. In the context of Single = u8, and
				// Double = u16, think of 255 * 256 + 255 which is just u16::MAX.
				let dividend =
					Double::from(self_norm.get(j + n)) * B + Double::from(self_norm.get(j + n - 1));
				let divisor = other_norm.get(n - 1);
				div_single(dividend, divisor)
			};

			// D3.1 test qhat
			// replace qhat and rhat with RefCells. This helps share state with the closure
			let qhat = RefCell::new(qhat);
			let rhat = RefCell::new(Double::from(rhat));

			let test = || {
				// decrease qhat if it is bigger than the base (B)
				let qhat_local = *qhat.borrow();
				let rhat_local = *rhat.borrow();
				let predicate_1 = qhat_local >= B;
				let predicate_2 = {
					let lhs = qhat_local * Double::from(other_norm.get(n - 2));
					let rhs = B * rhat_local + Double::from(self_norm.get(j + n - 2));
					lhs > rhs
				};
				if predicate_1 || predicate_2 {
					*qhat.borrow_mut() -= 1;
					*rhat.borrow_mut() += Double::from(other_norm.get(n - 1));
					true
				} else {
					false
				}
			};

			test();
			while (*rhat.borrow() as Double) < B {
				if !test() {
					break
				}
			}

			let qhat = qhat.into_inner();
			// we don't need rhat anymore. just let it go out of scope when it does.

			// step D4
			let lhs = Self { digits: (j..=j + n).rev().map(|d| self_norm.get(d)).collect() };
			let rhs = other_norm.clone().mul(&Self::from(qhat));

			let maybe_sub = lhs.sub(&rhs);
			let mut negative = false;
			let sub = match maybe_sub {
				Ok(t) => t,
				Err(t) => {
					negative = true;
					t
				},
			};
			(j..=j + n).for_each(|d| {
				self_norm.set(d, sub.get(d - j));
			});

			// step D5
			// PROOF: the `test()` specifically decreases qhat until it is below `B`. conversion
			// is safe.
			q.set(j, qhat as Single);

			// step D6: add back if negative happened.
			if negative {
				q.set(j, q.get(j) - 1);
				let u = Self { digits: (j..=j + n).rev().map(|d| self_norm.get(d)).collect() };
				let r = other_norm.clone().add(&u);
				(j..=j + n).rev().for_each(|d| {
					self_norm.set(d, r.get(d - j));
				})
			}
		}

		// if requested, calculate remainder.
		if rem {
			// undo the normalization.
			if normalizer_bits > 0 {
				let s = SHIFT as u32;
				let nb = normalizer_bits;
				for d in 0..n - 1 {
					let v = self_norm.get(d) >> nb | self_norm.get(d + 1).overflowing_shl(s - nb).0;
					r.set(d, v);
				}
				r.set(n - 1, self_norm.get(n - 1) >> normalizer_bits);
			} else {
				r = self_norm;
			}
		}

		Some((q, r))
	}

pub fn lpad(&mut self, size: usize)

Zero-pad self from left to reach size limbs. Will not make any difference if self is already bigger than size limbs.

Examples found in repository

src/biguint.rs (line 339)

	pub fn div(self, other: &Self, rem: bool) -> Option<(Self, Self)> {
		if other.len() <= 1 || other.msb() == 0 || self.msb() == 0 || self.len() <= other.len() {
			return None
		}
		let n = other.len();
		let m = self.len() - n;

		let mut q = Self::with_capacity(m + 1);
		let mut r = Self::with_capacity(n);

		// PROOF: 0 <= normalizer_bits < SHIFT 0 <= normalizer < B. all conversions are
		// safe.
		let normalizer_bits = other.msb().leading_zeros() as Single;
		let normalizer = 2_u32.pow(normalizer_bits as u32) as Single;

		// step D1.
		let mut self_norm = self.mul(&Self::from(normalizer));
		let mut other_norm = other.clone().mul(&Self::from(normalizer));

		// defensive only; the mul implementation should always create this.
		self_norm.lpad(n + m + 1);
		other_norm.lstrip();

		// step D2.
		for j in (0..=m).rev() {
			// step D3.0 Find an estimate of q[j], named qhat.
			let (qhat, rhat) = {
				// PROOF: this always fits into `Double`. In the context of Single = u8, and
				// Double = u16, think of 255 * 256 + 255 which is just u16::MAX.
				let dividend =
					Double::from(self_norm.get(j + n)) * B + Double::from(self_norm.get(j + n - 1));
				let divisor = other_norm.get(n - 1);
				div_single(dividend, divisor)
			};

			// D3.1 test qhat
			// replace qhat and rhat with RefCells. This helps share state with the closure
			let qhat = RefCell::new(qhat);
			let rhat = RefCell::new(Double::from(rhat));

			let test = || {
				// decrease qhat if it is bigger than the base (B)
				let qhat_local = *qhat.borrow();
				let rhat_local = *rhat.borrow();
				let predicate_1 = qhat_local >= B;
				let predicate_2 = {
					let lhs = qhat_local * Double::from(other_norm.get(n - 2));
					let rhs = B * rhat_local + Double::from(self_norm.get(j + n - 2));
					lhs > rhs
				};
				if predicate_1 || predicate_2 {
					*qhat.borrow_mut() -= 1;
					*rhat.borrow_mut() += Double::from(other_norm.get(n - 1));
					true
				} else {
					false
				}
			};

			test();
			while (*rhat.borrow() as Double) < B {
				if !test() {
					break
				}
			}

			let qhat = qhat.into_inner();
			// we don't need rhat anymore. just let it go out of scope when it does.

			// step D4
			let lhs = Self { digits: (j..=j + n).rev().map(|d| self_norm.get(d)).collect() };
			let rhs = other_norm.clone().mul(&Self::from(qhat));

			let maybe_sub = lhs.sub(&rhs);
			let mut negative = false;
			let sub = match maybe_sub {
				Ok(t) => t,
				Err(t) => {
					negative = true;
					t
				},
			};
			(j..=j + n).for_each(|d| {
				self_norm.set(d, sub.get(d - j));
			});

			// step D5
			// PROOF: the `test()` specifically decreases qhat until it is below `B`. conversion
			// is safe.
			q.set(j, qhat as Single);

			// step D6: add back if negative happened.
			if negative {
				q.set(j, q.get(j) - 1);
				let u = Self { digits: (j..=j + n).rev().map(|d| self_norm.get(d)).collect() };
				let r = other_norm.clone().add(&u);
				(j..=j + n).rev().for_each(|d| {
					self_norm.set(d, r.get(d - j));
				})
			}
		}

		// if requested, calculate remainder.
		if rem {
			// undo the normalization.
			if normalizer_bits > 0 {
				let s = SHIFT as u32;
				let nb = normalizer_bits;
				for d in 0..n - 1 {
					let v = self_norm.get(d) >> nb | self_norm.get(d + 1).overflowing_shl(s - nb).0;
					r.set(d, v);
				}
				r.set(n - 1, self_norm.get(n - 1) >> normalizer_bits);
			} else {
				r = self_norm;
			}
		}

		Some((q, r))
	}

pub fn add(self, other: &Self) -> Self

Adds self with other. self and other do not have to have any particular size. Given that the n = max{size(self), size(other)}, it will produce a number with n + 1 limbs.

This function does not strip the output and returns the original allocated n + 1 limbs. The caller may strip the output if desired.

Taken from “The Art of Computer Programming” by D.E. Knuth, vol 2, chapter 4.

Examples found in repository

src/biguint.rs (line 414)

	pub fn div(self, other: &Self, rem: bool) -> Option<(Self, Self)> {
		if other.len() <= 1 || other.msb() == 0 || self.msb() == 0 || self.len() <= other.len() {
			return None
		}
		let n = other.len();
		let m = self.len() - n;

		let mut q = Self::with_capacity(m + 1);
		let mut r = Self::with_capacity(n);

		// PROOF: 0 <= normalizer_bits < SHIFT 0 <= normalizer < B. all conversions are
		// safe.
		let normalizer_bits = other.msb().leading_zeros() as Single;
		let normalizer = 2_u32.pow(normalizer_bits as u32) as Single;

		// step D1.
		let mut self_norm = self.mul(&Self::from(normalizer));
		let mut other_norm = other.clone().mul(&Self::from(normalizer));

		// defensive only; the mul implementation should always create this.
		self_norm.lpad(n + m + 1);
		other_norm.lstrip();

		// step D2.
		for j in (0..=m).rev() {
			// step D3.0 Find an estimate of q[j], named qhat.
			let (qhat, rhat) = {
				// PROOF: this always fits into `Double`. In the context of Single = u8, and
				// Double = u16, think of 255 * 256 + 255 which is just u16::MAX.
				let dividend =
					Double::from(self_norm.get(j + n)) * B + Double::from(self_norm.get(j + n - 1));
				let divisor = other_norm.get(n - 1);
				div_single(dividend, divisor)
			};

			// D3.1 test qhat
			// replace qhat and rhat with RefCells. This helps share state with the closure
			let qhat = RefCell::new(qhat);
			let rhat = RefCell::new(Double::from(rhat));

			let test = || {
				// decrease qhat if it is bigger than the base (B)
				let qhat_local = *qhat.borrow();
				let rhat_local = *rhat.borrow();
				let predicate_1 = qhat_local >= B;
				let predicate_2 = {
					let lhs = qhat_local * Double::from(other_norm.get(n - 2));
					let rhs = B * rhat_local + Double::from(self_norm.get(j + n - 2));
					lhs > rhs
				};
				if predicate_1 || predicate_2 {
					*qhat.borrow_mut() -= 1;
					*rhat.borrow_mut() += Double::from(other_norm.get(n - 1));
					true
				} else {
					false
				}
			};

			test();
			while (*rhat.borrow() as Double) < B {
				if !test() {
					break
				}
			}

			let qhat = qhat.into_inner();
			// we don't need rhat anymore. just let it go out of scope when it does.

			// step D4
			let lhs = Self { digits: (j..=j + n).rev().map(|d| self_norm.get(d)).collect() };
			let rhs = other_norm.clone().mul(&Self::from(qhat));

			let maybe_sub = lhs.sub(&rhs);
			let mut negative = false;
			let sub = match maybe_sub {
				Ok(t) => t,
				Err(t) => {
					negative = true;
					t
				},
			};
			(j..=j + n).for_each(|d| {
				self_norm.set(d, sub.get(d - j));
			});

			// step D5
			// PROOF: the `test()` specifically decreases qhat until it is below `B`. conversion
			// is safe.
			q.set(j, qhat as Single);

			// step D6: add back if negative happened.
			if negative {
				q.set(j, q.get(j) - 1);
				let u = Self { digits: (j..=j + n).rev().map(|d| self_norm.get(d)).collect() };
				let r = other_norm.clone().add(&u);
				(j..=j + n).rev().for_each(|d| {
					self_norm.set(d, r.get(d - j));
				})
			}
		}

		// if requested, calculate remainder.
		if rem {
			// undo the normalization.
			if normalizer_bits > 0 {
				let s = SHIFT as u32;
				let nb = normalizer_bits;
				for d in 0..n - 1 {
					let v = self_norm.get(d) >> nb | self_norm.get(d + 1).overflowing_shl(s - nb).0;
					r.set(d, v);
				}
				r.set(n - 1, self_norm.get(n - 1) >> normalizer_bits);
			} else {
				r = self_norm;
			}
		}

		Some((q, r))
	}
}

impl sp_std::fmt::Debug for BigUint {
	#[cfg(feature = "std")]
	fn fmt(&self, f: &mut sp_std::fmt::Formatter<'_>) -> sp_std::fmt::Result {
		write!(
			f,
			"BigUint {{ {:?} ({:?})}}",
			self.digits,
			u128::try_from(self.clone()).unwrap_or(0),
		)
	}

	#[cfg(not(feature = "std"))]
	fn fmt(&self, _: &mut sp_std::fmt::Formatter<'_>) -> sp_std::fmt::Result {
		Ok(())
	}
}

impl PartialEq for BigUint {
	fn eq(&self, other: &Self) -> bool {
		self.cmp(other) == Ordering::Equal
	}
}

impl Eq for BigUint {}

impl Ord for BigUint {
	fn cmp(&self, other: &Self) -> Ordering {
		let lhs_first = self.digits.iter().position(|&e| e != 0);
		let rhs_first = other.digits.iter().position(|&e| e != 0);

		match (lhs_first, rhs_first) {
			// edge cases that should not happen. This basically means that one or both were
			// zero.
			(None, None) => Ordering::Equal,
			(Some(_), None) => Ordering::Greater,
			(None, Some(_)) => Ordering::Less,
			(Some(lhs_idx), Some(rhs_idx)) => {
				let lhs = &self.digits[lhs_idx..];
				let rhs = &other.digits[rhs_idx..];
				let len_cmp = lhs.len().cmp(&rhs.len());
				match len_cmp {
					Ordering::Equal => lhs.cmp(rhs),
					_ => len_cmp,
				}
			},
		}
	}
}

impl PartialOrd for BigUint {
	fn partial_cmp(&self, other: &Self) -> Option<Ordering> {
		Some(self.cmp(other))
	}
}

impl ops::Add for BigUint {
	type Output = Self;
	fn add(self, rhs: Self) -> Self::Output {
		self.add(&rhs)
	}

pub fn sub(self, other: &Self) -> Result<Self, Self>

Subtracts other from self. self and other do not have to have any particular size. Given that the n = max{size(self), size(other)}, it will produce a number of size n.

If other is bigger than self, Err(B - borrow) is returned.

Taken from “The Art of Computer Programming” by D.E. Knuth, vol 2, chapter 4.

Examples found in repository

src/biguint.rs (line 392)

	pub fn div(self, other: &Self, rem: bool) -> Option<(Self, Self)> {
		if other.len() <= 1 || other.msb() == 0 || self.msb() == 0 || self.len() <= other.len() {
			return None
		}
		let n = other.len();
		let m = self.len() - n;

		let mut q = Self::with_capacity(m + 1);
		let mut r = Self::with_capacity(n);

		// PROOF: 0 <= normalizer_bits < SHIFT 0 <= normalizer < B. all conversions are
		// safe.
		let normalizer_bits = other.msb().leading_zeros() as Single;
		let normalizer = 2_u32.pow(normalizer_bits as u32) as Single;

		// step D1.
		let mut self_norm = self.mul(&Self::from(normalizer));
		let mut other_norm = other.clone().mul(&Self::from(normalizer));

		// defensive only; the mul implementation should always create this.
		self_norm.lpad(n + m + 1);
		other_norm.lstrip();

		// step D2.
		for j in (0..=m).rev() {
			// step D3.0 Find an estimate of q[j], named qhat.
			let (qhat, rhat) = {
				// PROOF: this always fits into `Double`. In the context of Single = u8, and
				// Double = u16, think of 255 * 256 + 255 which is just u16::MAX.
				let dividend =
					Double::from(self_norm.get(j + n)) * B + Double::from(self_norm.get(j + n - 1));
				let divisor = other_norm.get(n - 1);
				div_single(dividend, divisor)
			};

			// D3.1 test qhat
			// replace qhat and rhat with RefCells. This helps share state with the closure
			let qhat = RefCell::new(qhat);
			let rhat = RefCell::new(Double::from(rhat));

			let test = || {
				// decrease qhat if it is bigger than the base (B)
				let qhat_local = *qhat.borrow();
				let rhat_local = *rhat.borrow();
				let predicate_1 = qhat_local >= B;
				let predicate_2 = {
					let lhs = qhat_local * Double::from(other_norm.get(n - 2));
					let rhs = B * rhat_local + Double::from(self_norm.get(j + n - 2));
					lhs > rhs
				};
				if predicate_1 || predicate_2 {
					*qhat.borrow_mut() -= 1;
					*rhat.borrow_mut() += Double::from(other_norm.get(n - 1));
					true
				} else {
					false
				}
			};

			test();
			while (*rhat.borrow() as Double) < B {
				if !test() {
					break
				}
			}

			let qhat = qhat.into_inner();
			// we don't need rhat anymore. just let it go out of scope when it does.

			// step D4
			let lhs = Self { digits: (j..=j + n).rev().map(|d| self_norm.get(d)).collect() };
			let rhs = other_norm.clone().mul(&Self::from(qhat));

			let maybe_sub = lhs.sub(&rhs);
			let mut negative = false;
			let sub = match maybe_sub {
				Ok(t) => t,
				Err(t) => {
					negative = true;
					t
				},
			};
			(j..=j + n).for_each(|d| {
				self_norm.set(d, sub.get(d - j));
			});

			// step D5
			// PROOF: the `test()` specifically decreases qhat until it is below `B`. conversion
			// is safe.
			q.set(j, qhat as Single);

			// step D6: add back if negative happened.
			if negative {
				q.set(j, q.get(j) - 1);
				let u = Self { digits: (j..=j + n).rev().map(|d| self_norm.get(d)).collect() };
				let r = other_norm.clone().add(&u);
				(j..=j + n).rev().for_each(|d| {
					self_norm.set(d, r.get(d - j));
				})
			}
		}

		// if requested, calculate remainder.
		if rem {
			// undo the normalization.
			if normalizer_bits > 0 {
				let s = SHIFT as u32;
				let nb = normalizer_bits;
				for d in 0..n - 1 {
					let v = self_norm.get(d) >> nb | self_norm.get(d + 1).overflowing_shl(s - nb).0;
					r.set(d, v);
				}
				r.set(n - 1, self_norm.get(n - 1) >> normalizer_bits);
			} else {
				r = self_norm;
			}
		}

		Some((q, r))
	}
}

impl sp_std::fmt::Debug for BigUint {
	#[cfg(feature = "std")]
	fn fmt(&self, f: &mut sp_std::fmt::Formatter<'_>) -> sp_std::fmt::Result {
		write!(
			f,
			"BigUint {{ {:?} ({:?})}}",
			self.digits,
			u128::try_from(self.clone()).unwrap_or(0),
		)
	}

	#[cfg(not(feature = "std"))]
	fn fmt(&self, _: &mut sp_std::fmt::Formatter<'_>) -> sp_std::fmt::Result {
		Ok(())
	}
}

impl PartialEq for BigUint {
	fn eq(&self, other: &Self) -> bool {
		self.cmp(other) == Ordering::Equal
	}
}

impl Eq for BigUint {}

impl Ord for BigUint {
	fn cmp(&self, other: &Self) -> Ordering {
		let lhs_first = self.digits.iter().position(|&e| e != 0);
		let rhs_first = other.digits.iter().position(|&e| e != 0);

		match (lhs_first, rhs_first) {
			// edge cases that should not happen. This basically means that one or both were
			// zero.
			(None, None) => Ordering::Equal,
			(Some(_), None) => Ordering::Greater,
			(None, Some(_)) => Ordering::Less,
			(Some(lhs_idx), Some(rhs_idx)) => {
				let lhs = &self.digits[lhs_idx..];
				let rhs = &other.digits[rhs_idx..];
				let len_cmp = lhs.len().cmp(&rhs.len());
				match len_cmp {
					Ordering::Equal => lhs.cmp(rhs),
					_ => len_cmp,
				}
			},
		}
	}
}

impl PartialOrd for BigUint {
	fn partial_cmp(&self, other: &Self) -> Option<Ordering> {
		Some(self.cmp(other))
	}
}

impl ops::Add for BigUint {
	type Output = Self;
	fn add(self, rhs: Self) -> Self::Output {
		self.add(&rhs)
	}
}

impl ops::Sub for BigUint {
	type Output = Self;
	fn sub(self, rhs: Self) -> Self::Output {
		self.sub(&rhs).unwrap_or_else(|e| e)
	}

pub fn mul(self, other: &Self) -> Self

Multiplies n-limb number self with m-limb number other.

The resulting number will always have n + m limbs.

This function does not strip the output and returns the original allocated n + m limbs. The caller may strip the output if desired.

Taken from “The Art of Computer Programming” by D.E. Knuth, vol 2, chapter 4.

Examples found in repository

src/rational.rs (line 73)

	fn cmp(&self, other: &Self) -> Ordering {
		// handle some edge cases.
		if self.d() == other.d() {
			self.n().cmp(other.n())
		} else if self.d().is_zero() {
			Ordering::Greater
		} else if other.d().is_zero() {
			Ordering::Less
		} else {
			// (a/b) cmp (c/d) => (a*d) cmp (c*b)
			self.n().clone().mul(other.d()).cmp(&other.n().clone().mul(self.d()))
		}
	}

src/biguint.rs (line 335)

	pub fn div(self, other: &Self, rem: bool) -> Option<(Self, Self)> {
		if other.len() <= 1 || other.msb() == 0 || self.msb() == 0 || self.len() <= other.len() {
			return None
		}
		let n = other.len();
		let m = self.len() - n;

		let mut q = Self::with_capacity(m + 1);
		let mut r = Self::with_capacity(n);

		// PROOF: 0 <= normalizer_bits < SHIFT 0 <= normalizer < B. all conversions are
		// safe.
		let normalizer_bits = other.msb().leading_zeros() as Single;
		let normalizer = 2_u32.pow(normalizer_bits as u32) as Single;

		// step D1.
		let mut self_norm = self.mul(&Self::from(normalizer));
		let mut other_norm = other.clone().mul(&Self::from(normalizer));

		// defensive only; the mul implementation should always create this.
		self_norm.lpad(n + m + 1);
		other_norm.lstrip();

		// step D2.
		for j in (0..=m).rev() {
			// step D3.0 Find an estimate of q[j], named qhat.
			let (qhat, rhat) = {
				// PROOF: this always fits into `Double`. In the context of Single = u8, and
				// Double = u16, think of 255 * 256 + 255 which is just u16::MAX.
				let dividend =
					Double::from(self_norm.get(j + n)) * B + Double::from(self_norm.get(j + n - 1));
				let divisor = other_norm.get(n - 1);
				div_single(dividend, divisor)
			};

			// D3.1 test qhat
			// replace qhat and rhat with RefCells. This helps share state with the closure
			let qhat = RefCell::new(qhat);
			let rhat = RefCell::new(Double::from(rhat));

			let test = || {
				// decrease qhat if it is bigger than the base (B)
				let qhat_local = *qhat.borrow();
				let rhat_local = *rhat.borrow();
				let predicate_1 = qhat_local >= B;
				let predicate_2 = {
					let lhs = qhat_local * Double::from(other_norm.get(n - 2));
					let rhs = B * rhat_local + Double::from(self_norm.get(j + n - 2));
					lhs > rhs
				};
				if predicate_1 || predicate_2 {
					*qhat.borrow_mut() -= 1;
					*rhat.borrow_mut() += Double::from(other_norm.get(n - 1));
					true
				} else {
					false
				}
			};

			test();
			while (*rhat.borrow() as Double) < B {
				if !test() {
					break
				}
			}

			let qhat = qhat.into_inner();
			// we don't need rhat anymore. just let it go out of scope when it does.

			// step D4
			let lhs = Self { digits: (j..=j + n).rev().map(|d| self_norm.get(d)).collect() };
			let rhs = other_norm.clone().mul(&Self::from(qhat));

			let maybe_sub = lhs.sub(&rhs);
			let mut negative = false;
			let sub = match maybe_sub {
				Ok(t) => t,
				Err(t) => {
					negative = true;
					t
				},
			};
			(j..=j + n).for_each(|d| {
				self_norm.set(d, sub.get(d - j));
			});

			// step D5
			// PROOF: the `test()` specifically decreases qhat until it is below `B`. conversion
			// is safe.
			q.set(j, qhat as Single);

			// step D6: add back if negative happened.
			if negative {
				q.set(j, q.get(j) - 1);
				let u = Self { digits: (j..=j + n).rev().map(|d| self_norm.get(d)).collect() };
				let r = other_norm.clone().add(&u);
				(j..=j + n).rev().for_each(|d| {
					self_norm.set(d, r.get(d - j));
				})
			}
		}

		// if requested, calculate remainder.
		if rem {
			// undo the normalization.
			if normalizer_bits > 0 {
				let s = SHIFT as u32;
				let nb = normalizer_bits;
				for d in 0..n - 1 {
					let v = self_norm.get(d) >> nb | self_norm.get(d + 1).overflowing_shl(s - nb).0;
					r.set(d, v);
				}
				r.set(n - 1, self_norm.get(n - 1) >> normalizer_bits);
			} else {
				r = self_norm;
			}
		}

		Some((q, r))
	}
}

impl sp_std::fmt::Debug for BigUint {
	#[cfg(feature = "std")]
	fn fmt(&self, f: &mut sp_std::fmt::Formatter<'_>) -> sp_std::fmt::Result {
		write!(
			f,
			"BigUint {{ {:?} ({:?})}}",
			self.digits,
			u128::try_from(self.clone()).unwrap_or(0),
		)
	}

	#[cfg(not(feature = "std"))]
	fn fmt(&self, _: &mut sp_std::fmt::Formatter<'_>) -> sp_std::fmt::Result {
		Ok(())
	}
}

impl PartialEq for BigUint {
	fn eq(&self, other: &Self) -> bool {
		self.cmp(other) == Ordering::Equal
	}
}

impl Eq for BigUint {}

impl Ord for BigUint {
	fn cmp(&self, other: &Self) -> Ordering {
		let lhs_first = self.digits.iter().position(|&e| e != 0);
		let rhs_first = other.digits.iter().position(|&e| e != 0);

		match (lhs_first, rhs_first) {
			// edge cases that should not happen. This basically means that one or both were
			// zero.
			(None, None) => Ordering::Equal,
			(Some(_), None) => Ordering::Greater,
			(None, Some(_)) => Ordering::Less,
			(Some(lhs_idx), Some(rhs_idx)) => {
				let lhs = &self.digits[lhs_idx..];
				let rhs = &other.digits[rhs_idx..];
				let len_cmp = lhs.len().cmp(&rhs.len());
				match len_cmp {
					Ordering::Equal => lhs.cmp(rhs),
					_ => len_cmp,
				}
			},
		}
	}
}

impl PartialOrd for BigUint {
	fn partial_cmp(&self, other: &Self) -> Option<Ordering> {
		Some(self.cmp(other))
	}
}

impl ops::Add for BigUint {
	type Output = Self;
	fn add(self, rhs: Self) -> Self::Output {
		self.add(&rhs)
	}
}

impl ops::Sub for BigUint {
	type Output = Self;
	fn sub(self, rhs: Self) -> Self::Output {
		self.sub(&rhs).unwrap_or_else(|e| e)
	}
}

impl ops::Mul for BigUint {
	type Output = Self;
	fn mul(self, rhs: Self) -> Self::Output {
		self.mul(&rhs)
	}

pub fn div_unit(self, other: Single) -> Self

Divides self by a single limb other. This can be used in cases where the original division cannot work due to the divisor (other) being just one limb.

Invariant: other cannot be zero.

pub fn div(self, other: &Self, rem: bool) -> Option<(Self, Self)>

Divides an n + m limb self by a n limb other. The result is a m + 1 limb quotient and a n limb remainder, if enabled by passing true in rem argument, both in the form of an option’s Ok.

• requires other to be stripped and have no leading zeros.
• requires self to be stripped and have no leading zeros.
• requires other to have at least two limbs.
• requires self to have a greater length compared to other.

All arguments are examined without being stripped for the above conditions. If any of the above fails, None is returned.`

Taken from “The Art of Computer Programming” by D.E. Knuth, vol 2, chapter 4.

Trait Implementations

impl Add<BigUint> for BigUint

type Output = BigUint

The resulting type after applying the + operator.

fn add(self, rhs: Self) -> Self::Output

Performs the + operation.

impl Clone for BigUint

fn clone(&self) -> BigUint

Returns a copy of the value.

fn clone_from(&mut self, source: &Self)

Performs copy-assignment from source.

impl Debug for BigUint

fn fmt(&self, f: &mut Formatter<'_>) -> Result

Formats the value using the given formatter.

impl Decode for BigUint

fn decode<__CodecInputEdqy: Input>(
    __codec_input_edqy: &mut __CodecInputEdqy
) -> Result<Self, Error>

Attempt to deserialise the value from input.

fn skip<I>(input: &mut I) -> Result<(), Error>where
    I: Input,

Attempt to skip the encoded value from input.

fn encoded_fixed_size() -> Option<usize>

Returns the fixed encoded size of the type.

impl Default for BigUint

fn default() -> BigUint

Returns the “default value” for a type.

impl Encode for BigUint

fn encode_to<__CodecOutputEdqy: Output + ?Sized>(
    &self,
    __codec_dest_edqy: &mut __CodecOutputEdqy
)

Convert self to a slice and append it to the destination.

fn encode(&self) -> Vec<u8>

Convert self to an owned vector.

fn using_encoded<R, F: FnOnce(&[u8]) -> R>(&self, f: F) -> R

Convert self to a slice and then invoke the given closure with it.

fn size_hint(&self) -> usize

If possible give a hint of expected size of the encoding.

fn encoded_size(&self) -> usize

Calculates the encoded size.

impl From<u128> for BigUint

fn from(a: u128) -> Self

Converts to this type from the input type.

impl From<u16> for BigUint

fn from(a: u16) -> Self

Converts to this type from the input type.

impl From<u32> for BigUint

fn from(a: u32) -> Self

Converts to this type from the input type.

impl From<u64> for BigUint

fn from(a: Double) -> Self

Converts to this type from the input type.

impl From<u8> for BigUint

fn from(a: u8) -> Self

Converts to this type from the input type.

impl Mul<BigUint> for BigUint

type Output = BigUint

The resulting type after applying the * operator.

fn mul(self, rhs: Self) -> Self::Output

Performs the * operation.

impl One for BigUint

fn one() -> Self

Returns the multiplicative identity element of Self, 1.

fn set_one(&mut self)

Sets self to the multiplicative identity element of Self, 1.

fn is_one(&self) -> boolwhere
    Self: PartialEq<Self>,

Returns true if self is equal to the multiplicative identity.

impl Ord for BigUint

fn cmp(&self, other: &Self) -> Ordering

This method returns an Ordering between self and other.

fn max(self, other: Self) -> Selfwhere
    Self: Sized,

Compares and returns the maximum of two values.

fn min(self, other: Self) -> Selfwhere
    Self: Sized,

Compares and returns the minimum of two values.

fn clamp(self, min: Self, max: Self) -> Selfwhere
    Self: Sized + PartialOrd<Self>,

Restrict a value to a certain interval.

impl PartialEq<BigUint> for BigUint

fn eq(&self, other: &Self) -> bool

This method tests for self and other values to be equal, and is used by ==.

fn ne(&self, other: &Rhs) -> bool

This method tests for !=. The default implementation is almost always sufficient, and should not be overridden without very good reason.

impl PartialOrd<BigUint> for BigUint

fn partial_cmp(&self, other: &Self) -> Option<Ordering>

This method returns an ordering between self and other values if one exists.

fn lt(&self, other: &Rhs) -> bool

This method tests less than (for self and other) and is used by the < operator.

fn le(&self, other: &Rhs) -> bool

This method tests less than or equal to (for self and other) and is used by the <= operator.

fn gt(&self, other: &Rhs) -> bool

This method tests greater than (for self and other) and is used by the > operator.

fn ge(&self, other: &Rhs) -> bool

This method tests greater than or equal to (for self and other) and is used by the >= operator.

impl Sub<BigUint> for BigUint

type Output = BigUint

The resulting type after applying the - operator.

fn sub(self, rhs: Self) -> Self::Output

Performs the - operation.

impl TryFrom<BigUint> for u128

type Error = &'static str

The type returned in the event of a conversion error.

fn try_from(value: BigUint) -> Result<u128, Self::Error>

Performs the conversion.

impl TryFrom<BigUint> for u64

type Error = &'static str

The type returned in the event of a conversion error.

fn try_from(value: BigUint) -> Result<u64, Self::Error>

Performs the conversion.

impl Zero for BigUint

fn zero() -> Self

Returns the additive identity element of Self, 0.

fn is_zero(&self) -> bool

Returns true if self is equal to the additive identity.

fn set_zero(&mut self)

Sets self to the additive identity element of Self, 0.

impl EncodeLike<BigUint> for BigUint

impl Eq for BigUint