xref: /aosp_15_r20/external/cronet/third_party/rust/chromium_crates_io/vendor/fend-core-1.4.6/src/num/bigrat.rs (revision 6777b5387eb2ff775bb5750e3f5d96f37fb7352b)

use crate::error::{FendError, Interrupt};
use crate::format::Format;
use crate::interrupt::test_int;
use crate::num::biguint::BigUint;
use crate::num::{Base, Exact, FormattingStyle, Range, RangeBound};
use crate::result::FResult;
use std::{cmp, fmt, hash, io, ops};

pub(crate) mod sign {
	use crate::{
		error::FendError,
		result::FResult,
		serialize::{Deserialize, Serialize},
	};
	use std::io;

	#[derive(Debug, Clone, Copy, PartialEq, Eq, PartialOrd, Ord, Hash)]
	pub(crate) enum Sign {
		Negative = 1,
		Positive = 2,
	}

	impl Sign {
		pub(crate) const fn flip(self) -> Self {
			match self {
				Self::Positive => Self::Negative,
				Self::Negative => Self::Positive,
			}
		}

		pub(crate) const fn sign_of_product(a: Self, b: Self) -> Self {
			match (a, b) {
				(Self::Positive, Self::Positive) | (Self::Negative, Self::Negative) => {
					Self::Positive
				}
				(Self::Positive, Self::Negative) | (Self::Negative, Self::Positive) => {
					Self::Negative
				}
			}
		}

		pub(crate) fn serialize(self, write: &mut impl io::Write) -> FResult<()> {
			(self as u8).serialize(write)
		}

		pub(crate) fn deserialize(read: &mut impl io::Read) -> FResult<Self> {
			Ok(match u8::deserialize(read)? {
				1 => Self::Positive,
				2 => Self::Negative,
				_ => return Err(FendError::DeserializationError),
			})
		}
	}
}

use super::biguint::{self, FormattedBigUint};
use super::out_of_range;
use sign::Sign;

#[derive(Clone)]
pub(crate) struct BigRat {
	sign: Sign,
	num: BigUint,
	den: BigUint,
}

impl fmt::Debug for BigRat {
	fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
		if self.sign == Sign::Negative {
			write!(f, "-")?;
		}
		write!(f, "{:?}", self.num)?;
		if !self.den.is_definitely_one() {
			write!(f, "/{:?}", self.den)?;
		}
		Ok(())
	}
}

impl Ord for BigRat {
	fn cmp(&self, other: &Self) -> cmp::Ordering {
		let int = &crate::interrupt::Never;
		let diff = self.clone().add(-other.clone(), int).unwrap();
		if diff.num == 0.into() {
			cmp::Ordering::Equal
		} else if diff.sign == Sign::Positive {
			cmp::Ordering::Greater
		} else {
			cmp::Ordering::Less
		}
	}
}

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

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

impl Eq for BigRat {}

impl hash::Hash for BigRat {
	fn hash<H: hash::Hasher>(&self, state: &mut H) {
		let int = &crate::interrupt::Never;
		if let Ok(res) = self.clone().simplify(int) {
			// don't hash the sign
			res.num.hash(state);
			res.den.hash(state);
		}
	}
}

impl BigRat {
	pub(crate) fn serialize(&self, write: &mut impl io::Write) -> FResult<()> {
		self.sign.serialize(write)?;
		self.num.serialize(write)?;
		self.den.serialize(write)?;
		Ok(())
	}

	pub(crate) fn deserialize(read: &mut impl io::Read) -> FResult<Self> {
		Ok(Self {
			sign: Sign::deserialize(read)?,
			num: BigUint::deserialize(read)?,
			den: BigUint::deserialize(read)?,
		})
	}

	pub(crate) fn is_integer(&self) -> bool {
		self.den == 1.into()
	}

	pub(crate) fn try_as_usize<I: Interrupt>(mut self, int: &I) -> FResult<usize> {
		if self.sign == Sign::Negative && self.num != 0.into() {
			return Err(FendError::NegativeNumbersNotAllowed);
		}
		self = self.simplify(int)?;
		if self.den != 1.into() {
			return Err(FendError::FractionToInteger);
		}
		self.num.try_as_usize(int)
	}

	pub(crate) fn try_as_i64<I: Interrupt>(mut self, int: &I) -> FResult<i64> {
		self = self.simplify(int)?;
		if self.den != 1.into() {
			return Err(FendError::FractionToInteger);
		}
		let res = self.num.try_as_usize(int)?;
		let res: i64 = res.try_into().map_err(|_| FendError::OutOfRange {
			value: Box::new(res),
			range: Range {
				start: RangeBound::None,
				end: RangeBound::Open(Box::new(i64::MAX)),
			},
		})?;
		Ok(match self.sign {
			Sign::Positive => res,
			Sign::Negative => -res,
		})
	}

	pub(crate) fn into_f64<I: Interrupt>(mut self, int: &I) -> FResult<f64> {
		if self.is_definitely_zero() {
			return Ok(0.0);
		}
		self = self.simplify(int)?;
		let positive_result = self.num.as_f64() / self.den.as_f64();
		if self.sign == Sign::Negative {
			Ok(-positive_result)
		} else {
			Ok(positive_result)
		}
	}

