use std::cmp::Ordering;
use std::convert::TryFrom;
use std::ops::{
Add, AddAssign, BitAnd, BitAndAssign, BitOr, BitOrAssign, BitXor,
BitXorAssign, Div, DivAssign, Mul, MulAssign, Not, Shl, ShlAssign, Shr,
ShrAssign, Sub, SubAssign,
};
use traiter::numbers::{
BitLength, CheckedShl, FloatInfo, Floor, FractExp, Gcd, LoadExp, One,
RemEuclid, Signed, Unitary, Zero, Zeroable,
};
use crate::contracts::{is_signed, is_unsigned};
use crate::traits::{
DoublePrecision, DoublePrecisionOf, HasSignBit, MantissaDigits, MaxExp,
MinExp, Oppose, OppositionOf, WrappingSub,
};
use super::types::{CheckedDivAsFloatError, ShlError, Sign};
pub trait BaseFromBinaryDigits<Source>: Sized {
fn base_from_binary_digits(
source: &[Source],
source_bitness: usize,
target_base: usize,
) -> Vec<Self>;
}
impl<
Source,
Target: BinaryBaseFromBinaryDigits<Source>
+ NonBinaryBaseFromBinaryDigits<Source>,
> BaseFromBinaryDigits<Source> for Target
{
fn base_from_binary_digits(
source: &[Source],
source_bitness: usize,
target_base: usize,
) -> Vec<Self> {
if target_base & (target_base - 1) == 0 {
Self::binary_base_from_binary_digits(
source,
source_bitness,
floor_log2::<usize>(target_base),
)
} else {
Self::non_binary_base_from_binary_digits(
source,
source_bitness,
target_base,
)
}
}
}
pub(super) trait BinaryBaseFromDigits<Source>: Sized {
fn binary_base_from_digits<const TARGET_BITNESS: usize>(
source: &[Source],
source_base: usize,
) -> Vec<Self>;
}
impl<
Source,
Target: BinaryBaseFromBinaryDigits<Source>
+ GreaterBinaryBaseFromNonBinaryDigits<Source>
+ LesserBinaryBaseFromNonBinaryDigits<Source>,
> BinaryBaseFromDigits<Source> for Target
{
fn binary_base_from_digits<const TARGET_BITNESS: usize>(
source: &[Source],
source_base: usize,
) -> Vec<Self> {
if source_base & (source_base - 1) == 0 {
Self::binary_base_from_binary_digits(
source,
floor_log2::<usize>(source_base),
TARGET_BITNESS,
)
} else if source_base < (1 << TARGET_BITNESS) {
Self::greater_binary_base_from_non_binary_digits::<TARGET_BITNESS>(
source,
source_base,
)
} else {
Self::lesser_binary_base_from_non_binary_digits::<TARGET_BITNESS>(
source,
source_base,
)
}
}
}
pub(super) trait BinaryBaseFromBinaryDigits<Source>: Sized {
fn binary_base_from_binary_digits(
source: &[Source],
source_bitness: usize,
target_bitness: usize,
) -> Vec<Self>;
}
impl<
Source: Copy,
Target: GreaterBinaryBaseFromBinaryDigits<Source>
+ LesserBinaryBaseFromBinaryDigits<Source>
+ TryFrom<Source>,
> BinaryBaseFromBinaryDigits<Source> for Target
{
fn binary_base_from_binary_digits(
source: &[Source],
source_bitness: usize,
target_bitness: usize,
) -> Vec<Self> {
match target_bitness.cmp(&source_bitness) {
Ordering::Equal => source
.iter()
.map(|&digit| unsafe {
Self::try_from(digit).unwrap_unchecked()
})
.collect(),
Ordering::Greater => Self::greater_binary_base_from_binary_digits(
source,
source_bitness,
target_bitness,
),
Ordering::Less => Self::lesser_binary_base_from_binary_digits(
source,
source_bitness,
target_bitness,
),
}
}
}
pub(super) trait NonBinaryBaseFromBinaryDigits<Source>: Sized {
fn non_binary_base_from_binary_digits(
source: &[Source],
source_bitness: usize,
target_base: usize,
) -> Vec<Self>;
}
impl<
Source: Copy,
Target: Copy + DoublePrecision + TryFrom<DoublePrecisionOf<Target>> + Zero,
> NonBinaryBaseFromBinaryDigits<Source> for Target
where
DoublePrecisionOf<Target>: BitOr<Output = DoublePrecisionOf<Target>>
+ Copy
+ Div<Output = DoublePrecisionOf<Target>>
+ DivAssign
+ Mul<Output = DoublePrecisionOf<Target>>
+ Shl<usize, Output = DoublePrecisionOf<Target>>
+ ShlAssign<usize>
+ Sub<Output = DoublePrecisionOf<Target>>
+ From<Source>
+ RemEuclid<Output = DoublePrecisionOf<Target>>
+ TryFrom<usize>
+ Zeroable,
{
fn non_binary_base_from_binary_digits(
source: &[Source],
source_bitness: usize,
target_base: usize,
) -> Vec<Self> {
let result_max_digits_count: usize = 1
+ ((((source.len() * source_bitness) as f64)
/ (target_base as f64).log2()) as usize);
let mut result = Vec::<Self>::with_capacity(result_max_digits_count);
let target_base = unsafe {
DoublePrecisionOf::<Self>::try_from(target_base).unwrap_unchecked()
};
for digit in source.iter().rev() {
let mut accumulator: DoublePrecisionOf<Self> =
DoublePrecisionOf::<Self>::from(*digit);
for result_position in &mut result {
let step: DoublePrecisionOf<Self> =
(<DoublePrecisionOf<Self> as From<Self>>::from(
*result_position,
) << source_bitness)
| accumulator;
accumulator = step / target_base;
*result_position = unsafe {
Self::try_from(step - accumulator * target_base)
.unwrap_unchecked()
};
}
while !accumulator.is_zero() {
result.push(unsafe {
Self::try_from(accumulator.rem_euclid(target_base))
.unwrap_unchecked()
});
accumulator /= target_base;
}
}
if result.is_empty() {
result.push(Self::zero());
}
result
}
}
trait GreaterBinaryBaseFromBinaryDigits<Source>: Sized {
fn greater_binary_base_from_binary_digits(
source: &[Source],
source_bitness: usize,
target_bitness: usize,
) -> Vec<Self>;
}
impl<
Source: Copy,
Target: DoublePrecision + TryFrom<DoublePrecisionOf<Target>>,
> GreaterBinaryBaseFromBinaryDigits<Source> for Target
where
DoublePrecisionOf<Target>: BitAnd<Output = DoublePrecisionOf<Target>>
+ BitOr<Output = DoublePrecisionOf<Target>>
+ BitOrAssign
+ Copy
+ From<Source>
+ One
+ Shl<usize, Output = DoublePrecisionOf<Target>>
+ ShlAssign<usize>
+ Shr<usize, Output = DoublePrecisionOf<Target>>
+ ShrAssign<usize>
+ Sub<Output = DoublePrecisionOf<Target>>
+ SubAssign
+ Zero
+ Zeroable,
{
fn greater_binary_base_from_binary_digits(
source: &[Source],
source_bitness: usize,
target_bitness: usize,
) -> Vec<Self> {
debug_assert!(target_bitness > source_bitness && source_bitness > 0);
let target_digit_mask =
DoublePrecisionOf::<Self>::digit_mask(target_bitness);
let result_capacity: usize = (source.len() * target_bitness
+ (target_bitness - 1))
/ target_bitness;
let mut result = Vec::<Self>::with_capacity(result_capacity);
let mut accumulator = DoublePrecisionOf::<Self>::zero();
let mut accumulator_bits_count: usize = 0;
for digit in source {
accumulator |= DoublePrecisionOf::<Self>::from(*digit)
<< accumulator_bits_count;
accumulator_bits_count += source_bitness;
if accumulator_bits_count >= target_bitness {
unsafe {
result.push(
Self::try_from(accumulator & target_digit_mask)
.unwrap_unchecked(),
);
}
accumulator >>= target_bitness;
accumulator_bits_count -= target_bitness;
}
}
if !accumulator.is_zero() || result.is_empty() {
unsafe {
result.push(Self::try_from(accumulator).unwrap_unchecked());
}
}
result
}
}
pub(super) trait LesserBinaryBaseFromBinaryDigits<Source>:
Sized
{
fn lesser_binary_base_from_binary_digits(
source: &[Source],
source_bitness: usize,
target_bitness: usize,
) -> Vec<Self>;
}
impl<
Source: Copy + BitLength<Output = usize> + DoublePrecision,
Target: TryFrom<DoublePrecisionOf<Source>>,
> LesserBinaryBaseFromBinaryDigits<Source> for Target
where
DoublePrecisionOf<Source>: BitAnd<Output = DoublePrecisionOf<Source>>
+ BitOrAssign
+ Copy
+ DigitMask
+ Shl<usize, Output = DoublePrecisionOf<Source>>
+ Shr<usize, Output = DoublePrecisionOf<Source>>
+ ShrAssign<usize>
+ Zeroable,
{
fn lesser_binary_base_from_binary_digits(
source: &[Source],
source_bitness: usize,
target_bitness: usize,
) -> Vec<Self> {
debug_assert!(source_bitness > target_bitness && target_bitness > 0);
let target_digit_mask =
DoublePrecisionOf::<Source>::digit_mask(target_bitness);
let digits_bits_count: usize = (source.len() - 1) * source_bitness
+ source[source.len() - 1].bit_length();
let digits_count: usize =
(digits_bits_count + (target_bitness - 1)) / target_bitness;
let mut result = Vec::<Self>::with_capacity(digits_count);
let mut accumulator = DoublePrecisionOf::<Source>::from(source[0]);
let mut accumulator_bits_count = source_bitness;
for &digit in source.iter().skip(1) {
loop {
result.push(unsafe {
Self::try_from(accumulator & target_digit_mask)
.unwrap_unchecked()
});
accumulator >>= target_bitness;
accumulator_bits_count -= target_bitness;
if accumulator_bits_count < target_bitness {
break;
}
}
accumulator |= DoublePrecisionOf::<Source>::from(digit)
<< accumulator_bits_count;
accumulator_bits_count += source_bitness;
}
loop {
result.push(unsafe {
Self::try_from(accumulator & target_digit_mask)
.unwrap_unchecked()
});
accumulator >>= target_bitness;
if accumulator.is_zero() {
break;
}
}
result
}
}
pub(super) trait BitwiseAndComponents: Sized {
fn bitwise_and_components<const DIGIT_BITNESS: usize>(
first_sign: Sign,
first: Vec<Self>,
second_sign: Sign,
second: Vec<Self>,
) -> (Sign, Vec<Self>);
}
impl<Digit: BitAndAssign + ComplementInPlace + Copy + DigitMask>
BitwiseAndComponents for Digit
where
for<'a> &'a Digit: Zeroable,
{
fn bitwise_and_components<const DIGIT_BITNESS: usize>(
first_sign: Sign,
first: Vec<Self>,
second_sign: Sign,
second: Vec<Self>,
) -> (Sign, Vec<Self>) {
let (longest_sign, mut longest, shortest_sign, mut shortest) =
if first.len() < second.len() {
(second_sign, second, first_sign, first)
} else {
(first_sign, first, second_sign, second)
};
if longest_sign.is_negative() {
Digit::complement_in_place::<DIGIT_BITNESS>(&mut longest);
};
if shortest_sign.is_negative() {
Digit::complement_in_place::<DIGIT_BITNESS>(&mut shortest);
};
let mut result = longest;
if !shortest_sign.is_negative() {
result.truncate(shortest.len());
};
for index in 0..shortest.len() {
result[index] &= shortest[index];
}
let mut sign = longest_sign & shortest_sign;
if sign.is_negative() {
result.push(Digit::digit_mask(DIGIT_BITNESS));
Digit::complement_in_place::<DIGIT_BITNESS>(&mut result);
}
trim_leading_zeros(&mut result);
sign *= to_digits_sign(&result);
(sign, result)
}
}
pub(super) trait BitwiseOrComponents: Sized {
fn bitwise_or_components<const DIGIT_BITNESS: usize>(
first_sign: Sign,
first: Vec<Self>,
second_sign: Sign,
second: Vec<Self>,
) -> (Sign, Vec<Self>);
}
impl<Digit: BitOrAssign + ComplementInPlace + Copy + DigitMask>
BitwiseOrComponents for Digit
where
for<'a> &'a Digit: Zeroable,
{
fn bitwise_or_components<const DIGIT_BITNESS: usize>(
first_sign: Sign,
first: Vec<Self>,
second_sign: Sign,
second: Vec<Self>,
) -> (Sign, Vec<Self>) {
let (longest_sign, mut longest, shortest_sign, mut shortest) =
if first.len() < second.len() {
(second_sign, second, first_sign, first)
} else {
(first_sign, first, second_sign, second)
};
if longest_sign.is_negative() {
Self::complement_in_place::<DIGIT_BITNESS>(&mut longest);
};
if shortest_sign.is_negative() {
Self::complement_in_place::<DIGIT_BITNESS>(&mut shortest);
};
let mut result = longest;
if shortest_sign.is_negative() {
result.truncate(shortest.len());
};
for index in 0..shortest.len() {
result[index] |= shortest[index];
}
let sign = longest_sign | shortest_sign;
if sign.is_negative() {
result.push(Self::digit_mask(DIGIT_BITNESS));
Self::complement_in_place::<DIGIT_BITNESS>(&mut result);
}
trim_leading_zeros(&mut result);
(sign, result)
}
}
pub(super) trait BitwiseXorComponents: Sized {
fn bitwise_xor_components<const DIGIT_BITNESS: usize>(
first_sign: Sign,
first: Vec<Self>,
second_sign: Sign,
second: Vec<Self>,
) -> (Sign, Vec<Self>);
}
impl<Digit: BitXorAssign + ComplementInPlace + Copy + DigitMask>
BitwiseXorComponents for Digit
where
for<'a> &'a Digit: Zeroable,
{
fn bitwise_xor_components<const DIGIT_BITNESS: usize>(
first_sign: Sign,
first: Vec<Self>,
second_sign: Sign,
second: Vec<Self>,
) -> (Sign, Vec<Self>) {
let (longest_sign, mut longest, shortest_sign, mut shortest) =
if first.len() < second.len() {
(second_sign, second, first_sign, first)
} else {
(first_sign, first, second_sign, second)
};
if longest_sign.is_negative() {
Self::complement_in_place::<DIGIT_BITNESS>(&mut longest);
};
if shortest_sign.is_negative() {
Self::complement_in_place::<DIGIT_BITNESS>(&mut shortest);
};
let mut result = longest;
for index in 0..shortest.len() {
result[index] ^= shortest[index];
}
if shortest_sign.is_negative() {
let digit_mask = Self::digit_mask(DIGIT_BITNESS);
for result_digit in &mut result[shortest.len()..] {
*result_digit ^= digit_mask;
}
};
let sign_is_negative =
longest_sign.is_negative() ^ shortest_sign.is_negative();
if sign_is_negative {
result.push(Self::digit_mask(DIGIT_BITNESS));
Self::complement_in_place::<DIGIT_BITNESS>(&mut result);
}
trim_leading_zeros(&mut result);
(
if sign_is_negative {
-Sign::one()
} else {
Sign::one()
} * to_digits_sign(&result),
result,
)
}
}
pub trait TryDivDigitsAsFloat<Output>: Sized {
type Error;
fn checked_div_digits_as_float<const DIGIT_BITNESS: usize>(
dividend_digits: &[Self],
divisor_digits: &[Self],
) -> Result<Output, Self::Error>;
}
macro_rules! checked_div_digits_as_float_impl {
($($float:ty)*) => ($(
impl<
Digit: AddAssign
+ BitAnd<Output = Digit>
+ BitLength<Output = usize>
+ BitOr<Digit, Output = Digit>
+ Copy
+ From<u8>
+ DivRemDigitsByDigit
+ DivRemDigitsByTwoOrMoreDigits
+ Mul<Output = Digit>
+ Not<Output = Digit>
+ One
+ ShiftDigitsLeftInPlace
+ ShiftDigitsRightInPlace
+ Shl<usize, Output = Digit>
+ Shr<usize, Output = Digit>
+ ReduceDigitsToFloat<$float>
+ Sub<Output = Digit>
+ Zero,
> TryDivDigitsAsFloat<$float> for Digit
where
for<'a> &'a Digit: Zeroable,
{
type Error = CheckedDivAsFloatError;
fn checked_div_digits_as_float<const DIGIT_BITNESS: usize>(
dividend_digits: &[Self],
divisor_digits: &[Self],
) -> Result<$float, Self::Error> {
const NON_EXPONENT_BITS_COUNT: usize =
<$float>::TOTAL_BITS_COUNT - <$float>::EXPONENT_BITS_COUNT;
if divisor_digits.len() == 1 && divisor_digits[0].is_zero() {
return Err(CheckedDivAsFloatError::ZeroDivision);
}
if dividend_digits.len() == 1 && dividend_digits[0].is_zero() {
return Ok(<$float>::zero());
}
let dividend_digits_count = dividend_digits.len();
let divisor_digits_count = divisor_digits.len();
let dividend_is_small = dividend_digits_count
<= (NON_EXPONENT_BITS_COUNT / DIGIT_BITNESS)
|| (dividend_digits_count
== (NON_EXPONENT_BITS_COUNT / DIGIT_BITNESS) + 1
&& (dividend_digits
[(NON_EXPONENT_BITS_COUNT / DIGIT_BITNESS)]
>> (NON_EXPONENT_BITS_COUNT % DIGIT_BITNESS))
.is_zero());
let divisor_is_small = divisor_digits_count
<= (NON_EXPONENT_BITS_COUNT / DIGIT_BITNESS)
|| (divisor_digits_count
== (NON_EXPONENT_BITS_COUNT / DIGIT_BITNESS) + 1
&& (divisor_digits
[(NON_EXPONENT_BITS_COUNT / DIGIT_BITNESS)]
>> (NON_EXPONENT_BITS_COUNT % DIGIT_BITNESS))
.is_zero());
if dividend_is_small && divisor_is_small {
let reduced_dividend =
Self::reduce_digits_to_float::<DIGIT_BITNESS>(
dividend_digits,
);
let reduced_divisor = Self::reduce_digits_to_float::<
DIGIT_BITNESS,
>(divisor_digits);
return Ok(reduced_dividend / reduced_divisor);
}
let digits_count_difference = (dividend_digits_count as isize)
- (divisor_digits_count as isize);
if digits_count_difference
> (((usize::MAX / DIGIT_BITNESS) - 1) as isize)
{
return Err(CheckedDivAsFloatError::TooLarge);
} else if digits_count_difference
< 1isize - ((usize::MAX / DIGIT_BITNESS) as isize)
{
return Ok(<$float>::zero());
}
let bit_lengths_difference = digits_count_difference
* (DIGIT_BITNESS as isize)
+ (((dividend_digits[dividend_digits.len() - 1]
.bit_length()) as isize)
- (divisor_digits[divisor_digits.len() - 1]
.bit_length()
as isize));
if bit_lengths_difference > (<$float>::MAX_EXP as isize) {
return Err(CheckedDivAsFloatError::TooLarge);
} else if bit_lengths_difference
< (<$float>::MIN_EXP as isize)
- ((NON_EXPONENT_BITS_COUNT as isize) - 1)
{
return Ok(<$float>::zero());
}
let shift = bit_lengths_difference
.max(<$float>::MIN_EXP as isize)
- (NON_EXPONENT_BITS_COUNT as isize)
- 2;
let mut inexact = false;
let mut quotient_digits = if shift <= 0 {
let shift_digits = ((-shift) as usize) / DIGIT_BITNESS;
if dividend_digits_count
>= ((isize::MAX - 1) as usize) - shift_digits
{
return Err(CheckedDivAsFloatError::TooLarge);
}
let quotient_digits_count =
dividend_digits_count + shift_digits + 1;
let mut quotient_data =
vec![Self::zero(); quotient_digits_count];
let remainder =
Self::shift_digits_left_in_place::<DIGIT_BITNESS>(
dividend_digits,
((-shift) as usize) % DIGIT_BITNESS,
&mut quotient_data[shift_digits..],
);
quotient_data[dividend_digits_count + shift_digits] =
remainder;
quotient_data
} else {
let mut shift_digits = (shift as usize) / DIGIT_BITNESS;
let quotient_digits_count =
dividend_digits_count - shift_digits;
let mut quotient_data =
vec![Self::zero(); quotient_digits_count];
let remainder =
Self::shift_digits_right_in_place::<DIGIT_BITNESS>(
÷nd_digits[shift_digits..],
(shift as usize) % DIGIT_BITNESS,
&mut quotient_data,
);
if !remainder.is_zero() {
inexact = true;
}
while !inexact && shift_digits > 0 {
shift_digits -= 1;
if !dividend_digits[shift_digits].is_zero() {
inexact = true;
}
}
quotient_data
};
trim_leading_zeros(&mut quotient_digits);
if divisor_digits_count == 1 {
let (next_quotient_digits, remainder) =
Self::div_rem_digits_by_digit::<DIGIT_BITNESS>(
"ient_digits,
divisor_digits[0],
);
quotient_digits = next_quotient_digits;
if !remainder.is_zero() {
inexact = true;
}
} else {
let (next_quotient_digits, remainder) =
Self::div_rem_by_two_or_more_digits::<DIGIT_BITNESS>(
"ient_digits,
divisor_digits,
);
quotient_digits = next_quotient_digits;
if !to_digits_sign(&remainder).is_zero() {
inexact = true;
}
}
let quotient_bit_length = ((quotient_digits.len() - 1)
* DIGIT_BITNESS
+ quotient_digits[quotient_digits.len() - 1].bit_length())
as isize;
let extra_bits = quotient_bit_length
.max((<$float>::MIN_EXP as isize) - shift)
- (NON_EXPONENT_BITS_COUNT as isize);
let mask = Self::one() << ((extra_bits as usize) - 1);
let mut quotient_low_digit =
quotient_digits[0] | Self::from(inexact as u8);
if !(quotient_low_digit & mask).is_zero()
&& !(quotient_low_digit
& (Self::from(3u8) * mask - Self::from(1u8)))
.is_zero()
{
quotient_low_digit += mask;
}
quotient_digits[0] = quotient_low_digit
& !(Self::from(2u8) * mask - Self::from(1u8));
let reduced_quotient = Self::reduce_digits_to_float::<
DIGIT_BITNESS,
>("ient_digits);
if shift + quotient_bit_length >= (<$float>::MAX_EXP as isize)
&& (shift + quotient_bit_length
> (<$float>::MAX_EXP as isize)
|| reduced_quotient
== (1 as $float)
.load_exp(quotient_bit_length as i32))
{
Err(CheckedDivAsFloatError::TooLarge)
} else {
Ok(reduced_quotient.load_exp(shift as i32))
}
}
}
)*)
}
checked_div_digits_as_float_impl!(f32 f64);
pub(super) trait CheckedDivComponents: Sized {
fn checked_div_components<const DIGIT_BITNESS: usize>(
dividend_sign: Sign,
dividend: &[Self],
divisor_sign: Sign,
divisor: &[Self],
) -> Option<(Sign, Vec<Self>)>;
}
impl<
Digit: Copy
+ DivRemDigitsByDigit
+ DivRemDigitsByTwoOrMoreDigits
+ PartialOrd
+ Zero,
> CheckedDivComponents for Digit
where
for<'a> &'a Digit: Zeroable,
{
fn checked_div_components<const DIGIT_BITNESS: usize>(
dividend_sign: Sign,
dividend: &[Self],
divisor_sign: Sign,
divisor: &[Self],
) -> Option<(Sign, Vec<Self>)> {
if divisor_sign.is_zero() {
None
} else if dividend_sign.is_zero()
|| digits_lesser_than(dividend, divisor)
{
Some((Sign::zero(), vec![Self::zero()]))
} else if divisor.len() == 1 {
let (digits, _) = Self::div_rem_digits_by_digit::<DIGIT_BITNESS>(
dividend, divisor[0],
);
Some((dividend_sign * divisor_sign, digits))
} else {
let (digits, _) = Self::div_rem_by_two_or_more_digits::<
DIGIT_BITNESS,
>(dividend, divisor);
Some((
dividend_sign * divisor_sign * to_digits_sign(&digits),
digits,
))
}
}
}
pub(super) trait CheckedDivEuclidComponents: Sized {
fn checked_div_euclid_components<const DIGIT_BITNESS: usize>(
dividend_sign: Sign,
dividend: &[Self],
divisor_sign: Sign,
divisor: &[Self],
) -> Option<(Sign, Vec<Self>)>;
}
impl<
Digit: Copy
+ DivRemDigitsByDigit
+ DivRemDigitsByTwoOrMoreDigits
+ One
+ PartialOrd
+ SumDigits
+ Zero,
> CheckedDivEuclidComponents for Digit
where
for<'a> &'a Digit: Zeroable,
{
fn checked_div_euclid_components<const DIGIT_BITNESS: usize>(
dividend_sign: Sign,
dividend: &[Self],
divisor_sign: Sign,
divisor: &[Self],
) -> Option<(Sign, Vec<Self>)> {
if divisor_sign.is_zero() {
None
} else if dividend_sign.is_zero() {
Some((Sign::zero(), vec![Self::zero()]))
} else if digits_lesser_than(dividend, divisor) {
Some(
if (dividend_sign.is_negative() && divisor_sign.is_positive())
|| (dividend_sign.is_positive()
&& divisor_sign.is_negative())
{
(-Sign::one(), vec![Self::one()])
} else {
(Sign::zero(), vec![Self::zero()])
},
)
} else {
let (sign, mut digits, remainder_is_non_zero) = if divisor.len()
== 1
{
let (digits, remainder_digit) =
Self::div_rem_digits_by_digit::<DIGIT_BITNESS>(
dividend, divisor[0],
);
(
dividend_sign * divisor_sign,
digits,
!remainder_digit.is_zero(),
)
} else {
let (digits, remainder) = Self::div_rem_by_two_or_more_digits::<
DIGIT_BITNESS,
>(dividend, divisor);
(
dividend_sign * divisor_sign * to_digits_sign(&digits),
digits,
!to_digits_sign(&remainder).is_zero(),
)
};
if remainder_is_non_zero
&& ((dividend_sign.is_negative()
&& divisor_sign.is_positive())
|| (dividend_sign.is_positive()
&& divisor_sign.is_negative()))
{
digits =
Self::sum_digits::<DIGIT_BITNESS>(&digits, &[Self::one()]);
}
Some((sign, digits))
}
}
}
pub(super) trait CheckedDivRemComponents: Sized {
fn checked_div_rem_components<const DIGIT_BITNESS: usize>(
dividend_sign: Sign,
dividend: &[Self],
divisor_sign: Sign,
divisor: &[Self],
) -> Option<(Sign, Vec<Self>, Sign, Vec<Self>)>;
}
impl<
Digit: Copy
+ DivRemDigitsByDigit
+ DivRemDigitsByTwoOrMoreDigits
+ PartialOrd
+ Zero,
> CheckedDivRemComponents for Digit
where
for<'a> &'a Digit: Zeroable,
{
fn checked_div_rem_components<const DIGIT_BITNESS: usize>(
dividend_sign: Sign,
dividend: &[Self],
divisor_sign: Sign,
divisor: &[Self],
) -> Option<(Sign, Vec<Self>, Sign, Vec<Self>)> {
if divisor_sign.is_zero() {
None
} else if dividend_sign.is_zero()
|| dividend.len() < divisor.len()
|| (dividend.len() == divisor.len()
&& dividend[dividend.len() - 1] < divisor[divisor.len() - 1])
{
Some((
Sign::zero(),
vec![Self::zero(); 1],
dividend_sign,
dividend.to_vec(),
))
} else if divisor.len() == 1 {
let (quotient_digits, remainder_digit) =
Self::div_rem_digits_by_digit::<DIGIT_BITNESS>(
dividend, divisor[0],
);
Some((
dividend_sign * divisor_sign,
quotient_digits,
dividend_sign * Sign::from(!remainder_digit.is_zero()),
vec![remainder_digit],
))
} else {
let (quotient_digits, remainder_digits) =
Self::div_rem_by_two_or_more_digits::<DIGIT_BITNESS>(
dividend, divisor,
);
Some((
dividend_sign
* divisor_sign
* to_digits_sign("ient_digits),
quotient_digits,
dividend_sign * to_digits_sign(&remainder_digits),
remainder_digits,
))
}
}
}
pub(super) trait CheckedDivRemEuclidComponents: Sized {
fn checked_div_rem_euclid_components<const DIGIT_BITNESS: usize>(
dividend_sign: Sign,
dividend: &[Self],
divisor_sign: Sign,
divisor: &[Self],
) -> Option<(Sign, Vec<Self>, Sign, Vec<Self>)>;
}
impl<
Digit: CheckedDivRemComponents + One + SubtractComponents + SumComponents,
> CheckedDivRemEuclidComponents for Digit
{
fn checked_div_rem_euclid_components<const DIGIT_BITNESS: usize>(
dividend_sign: Sign,
dividend: &[Digit],
divisor_sign: Sign,
divisor: &[Digit],
) -> Option<(Sign, Vec<Digit>, Sign, Vec<Digit>)> {
let (
mut quotient_sign,
mut quotient,
mut remainder_sign,
mut remainder,
) = Digit::checked_div_rem_components::<DIGIT_BITNESS>(
dividend_sign,
dividend,
divisor_sign,
divisor,
)?;
if (divisor_sign.is_negative() && remainder_sign.is_positive())
|| (divisor_sign.is_positive() && remainder_sign.is_negative())
{
(quotient_sign, quotient) =
Digit::subtract_components::<DIGIT_BITNESS>(
quotient_sign,
"ient,
Sign::one(),
&[Digit::one()],
);
(remainder_sign, remainder) = Digit::sum_components::<DIGIT_BITNESS>(
remainder_sign,
&remainder,
divisor_sign,
divisor,
);
}
Some((quotient_sign, quotient, remainder_sign, remainder))
}
}
pub(super) trait CheckedRemComponents: Sized {
fn checked_rem_components<const DIGIT_BITNESS: usize>(
dividend_sign: Sign,
dividend: &[Self],
divisor_sign: Sign,
divisor: &[Self],
) -> Option<(Sign, Vec<Self>)>;
}
impl<
Digit: Copy
+ DivRemDigitsByDigit
+ DivRemDigitsByTwoOrMoreDigits
+ PartialOrd,
> CheckedRemComponents for Digit
where
for<'a> &'a Digit: Zeroable,
{
fn checked_rem_components<const DIGIT_BITNESS: usize>(
dividend_sign: Sign,
dividend: &[Self],
divisor_sign: Sign,
divisor: &[Self],
) -> Option<(Sign, Vec<Self>)> {
if divisor_sign.is_zero() {
None
} else if dividend_sign.is_zero()
|| digits_lesser_than(dividend, divisor)
{
Some((dividend_sign, dividend.to_vec()))
} else if divisor.len() == 1 {
let (_, remainder) = Self::div_rem_digits_by_digit::<DIGIT_BITNESS>(
dividend, divisor[0],
);
Some((
dividend_sign * Sign::from(!remainder.is_zero()),
vec![remainder],
))
} else {
let (_, remainder) = Self::div_rem_by_two_or_more_digits::<
DIGIT_BITNESS,
>(dividend, divisor);
Some((dividend_sign * to_digits_sign(&remainder), remainder))
}
}
}
pub(super) trait CheckedRemEuclidComponents: Sized {
fn checked_rem_euclid_components<const DIGIT_BITNESS: usize>(
dividend_sign: Sign,
dividend: &[Self],
divisor_sign: Sign,
divisor: &[Self],
) -> Option<(Sign, Vec<Self>)>;
}
impl<
Digit: Copy
+ DivRemDigitsByDigit
+ DivRemDigitsByTwoOrMoreDigits
+ PartialOrd
+ SubtractDigits,
> CheckedRemEuclidComponents for Digit
where
for<'a> &'a Digit: Zeroable,
{
fn checked_rem_euclid_components<const DIGIT_BITNESS: usize>(
dividend_sign: Sign,
dividend: &[Self],
divisor_sign: Sign,
divisor: &[Self],
) -> Option<(Sign, Vec<Self>)> {
if divisor_sign.is_zero() {
None
} else if dividend_sign.is_zero() {
Some((dividend_sign, dividend.to_vec()))
} else if digits_lesser_than(dividend, divisor) {
Some(
if (dividend_sign.is_negative() && divisor_sign.is_positive())
|| (dividend_sign.is_positive()
&& divisor_sign.is_negative())
{
Digit::subtract_digits::<DIGIT_BITNESS>(
dividend,
divisor,
dividend_sign,
)
} else {
(dividend_sign, dividend.to_vec())
},
)
} else {
let (mut sign, mut digits) = if divisor.len() == 1 {
let (_, digit) = Digit::div_rem_digits_by_digit::<DIGIT_BITNESS>(
dividend, divisor[0],
);
(dividend_sign * Sign::from(!digit.is_zero()), vec![digit])
} else {
let (_, digits) = Digit::div_rem_by_two_or_more_digits::<
DIGIT_BITNESS,
>(dividend, divisor);
(dividend_sign * to_digits_sign(&digits), digits)
};
if (divisor_sign.is_negative() && sign.is_positive())
|| (divisor_sign.is_positive() && sign.is_negative())
{
(sign, digits) = Digit::subtract_digits::<DIGIT_BITNESS>(
&digits, divisor, sign,
);
}
Some((sign, digits))
}
}
}
pub(super) trait ComplementInPlace: Sized {
fn complement_in_place<const DIGIT_BITNESS: usize>(digits: &mut [Self]);
}
impl<
Digit: AddAssign
+ BitAnd<Output = Digit>
+ BitXor<Output = Digit>
+ Copy
+ DigitMask
+ One
+ ShrAssign<usize>,
> ComplementInPlace for Digit
where
for<'a> &'a Digit: Zeroable,
{
fn complement_in_place<const DIGIT_BITNESS: usize>(digits: &mut [Self]) {
let mut accumulator = Self::one();
let digit_mask = Self::digit_mask(DIGIT_BITNESS);
for digit in digits {
accumulator += (*digit) ^ digit_mask;
*digit = accumulator & digit_mask;
accumulator >>= DIGIT_BITNESS;
}
debug_assert!(accumulator.is_zero());
}
}
#[inline]
pub(super) fn compare_digits<Digit: Ord>(
left: &[Digit],
right: &[Digit],
) -> Ordering {
match left.len().cmp(&right.len()) {
Ordering::Equal => left.iter().rev().cmp(right.iter().rev()),
value => value,
}
}
#[inline]
fn digits_lesser_than<Digit: PartialOrd>(
left: &[Digit],
right: &[Digit],
) -> bool {
left.len() < right.len()
|| left.len() == right.len()
&& left.iter().rev().lt(right.iter().rev())
}
pub(super) trait DivRemDigitsByDigit: Sized {
fn div_rem_digits_by_digit<const DIGIT_BITNESS: usize>(
dividend: &[Self],
divisor: Self,
) -> (Vec<Self>, Self);
}
impl<
Digit: Copy + DoublePrecision + TryFrom<DoublePrecisionOf<Digit>> + Zero,
> DivRemDigitsByDigit for Digit
where
for<'a> &'a Digit: Zeroable,
DoublePrecisionOf<Digit>: Copy
+ Mul<Output = DoublePrecisionOf<Digit>>
+ Div<Output = DoublePrecisionOf<Digit>>
+ BitOrAssign
+ ShlAssign<usize>
+ SubAssign
+ Zero,
{
fn div_rem_digits_by_digit<const DIGIT_BITNESS: usize>(
dividend: &[Self],
divisor: Self,
) -> (Vec<Self>, Self) {
let mut quotient = vec![Self::zero(); dividend.len()];
let mut remainder = DoublePrecisionOf::<Self>::zero();
let digits_count = dividend.len();
let divisor = DoublePrecisionOf::<Self>::from(divisor);
for offset in 1..=digits_count {
remainder <<= DIGIT_BITNESS;
remainder |= DoublePrecisionOf::<Self>::from(
dividend[digits_count - offset],
);
let quotient_digit = unsafe {
Self::try_from(remainder / divisor).unwrap_unchecked()
};
quotient[digits_count - offset] = quotient_digit;
remainder -=
DoublePrecisionOf::<Self>::from(quotient_digit) * divisor;
}
trim_leading_zeros(&mut quotient);
(quotient, unsafe {
Self::try_from(remainder).unwrap_unchecked()
})
}
}
pub(super) trait DivRemDigitsByTwoOrMoreDigits: Sized {
fn div_rem_by_two_or_more_digits<const DIGIT_BITNESS: usize>(
dividend: &[Self],
divisor: &[Self],
) -> (Vec<Self>, Vec<Self>);
}
impl<
Digit: Add<Output = Digit>
+ AddAssign
+ BitAnd<Output = Digit>
+ BitLength<Output = usize>
+ Copy
+ DigitMask
+ DoublePrecision
+ One
+ Oppose
+ PartialOrd
+ ShiftDigitsLeftInPlace
+ ShiftDigitsRightInPlace
+ Shl<usize, Output = Digit>
+ Shr<usize, Output = Digit>
+ ShrAssign<usize>
+ SubAssign
+ TryFrom<DoublePrecisionOf<Digit>>
+ TryFrom<OppositionOf<DoublePrecisionOf<Digit>>>
+ Zero,
> DivRemDigitsByTwoOrMoreDigits for Digit
where
for<'a> &'a Digit: Zeroable,
DoublePrecisionOf<Digit>: BitOr<Output = DoublePrecisionOf<Digit>>
+ Copy
+ Div<Output = DoublePrecisionOf<Digit>>
+ Mul<Output = DoublePrecisionOf<Digit>>
+ Oppose
+ PartialOrd
+ Shl<usize, Output = DoublePrecisionOf<Digit>>
+ Sub<Output = DoublePrecisionOf<Digit>>,
OppositionOf<Digit>: Add<Output = OppositionOf<Digit>>
+ Copy
+ PartialOrd
+ TryFrom<OppositionOf<DoublePrecisionOf<Digit>>>
+ TryFrom<Digit>
+ Zero,
OppositionOf<DoublePrecisionOf<Digit>>: Add<Output = OppositionOf<DoublePrecisionOf<Digit>>>
+ BitAnd<Output = OppositionOf<DoublePrecisionOf<Digit>>>
+ Copy
+ From<Digit>
+ From<OppositionOf<Digit>>
+ Mul<Output = OppositionOf<DoublePrecisionOf<Digit>>>
+ Shr<usize, Output = OppositionOf<DoublePrecisionOf<Digit>>>
+ Sub<Output = OppositionOf<DoublePrecisionOf<Digit>>>,
{
fn div_rem_by_two_or_more_digits<const DIGIT_BITNESS: usize>(
dividend: &[Digit],
divisor: &[Digit],
) -> (Vec<Digit>, Vec<Digit>) {
let dividend_digits_count = dividend.len();
let divisor_digits_count = divisor.len();
let mut dividend_normalized =
vec![Digit::zero(); dividend_digits_count];
let mut divisor_normalized = vec![Digit::zero(); divisor_digits_count];
let shift = DIGIT_BITNESS - divisor[divisor.len() - 1].bit_length();
Digit::shift_digits_left_in_place::<DIGIT_BITNESS>(
divisor,
shift,
&mut divisor_normalized,
);
let accumulator = Digit::shift_digits_left_in_place::<DIGIT_BITNESS>(
dividend,
shift,
&mut dividend_normalized,
);
let last_divisor_digit_normalized =
divisor_normalized[divisor_normalized.len() - 1];
if !accumulator.is_zero()
|| dividend_normalized[dividend_normalized.len() - 1]
>= last_divisor_digit_normalized
{
dividend_normalized.push(accumulator);
}
let quotient_size =
dividend_normalized.len() - divisor_normalized.len();
let mut quotient = vec![Digit::zero(); quotient_size];
let penult_divisor_digit_normalized =
divisor_normalized[divisor_digits_count - 2];
let mut quotient_index = quotient_size;
let base = Digit::one() << DIGIT_BITNESS;
let digit_mask = Digit::digit_mask(DIGIT_BITNESS);
for offset in (0..quotient_size).rev() {
let step = (DoublePrecisionOf::<Digit>::from(
dividend_normalized[offset + divisor_digits_count],
) << DIGIT_BITNESS)
| DoublePrecisionOf::<Digit>::from(
dividend_normalized[offset + divisor_digits_count - 1],
);
let mut quotient_digit = unsafe {
Digit::try_from(
step / DoublePrecisionOf::<Digit>::from(
last_divisor_digit_normalized,
),
)
.unwrap_unchecked()
};
let mut step_remainder = unsafe {
Digit::try_from(
step - DoublePrecisionOf::<Digit>::from(
last_divisor_digit_normalized,
) * DoublePrecisionOf::<Digit>::from(
quotient_digit,
),
)
.unwrap_unchecked()
};
while DoublePrecisionOf::<Digit>::from(
penult_divisor_digit_normalized,
) * DoublePrecisionOf::<Digit>::from(quotient_digit)
> ((DoublePrecisionOf::<Digit>::from(step_remainder)
<< DIGIT_BITNESS)
| DoublePrecisionOf::<Digit>::from(
dividend_normalized[offset + divisor_digits_count - 2],
))
{
quotient_digit -= Digit::one();
step_remainder += last_divisor_digit_normalized;
if step_remainder >= base {
break;
}
}
let mut accumulator = OppositionOf::<Digit>::zero();
for index in 0..divisor_digits_count {
let step = OppositionOf::<DoublePrecisionOf<Digit>>::from(
dividend_normalized[offset + index],
) + OppositionOf::<DoublePrecisionOf<Digit>>::from(
accumulator,
) - OppositionOf::<DoublePrecisionOf<Digit>>::from(
quotient_digit,
)
* OppositionOf::<DoublePrecisionOf<Digit>>::from(
divisor_normalized[index],
);
dividend_normalized[offset + index] = unsafe {
Digit::try_from(
step & OppositionOf::<DoublePrecisionOf<Digit>>::from(
digit_mask,
),
)
.unwrap_unchecked()
};
accumulator = unsafe {
OppositionOf::<Digit>::try_from(step >> DIGIT_BITNESS)
.unwrap_unchecked()
};
}
if unsafe {
OppositionOf::<Digit>::try_from(
dividend_normalized[offset + divisor_digits_count],
)
.unwrap_unchecked()
} + accumulator
< OppositionOf::<Digit>::zero()
{
let mut accumulator = Digit::zero();
for index in 0..divisor_digits_count {
accumulator = accumulator
+ dividend_normalized[offset + index]
+ divisor_normalized[index];
dividend_normalized[offset + index] =
accumulator & digit_mask;
accumulator >>= DIGIT_BITNESS;
}
quotient_digit -= Digit::one();
}
quotient_index -= 1;
quotient[quotient_index] = quotient_digit;
}
if quotient_size.is_zero() {
quotient = vec![Digit::zero()];
}
trim_leading_zeros(&mut quotient);
let mut remainder = divisor_normalized;
Digit::shift_digits_right_in_place::<DIGIT_BITNESS>(
÷nd_normalized[..divisor_digits_count],
shift,
remainder.as_mut_slice(),
);
trim_leading_zeros(&mut remainder);
(quotient, remainder)
}
}
pub(super) trait FractExpDigits<Fraction>: Sized {
fn fract_exp_digits<const DIGIT_BITNESS: usize>(
digits: &[Self],
) -> Option<(Fraction, i32)>;
}
impl<
Digit: BitAnd<Output = Digit>
+ BitOrAssign<Digit>
+ BitLength<Output = usize>
+ Copy
+ From<u8>
+ TryFrom<OppositionOf<Digit>>
+ One
+ Oppose
+ ShiftDigitsLeftInPlace
+ ShiftDigitsRightInPlace
+ Zero,
Fraction: Add<Output = Fraction>
+ Div<Output = Fraction>
+ DivAssign
+ Copy
+ Floor<Output = Fraction>
+ FractExp<Output = (Fraction, i32)>
+ From<Digit>
+ From<f32>
+ LoadExp<i32, Output = Fraction>
+ MantissaDigits
+ MaxExp
+ MinExp
+ Mul<Output = Fraction>
+ PartialEq
+ One
+ Sub<Output = Fraction>
+ SubAssign,
> FractExpDigits<Fraction> for Digit
where
for<'a> &'a Digit: Zeroable,
for<'a> &'a Fraction: Unitary + Zeroable,
OppositionOf<Digit>:
Add<Output = OppositionOf<Digit>> + From<i8> + TryFrom<Digit>,
usize: TryFrom<Digit>,
{
fn fract_exp_digits<const DIGIT_BITNESS: usize>(
digits: &[Self],
) -> Option<(Fraction, i32)> {
let mut result_digits =
vec![
Self::zero();
2usize + (Fraction::MANTISSA_DIGITS + 1usize) / DIGIT_BITNESS
];
let size = digits.len();
let mut bits_count = digits[digits.len() - 1].bit_length();
if size > (usize::MAX - 1) / DIGIT_BITNESS
&& (size > (usize::MAX - 1) / DIGIT_BITNESS + 1
|| bits_count > (usize::MAX - 1) % DIGIT_BITNESS + 1)
{
return None;
}
bits_count += (size - 1) * DIGIT_BITNESS;
let mut result_digits_count = if bits_count
<= Fraction::MANTISSA_DIGITS + 2
{
let shift_digits =
(Fraction::MANTISSA_DIGITS + 2 - bits_count) / DIGIT_BITNESS;
let shift_bits =
(Fraction::MANTISSA_DIGITS + 2 - bits_count) % DIGIT_BITNESS;
let mut result_size = shift_digits;
let remainder = Self::shift_digits_left_in_place::<DIGIT_BITNESS>(
digits,
shift_bits,
&mut result_digits[result_size..],
);
result_size += size;
result_digits[result_size] = remainder;
result_size += 1;
result_size
} else {
let mut shift_digits =
(bits_count - Fraction::MANTISSA_DIGITS - 2) / DIGIT_BITNESS;
let shift_bits =
(bits_count - Fraction::MANTISSA_DIGITS - 2) % DIGIT_BITNESS;
let remainder = Self::shift_digits_right_in_place::<DIGIT_BITNESS>(
&digits[shift_digits..],
shift_bits,
&mut result_digits,
);
let result_size = size - shift_digits;
if remainder.is_zero() {
while shift_digits > 0 {
shift_digits -= 1;
if !digits[shift_digits].is_zero() {
result_digits[0] |= Self::one();
break;
}
}
} else {
result_digits[0] |= Self::one();
}
result_size
};
{
const HALF_EVEN_CORRECTION: [i8; 8] = [0, -1, -2, 1, 0, -1, 2, 1];
result_digits[0] = unsafe {
Self::try_from(
OppositionOf::<Self>::try_from(result_digits[0])
.unwrap_unchecked()
+ OppositionOf::<Self>::from(
HALF_EVEN_CORRECTION[usize::try_from(
result_digits[0] & Self::from(7u8),
)
.unwrap_unchecked()],
),
)
.unwrap_unchecked()
};
}
result_digits_count -= 1;
let mut fraction = Fraction::from(result_digits[result_digits_count]);
while result_digits_count > 0 {
result_digits_count -= 1;
fraction = fraction
* Fraction::from((1usize << DIGIT_BITNESS) as f32)
+ Fraction::from(result_digits[result_digits_count]);
}
fraction /=
Fraction::from((1u64 << (Fraction::MANTISSA_DIGITS + 2)) as f32);
if fraction.is_one() {
if bits_count == usize::MAX {
return None;
}
fraction = Fraction::from(0.5);
bits_count += 1;
}
let exponent = unsafe { i32::try_from(bits_count).unwrap_unchecked() };
if exponent > Fraction::MAX_EXP {
None
} else {
Some((fraction, exponent))
}
}
}
pub(super) trait InvertComponents: Sized {
fn invert_components<const DIGIT_BITNESS: usize>(
sign: Sign,
digits: &[Self],
) -> (Sign, Vec<Self>);
}
impl<Digit: One + SumComponents> InvertComponents for Digit {
fn invert_components<const DIGIT_BITNESS: usize>(
sign: Sign,
digits: &[Digit],
) -> (Sign, Vec<Digit>) {
let (sign, digits) = Digit::sum_components::<DIGIT_BITNESS>(
sign,
digits,
Sign::one(),
&[Digit::one()],
);
(-sign, digits)
}
}
pub(super) trait MultiplyDigits: Sized {
fn multiply_digits<const DIGIT_BITNESS: usize>(
first: &[Self],
second: &[Self],
) -> Vec<Self>;
}
impl<
Digit: Copy
+ MultiplyDigitsPlain
+ SubtractDigitsInPlace
+ SumDigits
+ SumDigitsInPlace
+ Zero,
> MultiplyDigits for Digit
where
for<'a> &'a Digit: Zeroable,
{
fn multiply_digits<const DIGIT_BITNESS: usize>(
first: &[Self],
second: &[Self],
) -> Vec<Self> {
const KARATSUBA_CUTOFF: usize = 70;
const KARATSUBA_SQUARE_CUTOFF: usize = KARATSUBA_CUTOFF * 2;
let (longest, shortest) = if first.len() < second.len() {
(&second, &first)
} else {
(&first, &second)
};
if shortest.len()
<= if shortest.as_ptr() == longest.as_ptr() {
KARATSUBA_SQUARE_CUTOFF
} else {
KARATSUBA_CUTOFF
}
{
if shortest.len() == 1 && shortest[0].is_zero() {
vec![Self::zero()]
} else {
Self::multiply_digits_plain::<DIGIT_BITNESS>(shortest, longest)
}
} else {
let are_digits_lopsided = 2 * shortest.len() <= longest.len();
if are_digits_lopsided {
let shortest_size = shortest.len();
let mut longest_size = longest.len();
let mut result =
vec![Self::zero(); shortest_size + longest_size];
let mut processed_digits_count = 0;
while longest_size > 0 {
let step_digits_count = longest_size.min(shortest_size);
let product = Self::multiply_digits::<DIGIT_BITNESS>(
shortest,
&longest[processed_digits_count
..processed_digits_count + step_digits_count],
);
Self::sum_digits_in_place::<DIGIT_BITNESS>(
&mut result[processed_digits_count..],
&product,
);
longest_size -= step_digits_count;
processed_digits_count += step_digits_count;
}
trim_leading_zeros(&mut result);
result
} else {
let shift = longest.len() >> 1;
let (shortest_high, shortest_low) =
split_digits(shortest, shift);
let (longest_high, longest_low) =
if shortest.as_ptr() == longest.as_ptr() {
(shortest_high.clone(), shortest_low.clone())
} else {
split_digits(longest, shift)
};
let mut result =
vec![Self::zero(); shortest.len() + longest.len()];
let highs_product = Self::multiply_digits::<DIGIT_BITNESS>(
&shortest_high,
&longest_high,
);
for (index, &digit) in highs_product.iter().enumerate() {
result[index + 2 * shift] = digit;
}
let lows_product = Self::multiply_digits::<DIGIT_BITNESS>(
&shortest_low,
&longest_low,
);
for (index, &digit) in lows_product.iter().enumerate() {
result[index] = digit;
}
Self::subtract_digits_in_place::<DIGIT_BITNESS>(
&mut result[shift..],
&lows_product,
);
Self::subtract_digits_in_place::<DIGIT_BITNESS>(
&mut result[shift..],
&highs_product,
);
let shortest_components_sum = Self::sum_digits::<DIGIT_BITNESS>(
&shortest_high,
&shortest_low,
);
let longest_components_sum =
if shortest.as_ptr() == longest.as_ptr() {
shortest_components_sum.clone()
} else {
Self::sum_digits::<DIGIT_BITNESS>(
&longest_high,
&longest_low,
)
};
let components_sums_product =
Self::multiply_digits::<DIGIT_BITNESS>(
&shortest_components_sum,
&longest_components_sum,
);
Self::sum_digits_in_place::<DIGIT_BITNESS>(
&mut result[shift..],
&components_sums_product,
);
trim_leading_zeros(&mut result);
result
}
}
}
}
pub(super) trait MultiplyDigitsPlain: Sized {
fn multiply_digits_plain<const DIGIT_BITNESS: usize>(
shortest: &[Self],
longest: &[Self],
) -> Vec<Self>;
}
impl<
Digit: AddAssign
+ Copy
+ DoublePrecision
+ TryFrom<DoublePrecisionOf<Digit>>
+ Zero,
> MultiplyDigitsPlain for Digit
where
for<'a> &'a Digit: Zeroable,
for<'a> &'a DoublePrecisionOf<Digit>: Zeroable,
DoublePrecisionOf<Digit>: Add<Output = DoublePrecisionOf<Digit>>
+ AddAssign
+ BitAnd<Output = DoublePrecisionOf<Digit>>
+ Copy
+ DigitMask
+ Mul<Output = DoublePrecisionOf<Digit>>
+ ShlAssign<usize>
+ ShrAssign<usize>
+ Zero,
{
fn multiply_digits_plain<const DIGIT_BITNESS: usize>(
shortest: &[Self],
longest: &[Self],
) -> Vec<Self> {
let mut result = vec![Self::zero(); shortest.len() + longest.len()];
let digit_mask = DoublePrecisionOf::<Self>::digit_mask(DIGIT_BITNESS);
if shortest.as_ptr() == longest.as_ptr() {
for index in 0..shortest.len() {
let mut digit =
DoublePrecisionOf::<Self>::from(shortest[index]);
let mut result_position = index << 1;
let mut accumulator =
DoublePrecisionOf::<Self>::from(result[result_position])
+ digit * digit;
result[result_position] = unsafe {
Self::try_from(accumulator & digit_mask).unwrap_unchecked()
};
result_position += 1;
accumulator >>= DIGIT_BITNESS;
digit <<= 1;
for &digit_of_shortest in &shortest[index + 1..] {
accumulator += DoublePrecisionOf::<Self>::from(
result[result_position],
) + DoublePrecisionOf::<Self>::from(
digit_of_shortest,
) * digit;
result[result_position] = unsafe {
Self::try_from(accumulator & digit_mask)
.unwrap_unchecked()
};
result_position += 1;
accumulator >>= DIGIT_BITNESS;
}
if !accumulator.is_zero() {
accumulator += DoublePrecisionOf::<Self>::from(
result[result_position],
);
result[result_position] = unsafe {
Self::try_from(accumulator & digit_mask)
.unwrap_unchecked()
};
result_position += 1;
accumulator >>= DIGIT_BITNESS;
}
if !accumulator.is_zero() {
result[result_position] += unsafe {
Self::try_from(accumulator & digit_mask)
.unwrap_unchecked()
};
}
}
} else {
for (index, digit_of_shortest) in shortest.iter().enumerate() {
let mut accumulator = DoublePrecisionOf::<Self>::zero();
let digit =
DoublePrecisionOf::<Self>::from(*digit_of_shortest);
let mut result_position = index;
for &second_digit in longest {
accumulator = accumulator
+ DoublePrecisionOf::<Self>::from(
result[result_position],
)
+ DoublePrecisionOf::<Self>::from(second_digit)
* digit;
result[result_position] = unsafe {
Self::try_from(accumulator & digit_mask)
.unwrap_unchecked()
};
result_position += 1;
accumulator >>= DIGIT_BITNESS;
}
if !accumulator.is_zero() {
result[result_position] += unsafe {
Self::try_from(accumulator & digit_mask)
.unwrap_unchecked()
};
}
}
}
trim_leading_zeros(&mut result);
result
}
}
pub(super) fn negate_bytes(digits: &mut [u8]) {
let mut carry = true;
for digit in digits {
*digit = !*digit;
if carry {
*digit = digit.wrapping_add(1);
carry = digit.is_zero();
}
}
}
pub(super) trait GreaterBinaryBaseFromNonBinaryDigits<Source>:
Sized
{
fn greater_binary_base_from_non_binary_digits<
const TARGET_BITNESS: usize,
>(
source: &[Source],
source_base: usize,
) -> Vec<Self>;
}
impl<
Source: Copy,
Target: Copy + DoublePrecision + TryFrom<DoublePrecisionOf<Target>> + Zero,
> GreaterBinaryBaseFromNonBinaryDigits<Source> for Target
where
for<'a> &'a DoublePrecisionOf<Target>: Zeroable,
DoublePrecisionOf<Target>: AddAssign
+ BitAnd<Output = DoublePrecisionOf<Target>>
+ Copy
+ DigitMask
+ From<Source>
+ Mul<Output = DoublePrecisionOf<Target>>
+ MulAssign
+ ShrAssign<usize>
+ TryFrom<usize>
+ Zero,
{
fn greater_binary_base_from_non_binary_digits<
const TARGET_BITNESS: usize,
>(
source: &[Source],
source_base: usize,
) -> Vec<Self> {
static mut BASES_LOGS: [f64; 37] = [0.0; 37];
static mut INFIMUM_BASES_EXPONENTS: [usize; 37] = [0; 37];
static mut INFIMUM_BASES_POWERS: [usize; 37] = [0; 37];
let target_digit_mask =
DoublePrecisionOf::<Self>::digit_mask(TARGET_BITNESS);
if unsafe { BASES_LOGS[source_base] } == 0.0 {
let bases_log = (source_base as f64).ln()
/ ((1usize << TARGET_BITNESS) as f64).ln();
unsafe { BASES_LOGS[source_base] = bases_log };
let mut infimum_base_power = source_base;
let mut infimum_base_exponent: usize = 1;
loop {
let candidate: usize = infimum_base_power * source_base;
if candidate > 1usize << TARGET_BITNESS {
break;
}
infimum_base_power = candidate;
infimum_base_exponent += 1;
}
unsafe { INFIMUM_BASES_POWERS[source_base] = infimum_base_power };
unsafe {
INFIMUM_BASES_EXPONENTS[source_base] = infimum_base_exponent;
};
}
let digits_count_upper_bound =
(source.len() as f64) * unsafe { BASES_LOGS[source_base] } + 1.0;
let mut result =
Vec::<Self>::with_capacity(digits_count_upper_bound as usize);
let infimum_base_exponent =
unsafe { INFIMUM_BASES_EXPONENTS[source_base] };
let infimum_base_power = unsafe { INFIMUM_BASES_POWERS[source_base] };
let mut reversed_source = source.iter().rev();
while let Some(&digit) = reversed_source.next() {
let mut accumulator = DoublePrecisionOf::<Self>::from(digit);
let mut base_exponent: usize = 1;
while base_exponent < infimum_base_exponent {
if let Some(&digit) = reversed_source.next() {
base_exponent += 1;
accumulator *= unsafe {
DoublePrecisionOf::<Self>::try_from(source_base)
.unwrap_unchecked()
};
accumulator += DoublePrecisionOf::<Self>::from(digit);
} else {
break;
}
}
let base_power = if base_exponent == infimum_base_exponent {
infimum_base_power
} else {
source_base.pow(base_exponent as u32)
};
for result_position in &mut result {
accumulator += <DoublePrecisionOf<Self> as From<Self>>::from(
*result_position,
) * unsafe {
DoublePrecisionOf::<Self>::try_from(base_power)
.unwrap_unchecked()
};
*result_position = unsafe {
Self::try_from(accumulator & target_digit_mask)
.unwrap_unchecked()
};
accumulator >>= TARGET_BITNESS;
}
if !accumulator.is_zero() {
result.push(unsafe {
Self::try_from(accumulator).unwrap_unchecked()
});
}
}
if result.is_empty() {
result.push(Self::zero());
}
result
}
}
pub(super) trait LesserBinaryBaseFromNonBinaryDigits<Source>:
Sized
{
fn lesser_binary_base_from_non_binary_digits<const TARGET_BITNESS: usize>(
source: &[Source],
source_base: usize,
) -> Vec<Self>;
}
impl<
Source: Copy,
Target: Copy + DoublePrecision + TryFrom<DoublePrecisionOf<Target>> + Zero,
> LesserBinaryBaseFromNonBinaryDigits<Source> for Target
where
for<'a> &'a DoublePrecisionOf<Target>: Zeroable,
DoublePrecisionOf<Target>: AddAssign
+ BitAnd<Output = DoublePrecisionOf<Target>>
+ Copy
+ DigitMask
+ From<Source>
+ Mul<Output = DoublePrecisionOf<Target>>
+ ShrAssign<usize>
+ TryFrom<usize>,
{
fn lesser_binary_base_from_non_binary_digits<
const TARGET_BITNESS: usize,
>(
source: &[Source],
source_base: usize,
) -> Vec<Self> {
static mut BASES_LOGS: [f64; 37] = [0.0; 37];
let target_digit_mask =
DoublePrecisionOf::<Self>::digit_mask(TARGET_BITNESS);
if unsafe { BASES_LOGS[source_base] } == 0.0 {
let bases_log = (source_base as f64).ln()
/ ((1usize << TARGET_BITNESS) as f64).ln();
unsafe { BASES_LOGS[source_base] = bases_log };
}
let digits_count_upper_bound =
(source.len() as f64) * unsafe { BASES_LOGS[source_base] } + 1.0;
let mut result =
Vec::<Self>::with_capacity(digits_count_upper_bound as usize);
let source_base = unsafe {
DoublePrecisionOf::<Self>::try_from(source_base).unwrap_unchecked()
};
for &digit in source.iter().rev() {
let mut accumulator = DoublePrecisionOf::<Self>::from(digit);
for result_position in &mut result {
accumulator += <DoublePrecisionOf<Self> as From<Self>>::from(
*result_position,
) * source_base;
*result_position = unsafe {
Self::try_from(accumulator & target_digit_mask)
.unwrap_unchecked()
};
accumulator >>= TARGET_BITNESS;
}
while !accumulator.is_zero() {
result.push(unsafe {
Self::try_from(accumulator & target_digit_mask)
.unwrap_unchecked()
});
accumulator >>= TARGET_BITNESS;
}
}
if result.is_empty() {
result.push(Self::zero());
}
result
}
}
pub(super) trait ReduceDigits<Output>: Sized {
fn reduce_digits<const DIGIT_BITNESS: usize>(digits: &[Self]) -> Output;
}
impl<
Digit: Copy,
Output: BitOr<Output = Output>
+ Shl<usize, Output = Output>
+ From<Digit>
+ Zero,
> ReduceDigits<Output> for Digit
{
fn reduce_digits<const DIGIT_BITNESS: usize>(digits: &[Self]) -> Output {
let mut result = Output::zero();
for &digit in digits.iter().rev() {
result = (result << DIGIT_BITNESS) | Output::from(digit);
}
result
}
}
pub(super) trait MaybeReduceDigits<Output>: Sized {
fn maybe_reduce_digits<const DIGIT_BITNESS: usize>(
digits: &[Self],
) -> Option<Output>;
}
impl<
Digit: Copy,
Output: CheckedShl<u32, Output = Option<Output>>
+ BitOr<Output = Output>
+ TryFrom<Digit>
+ Zero,
> MaybeReduceDigits<Output> for Digit
{
fn maybe_reduce_digits<const DIGIT_BITNESS: usize>(
digits: &[Self],
) -> Option<Output> {
let mut result = Output::zero();
for &digit in digits.iter().rev() {
result = result.checked_shl(unsafe {
u32::try_from(DIGIT_BITNESS).unwrap_unchecked()
})? | Output::try_from(digit).ok()?;
}
Some(result)
}
}
pub(super) trait ReduceDigitsToFloat<Output>: Sized {
fn reduce_digits_to_float<const DIGIT_BITNESS: usize>(
digits: &[Self],
) -> Output;
}
macro_rules! reduce_digits_to_float_impl {
($($float:ty)*) => ($(
impl<Digit: Copy> ReduceDigitsToFloat<$float> for Digit
where
$float: From<Digit>,
{
fn reduce_digits_to_float<const DIGIT_BITNESS: usize>(
digits: &[Self],
) -> $float {
const EXPONENT_BASE: u32 =
(1 << (<f32>::EXPONENT_BITS_COUNT - 1usize)) - 1;
debug_assert!(DIGIT_BITNESS < ((1 << f32::EXPONENT_BITS_COUNT) - 1));
let mut result = 0 as $float;
let scale = f32::from_bits(
(EXPONENT_BASE + (DIGIT_BITNESS as u32))
<< f32::SIGNIFICAND_BITS_COUNT,
) as $float;
for &digit in digits.iter().rev() {
result = result * scale + <$float>::from(digit);
}
result
}
}
)*)
}
reduce_digits_to_float_impl!(f32 f64);
pub(super) trait PrimitiveShiftDigitsLeft: Sized {
fn primitive_shift_digits_left<const DIGIT_BITNESS: usize>(
digits: &[Self],
shift_quotient: usize,
shift_remainder: Self,
) -> Option<Vec<Self>>;
}
impl<
Digit: Copy + DoublePrecision + TryFrom<DoublePrecisionOf<Digit>> + Zero,
> PrimitiveShiftDigitsLeft for Digit
where
for<'a> &'a Digit: Zeroable,
DoublePrecisionOf<Digit>: BitAnd<Output = DoublePrecisionOf<Digit>>
+ BitOrAssign
+ Copy
+ DigitMask
+ Shl<Digit, Output = DoublePrecisionOf<Digit>>
+ ShrAssign<usize>
+ Zero,
{
fn primitive_shift_digits_left<const DIGIT_BITNESS: usize>(
digits: &[Self],
shift_quotient: usize,
shift_remainder: Self,
) -> Option<Vec<Self>> {
let mut result = Vec::<Self>::new();
result
.try_reserve_exact(
digits.len()
+ shift_quotient
+ usize::from(!shift_remainder.is_zero()),
)
.ok()?;
for _ in 0..shift_quotient {
result.push(Self::zero());
}
let mut accumulator = DoublePrecisionOf::<Self>::zero();
let digit_mask = DoublePrecisionOf::<Self>::digit_mask(DIGIT_BITNESS);
for &digit in digits {
accumulator |=
DoublePrecisionOf::<Self>::from(digit) << shift_remainder;
result.push(unsafe {
Self::try_from(accumulator & digit_mask).unwrap_unchecked()
});
accumulator >>= DIGIT_BITNESS;
}
if !shift_remainder.is_zero() {
result.push(unsafe {
Self::try_from(accumulator).unwrap_unchecked()
});
}
trim_leading_zeros(&mut result);
Some(result)
}
}
pub(super) trait ShiftDigitsLeft: Sized {
fn shift_digits_left<const DIGIT_BITNESS: usize>(
base: &[Self],
shift: &[Self],
) -> Result<Vec<Self>, ShlError>;
}
impl<
Digit: Copy
+ DivRemDigitsByDigit
+ MaybeReduceDigits<usize>
+ PrimitiveShiftDigitsLeft
+ TryFrom<usize>,
> ShiftDigitsLeft for Digit
{
fn shift_digits_left<const DIGIT_BITNESS: usize>(
base: &[Self],
shift: &[Self],
) -> Result<Vec<Self>, ShlError> {
let (shift_quotient_digits, shift_remainder) =
Self::div_rem_digits_by_digit::<DIGIT_BITNESS>(shift, unsafe {
Self::try_from(DIGIT_BITNESS).unwrap_unchecked()
});
let shift_quotient =
Self::maybe_reduce_digits::<DIGIT_BITNESS>(&shift_quotient_digits)
.ok_or(ShlError::TooLarge)?;
if shift_quotient >= usize::MAX / std::mem::size_of::<Self>() {
Err(ShlError::TooLarge)
} else {
Self::primitive_shift_digits_left::<DIGIT_BITNESS>(
base,
shift_quotient,
shift_remainder,
)
.ok_or(ShlError::OutOfMemory)
}
}
}
pub(super) trait ShiftDigitsLeftInPlace: Sized {
fn shift_digits_left_in_place<const DIGIT_BITNESS: usize>(
input: &[Self],
shift: usize,
output: &mut [Self],
) -> Self;
}
impl<Digit: Copy + DoublePrecision + TryFrom<DoublePrecisionOf<Self>>>
ShiftDigitsLeftInPlace for Digit
where
for<'a> &'a Digit: Zeroable,
DoublePrecisionOf<Digit>: BitAnd<Output = DoublePrecisionOf<Digit>>
+ BitOrAssign
+ Copy
+ DigitMask
+ Shl<usize, Output = DoublePrecisionOf<Digit>>
+ ShrAssign<usize>
+ Zero,
{
fn shift_digits_left_in_place<const DIGIT_BITNESS: usize>(
input: &[Self],
shift: usize,
output: &mut [Self],
) -> Self {
let mut accumulator = DoublePrecisionOf::<Self>::zero();
let mask = DoublePrecisionOf::<Self>::digit_mask(DIGIT_BITNESS);
for index in 0..input.len() {
accumulator |=
DoublePrecisionOf::<Self>::from(input[index]) << shift;
output[index] = unsafe {
Self::try_from(accumulator & mask).unwrap_unchecked()
};
accumulator >>= DIGIT_BITNESS;
}
unsafe { Self::try_from(accumulator).unwrap_unchecked() }
}
}
pub(super) trait ShiftDigitsRightInPlace: Sized {
fn shift_digits_right_in_place<const DIGIT_BITNESS: usize>(
input: &[Self],
shift: usize,
output: &mut [Self],
) -> Self;
}
impl<Digit: Copy + DoublePrecision + TryFrom<DoublePrecisionOf<Self>>>
ShiftDigitsRightInPlace for Digit
where
for<'a> &'a Digit: Zeroable,
DoublePrecisionOf<Digit>: BitAndAssign
+ BitOrAssign
+ Copy
+ DigitMask
+ Shr<usize, Output = DoublePrecisionOf<Digit>>
+ ShlAssign<usize>
+ Zero,
{
fn shift_digits_right_in_place<const DIGIT_BITNESS: usize>(
input: &[Self],
shift: usize,
output: &mut [Self],
) -> Self {
let mut accumulator = DoublePrecisionOf::<Self>::zero();
let mask = DoublePrecisionOf::<Self>::digit_mask(shift);
for index in (0..input.len()).rev() {
accumulator <<= DIGIT_BITNESS;
accumulator |= DoublePrecisionOf::<Self>::from(input[index]);
output[index] = unsafe {
Self::try_from(accumulator >> shift).unwrap_unchecked()
};
accumulator &= mask;
}
unsafe { Self::try_from(accumulator).unwrap_unchecked() }
}
}
pub(super) trait PrimitiveShiftDigitsRight: Sized {
fn primitive_shift_digits_right<const DIGIT_BITNESS: usize>(
digits: &[Self],
shift_quotient: usize,
shift_remainder: Self,
) -> Vec<Self>;
}
impl<
Digit: BitAnd<Output = Digit>
+ BitOrAssign
+ BitXor<Output = Digit>
+ Copy
+ DigitMask
+ Shl<usize, Output = Digit>
+ Shr<usize, Output = Digit>
+ Zero,
> PrimitiveShiftDigitsRight for Digit
where
for<'a> &'a Digit: Zeroable,
usize: TryFrom<Digit>,
{
fn primitive_shift_digits_right<const DIGIT_BITNESS: usize>(
digits: &[Self],
shift_quotient: usize,
shift_remainder: Self,
) -> Vec<Self> {
if digits.len() <= shift_quotient {
return vec![Self::zero()];
}
let result_digits_count = digits.len() - shift_quotient;
let shift_remainder =
unsafe { usize::try_from(shift_remainder).unwrap_unchecked() };
let high_shift = DIGIT_BITNESS - shift_remainder;
let low_mask = Self::digit_mask(high_shift);
let high_mask = Self::digit_mask(DIGIT_BITNESS) ^ low_mask;
let mut result = vec![Self::zero(); result_digits_count];
let mut position = shift_quotient;
for (index, result_digit) in result.iter_mut().enumerate() {
*result_digit = (digits[position] >> shift_remainder) & low_mask;
if index + 1 < result_digits_count {
*result_digit |=
(digits[position + 1] << high_shift) & high_mask;
}
position += 1;
}
trim_leading_zeros(&mut result);
result
}
}
pub(super) trait ShiftDigitsRight: Sized {
fn shift_digits_right<const DIGIT_BITNESS: usize>(
base_sign: Sign,
base: &[Self],
shift: &[Self],
) -> (Sign, Vec<Self>);
}
impl<
Digit: Copy
+ DivRemDigitsByDigit
+ InvertComponents
+ MaybeReduceDigits<usize>
+ One
+ PrimitiveShiftDigitsRight
+ TryFrom<usize>
+ Zero,
> ShiftDigitsRight for Digit
where
for<'a> &'a Digit: Zeroable,
{
fn shift_digits_right<const DIGIT_BITNESS: usize>(
base_sign: Sign,
base: &[Self],
shift: &[Self],
) -> (Sign, Vec<Self>) {
let (shift_quotient_digits, shift_remainder) =
Self::div_rem_digits_by_digit::<DIGIT_BITNESS>(shift, unsafe {
Self::try_from(DIGIT_BITNESS).unwrap_unchecked()
});
let shift_quotient =
Self::maybe_reduce_digits::<DIGIT_BITNESS>(&shift_quotient_digits)
.unwrap_or(usize::MAX / std::mem::size_of::<Self>());
if shift_quotient >= usize::MAX / std::mem::size_of::<Self>() {
if base_sign.is_negative() {
(-Sign::one(), vec![Self::one(); 1])
} else {
(Sign::zero(), vec![Self::zero(); 1])
}
} else if base_sign.is_negative() {
let (inverted_sign, inverted_digits) =
Self::invert_components::<DIGIT_BITNESS>(base_sign, base);
let digits = Self::primitive_shift_digits_right::<DIGIT_BITNESS>(
&inverted_digits,
shift_quotient,
shift_remainder,
);
Self::invert_components::<DIGIT_BITNESS>(
inverted_sign * to_digits_sign(&digits),
&digits,
)
} else {
let digits = Self::primitive_shift_digits_right::<DIGIT_BITNESS>(
base,
shift_quotient,
shift_remainder,
);
(base_sign * to_digits_sign(&digits), digits)
}
}
}
fn split_digits<Digit: Clone>(
digits: &[Digit],
size: usize,
) -> (Vec<Digit>, Vec<Digit>)
where
for<'a> &'a Digit: Zeroable,
{
let (low, high) = digits.split_at(digits.len().min(size));
let (mut low, mut high) = (low.to_vec(), high.to_vec());
trim_leading_zeros(&mut high);
trim_leading_zeros(&mut low);
(high, low)
}
pub(super) trait SubtractComponents: Sized {
fn subtract_components<const DIGIT_BITNESS: usize>(
minuend_sign: Sign,
minuend: &[Self],
subtrahend_sign: Sign,
subtrahend: &[Self],
) -> (Sign, Vec<Self>);
}
impl<Digit: SubtractDigits + SumDigits> SubtractComponents for Digit {
fn subtract_components<const DIGIT_BITNESS: usize>(
minuend_sign: Sign,
minuend: &[Self],
subtrahend_sign: Sign,
subtrahend: &[Self],
) -> (Sign, Vec<Self>) {
if minuend_sign.is_negative() {
if subtrahend_sign.is_negative() {
Self::subtract_digits::<DIGIT_BITNESS>(
subtrahend,
minuend,
Sign::one(),
)
} else {
(
-Sign::one(),
Self::sum_digits::<DIGIT_BITNESS>(minuend, subtrahend),
)
}
} else if subtrahend_sign.is_negative() {
(
Sign::one(),
Self::sum_digits::<DIGIT_BITNESS>(minuend, subtrahend),
)
} else {
Self::subtract_digits::<DIGIT_BITNESS>(
minuend,
subtrahend,
Sign::one(),
)
}
}
}
pub(super) trait SubtractDigits: Sized {
fn subtract_digits<const DIGIT_BITNESS: usize>(
minuend: &[Self],
subtrahend: &[Self],
sign: Sign,
) -> (Sign, Vec<Self>);
}
impl<
Digit: BitAnd<Output = Digit>
+ BitAndAssign
+ Copy
+ DigitMask
+ One
+ PartialOrd
+ ShrAssign<usize>
+ WrappingSub<Output = Digit>
+ Zero,
> SubtractDigits for Digit
where
for<'a> &'a Digit: Zeroable,
{
fn subtract_digits<const DIGIT_BITNESS: usize>(
minuend: &[Self],
subtrahend: &[Self],
mut sign: Sign,
) -> (Sign, Vec<Self>) {
let mut longest = &minuend;
let mut shortest = &subtrahend;
let mut longest_size = longest.len();
let mut shortest_size = shortest.len();
match longest_size.cmp(&shortest_size) {
Ordering::Less => {
(longest, shortest) = (shortest, longest);
(longest_size, shortest_size) = (shortest_size, longest_size);
sign = -sign;
}
Ordering::Equal => {
let mut index = shortest_size;
loop {
index -= 1;
if index == 0 || longest[index] != shortest[index] {
break;
}
}
if index == 0 && longest[0] == shortest[0] {
return (Sign::zero(), vec![Self::zero()]);
}
if longest[index] < shortest[index] {
(longest, shortest) = (shortest, longest);
sign = -sign;
}
longest_size = index + 1;
shortest_size = index + 1;
}
Ordering::Greater => {}
};
let mut result = Vec::<Self>::with_capacity(longest_size);
let mut accumulator = Self::zero();
let digit_mask = Self::digit_mask(DIGIT_BITNESS);
for index in 0..shortest_size {
accumulator = longest[index]
.wrapping_sub(shortest[index])
.wrapping_sub(accumulator);
result.push(accumulator & digit_mask);
accumulator >>= DIGIT_BITNESS;
accumulator &= Self::one();
}
for index in shortest_size..longest_size {
accumulator = longest[index].wrapping_sub(accumulator);
result.push(accumulator & digit_mask);
accumulator >>= DIGIT_BITNESS;
accumulator &= Self::one();
}
trim_leading_zeros(&mut result);
(sign, result)
}
}
pub(super) trait SubtractDigitsInPlace: Sized {
fn subtract_digits_in_place<const DIGIT_BITNESS: usize>(
longest: &mut [Self],
shortest: &[Self],
) -> Self;
}
impl<
Digit: BitAnd<Output = Digit>
+ BitAndAssign
+ Copy
+ DigitMask
+ One
+ ShrAssign<usize>
+ WrappingSub<Output = Digit>
+ Zero,
> SubtractDigitsInPlace for Digit
where
for<'a> &'a Digit: Zeroable,
{
fn subtract_digits_in_place<const DIGIT_BITNESS: usize>(
longest: &mut [Self],
shortest: &[Self],
) -> Self {
let mut accumulator = Self::zero();
let digit_mask = Self::digit_mask(DIGIT_BITNESS);
for index in 0..shortest.len() {
accumulator = longest[index]
.wrapping_sub(shortest[index])
.wrapping_sub(accumulator);
longest[index] = accumulator & digit_mask;
accumulator >>= DIGIT_BITNESS;
accumulator &= Self::one();
}
for digit_of_longest in &mut longest[shortest.len()..] {
if accumulator.is_zero() {
break;
}
accumulator = (*digit_of_longest).wrapping_sub(accumulator);
*digit_of_longest = accumulator & digit_mask;
accumulator >>= DIGIT_BITNESS;
accumulator &= Self::one();
}
accumulator
}
}
pub(super) trait SumComponents: Sized {
fn sum_components<const DIGIT_BITNESS: usize>(
first_sign: Sign,
first: &[Self],
second_sign: Sign,
second: &[Self],
) -> (Sign, Vec<Self>);
}
impl<Digit: SubtractDigits + SumDigits> SumComponents for Digit {
fn sum_components<const DIGIT_BITNESS: usize>(
first_sign: Sign,
first: &[Self],
second_sign: Sign,
second: &[Self],
) -> (Sign, Vec<Self>) {
if first_sign.is_negative() {
if second_sign.is_negative() {
(
-Sign::one(),
Self::sum_digits::<DIGIT_BITNESS>(first, second),
)
} else {
Self::subtract_digits::<DIGIT_BITNESS>(
second,
first,
Sign::one(),
)
}
} else if second_sign.is_negative() {
Self::subtract_digits::<DIGIT_BITNESS>(first, second, Sign::one())
} else {
(
first_sign.max(second_sign),
Self::sum_digits::<DIGIT_BITNESS>(first, second),
)
}
}
}
pub(super) trait SumDigits: Sized {
fn sum_digits<const DIGIT_BITNESS: usize>(
first: &[Self],
second: &[Self],
) -> Vec<Self>;
}
impl<
Digit: Add<Output = Digit>
+ AddAssign
+ BitAnd<Output = Digit>
+ Copy
+ DigitMask
+ ShrAssign<usize>
+ Zero,
> SumDigits for Digit
where
for<'a> &'a Digit: Zeroable,
{
fn sum_digits<const DIGIT_BITNESS: usize>(
first: &[Self],
second: &[Self],
) -> Vec<Self> {
let (longest, shortest) = if first.len() < second.len() {
(&second, &first)
} else {
(&first, &second)
};
let mut result = Vec::<Self>::with_capacity(longest.len() + 1);
let mut accumulator: Self = Self::zero();
let digit_mask = Self::digit_mask(DIGIT_BITNESS);
for index in 0..shortest.len() {
accumulator += longest[index] + shortest[index];
result.push(accumulator & digit_mask);
accumulator >>= DIGIT_BITNESS;
}
for index in shortest.len()..longest.len() {
accumulator += longest[index];
result.push(accumulator & digit_mask);
accumulator >>= DIGIT_BITNESS;
}
result.push(accumulator);
trim_leading_zeros(&mut result);
result
}
}
pub(super) trait SumDigitsInPlace: Sized {
fn sum_digits_in_place<const DIGIT_BITNESS: usize>(
longest: &mut [Self],
shortest: &[Self],
) -> Self;
}
impl<
Digit: Add<Output = Digit>
+ AddAssign
+ BitAnd<Output = Digit>
+ Copy
+ DigitMask
+ ShrAssign<usize>
+ Zero,
> SumDigitsInPlace for Digit
where
for<'a> &'a Digit: Zeroable,
{
fn sum_digits_in_place<const DIGIT_BITNESS: usize>(
longest: &mut [Self],
shortest: &[Self],
) -> Self {
let mut accumulator = Self::zero();
let digit_mask = Self::digit_mask(DIGIT_BITNESS);
for index in 0..shortest.len() {
accumulator = longest[index] + shortest[index] + accumulator;
longest[index] = accumulator & digit_mask;
accumulator >>= DIGIT_BITNESS;
}
for digit_of_longest in &mut longest[shortest.len()..] {
if accumulator.is_zero() {
break;
}
accumulator += *digit_of_longest;
*digit_of_longest = accumulator & digit_mask;
accumulator >>= DIGIT_BITNESS;
}
accumulator
}
}
pub trait DigitMask {
fn digit_mask(bitness: usize) -> Self;
}
impl<Digit: One + Shl<usize, Output = Digit> + Sub<Output = Digit>> DigitMask
for Digit
{
#[inline]
fn digit_mask(bitness: usize) -> Self {
(Self::one() << bitness) - Self::one()
}
}
#[inline]
pub(super) fn to_digits_sign<Digit>(digits: &[Digit]) -> Sign
where
for<'a> &'a Digit: Zeroable,
{
Sign::from(digits.len() > 1 || !digits[0].is_zero())
}
pub(super) trait GcdDigits: Sized {
fn gcd_digits<const DIGIT_BITNESS: usize>(
first: Vec<Self>,
second: Vec<Self>,
) -> (Sign, Vec<Self>);
}
impl<
Digit: BitLength<Output = usize>
+ Copy
+ DigitsFromNonZeroValue<DoublePrecisionOf<Digit>>
+ DivRemDigitsByDigit
+ DivRemDigitsByTwoOrMoreDigits
+ DoublePrecision
+ HasSignBit
+ PartialOrd
+ ReduceDigits<DoublePrecisionOf<Digit>>
+ Shr<usize, Output = Digit>
+ TryFrom<OppositionOf<DoublePrecisionOf<Digit>>>
+ WrappingSub<Output = Digit>
+ Zero,
> GcdDigits for Digit
where
for<'a> &'a Digit: Zeroable,
for<'a> &'a DoublePrecisionOf<Digit>: Zeroable,
DoublePrecisionOf<Digit>: Gcd<Output = DoublePrecisionOf<Digit>>
+ HasSignBit
+ Oppose
+ RemEuclid<Output = DoublePrecisionOf<Digit>>
+ TryFrom<OppositionOf<DoublePrecisionOf<Digit>>>,
OppositionOf<DoublePrecisionOf<Digit>>: Add<Output = OppositionOf<DoublePrecisionOf<Digit>>>
+ AddAssign
+ BitAnd<Output = OppositionOf<DoublePrecisionOf<Digit>>>
+ BitOr<Output = OppositionOf<DoublePrecisionOf<Digit>>>
+ BitOrAssign
+ Copy
+ DigitMask
+ Div<Output = OppositionOf<DoublePrecisionOf<Digit>>>
+ From<Digit>
+ Mul<Output = OppositionOf<DoublePrecisionOf<Digit>>>
+ One
+ PartialOrd
+ RemEuclid<Output = OppositionOf<DoublePrecisionOf<Digit>>>
+ Shl<usize, Output = OppositionOf<DoublePrecisionOf<Digit>>>
+ Shr<usize, Output = OppositionOf<DoublePrecisionOf<Digit>>>
+ ShrAssign<usize>
+ Sub<Output = OppositionOf<DoublePrecisionOf<Digit>>>
+ SubAssign
+ TryFrom<DoublePrecisionOf<Digit>>
+ Zero,
{
fn gcd_digits<const DIGIT_BITNESS: usize>(
first: Vec<Self>,
second: Vec<Self>,
) -> (Sign, Vec<Self>) {
let (mut largest, mut smallest) =
if digits_lesser_than(&first, &second) {
(second, first)
} else {
(first, second)
};
loop {
let largest_digits_count = largest.len();
if largest_digits_count <= 2usize {
break;
}
let smallest_digits_count = smallest.len();
if smallest_digits_count == 1usize && smallest[0].is_zero() {
return (Sign::one(), largest);
}
let highest_digit_bit_length =
largest[largest.len() - 1].bit_length();
let mut largest_leading_bits =
(OppositionOf::<DoublePrecisionOf<Self>>::from(
largest[largest_digits_count - 1usize],
) << (2 * DIGIT_BITNESS - highest_digit_bit_length))
| (OppositionOf::<DoublePrecisionOf<Self>>::from(
largest[largest_digits_count - 2usize],
) << (DIGIT_BITNESS - highest_digit_bit_length))
| OppositionOf::<DoublePrecisionOf<Self>>::from(
largest[largest_digits_count - 3usize]
>> highest_digit_bit_length,
);
let mut smallest_leading_bits =
if smallest_digits_count >= largest_digits_count - 2usize {
OppositionOf::<DoublePrecisionOf<Self>>::from(
smallest[largest_digits_count - 3usize]
>> highest_digit_bit_length,
)
} else {
OppositionOf::<DoublePrecisionOf<Self>>::zero()
} | if smallest_digits_count >= largest_digits_count - 1usize {
OppositionOf::<DoublePrecisionOf<Self>>::from(
smallest[largest_digits_count - 2usize],
) << (DIGIT_BITNESS - highest_digit_bit_length)
} else {
OppositionOf::<DoublePrecisionOf<Self>>::zero()
} | if smallest_digits_count >= largest_digits_count {
OppositionOf::<DoublePrecisionOf<Self>>::from(
smallest[largest_digits_count - 1],
) << (2 * DIGIT_BITNESS - highest_digit_bit_length)
} else {
OppositionOf::<DoublePrecisionOf<Self>>::zero()
};
let mut first_coefficient =
OppositionOf::<DoublePrecisionOf<Self>>::one();
let mut second_coefficient =
OppositionOf::<DoublePrecisionOf<Self>>::zero();
let mut third_coefficient =
OppositionOf::<DoublePrecisionOf<Self>>::zero();
let mut fourth_coefficient =
OppositionOf::<DoublePrecisionOf<Self>>::one();
let mut iterations_count = 0usize;
loop {
if third_coefficient == smallest_leading_bits {
break;
}
let scale = (largest_leading_bits
+ (first_coefficient
- OppositionOf::<DoublePrecisionOf<Self>>::one()))
/ (smallest_leading_bits - third_coefficient);
let next_third_coefficient =
second_coefficient + scale * fourth_coefficient;
let next_smallest_leading_bits =
largest_leading_bits - scale * smallest_leading_bits;
if next_third_coefficient > next_smallest_leading_bits {
break;
}
largest_leading_bits = smallest_leading_bits;
smallest_leading_bits = next_smallest_leading_bits;
let next_fourth_coefficient =
first_coefficient + scale * third_coefficient;
first_coefficient = fourth_coefficient;
second_coefficient = third_coefficient;
third_coefficient = next_third_coefficient;
fourth_coefficient = next_fourth_coefficient;
iterations_count += 1;
}
if iterations_count == 0 {
(largest, smallest) = if smallest_digits_count == 1 {
let (_, remainder) = Self::div_rem_digits_by_digit::<
DIGIT_BITNESS,
>(
&largest, smallest[0]
);
(smallest, vec![remainder])
} else {
let (_, remainder) =
Self::div_rem_by_two_or_more_digits::<DIGIT_BITNESS>(
&largest, &smallest,
);
(smallest, remainder)
};
continue;
}
if iterations_count % 2 != 0 {
(first_coefficient, second_coefficient) =
(-second_coefficient, -first_coefficient);
(third_coefficient, fourth_coefficient) =
(-fourth_coefficient, -third_coefficient);
}
let digit_mask =
OppositionOf::<DoublePrecisionOf<Self>>::digit_mask(
DIGIT_BITNESS,
);
let mut next_largest_accumulator =
OppositionOf::<DoublePrecisionOf<Self>>::zero();
let mut next_smallest_accumulator =
OppositionOf::<DoublePrecisionOf<Self>>::zero();
let mut next_largest_digits =
Vec::<Self>::with_capacity(largest_digits_count);
let mut next_smallest_digits =
Vec::<Self>::with_capacity(largest_digits_count);
for index in 0..smallest_digits_count {
next_largest_accumulator = next_largest_accumulator
+ (first_coefficient
* OppositionOf::<DoublePrecisionOf<Self>>::from(
largest[index],
))
- (second_coefficient
* OppositionOf::<DoublePrecisionOf<Self>>::from(
smallest[index],
));
next_smallest_accumulator = next_smallest_accumulator
+ (fourth_coefficient
* OppositionOf::<DoublePrecisionOf<Self>>::from(
smallest[index],
))
- (third_coefficient
* OppositionOf::<DoublePrecisionOf<Self>>::from(
largest[index],
));
next_largest_digits.push(unsafe {
Self::try_from(next_largest_accumulator & digit_mask)
.unwrap_unchecked()
});
next_smallest_digits.push(unsafe {
Self::try_from(next_smallest_accumulator & digit_mask)
.unwrap_unchecked()
});
next_largest_accumulator >>= DIGIT_BITNESS;
next_smallest_accumulator >>= DIGIT_BITNESS;
}
for &digit_of_largest in &largest[smallest_digits_count..] {
next_largest_accumulator += first_coefficient
* OppositionOf::<DoublePrecisionOf<Self>>::from(
digit_of_largest,
);
next_smallest_accumulator -= third_coefficient
* OppositionOf::<DoublePrecisionOf<Self>>::from(
digit_of_largest,
);
next_largest_digits.push(unsafe {
Self::try_from(next_largest_accumulator & digit_mask)
.unwrap_unchecked()
});
next_smallest_digits.push(unsafe {
Self::try_from(next_smallest_accumulator & digit_mask)
.unwrap_unchecked()
});
next_largest_accumulator >>= DIGIT_BITNESS;
next_smallest_accumulator >>= DIGIT_BITNESS;
}
trim_leading_zeros(&mut next_largest_digits);
trim_leading_zeros(&mut next_smallest_digits);
largest = next_largest_digits;
smallest = next_smallest_digits;
}
let reduced_result = Self::reduce_digits::<DIGIT_BITNESS>(&largest)
.gcd(Self::reduce_digits::<DIGIT_BITNESS>(&smallest));
if reduced_result.is_zero() {
(Sign::zero(), vec![Self::zero(); 1])
} else {
(
Sign::one(),
Self::digits_from_non_zero_value::<DIGIT_BITNESS>(
reduced_result,
),
)
}
}
}
pub(super) fn trim_leading_zeros<Digit>(digits: &mut Vec<Digit>)
where
for<'a> &'a Digit: Zeroable,
{
let mut digits_count = digits.len();
while digits_count > 1 && digits[digits_count - 1].is_zero() {
digits_count -= 1;
}
if digits_count != digits.len() {
digits.truncate(digits_count);
}
}
pub(super) trait DigitsFromNonZeroValue<Source>: Sized {
fn digits_from_non_zero_value<const DIGIT_BITNESS: usize>(
value: Source,
) -> Vec<Self>;
}
impl<
Digit: BitAnd<Output = Digit>
+ Copy
+ DigitMask
+ HasSignBit
+ Oppose
+ ShrAssign<usize>
+ TryFrom<Source>,
Source: BitAnd<Output = Source>
+ Copy
+ DigitMask
+ HasSignBit
+ Oppose
+ ShrAssign<usize>
+ TryFrom<OppositionOf<Source>>,
> DigitsFromNonZeroValue<Source> for Digit
where
for<'a> &'a Digit: Zeroable,
for<'a> &'a Source: Zeroable,
OppositionOf<Source>: TryFrom<Source>,
{
fn digits_from_non_zero_value<const DIGIT_BITNESS: usize>(
value: Source,
) -> Vec<Self> {
if std::mem::size_of::<Source>() < std::mem::size_of::<Self>()
|| (std::mem::size_of::<Source>() == std::mem::size_of::<Self>()
&& is_signed::<Source>()
&& is_unsigned::<Self>())
{
let mut value = if is_signed::<Source>() {
let value = unsafe {
OppositionOf::<Source>::try_from(value).unwrap_unchecked()
};
unsafe {
Self::try_from(
Source::try_from(if value.is_negative() {
-value
} else {
value
})
.unwrap_unchecked(),
)
.unwrap_unchecked()
}
} else {
unsafe { Self::try_from(value).unwrap_unchecked() }
};
let mut digits = Vec::<Self>::new();
let digit_mask = Self::digit_mask(DIGIT_BITNESS);
while !value.is_zero() {
digits.push(value & digit_mask);
value >>= DIGIT_BITNESS;
}
digits
} else {
let mut value = if is_signed::<Source>() {
let value = unsafe {
OppositionOf::<Source>::try_from(value).unwrap_unchecked()
};
if value.is_negative() {
unsafe { Source::try_from(-value).unwrap_unchecked() }
} else {
unsafe { Source::try_from(value).unwrap_unchecked() }
}
} else {
value
};
let mut digits = Vec::<Self>::new();
let digit_mask = Source::digit_mask(DIGIT_BITNESS);
while !value.is_zero() {
digits.push(unsafe {
Self::try_from(value & digit_mask).unwrap_unchecked()
});
value >>= DIGIT_BITNESS;
}
digits
}
}
}
#[inline]
pub(super) fn value_to_sign<Source>(value: Source) -> Sign
where
for<'a> &'a Source: Zeroable,
Source: HasSignBit + Oppose,
OppositionOf<Source>: TryFrom<Source>,
{
if value.is_zero() {
Sign::zero()
} else {
non_zero_value_to_sign(value)
}
}
#[inline]
pub(super) fn non_zero_value_to_sign<Source>(value: Source) -> Sign
where
Source: HasSignBit + Oppose,
OppositionOf<Source>: TryFrom<Source>,
{
if is_signed::<Source>()
&& unsafe {
OppositionOf::<Source>::try_from(value).unwrap_unchecked()
}
.is_negative()
{
-Sign::one()
} else {
Sign::one()
}
}
#[inline]
fn floor_log2<T: BitLength<Output = usize>>(value: T) -> usize
where
for<'a> &'a T: Zeroable,
{
debug_assert!(!value.is_zero());
value.bit_length() - 1
}