use super::{bounded, choose, err, factorial};
use crate::Error;
use num_bigint::BigInt;
use num_integer::Integer;
use num_rational::BigRational;
use num_traits::{One, Signed, ToPrimitive, Zero};
#[derive(Clone)]
pub(super) enum Expr {
Value(BigInt),
Decimal(String),
Variable(String),
Unary(char, Box<Expr>),
Binary(String, Box<Expr>, Box<Expr>),
Call(String, Vec<Expr>),
}
pub(super) fn parse(input: &str) -> Result<Expr, Error> {
parse_mode(input, false, &[])
}
pub(super) fn ratio(input: &str) -> Result<(BigInt, BigInt), Error> {
parse_mode(input, true, &[])?.eval_ratio()
}
fn parse_mode(input: &str, ratios: bool, variables: &[&str]) -> Result<Expr, Error> {
let mut parser = Parser {
tokens: tokenize(input, ratios, variables)?,
at: 0,
ratios,
variables: variables.iter().map(|name| (*name).to_owned()).collect(),
};
let result = parser.expression(0, 0)?;
if parser.at != parser.tokens.len() {
return err("invalid_integer_expression");
}
Ok(result)
}
fn tokenize(input: &str, ratios: bool, variables: &[&str]) -> Result<Vec<String>, Error> {
let mut tokens = Vec::new();
let mut at = 0;
let mut groups = Vec::new();
let mut functions: Vec<String> = Vec::new();
let bytes = input.as_bytes();
while at < bytes.len() {
let c = bytes[at] as char;
if c.is_ascii_whitespace() {
at += 1;
continue;
}
let start = at;
if c.is_ascii_digit()
|| ratios && c == '.' && bytes.get(at + 1).is_some_and(u8::is_ascii_digit)
{
at += 1;
if c == '0'
&& at < bytes.len()
&& matches!(bytes[at], b'x' | b'b' | b'o')
&& (!variables.contains(&&input[at..at + 1])
|| bytes.get(at + 1).is_some_and(u8::is_ascii_hexdigit))
{
at += 1;
while at < bytes.len() && (bytes[at] as char).is_ascii_hexdigit() {
at += 1;
}
} else {
while at < bytes.len() && (bytes[at] as char).is_ascii_digit() {
at += 1;
}
if bytes.get(at) == Some(&b',') {
let grouped = c
.is_ascii_digit()
.then(|| grouped_digits(bytes, start, at))
.flatten();
if functions.is_empty() {
at =
grouped.ok_or_else(|| crate::Error("invalid_digit_grouping".into()))?;
} else if ratios
&& functions
.last()
.is_some_and(|name| matches!(name.as_str(), "abs" | "square"))
&& let Some(end) = grouped
{
at = end;
}
}
if at < bytes.len() && bytes[at] == b'.' {
if !ratios {
return err("integer_required");
}
at += 1;
while at < bytes.len() && bytes[at].is_ascii_digit() {
at += 1;
}
}
if ratios
&& bytes.get(at).is_some_and(|b| matches!(b, b'e' | b'E'))
&& (!variables.contains(&&input[at..at + 1])
|| bytes.get(at + 1).is_some_and(u8::is_ascii_digit))
{
at += 1;
if bytes.get(at).is_some_and(|b| matches!(b, b'+' | b'-')) {
at += 1;
}
let exponent = at;
while at < bytes.len() && bytes[at].is_ascii_digit() {
at += 1;
}
if at == exponent {
return err("invalid_integer_expression");
}
}
}
} else if matches!(c, 'c' | 'p') && at + 1 < bytes.len() && bytes[at + 1].is_ascii_digit() {
at += 1;
} else if c.is_ascii_alphabetic() {
at += 1;
while at < bytes.len() && (bytes[at] as char).is_ascii_alphabetic() {
at += 1;
}
} else if c == ',' && functions.is_empty() {
return err("invalid_digit_grouping");
} else if "+-*/^!(),&|".contains(c) {
if c == '(' {
let function = tokens.last().is_some_and(|token: &String| {
token.chars().all(|c| c.is_ascii_alphabetic())
&& !variables.contains(&token.as_str())
});
groups.push(function);
if function {
functions.push(tokens.last().unwrap().clone());
}
} else if c == ')' && groups.pop() == Some(true) {
functions.pop();
}
at += 1;
} else if matches!(c, '<' | '>') && bytes.get(at + 1) == Some(&bytes[at]) {
at += 2;
} else {
return err("invalid_integer_expression");
}
let token = &input[start..at];
tokens.push(if c.is_ascii_digit() && token.contains(',') {
token.replace(',', "")
} else {
token.into()
});
}
Ok(tokens)
}
fn grouped_digits(bytes: &[u8], start: usize, mut at: usize) -> Option<usize> {
if at - start > 3 {
return None;
}
while bytes.get(at) == Some(&b',') {
let end = at + 4;
if end > bytes.len()
|| !bytes[at + 1..end].iter().all(u8::is_ascii_digit)
|| bytes.get(end).is_some_and(u8::is_ascii_digit)
{
return None;
}
at = end;
}
Some(at)
}
fn function(name: &str, ratios: bool) -> bool {
matches!(
name,
"gcd" | "gcf" | "lcm" | "choose" | "perm" | "factorial" | "pow" | "rational"
) || ratios && matches!(name, "abs" | "min" | "max" | "sum" | "mean" | "square")
}
struct Parser {
tokens: Vec<String>,
at: usize,
ratios: bool,
variables: Vec<String>,
}
impl Parser {
fn take(&mut self) -> Result<String, Error> {
let token = self
.tokens
.get(self.at)
.cloned()
.ok_or_else(|| Error("invalid_integer_expression".into()))?;
self.at += 1;
Ok(token)
}
fn expression(&mut self, minimum: u8, depth: usize) -> Result<Expr, Error> {
if depth > 64 {
return err("integer_limit");
}
let token = self.take()?;
let mut left = match token.as_str() {
"+" | "-" => Expr::Unary(
token.chars().next().unwrap(),
Box::new(self.expression(70, depth + 1)?),
),
"(" => {
let value = self.expression(0, depth + 1)?;
if self.take()? != ")" {
return err("invalid_integer_expression");
}
value
}
_ if self.variables.iter().any(|name| name == &token) => Expr::Variable(token),
_ if function(&token, self.ratios) => {
if self.take()? != "(" {
return err("invalid_integer_expression");
}
let mut args = vec![self.expression(0, depth + 1)?];
while self.tokens.get(self.at).is_some_and(|s| s == ",") {
self.at += 1;
args.push(self.expression(0, depth + 1)?);
}
if self.take()? != ")" {
return err("invalid_integer_expression");
}
Expr::Call(token, args)
}
_ => {
let (digits, base) = if let Some(s) = token.strip_prefix("0x") {
(s, 16)
} else if let Some(s) = token.strip_prefix("0b") {
(s, 2)
} else if let Some(s) = token.strip_prefix("0o") {
(s, 8)
} else {
(token.as_str(), 10)
};
if base == 10 && token.contains(['.', 'e', 'E']) {
Expr::Decimal(token)
} else {
Expr::Value(
BigInt::parse_bytes(digits.as_bytes(), base)
.ok_or_else(|| Error("invalid_integer_expression".into()))?,
)
}
}
};
while let Some(op) = self.tokens.get(self.at).cloned() {
let implicit = !self.variables.is_empty()
&& (op == "(" || self.variables.iter().any(|name| name == &op));
let op = if implicit { "*".to_owned() } else { op };
let binding = match op.as_str() {
"|" => 10,
"xor" => 15,
"&" => 20,
"<<" | ">>" => 25,
"+" | "-" => 30,
"*" | "/" | "mod" | "modulo" => 40,
"choose" | "c" | "p" | "permutation" | "permutations" => 60,
"^" => 80,
"!" => 90,
_ => break,
};
if binding < minimum {
break;
}
if !implicit {
self.at += 1;
}
if op == "!" {
left = Expr::Call("factorial".into(), vec![left]);
continue;
}
let right = self.expression(binding + u8::from(op != "^"), depth + 1)?;
left = Expr::Binary(op, Box::new(left), Box::new(right));
}
Ok(left)
}
}
impl Expr {
pub(super) fn eval(&self) -> Result<BigInt, Error> {
let value = match self {
Self::Value(n) => n.clone(),
Self::Decimal(_) => return err("integer_required"),
Self::Variable(_) => return err("invalid_integer_expression"),
Self::Unary('-', n) => -n.eval()?,
Self::Unary(_, n) => n.eval()?,
Self::Binary(op, left, right) => {
let b = right.eval()?;
if matches!(op.as_str(), "mod" | "modulo") {
if b.is_zero() {
return err("division_by_zero");
}
return left.modular(&b.abs());
}
let a = left.eval()?;
match op.as_str() {
"+" => a + b,
"-" => a - b,
"*" => a * b,
"/" => {
if b.is_zero() {
return err("division_by_zero");
}
let (q, r) = a.div_rem(&b);
if !r.is_zero() {
return err("integer_required");
}
q
}
"^" => {
if b.is_negative() {
return err("negative_exponent");
}
let power = bounded(&b, 100_000)? as u32;
if a.bits().saturating_mul(u64::from(power)) > 1_000_000 {
return err("integer_limit");
}
a.pow(power)
}
"c" | "choose" => choose(&a, &b, false)?,
"p" | "permutation" | "permutations" => choose(&a, &b, true)?,
"&" => a & b,
"|" => a | b,
"xor" => a ^ b,
"<<" | ">>" => {
let bits = bounded(&b, 1_000_000)? as usize;
if op == "<<" { a << bits } else { a >> bits }
}
_ => return err("invalid_integer_expression"),
}
}
Self::Call(name, args) => {
if name == "factorial" && args.len() == 1 {
factorial(&args[0].eval()?)?
} else if matches!(name.as_str(), "choose" | "perm" | "pow" | "rational")
&& args.len() == 2
{
let op = match name.as_str() {
"perm" => "p",
"pow" => "^",
"rational" => "/",
_ => "c",
};
Self::Binary(
op.into(),
Box::new(args[0].clone()),
Box::new(args[1].clone()),
)
.eval()?
} else if matches!(name.as_str(), "gcd" | "gcf" | "lcm") && args.len() >= 2 {
let mut result = args[0].eval()?.abs();
for argument in &args[1..] {
let n = argument.eval()?.abs();
result = if name == "lcm" {
result.lcm(&n)
} else {
result.gcd(&n)
};
}
result
} else {
return err("invalid_integer_expression");
}
}
};
if value.bits() > 1_000_000 {
return err("integer_limit");
}
Ok(value)
}
fn eval_ratio(&self) -> Result<(BigInt, BigInt), Error> {
let (n, d) = match self {
Self::Decimal(raw) => {
let (mantissa, exponent) = raw.split_once(['e', 'E']).unwrap_or((raw, "0"));
let (whole, fraction) = mantissa.split_once('.').unwrap_or((mantissa, ""));
let n = format!("{whole}{fraction}")
.parse::<BigInt>()
.map_err(|_| Error("invalid_integer_expression".into()))?;
let exponent = exponent
.parse::<i64>()
.ok()
.and_then(|e| e.checked_sub(fraction.len() as i64))
.filter(|e| e.unsigned_abs() <= 100_000)
.ok_or_else(|| Error("integer_limit".into()))?;
let scale = BigInt::from(10).pow(exponent.unsigned_abs() as u32);
if exponent < 0 {
(n, scale)
} else {
(n * scale, BigInt::one())
}
}
Self::Unary('-', value) => {
let (n, d) = value.eval_ratio()?;
(-n, d)
}
Self::Unary(_, value) => value.eval_ratio()?,
Self::Binary(op, left, right) if matches!(op.as_str(), "+" | "-" | "*" | "/" | "^") => {
let (a, ad) = left.eval_ratio()?;
let (b, bd) = right.eval_ratio()?;
match op.as_str() {
"+" => (a * &bd + b * &ad, ad * bd),
"-" => (a * &bd - b * &ad, ad * bd),
"*" => (a * b, ad * bd),
"/" => (a * bd, ad * b),
_ => {
if !bd.is_one() {
return err("non_rational_expression");
}
let power = bounded(&b.abs(), 100_000)? as u32;
if a.bits().max(ad.bits()).saturating_mul(u64::from(power)) > 1_000_000 {
return err("integer_limit");
}
if b.is_negative() {
(ad.pow(power), a.pow(power))
} else {
(a.pow(power), ad.pow(power))
}
}
}
}
Self::Call(name, args) if name == "rational" && args.len() == 2 => Self::Binary(
"/".into(),
Box::new(args[0].clone()),
Box::new(args[1].clone()),
)
.eval_ratio()?,
Self::Call(name, args) if name == "pow" && args.len() == 2 => Self::Binary(
"^".into(),
Box::new(args[0].clone()),
Box::new(args[1].clone()),
)
.eval_ratio()?,
Self::Call(name, args)
if matches!(
name.as_str(),
"abs" | "min" | "max" | "sum" | "mean" | "square"
) =>
{
let mut values = args.iter().map(Self::eval_ratio);
let (mut n, mut d) = values
.next()
.ok_or_else(|| Error("invalid_integer_expression".into()))??;
if matches!(name.as_str(), "abs" | "square") {
if args.len() != 1 {
return err("invalid_integer_expression");
}
if name == "abs" {
n = n.abs();
} else {
n = &n * &n;
d = &d * &d;
}
} else {
for value in values {
let (b, bd) = value?;
if matches!(name.as_str(), "min" | "max") {
let order = (&n * &bd).cmp(&(&b * &d));
if (name == "min" && order.is_gt()) || (name == "max" && order.is_lt())
{
(n, d) = (b, bd);
}
} else {
(n, d) = reduce_ratio(n * &bd + b * &d, d * bd)?;
}
}
if name == "mean" {
d *= args.len();
}
}
(n, d)
}
Self::Call(name, args) => {
let arguments = args
.iter()
.map(|argument| {
let (n, d) = argument.eval_ratio()?;
if !d.is_one() {
return err("integer_required");
}
Ok(Self::Value(n))
})
.collect::<Result<Vec<_>, Error>>()?;
(Self::Call(name.clone(), arguments).eval()?, BigInt::one())
}
_ => (self.eval()?, BigInt::one()),
};
reduce_ratio(n, d)
}
fn modular(&self, modulus: &BigInt) -> Result<BigInt, Error> {
match self {
Self::Binary(op, left, right) if op == "^" => {
let exponent = right.eval()?;
if exponent.is_negative() {
return err("negative_exponent");
}
Ok(left.modular(modulus)?.modpow(&exponent, modulus))
}
Self::Binary(op, left, right) if matches!(op.as_str(), "+" | "-" | "*") => {
let (a, b) = (left.modular(modulus)?, right.modular(modulus)?);
Ok(match op.as_str() {
"+" => a + b,
"-" => a - b,
_ => a * b,
}
.mod_floor(modulus))
}
Self::Call(name, args) if name == "factorial" && args.len() == 1 => {
let n = args[0].eval()?;
if n.is_negative() {
return err("invalid_integer_argument");
}
if &n >= modulus {
return Ok(BigInt::zero());
}
let n = bounded(&n, 1_000_000)?;
let mut result = BigInt::one();
for i in 2..=n {
result = (result * i).mod_floor(modulus);
if result.is_zero() {
break;
}
}
Ok(result.mod_floor(modulus))
}
_ => Ok(self.eval()?.mod_floor(modulus)),
}
}
}
fn variable_names(names: &[&str]) -> Result<(), Error> {
if names.is_empty()
|| names.len() > 8
|| names.iter().enumerate().any(|(at, name)| {
name.len() != 1
|| !name.as_bytes()[0].is_ascii_alphabetic()
|| names[..at].contains(name)
})
{
return err("invalid_integer_expression");
}
Ok(())
}
fn rational(value: BigRational) -> Result<BigRational, Error> {
if value.numer().bits().max(value.denom().bits()) > 1_000_000 {
return err("integer_limit");
}
Ok(value)
}
fn constant(value: &BigRational) -> Expr {
Expr::Call(
"rational".into(),
vec![
Expr::Value(value.numer().clone()),
Expr::Value(value.denom().clone()),
],
)
}
fn exact(expression: &Expr) -> Result<BigRational, Error> {
let (n, d) = expression.eval_ratio()?;
rational(BigRational::new(n, d))
}
pub(super) fn with_bindings(
input: &str,
bindings: &[(&str, BigRational)],
) -> Result<BigRational, Error> {
let names = bindings.iter().map(|(name, _)| *name).collect::<Vec<_>>();
variable_names(&names)?;
for (_, value) in bindings {
rational(value.clone())?;
}
fn bind(expression: Expr, bindings: &[(&str, BigRational)]) -> Result<Expr, Error> {
Ok(match expression {
Expr::Variable(name) => constant(
&bindings
.iter()
.find(|(key, _)| *key == name.as_str())
.ok_or_else(|| Error("invalid_integer_expression".into()))?
.1,
),
Expr::Unary(op, value) => Expr::Unary(op, Box::new(bind(*value, bindings)?)),
Expr::Binary(op, a, b) => Expr::Binary(
op,
Box::new(bind(*a, bindings)?),
Box::new(bind(*b, bindings)?),
),
Expr::Call(name, arguments) => Expr::Call(
name,
arguments
.into_iter()
.map(|arg| bind(arg, bindings))
.collect::<Result<_, _>>()?,
),
value => value,
})
}
exact(&bind(parse_mode(input, true, &names)?, bindings)?)
}
struct Affine {
constant: BigRational,
coefficients: Vec<BigRational>,
}
impl Affine {
fn fixed(value: BigRational, count: usize) -> Self {
Self {
constant: value,
coefficients: vec![BigRational::zero(); count],
}
}
fn variable(&self) -> bool {
self.coefficients.iter().any(|value| !value.is_zero())
}
fn scale(self, by: &BigRational) -> Result<Self, Error> {
Ok(Self {
constant: rational(self.constant * by)?,
coefficients: self
.coefficients
.into_iter()
.map(|value| rational(value * by))
.collect::<Result<_, _>>()?,
})
}
}
pub(super) fn affine(
input: &str,
variables: &[&str],
) -> Result<(BigRational, Vec<BigRational>), Error> {
variable_names(variables)?;
fn read(expression: &Expr, variables: &[&str]) -> Result<Affine, Error> {
let count = variables.len();
match expression {
Expr::Variable(name) => {
let index = variables
.iter()
.position(|key| *key == name.as_str())
.ok_or_else(|| Error("invalid_integer_expression".into()))?;
let mut result = Affine::fixed(BigRational::zero(), count);
result.coefficients[index] = BigRational::one();
Ok(result)
}
Expr::Unary(op, value) => {
let value = read(value, variables)?;
if *op == '-' {
value.scale(&-BigRational::one())
} else {
Ok(value)
}
}
Expr::Binary(op, a, b) => {
let a = read(a, variables)?;
let b = read(b, variables)?;
match op.as_str() {
"+" | "-" => {
let b = if op == "-" {
b.scale(&-BigRational::one())?
} else {
b
};
Ok(Affine {
constant: rational(a.constant + b.constant)?,
coefficients: a
.coefficients
.into_iter()
.zip(b.coefficients)
.map(|(a, b)| rational(a + b))
.collect::<Result<_, _>>()?,
})
}
"*" if !b.variable() => a.scale(&b.constant),
"*" if !a.variable() => b.scale(&a.constant),
"/" if !b.variable() => {
if b.constant.is_zero() {
return err("division_by_zero");
}
a.scale(&b.constant.recip())
}
"^" if !b.variable() && b.constant.is_zero() => {
Ok(Affine::fixed(BigRational::one(), count))
}
"^" if !b.variable() && b.constant.is_one() => Ok(a),
_ if !a.variable() && !b.variable() => Ok(Affine::fixed(
exact(&Expr::Binary(
op.clone(),
Box::new(constant(&a.constant)),
Box::new(constant(&b.constant)),
))?,
count,
)),
_ => err("invalid_integer_expression"),
}
}
Expr::Call(name, arguments) => {
let arguments = arguments
.iter()
.map(|arg| read(arg, variables))
.collect::<Result<Vec<_>, _>>()?;
if arguments.iter().any(Affine::variable) {
return err("invalid_integer_expression");
}
Ok(Affine::fixed(
exact(&Expr::Call(
name.clone(),
arguments
.iter()
.map(|arg| constant(&arg.constant))
.collect(),
))?,
count,
))
}
_ => Ok(Affine::fixed(exact(expression)?, count)),
}
}
let value = read(&parse_mode(input, true, variables)?, variables)?;
Ok((value.constant, value.coefficients))
}
pub(super) fn quadratic(input: &str, variable: &str) -> Result<[BigRational; 3], Error> {
variable_names(&[variable])?;
fn degree(expression: &Expr, variable: &str) -> Result<u8, Error> {
match expression {
Expr::Variable(name) if name == variable => Ok(1),
Expr::Unary(_, child) => degree(child, variable),
Expr::Binary(op, left, right) => {
let a = degree(left, variable)?;
let b = degree(right, variable)?;
let result = match op.as_str() {
"+" | "-" => a.max(b),
"*" => a.saturating_add(b),
"/" if b == 0 => a,
"^" if b == 0 => {
if a == 0 {
exact(expression)?;
0
} else {
let power = exact(right)?;
if !power.is_integer() || power.is_negative() {
return err("invalid_integer_expression");
}
let n = power.to_integer();
if n > BigInt::from(2) {
return err("invalid_integer_expression");
}
a.saturating_mul(n.to_u8().unwrap_or(3))
}
}
_ if a == 0 && b == 0 => {
exact(expression)?;
0
}
_ => return err("invalid_integer_expression"),
};
if result > 2 {
return err("invalid_integer_expression");
}
Ok(result)
}
Expr::Call(_, arguments) => {
for argument in arguments {
if degree(argument, variable)? != 0 {
return err("invalid_integer_expression");
}
}
exact(expression)?;
Ok(0)
}
_ => {
exact(expression)?;
Ok(0)
}
}
}
fn read(expression: &Expr, variable: &str) -> Result<([BigRational; 3], bool), Error> {
let fixed = |value| {
Ok((
[rational(value)?, BigRational::zero(), BigRational::zero()],
false,
))
};
match expression {
Expr::Variable(name) if name == variable => Ok((
[BigRational::zero(), BigRational::one(), BigRational::zero()],
true,
)),
Expr::Unary(op, child) => {
let (mut terms, variable) = read(child, variable)?;
if *op == '-' {
for term in &mut terms {
*term = rational(-term.clone())?;
}
}
Ok((terms, variable))
}
Expr::Binary(op, left, right) => {
let (a, av) = read(left, variable)?;
let (b, bv) = read(right, variable)?;
if !av && !bv {
return fixed(exact(expression)?);
}
let mut terms = [
BigRational::zero(),
BigRational::zero(),
BigRational::zero(),
];
match op.as_str() {
"+" | "-" => {
for i in 0..3 {
terms[i] = rational(if op == "+" {
&a[i] + &b[i]
} else {
&a[i] - &b[i]
})?;
}
}
"*" => {
for i in 0..3 {
for j in 0..3 {
if i + j > 2 {
if !a[i].is_zero() && !b[j].is_zero() {
return err("invalid_integer_expression");
}
} else {
terms[i + j] = rational(&terms[i + j] + &a[i] * &b[j])?;
}
}
}
}
"/" if !bv && !b[0].is_zero() => {
for i in 0..3 {
terms[i] = rational(&a[i] / &b[0])?;
}
}
"^" if !bv && b[0].is_integer() => {
let power = b[0].to_integer();
if power.is_zero() {
terms[0] = BigRational::one();
} else if power.is_one() {
terms = a;
} else if power == BigInt::from(2) {
for i in 0..3 {
for j in 0..3 {
if i + j > 2 {
if !a[i].is_zero() && !a[j].is_zero() {
return err("invalid_integer_expression");
}
} else {
terms[i + j] = rational(&terms[i + j] + &a[i] * &a[j])?;
}
}
}
} else {
return err("invalid_integer_expression");
}
}
_ => return err("invalid_integer_expression"),
}
Ok((terms, av || bv))
}
Expr::Call(_, arguments) => {
for argument in arguments {
if read(argument, variable)?.1 {
return err("invalid_integer_expression");
}
}
fixed(exact(expression)?)
}
_ => fixed(exact(expression)?),
}
}
let expression = parse_mode(input, true, &[variable])?;
degree(&expression, variable)?;
Ok(read(&expression, variable)?.0)
}
pub(super) fn quadratic_variable(input: &str) -> Result<String, Error> {
let mut variable: Option<String> = None;
for token in tokenize(input, true, &[])? {
if token.len() == 1 && token.as_bytes()[0].is_ascii_alphabetic() {
if variable
.as_deref()
.is_some_and(|name| name != token.as_str())
{
return err("invalid_integer_expression");
}
variable = Some(token);
}
}
Ok(variable.unwrap_or_else(|| "x".into()))
}
fn reduce_ratio(mut n: BigInt, mut d: BigInt) -> Result<(BigInt, BigInt), Error> {
if d.is_zero() {
return err("division_by_zero");
}
if d.is_negative() {
n = -n;
d = -d;
}
let gcd = n.gcd(&d);
n /= &gcd;
d /= gcd;
if n.bits().max(d.bits()) > 1_000_000 {
return err("integer_limit");
}
Ok((n, d))
}