	#[allow(
		clippy::cast_possible_truncation,
		clippy::cast_sign_loss,
		clippy::cast_precision_loss
	)]
	pub(crate) fn from_f64<I: Interrupt>(mut f: f64, int: &I) -> FResult<Self> {
		let negative = f < 0.0;
		if negative {
			f = -f;
		}
		let i = (f * u64::MAX as f64) as u128;
		let part1 = i as u64;
		let part2 = (i >> 64) as u64;
		Ok(Self {
			sign: if negative {
				Sign::Negative
			} else {
				Sign::Positive
			},
			num: BigUint::from(part1)
				.add(&BigUint::from(part2).mul(&BigUint::from(u64::MAX), int)?),
			den: BigUint::from(u64::MAX),
		})
	}

	// sin works for all real numbers
	pub(crate) fn sin<I: Interrupt>(self, int: &I) -> FResult<Exact<Self>> {
		Ok(if self == 0.into() {
			Exact::new(Self::from(0), true)
		} else {
			Exact::new(Self::from_f64(f64::sin(self.into_f64(int)?), int)?, false)
		})
	}

	// asin, acos and atan only work for values between -1 and 1
	pub(crate) fn asin<I: Interrupt>(self, int: &I) -> FResult<Self> {
		let one = Self::from(1);
		if self > one || self < -one {
			return Err(out_of_range(self.fm(int)?, Range::open(-1, 1)));
		}
		Self::from_f64(f64::asin(self.into_f64(int)?), int)
	}

	pub(crate) fn acos<I: Interrupt>(self, int: &I) -> FResult<Self> {
		let one = Self::from(1);
		if self > one || self < -one {
			return Err(out_of_range(self.fm(int)?, Range::open(-1, 1)));
		}
		Self::from_f64(f64::acos(self.into_f64(int)?), int)
	}

	// note that this works for any real number, unlike asin and acos
	pub(crate) fn atan<I: Interrupt>(self, int: &I) -> FResult<Self> {
		Self::from_f64(f64::atan(self.into_f64(int)?), int)
	}

	pub(crate) fn atan2<I: Interrupt>(self, rhs: Self, int: &I) -> FResult<Self> {
		Self::from_f64(f64::atan2(self.into_f64(int)?, rhs.into_f64(int)?), int)
	}

	pub(crate) fn sinh<I: Interrupt>(self, int: &I) -> FResult<Self> {
		Self::from_f64(f64::sinh(self.into_f64(int)?), int)
	}

	pub(crate) fn cosh<I: Interrupt>(self, int: &I) -> FResult<Self> {
		Self::from_f64(f64::cosh(self.into_f64(int)?), int)
	}

	pub(crate) fn tanh<I: Interrupt>(self, int: &I) -> FResult<Self> {
		Self::from_f64(f64::tanh(self.into_f64(int)?), int)
	}

	pub(crate) fn asinh<I: Interrupt>(self, int: &I) -> FResult<Self> {
		Self::from_f64(f64::asinh(self.into_f64(int)?), int)
	}

	// value must not be less than 1
	pub(crate) fn acosh<I: Interrupt>(self, int: &I) -> FResult<Self> {
		if self < 1.into() {
			return Err(out_of_range(
				self.fm(int)?,
				Range {
					start: RangeBound::Closed(1),
					end: RangeBound::None,
				},
			));
		}
		Self::from_f64(f64::acosh(self.into_f64(int)?), int)
	}

	// value must be between -1 and 1.
	pub(crate) fn atanh<I: Interrupt>(self, int: &I) -> FResult<Self> {
		let one: Self = 1.into();
		if self >= one || self <= -one {
			return Err(out_of_range(self.fm(int)?, Range::open(-1, 1)));
		}
		Self::from_f64(f64::atanh(self.into_f64(int)?), int)
	}

	// For all logs: value must be greater than 0
	pub(crate) fn ln<I: Interrupt>(self, int: &I) -> FResult<Exact<Self>> {
		if self <= 0.into() {
			return Err(out_of_range(
				self.fm(int)?,
				Range {
					start: RangeBound::Open(0),
					end: RangeBound::None,
				},
			));
		}
		if self == 1.into() {
			return Ok(Exact::new(0.into(), true));
		}
		Ok(Exact::new(
			Self::from_f64(f64::ln(self.into_f64(int)?), int)?,
			false,
		))
	}

	pub(crate) fn log2<I: Interrupt>(self, int: &I) -> FResult<Self> {
		if self <= 0.into() {
			return Err(out_of_range(
				self.fm(int)?,
				Range {
					start: RangeBound::Open(0),
					end: RangeBound::None,
				},
			));
		}
		Self::from_f64(f64::log2(self.into_f64(int)?), int)
	}

	pub(crate) fn log10<I: Interrupt>(self, int: &I) -> FResult<Self> {
		if self <= 0.into() {
			return Err(out_of_range(
				self.fm(int)?,
				Range {
					start: RangeBound::Open(0),
					end: RangeBound::None,
				},
			));
		}
		Self::from_f64(f64::log10(self.into_f64(int)?), int)
	}

	fn apply_uint_op<I: Interrupt, R>(
		mut self,
		f: impl FnOnce(BigUint, &I) -> FResult<R>,
		int: &I,
	) -> FResult<R> {
		self = self.simplify(int)?;
		if self.den != 1.into() {
			let n = self.fm(int)?;
			return Err(FendError::MustBeAnInteger(Box::new(n)));
		}
		if self.sign == Sign::Negative && self.num != 0.into() {
			return Err(out_of_range(self.fm(int)?, Range::ZERO_OR_GREATER));
		}
		f(self.num, int)
	}

	pub(crate) fn factorial<I: Interrupt>(self, int: &I) -> FResult<Self> {
		Ok(self.apply_uint_op(BigUint::factorial, int)?.into())
	}

	pub(crate) fn floor<I: Interrupt>(self, int: &I) -> FResult<Self> {
		let float = self.into_f64(int)?.floor();
		Self::from_f64(float, int)
	}

	pub(crate) fn ceil<I: Interrupt>(self, int: &I) -> FResult<Self> {
		let float = self.into_f64(int)?.ceil();
		Self::from_f64(float, int)
	}

	pub(crate) fn round<I: Interrupt>(self, int: &I) -> FResult<Self> {
		let float = self.into_f64(int)?.round();
		Self::from_f64(float, int)
	}

	pub(crate) fn bitwise<I: Interrupt>(
		self,
		rhs: Self,
		op: crate::ast::BitwiseBop,
		int: &I,
	) -> FResult<Self> {
		use crate::ast::BitwiseBop;

		Ok(self
			.apply_uint_op(
				|lhs, int| {
					let rhs = rhs.apply_uint_op(|rhs, _int| Ok(rhs), int)?;
					let result = match op {
						BitwiseBop::And => lhs.bitwise_and(&rhs),
						BitwiseBop::Or => lhs.bitwise_or(&rhs),
						BitwiseBop::Xor => lhs.bitwise_xor(&rhs),
						BitwiseBop::LeftShift => lhs.lshift_n(&rhs, int)?,
						BitwiseBop::RightShift => lhs.rshift_n(&rhs, int)?,
					};
					Ok(result)
				},
				int,
			)?
			.into())
	}

	/// compute a + b
	fn add_internal<I: Interrupt>(self, rhs: Self, int: &I) -> FResult<Self> {
		// a + b == -((-a) + (-b))
		if self.sign == Sign::Negative {
			return Ok(-((-self).add_internal(-rhs, int)?));
		}

		assert_eq!(self.sign, Sign::Positive);

		Ok(if self.den == rhs.den {
			if rhs.sign == Sign::Negative && self.num < rhs.num {
				Self {
					sign: Sign::Negative,
					num: rhs.num.sub(&self.num),
					den: self.den,
				}
			} else {
				Self {
					sign: Sign::Positive,
					num: if rhs.sign == Sign::Positive {
						self.num.add(&rhs.num)
					} else {
						self.num.sub(&rhs.num)
					},
					den: self.den,
				}
			}
		} else {
			let gcd = BigUint::gcd(self.den.clone(), rhs.den.clone(), int)?;
			let new_denominator = self.den.clone().mul(&rhs.den, int)?.div(&gcd, int)?;
			let a = self.num.mul(&rhs.den, int)?.div(&gcd, int)?;
			let b = rhs.num.mul(&self.den, int)?.div(&gcd, int)?;

			if rhs.sign == Sign::Negative && a < b {
				Self {
					sign: Sign::Negative,
					num: b.sub(&a),
					den: new_denominator,
				}
			} else {
				Self {
					sign: Sign::Positive,
					num: if rhs.sign == Sign::Positive {
						a.add(&b)
					} else {
						a.sub(&b)
					},
					den: new_denominator,
				}
			}
		})
	}

	fn simplify<I: Interrupt>(mut self, int: &I) -> FResult<Self> {
		if self.den == 1.into() {
			return Ok(self);
		}
		let gcd = BigUint::gcd(self.num.clone(), self.den.clone(), int)?;
		self.num = self.num.div(&gcd, int)?;
		self.den = self.den.div(&gcd, int)?;
		Ok(self)
	}

	pub(crate) fn div<I: Interrupt>(self, rhs: &Self, int: &I) -> FResult<Self> {
		if rhs.num == 0.into() {
			return Err(FendError::DivideByZero);
		}
		Ok(Self {
			sign: Sign::sign_of_product(self.sign, rhs.sign),
			num: self.num.mul(&rhs.den, int)?,
			den: self.den.mul(&rhs.num, int)?,
		})
	}

	pub(crate) fn modulo<I: Interrupt>(mut self, mut rhs: Self, int: &I) -> FResult<Self> {
		if rhs.num == 0.into() {
			return Err(FendError::ModuloByZero);
		}
		self = self.simplify(int)?;
		rhs = rhs.simplify(int)?;
		if (self.sign == Sign::Negative && self.num != 0.into())
			|| rhs.sign == Sign::Negative
			|| self.den != 1.into()
			|| rhs.den != 1.into()
		{
			return Err(FendError::ModuloForPositiveInts);
		}
		Ok(Self {
			sign: Sign::Positive,
			num: self.num.divmod(&rhs.num, int)?.1,
			den: 1.into(),
		})
	}

	// test if this fraction has a terminating representation
	// e.g. in base 10: 1/4 = 0.25, but not 1/3
	fn terminates_in_base<I: Interrupt>(&self, base: Base, int: &I) -> FResult<bool> {
		let mut x = self.clone();
		let base_as_u64: u64 = base.base_as_u8().into();
		let base = Self {
			sign: Sign::Positive,
			num: base_as_u64.into(),
			den: 1.into(),
		};
		loop {
			let old_den = x.den.clone();
			x = x.mul(&base, int)?.simplify(int)?;
			let new_den = x.den.clone();
			if new_den == old_den {
				break;
			}
		}
		Ok(x.den == 1.into())
	}

	fn format_as_integer<I: Interrupt>(
		num: &BigUint,
		base: Base,
		sign: Sign,
		term: &'static str,
		use_parens_if_product: bool,
		sf_limit: Option<usize>,
		int: &I,
	) -> FResult<Exact<FormattedBigRat>> {
		let (ty, exact) = if !term.is_empty() && !base.has_prefix() && num == &1.into() {
			(FormattedBigRatType::Integer(None, false, term, false), true)
		} else {
			let formatted_int = num.format(
				&biguint::FormatOptions {
					base,
					write_base_prefix: true,
					sf_limit,
				},
				int,
			)?;
			(
				FormattedBigRatType::Integer(
					Some(formatted_int.value),
					!term.is_empty() && base.base_as_u8() > 10,
					term,
					// print surrounding parentheses if the number is imaginary
					use_parens_if_product && !term.is_empty(),
				),
				formatted_int.exact,
			)
		};
		Ok(Exact::new(FormattedBigRat { sign, ty }, exact))
	}

	fn format_as_fraction<I: Interrupt>(
		&self,
		base: Base,
		sign: Sign,
		term: &'static str,
		mixed: bool,
		use_parens: bool,
		int: &I,
	) -> FResult<Exact<FormattedBigRat>> {
		let format_options = biguint::FormatOptions {
			base,
			write_base_prefix: true,
			sf_limit: None,
		};
		let formatted_den = self.den.format(&format_options, int)?;
		let (pref, num, prefix_exact) = if mixed {
			let (prefix, num) = self.num.divmod(&self.den, int)?;
			if prefix == 0.into() {
				(None, num, true)
			} else {
				let formatted_prefix = prefix.format(&format_options, int)?;
				(Some(formatted_prefix.value), num, formatted_prefix.exact)
			}
		} else {
			(None, self.num.clone(), true)
		};
		// mixed fractions without a prefix aren't really mixed
		let actually_mixed = pref.is_some();
		let (ty, num_exact) =
			if !term.is_empty() && !actually_mixed && !base.has_prefix() && num == 1.into() {
				(
					FormattedBigRatType::Fraction(
						pref,
						None,
						false,
						term,
						formatted_den.value,
						"",
						use_parens,
					),
					true,
				)
			} else {
				let formatted_num = num.format(&format_options, int)?;
				let i_suffix = term;
				let space = !term.is_empty() && (base.base_as_u8() >= 19 || actually_mixed);
				let (isuf1, isuf2) = if actually_mixed {
					("", i_suffix)
				} else {
					(i_suffix, "")
				};
				(
					FormattedBigRatType::Fraction(
						pref,
						Some(formatted_num.value),
						space,
						isuf1,
						formatted_den.value,
						isuf2,
						use_parens,
					),
					formatted_num.exact,
				)
			};
		Ok(Exact::new(
			FormattedBigRat { sign, ty },
			formatted_den.exact && prefix_exact && num_exact,
		))
	}

	fn format_as_decimal<I: Interrupt>(
		&self,
		style: FormattingStyle,
		base: Base,
		sign: Sign,
		term: &'static str,
		mut terminating: impl FnMut() -> FResult<bool>,
		int: &I,
	) -> FResult<Exact<FormattedBigRat>> {
		let integer_part = self.clone().num.div(&self.den, int)?;
		let sf_limit = if let FormattingStyle::SignificantFigures(sf) = style {
			Some(sf)
		} else {
			None
		};
		let formatted_integer_part = integer_part.format(
			&biguint::FormatOptions {
				base,
				write_base_prefix: true,
				sf_limit,
			},
			int,
		)?;

		let num_trailing_digits_to_print = if style == FormattingStyle::ExactFloat
			|| (style == FormattingStyle::Auto && terminating()?)
			|| style == FormattingStyle::Exact
		{
			MaxDigitsToPrint::AllDigits
		} else if let FormattingStyle::DecimalPlaces(n) = style {
			MaxDigitsToPrint::DecimalPlaces(n)
		} else if let FormattingStyle::SignificantFigures(sf) = style {
			let num_digits_of_int_part = formatted_integer_part.value.num_digits();
			let dp = if sf > num_digits_of_int_part {
				// we want more significant figures than what was printed
				// in the int component
				sf - num_digits_of_int_part
			} else {
				// no more digits, we already exhausted the number of significant
				// figures
				0
			};
			if integer_part == 0.into() {
				// if the integer part is 0, we don't want leading zeroes
				// after the decimal point to affect the number of non-zero
				// digits printed

				// we add 1 to the number of decimal places in this case because
				// the integer component of '0' shouldn't count against the
				// number of significant figures
				MaxDigitsToPrint::DpButIgnoreLeadingZeroes(dp + 1)
			} else {
				MaxDigitsToPrint::DecimalPlaces(dp)
			}
		} else {
			MaxDigitsToPrint::DecimalPlaces(10)
		};
		let print_integer_part = |ignore_minus_if_zero: bool| {
			let sign =
				if sign == Sign::Negative && (!ignore_minus_if_zero || integer_part != 0.into()) {
					Sign::Negative
				} else {
					Sign::Positive
				};
			Ok((sign, formatted_integer_part.value.to_string()))
		};
		let integer_as_rational = Self {
			sign: Sign::Positive,
			num: integer_part.clone(),
			den: 1.into(),
		};
		let remaining_fraction = self.clone().add(-integer_as_rational, int)?;
		let (sign, formatted_trailing_digits) = Self::format_trailing_digits(
			base,
			&remaining_fraction.num,
			&remaining_fraction.den,
			num_trailing_digits_to_print,
			terminating,
			print_integer_part,
			int,
		)?;
		Ok(Exact::new(
			FormattedBigRat {
				sign,
				ty: FormattedBigRatType::Decimal(
					formatted_trailing_digits.value,
					!term.is_empty() && base.base_as_u8() > 10,
					term,
				),
			},
			formatted_integer_part.exact && formatted_trailing_digits.exact,
		))
	}

	/// Prints the decimal expansion of num/den, where num < den, in the given base.
	fn format_trailing_digits<I: Interrupt>(
		base: Base,
		numerator: &BigUint,
		denominator: &BigUint,
		max_digits: MaxDigitsToPrint,
		mut terminating: impl FnMut() -> FResult<bool>,
		print_integer_part: impl Fn(bool) -> FResult<(Sign, String)>,
		int: &I,
	) -> FResult<(Sign, Exact<String>)> {
		let base_as_u64: u64 = base.base_as_u8().into();
		let b: BigUint = base_as_u64.into();
		let next_digit =
			|i: usize, num: BigUint, base: &BigUint| -> Result<(BigUint, BigUint), NextDigitErr> {
				test_int(int)?;
				if num == 0.into()
					|| max_digits == MaxDigitsToPrint::DecimalPlaces(i)
					|| max_digits == MaxDigitsToPrint::DpButIgnoreLeadingZeroes(i)
				{
					return Err(NextDigitErr::Terminated);
				}
				// digit = base * numerator / denominator
				// next_numerator = base * numerator - digit * denominator
				let bnum = num.mul(base, int)?;
				let digit = bnum.clone().div(denominator, int)?;
				let next_num = bnum.sub(&digit.clone().mul(denominator, int)?);
				Ok((next_num, digit))
			};
		let fold_digits = |mut s: String, digit: BigUint| -> FResult<String> {
			let digit_str = digit
				.format(
					&biguint::FormatOptions {
						base,
						write_base_prefix: false,
						sf_limit: None,
					},
					int,
				)?
				.value
				.to_string();
			s.push_str(digit_str.as_str());
			Ok(s)
		};
		let skip_cycle_detection = max_digits != MaxDigitsToPrint::AllDigits || terminating()?;
		if skip_cycle_detection {
			let ignore_number_of_leading_zeroes =
				matches!(max_digits, MaxDigitsToPrint::DpButIgnoreLeadingZeroes(_));
			return Self::format_nonrecurring(
				numerator,
				base,
				ignore_number_of_leading_zeroes,
				next_digit,
				print_integer_part,
				int,
			);
		}
		match Self::brents_algorithm(
			next_digit,
			fold_digits,
			numerator.clone(),
			&b,
			String::new(),
		) {
			Ok((cycle_length, location, output)) => {
				let (ab, _) = output.split_at(location + cycle_length);
				let (a, b) = ab.split_at(location);
				let (sign, formatted_int) = print_integer_part(false)?;
				let mut trailing_digits = String::new();
				trailing_digits.push_str(&formatted_int);
				trailing_digits.push('.');
				trailing_digits.push_str(a);
				trailing_digits.push('(');
				trailing_digits.push_str(b);
				trailing_digits.push(')');
				Ok((sign, Exact::new(trailing_digits, true))) // the recurring decimal is exact
			}
			Err(NextDigitErr::Terminated) => {
				panic!("decimal number terminated unexpectedly");
			}
			Err(NextDigitErr::Error(e)) => Err(e),
		}
	}

	fn format_nonrecurring<I: Interrupt>(
		numerator: &BigUint,
		base: Base,
		ignore_number_of_leading_zeroes: bool,
		mut next_digit: impl FnMut(usize, BigUint, &BigUint) -> Result<(BigUint, BigUint), NextDigitErr>,
		print_integer_part: impl Fn(bool) -> FResult<(Sign, String)>,
		int: &I,
	) -> FResult<(Sign, Exact<String>)> {
		let mut current_numerator = numerator.clone();
		let mut i = 0;
		let mut trailing_zeroes = 0;
		// this becomes Some(_) when we write the decimal point
		let mut actual_sign = None;
		let mut trailing_digits = String::new();
		let b: BigUint = u64::from(base.base_as_u8()).into();
		loop {
			match next_digit(i, current_numerator.clone(), &b) {
				Ok((next_n, digit)) => {
					current_numerator = next_n;
					if digit == 0.into() {
						trailing_zeroes += 1;
						if !(i == 0 && ignore_number_of_leading_zeroes) {
							i += 1;
						}
					} else {
						if actual_sign.is_none() {
							// always print leading minus because we have non-zero digits
							let (sign, formatted_int) = print_integer_part(false)?;
							actual_sign = Some(sign);
							trailing_digits.push_str(&formatted_int);
							trailing_digits.push('.');
						}
						for _ in 0..trailing_zeroes {
							trailing_digits.push('0');
						}
						trailing_zeroes = 0;
						trailing_digits.push_str(
							&digit
								.format(
									&biguint::FormatOptions {
										base,
										write_base_prefix: false,
										sf_limit: None,
									},
									int,
								)?
								.value
								.to_string(),
						);
						i += 1;
					}
				}
				Err(NextDigitErr::Terminated) => {
					let sign = if let Some(actual_sign) = actual_sign {
						actual_sign
					} else {
						// if we reach this point we haven't printed any non-zero digits,
						// so we can skip the leading minus sign if the integer part is also zero
						let (sign, formatted_int) = print_integer_part(true)?;
						trailing_digits.push_str(&formatted_int);
						sign
					};
					// is the number exact, or did we need to truncate?
					let exact = current_numerator == 0.into();
					return Ok((sign, Exact::new(trailing_digits, exact)));
				}
				Err(NextDigitErr::Error(e)) => {
					return Err(e);
				}
			}
		}
	}

	// Brent's cycle detection algorithm (based on pseudocode from Wikipedia)
	// returns (length of cycle, index of first element of cycle, collected result)
	fn brents_algorithm<T: Clone + Eq, R, U, E1: From<E2>, E2>(
		f: impl Fn(usize, T, &T) -> Result<(T, U), E1>,
		g: impl Fn(R, U) -> Result<R, E2>,
		x0: T,
		state: &T,
		r0: R,
	) -> Result<(usize, usize, R), E1> {
		// main phase: search successive powers of two
		let mut power = 1;
		// lam is the length of the cycle
		let mut lam = 1;
		let mut tortoise = x0.clone();
		let mut depth = 0;
		let (mut hare, _) = f(depth, x0.clone(), state)?;
		depth += 1;
		while tortoise != hare {
			if power == lam {
				tortoise = hare.clone();
				power *= 2;
				lam = 0;
			}
			hare = f(depth, hare, state)?.0;
			depth += 1;
			lam += 1;
		}

		// Find the position of the first repetition of length lam
		tortoise = x0.clone();
		hare = x0;
		let mut collected_res = r0;
		let mut hare_depth = 0;
		for _ in 0..lam {
			let (new_hare, u) = f(hare_depth, hare, state)?;
			hare_depth += 1;
			hare = new_hare;
			collected_res = g(collected_res, u)?;
		}
		// The distance between the hare and tortoise is now lam.

		// Next, the hare and tortoise move at same speed until they agree
		// mu will be the length of the initial sequence, before the cycle
		let mut mu = 0;
		let mut tortoise_depth = 0;
		while tortoise != hare {
			tortoise = f(tortoise_depth, tortoise, state)?.0;
			tortoise_depth += 1;
			let (new_hare, u) = f(hare_depth, hare, state)?;
			hare_depth += 1;
			hare = new_hare;
			collected_res = g(collected_res, u)?;
			mu += 1;
		}
		Ok((lam, mu, collected_res))
	}

	pub(crate) fn pow<I: Interrupt>(mut self, mut rhs: Self, int: &I) -> FResult<Exact<Self>> {
		self = self.simplify(int)?;
		rhs = rhs.simplify(int)?;
		if self.num != 0.into() && self.sign == Sign::Negative && rhs.den != 1.into() {
			return Err(FendError::RootsOfNegativeNumbers);
		}
		if rhs.sign == Sign::Negative {
			// a^-b => 1/a^b
			rhs.sign = Sign::Positive;
			let inverse_res = self.pow(rhs, int)?;
			return Ok(Exact::new(
				Self::from(1).div(&inverse_res.value, int)?,
				inverse_res.exact,
			));
		}
		let result_sign = if self.sign == Sign::Positive || rhs.num.is_even(int)? {
			Sign::Positive
		} else {
			Sign::Negative
		};
		let pow_res = Self {
			sign: result_sign,
			num: BigUint::pow(&self.num, &rhs.num, int)?,
			den: BigUint::pow(&self.den, &rhs.num, int)?,
		};
		if rhs.den == 1.into() {
			Ok(Exact::new(pow_res, true))
		} else {
			Ok(pow_res.root_n(
				&Self {
					sign: Sign::Positive,
					num: rhs.den,
					den: 1.into(),
				},
				int,
			)?)
		}
	}

	/// n must be an integer
	fn iter_root_n<I: Interrupt>(
		mut low_bound: Self,
		val: &Self,
		n: &Self,
		int: &I,
	) -> FResult<Self> {
		let mut high_bound = low_bound.clone().add(1.into(), int)?;
		for _ in 0..30 {
			let guess = low_bound
				.clone()
				.add(high_bound.clone(), int)?
				.div(&2.into(), int)?;
			if &guess.clone().pow(n.clone(), int)?.value < val {
				low_bound = guess;
			} else {
				high_bound = guess;
			}
		}
		low_bound.add(high_bound, int)?.div(&2.into(), int)
	}

	pub(crate) fn exp<I: Interrupt>(self, int: &I) -> FResult<Exact<Self>> {
		if self.num == 0.into() {
			return Ok(Exact::new(Self::from(1), true));
		}
		Ok(Exact::new(
			Self::from_f64(self.into_f64(int)?.exp(), int)?,
			false,
		))
	}

	// the boolean indicates whether or not the result is exact
	// n must be an integer
	pub(crate) fn root_n<I: Interrupt>(self, n: &Self, int: &I) -> FResult<Exact<Self>> {
		if self.num != 0.into() && self.sign == Sign::Negative {
			return Err(FendError::RootsOfNegativeNumbers);
		}
		let n = n.clone().simplify(int)?;
		if n.den != 1.into() || n.sign == Sign::Negative {
			return Err(FendError::NonIntegerNegRoots);
		}
		let n = &n.num;
		if self.num == 0.into() {
			return Ok(Exact::new(self, true));
		}
		let num = self.clone().num.root_n(n, int)?;
		let den = self.clone().den.root_n(n, int)?;
		if num.exact && den.exact {
			return Ok(Exact::new(
				Self {
					sign: Sign::Positive,
					num: num.value,
					den: den.value,
				},
				true,
			));
		}
		// TODO check in which cases this might still be exact
		let num_rat = if num.exact {
			Self::from(num.value)
		} else {
			Self::iter_root_n(
				Self::from(num.value),
				&Self::from(self.num),
				&Self::from(n.clone()),
				int,
			)?
		};
		let den_rat = if den.exact {
			Self::from(den.value)
		} else {
			Self::iter_root_n(
				Self::from(den.value),
				&Self::from(self.den),
				&Self::from(n.clone()),
				int,
			)?
		};
		Ok(Exact::new(num_rat.div(&den_rat, int)?, false))
	}

	pub(crate) fn mul<I: Interrupt>(self, rhs: &Self, int: &I) -> FResult<Self> {
		Ok(Self {
			sign: Sign::sign_of_product(self.sign, rhs.sign),
			num: self.num.mul(&rhs.num, int)?,
			den: self.den.mul(&rhs.den, int)?,
		})
	}

	pub(crate) fn add<I: Interrupt>(self, rhs: Self, int: &I) -> FResult<Self> {
		self.add_internal(rhs, int)
	}

	pub(crate) fn is_definitely_zero(&self) -> bool {
		self.num.is_definitely_zero()
	}

	pub(crate) fn is_definitely_one(&self) -> bool {
		self.sign == Sign::Positive && self.num.is_definitely_one() && self.den.is_definitely_one()
	}

	pub(crate) fn combination<I: Interrupt>(self, rhs: Self, int: &I) -> FResult<Self> {
		let n_factorial = self.clone().factorial(int)?;
		let r_factorial = rhs.clone().factorial(int)?;
		let n_minus_r_factorial = self.add(-rhs, int)?.factorial(int)?;
		let denominator = r_factorial.mul(&n_minus_r_factorial, int)?;
		n_factorial.div(&denominator, int)
	}

	pub(crate) fn permutation<I: Interrupt>(self, rhs: Self, int: &I) -> FResult<Self> {
		let n_factorial = self.clone().factorial(int)?;
		let n_minus_r_factorial = self.add(-rhs, int)?.factorial(int)?;
		n_factorial.div(&n_minus_r_factorial, int)
	}
}
enum NextDigitErr {
	Error(FendError),
	Terminated,
}

impl From<FendError> for NextDigitErr {
	fn from(e: FendError) -> Self {
		Self::Error(e)
	}
}

#[derive(Copy, Clone, Eq, PartialEq, Debug)]
enum MaxDigitsToPrint {
	/// Print all digits, possibly by writing recurring decimals in parentheses
	AllDigits,
	/// Print only the given number of decimal places, omitting any trailing zeroes
	DecimalPlaces(usize),
	/// Print only the given number of dps, but ignore leading zeroes after the decimal point
	DpButIgnoreLeadingZeroes(usize),
}

impl ops::Neg for BigRat {
	type Output = Self;

	fn neg(self) -> Self {
		Self {
			sign: self.sign.flip(),
			..self
		}
	}
}

impl From<u64> for BigRat {
	fn from(i: u64) -> Self {
		Self {
			sign: Sign::Positive,
			num: i.into(),
			den: 1.into(),
		}
	}
}

impl From<BigUint> for BigRat {
	fn from(n: BigUint) -> Self {
		Self {
			sign: Sign::Positive,
			num: n,
			den: BigUint::from(1),
		}
	}
}

#[derive(Default)]
pub(crate) struct FormatOptions {
	pub(crate) base: Base,
	pub(crate) style: FormattingStyle,
	pub(crate) term: &'static str,
	pub(crate) use_parens_if_fraction: bool,
}

impl Format for BigRat {
	type Params = FormatOptions;
	type Out = FormattedBigRat;

	// Formats as an integer if possible, or a terminating float, otherwise as
	// either a fraction or a potentially approximated floating-point number.
	// The result 'exact' field indicates whether the number was exact or not.
	fn format<I: Interrupt>(&self, params: &Self::Params, int: &I) -> FResult<Exact<Self::Out>> {
		let base = params.base;
		let style = params.style;
		let term = params.term;
		let use_parens_if_fraction = params.use_parens_if_fraction;

		let mut x = self.clone().simplify(int)?;
		let sign = if x.sign == Sign::Positive || x == 0.into() {
			Sign::Positive
		} else {
			Sign::Negative
		};
		x.sign = Sign::Positive;

		// try as integer if possible
		if x.den == 1.into() {
			let sf_limit = if let FormattingStyle::SignificantFigures(sf) = style {
				Some(sf)
			} else {
				None
			};
			return Self::format_as_integer(
				&x.num,
				base,
				sign,
				term,
				use_parens_if_fraction,
				sf_limit,
				int,
			);
		}

		let mut terminating_res = None;
		let mut terminating = || match terminating_res {
			None => {
				let t = x.terminates_in_base(base, int)?;
				terminating_res = Some(t);
				Ok(t)
			}
			Some(t) => Ok(t),
		};
		let fraction = style == FormattingStyle::ImproperFraction
			|| style == FormattingStyle::MixedFraction
			|| (style == FormattingStyle::Exact && !terminating()?);
		if fraction {
			let mixed = style == FormattingStyle::MixedFraction || style == FormattingStyle::Exact;
			return x.format_as_fraction(base, sign, term, mixed, use_parens_if_fraction, int);
		}

		// not a fraction, will be printed as a decimal
		x.format_as_decimal(style, base, sign, term, terminating, int)
	}
}

#[derive(Debug)]
enum FormattedBigRatType {
	// optional int,
	// bool whether to add a space before the string
	// followed by a string (empty, "i" or "pi"),
	// followed by whether to wrap the number in parentheses
	Integer(Option<FormattedBigUint>, bool, &'static str, bool),
	// optional int (for mixed fractions)
	// optional int (numerator)
	// space
	// string (empty, "i", "pi", etc.)
	// '/'
	// int (denominator)
	// string (empty, "i", "pi", etc.) (used for mixed fractions, e.g. 1 2/3 i)
	// bool (whether or not to wrap the fraction in parentheses)
	Fraction(
		Option<FormattedBigUint>,
		Option<FormattedBigUint>,
		bool,
		&'static str,
		FormattedBigUint,
		&'static str,
		bool,
	),
	// string representation of decimal number (may or may not contain recurring digits)
	// space
	// string (empty, "i", "pi", etc.)
	Decimal(String, bool, &'static str),
}

#[must_use]
#[derive(Debug)]
pub(crate) struct FormattedBigRat {
	// whether or not to print a minus sign
	sign: Sign,
	ty: FormattedBigRatType,
}

impl fmt::Display for FormattedBigRat {
	fn fmt(&self, f: &mut fmt::Formatter<'_>) -> Result<(), fmt::Error> {
		if self.sign == Sign::Negative {
			write!(f, "-")?;
		}
		match &self.ty {
			FormattedBigRatType::Integer(int, space, isuf, use_parens) => {
				if *use_parens {
					write!(f, "(")?;
				}
				if let Some(int) = int {
					write!(f, "{int}")?;
				}
				if *space {
					write!(f, " ")?;
				}
				write!(f, "{isuf}")?;
				if *use_parens {
					write!(f, ")")?;
				}
			}
			FormattedBigRatType::Fraction(integer, num, space, isuf, den, isuf2, use_parens) => {
				if *use_parens {
					write!(f, "(")?;
				}
				if let Some(integer) = integer {
					write!(f, "{integer} ")?;
				}
				if let Some(num) = num {
					write!(f, "{num}")?;
				}
				if *space && !isuf.is_empty() {
					write!(f, " ")?;
				}
				write!(f, "{isuf}/{den}")?;
				if *space && !isuf2.is_empty() {
					write!(f, " ")?;
				}
				write!(f, "{isuf2}")?;
				if *use_parens {
					write!(f, ")")?;
				}
			}
			FormattedBigRatType::Decimal(s, space, term) => {
				write!(f, "{s}")?;
				if *space {
					write!(f, " ")?;
				}
				write!(f, "{term}")?;
			}
		}
		Ok(())
	}
}

#[cfg(test)]
mod tests {
	use super::sign::Sign;
	use super::BigRat;

	use crate::num::biguint::BigUint;
	use crate::result::FResult;
	use std::mem;

	#[test]
	fn test_bigrat_from() {
		mem::drop(BigRat::from(2));
		mem::drop(BigRat::from(0));
		mem::drop(BigRat::from(u64::MAX));
		mem::drop(BigRat::from(u64::from(u32::MAX)));
	}

	#[test]
	fn test_addition() -> FResult<()> {
		let int = &crate::interrupt::Never;
		let two = BigRat::from(2);
		assert_eq!(two.clone().add(two, int)?, BigRat::from(4));
		Ok(())
	}

	#[test]
	fn test_cmp() {
		assert!(
			BigRat {
				sign: Sign::Positive,
				num: BigUint::from(16),
				den: BigUint::from(9)
			} < BigRat::from(2)
		);
	}

	#[test]
	fn test_cmp_2() {
		assert!(
			BigRat {
				sign: Sign::Positive,
				num: BigUint::from(36),
				den: BigUint::from(49)
			} < BigRat {
				sign: Sign::Positive,
				num: BigUint::from(3),
				den: BigUint::from(4)
			}
		);
	}
}