use std::collections::VecDeque;
use std::cmp::Ordering;
pub const ERR_UNIMPLEMENTED: i16 = -1;
pub const ERR_INVALID_FORMAT: i16 = 1;
pub const ERR_DIV_BY_ZERO: i16 = 2;
pub const ERR_NEGATIVE_RESULT: i16 = 3;
pub const ERR_NEGATIVE_SQRT: i16 = 4;
pub const ERR_NUMBER_TOO_LARGE: i16 = 5;
pub const ERR_INFINITE_RESULT: i16 = 6;
type IntResult<T> = std::result::Result<(T, bool), i16>;
type FloatResult<T> = std::result::Result<(T, i32, bool), i16>;
fn parse_num(s: &str) -> IntResult<VecDeque<u8>> {
if s.is_empty() || !s.chars().all(|c| c.is_ascii_digit()) {
return Err(ERR_INVALID_FORMAT);
}
Ok((s.chars().rev().map(|c| c as u8 - b'0').collect(), false))
}
fn to_string(mut digits: VecDeque<u8>, _negative: bool) -> String {
while digits.len() > 1 && *digits.back().unwrap() == 0 {
digits.pop_back();
}
digits.into_iter().rev().map(|d| (b'0' + d) as char).collect()
}
fn is_smaller(a: &VecDeque<u8>, b: &VecDeque<u8>) -> bool {
if a.len() != b.len() {
return a.len() < b.len();
}
for (x, y) in a.iter().rev().zip(b.iter().rev()) {
if x != y {
return x < y;
}
}
false
}
fn is_vec_ge(a: &Vec<u32>, b: &Vec<u32>) -> bool {
if a.len() != b.len() {
return a.len() > b.len();
}
for (x, y) in a.iter().zip(b.iter()) {
if x != y {
return x > y;
}
}
true
}
fn vec_sub(a: &Vec<u32>, b: &Vec<u32>) -> Vec<u32> {
let mut a = a.clone();
let mut b = b.clone();
let mut res = Vec::new();
let mut borrow = 0;
a.reverse();
b.reverse();
for i in 0..a.len() {
let x = a[i];
let y = if i < b.len() { b[i] } else { 0 };
let sub = if x >= y + borrow {
x - y - borrow
} else {
x + 10 - y - borrow
};
borrow = if x < y + borrow { 1 } else { 0 };
res.push(sub);
}
while res.len() > 1 && res.last() == Some(&0) {
res.pop();
}
res.reverse();
res
}
pub fn is_string_odd(s: &str) -> bool {
s.chars().rev().next().map_or(false, |c| c.to_digit(10).unwrap_or(0) % 2 == 1)
}
pub fn add_strings(a: &str, b: &str) -> IntResult<String> {
let (mut a, _) = parse_num(a)?;
let (mut b, _) = parse_num(b)?;
let mut res = VecDeque::new();
let mut carry = 0;
while !a.is_empty() || !b.is_empty() || carry > 0 {
let x = a.pop_front().unwrap_or(0);
let y = b.pop_front().unwrap_or(0);
let sum = x + y + carry;
res.push_back(sum % 10);
carry = sum / 10;
}
Ok((to_string(res, false), false))
}
pub fn sub_strings(a: &str, b: &str) -> IntResult<String> {
let (mut a, _) = parse_num(a)?;
let (mut b, _) = parse_num(b)?;
let mut flipped = false;
if is_smaller(&a, &b) {
std::mem::swap(&mut a, &mut b);
flipped = true;
}
let mut res = VecDeque::new();
let mut borrow = 0;
while !a.is_empty() {
let x = a.pop_front().unwrap();
let y = b.pop_front().unwrap_or(0);
let val = if x >= y + borrow {
x - y - borrow
} else {
x + 10 - y - borrow
};
borrow = if x < y + borrow { 1 } else { 0 };
res.push_back(val);
}
Ok((to_string(res, flipped), flipped))
}
pub fn mul_strings(a: &str, b: &str) -> IntResult<String> {
let (a, _) = parse_num(a)?;
let (b, _) = parse_num(b)?;
let mut res = vec![0u16; a.len() + b.len()];
for (i, &x) in a.iter().enumerate() {
let mut carry = 0u16;
for (j, &y) in b.iter().enumerate() {
let idx = i + j;
let prod = x as u16 * y as u16 + res[idx] + carry;
res[idx] = prod % 10;
carry = prod / 10;
}
res[i + b.len()] += carry;
}
let mut dq: VecDeque<u8> = res.into_iter().map(|v| v as u8).collect();
while dq.len() > 1 && *dq.back().unwrap() == 0 {
dq.pop_back();
}
Ok((to_string(dq, false), false))
}
pub fn div_strings(a: &str, b: &str) -> IntResult<String> {
let (a_digits, _) = parse_num(a)?;
let (b_digits, _) = parse_num(b)?;
if b_digits.iter().all(|&d| d == 0) {
return Err(ERR_DIV_BY_ZERO);
}
let dividend = a_digits.iter().rev().map(|&d| d as u32).collect::<Vec<u32>>();
let divisor = b_digits.iter().rev().map(|&d| d as u32).collect::<Vec<u32>>();
let mut result = Vec::new();
let mut current = Vec::new();
for &digit in ÷nd {
current.push(digit);
while current.len() > 1 && current[0] == 0 {
current.remove(0);
}
let mut count = 0;
while is_vec_ge(¤t, &divisor) {
current = vec_sub(¤t, &divisor);
count += 1;
}
result.push(count as u8);
}
result.reverse();
let dq = VecDeque::from(result);
Ok((to_string(dq, false), false))
}
pub fn mod_strings(a: &str, b: &str) -> IntResult<String> {
let (div, _) = div_strings(a, b)?;
let (prod, _) = mul_strings(&div, b)?;
let (rem, flipped) = sub_strings(a, &prod)?;
Ok((rem, flipped))
}
pub fn rem_strings(a: &str, b: &str) -> IntResult<String> {
let (div, _) = div_strings(a, b)?;
let (prod, _) = mul_strings(&div, b)?;
let (rem, flipped) = sub_strings(a, &prod)?;
Ok((rem, flipped))
}
pub fn pow_strings(base: &str, exponent: &str) -> IntResult<String> {
let (mut exp, _) = parse_num(exponent)?;
if exp.is_empty() || exp.iter().all(|&x| x == 0) {
return Ok(("1".to_string(), false));
}
let (mut result, _) = parse_num("1")?;
let (mut base_val, _) = parse_num(base)?;
while !exp.iter().all(|&x| x == 0) {
if exp[0] % 2 == 1 {
result = parse_num(&mul_strings(&to_string(result.clone(), false), &to_string(base_val.clone(), false))?.0)?.0;
}
exp = parse_num(&div_strings(&to_string(exp.clone(), false), "2")?.0)?.0;
base_val = parse_num(&mul_strings(&to_string(base_val.clone(), false), &to_string(base_val.clone(), false))?.0)?.0;
}
Ok((to_string(result, false), false))
}
pub fn sqrt_string(a: &str) -> IntResult<String> {
if a.starts_with('-') {
return Err(ERR_NEGATIVE_SQRT);
}
let (mut low, _) = parse_num("0")?;
let (mut high, _) = parse_num(a)?;
let mut ans = low.clone();
while is_smaller(&low, &high) || low == high {
let mid = parse_num(&div_strings(
&add_strings(&to_string(low.clone(), false), &to_string(high.clone(), false))?.0,
"2",
)?.0)?.0;
let sq = parse_num(&mul_strings(&to_string(mid.clone(), false), &to_string(mid.clone(), false))?.0)?.0;
if is_smaller(&sq, &parse_num(a)?.0) || sq == parse_num(a)?.0 {
ans = mid.clone();
low = parse_num(&add_strings(&to_string(mid, false), "1")?.0)?.0;
} else {
high = parse_num(&sub_strings(&to_string(mid, false), "1")?.0)?.0;
}
}
Ok((to_string(ans, false), false))
}
fn normalize(mut mantissa: String, mut exp: i32, negative: bool) -> FloatResult<String> {
while mantissa.ends_with('0') && mantissa.len() > 1 {
mantissa.pop();
exp += 1;
}
if mantissa == "0" {
return Ok(("0".to_string(), 0, false));
}
Ok((mantissa, exp, negative))
}
fn cmp_mantissa(a: &str, b: &str) -> Ordering {
if a.len() != b.len() {
return a.len().cmp(&b.len());
}
a.cmp(b)
}
fn add_mantissa(a: &str, b: &str) -> String {
let mut carry = 0;
let mut res = Vec::with_capacity(a.len() + 1);
for (da, db) in a.chars().rev().zip(b.chars().rev()) {
let sum = da.to_digit(10).unwrap() + db.to_digit(10).unwrap() + carry;
carry = sum / 10;
res.push((sum % 10).to_string().chars().next().unwrap());
}
if carry > 0 {
res.push('1');
}
res.reverse();
res.into_iter().collect()
}
fn sub_mantissa(a: &str, b: &str) -> String {
let mut borrow = 0;
let mut res = Vec::with_capacity(a.len());
for (da, db) in a.chars().rev().zip(b.chars().rev()) {
let mut d_a = da.to_digit(10).unwrap() as i32 - borrow;
let d_b = db.to_digit(10).unwrap() as i32;
if d_a < d_b {
d_a += 10;
borrow = 1;
} else {
borrow = 0;
}
let d = d_a - d_b;
res.push(std::char::from_digit(d as u32, 10).unwrap());
}
res.reverse();
while res.len() > 1 && res[0] == '0' {
res.remove(0);
}
res.into_iter().collect()
}
fn align(
m1: &str,
e1: i32,
m2: &str,
e2: i32,
) -> (String, String, i32) {
let target_exp = e1.min(e2);
let diff1 = e1 - target_exp;
let diff2 = e2 - target_exp;
let mut nm1 = m1.to_string();
for _ in 0..diff1 {
nm1.push('0');
}
let mut nm2 = m2.to_string();
for _ in 0..diff2 {
nm2.push('0');
}
(nm1, nm2, target_exp)
}
pub fn add_float(
mant1: String,
exp1: i32,
neg1: bool,
mant2: String,
exp2: i32,
neg2: bool,
) -> FloatResult<String> {
if neg1 == neg2 {
let (a, b, exp) = align(&mant1, exp1, &mant2, exp2);
let sum = add_mantissa(&a, &b);
normalize(sum, exp, neg1)
} else {
sub_float(mant1, exp1, neg1, mant2, exp2, !neg2)
}
}
pub fn sub_float(
mant1: String,
exp1: i32,
neg1: bool,
mant2: String,
exp2: i32,
neg2: bool,
) -> FloatResult<String> {
if neg1 != neg2 {
add_float(mant1, exp1, neg1, mant2, exp2, !neg2)
} else {
let (a, b, exp) = align(&mant1, exp1, &mant2, exp2);
match cmp_mantissa(&a, &b) {
std::cmp::Ordering::Equal => Ok(("0".to_string(), 0, false)),
std::cmp::Ordering::Greater => {
let diff = sub_mantissa(&a, &b);
normalize(diff, exp, neg1)
}
std::cmp::Ordering::Less => {
let diff = sub_mantissa(&b, &a);
normalize(diff, exp, !neg1)
}
}
}
}
pub fn mul_float(
mant1: String,
exp1: i32,
neg1: bool,
mant2: String,
exp2: i32,
neg2: bool,
) -> FloatResult<String> {
let n1 = mant1.len();
let n2 = mant2.len();
let mut res = vec![0; n1 + n2];
let a: Vec<_> = mant1.chars().rev().map(|c| c.to_digit(10).unwrap()).collect();
let b: Vec<_> = mant2.chars().rev().map(|c| c.to_digit(10).unwrap()).collect();
for i in 0..n1 {
for j in 0..n2 {
res[i + j] += a[i] * b[j];
}
}
for i in 0..res.len() - 1 {
let c = res[i] / 10;
res[i] %= 10;
res[i + 1] += c;
}
while res.len() > 1 && *res.last().unwrap() == 0 {
res.pop();
}
res.reverse();
let mant: String = res.iter().map(|d| std::char::from_digit(*d, 10).unwrap()).collect();
let exp = exp1 + exp2;
let negative = neg1 ^ neg2;
normalize(mant, exp, negative)
}
pub fn div_float(
mant1: String,
exp1: i32,
neg1: bool,
mant2: String,
exp2: i32,
neg2: bool,
) -> FloatResult<String> {
if mant2 == "0" {
return Err(ERR_DIV_BY_ZERO);
}
let desired_precision = 20;
let mut numerator = mant1.clone();
for _ in 0..desired_precision {
numerator.push('0');
}
let denominator = mant2.clone();
let (quotient, _remainder) = div_mod_strings(&numerator, &denominator)?;
let exp = exp1 - exp2 - desired_precision;
let negative = neg1 ^ neg2;
normalize(quotient, exp, negative)
}
pub fn mod_float(
mant1: String,
exp1: i32,
neg1: bool,
mant2: String,
exp2: i32,
neg2: bool,
) -> FloatResult<String> {
if mant2 == "0" {
return Err(ERR_DIV_BY_ZERO);
}
let (q, exp_q, neg_q) = div_float(mant1.clone(), exp1, neg1, mant2.clone(), exp2, neg2)?;
let int_part = if exp_q >= 0 {
(q.clone(), exp_q, neg_q)
} else {
let cutoff = (q.len() as i32 + exp_q) as usize;
if cutoff <= 0 {
("0".to_string(), 0, false)
} else {
(q[..cutoff].to_string(), 0, neg_q)
}
};
let (mul_m, mul_e, mul_neg) = mul_float(mant2, exp2, neg2, int_part.0, int_part.1, int_part.2)?;
let (res_m, res_e, res_neg) = sub_float(mant1, exp1, neg1, mul_m, mul_e, mul_neg)?;
Ok((res_m, res_e, res_neg))
}
fn div_mod_strings(a: &str, b: &str) -> Result<(String, String), i16> {
if b == "0" {
return Err(ERR_DIV_BY_ZERO);
}
if a == "0" {
return Ok(("0".to_string(), "0".to_string()));
}
if cmp_mantissa(a, b) == std::cmp::Ordering::Less {
return Ok(("0".to_string(), a.to_string()));
}
let mut remainder = String::new();
let mut quotient = String::new();
let mut idx = 0;
while idx < a.len() {
remainder.push(a.chars().nth(idx).unwrap());
while remainder.len() > 1 && remainder.starts_with('0') {
remainder.remove(0);
}
let mut count = 0;
while cmp_mantissa(&remainder, b) != std::cmp::Ordering::Less {
remainder = sub_mantissa(&remainder, b);
count += 1;
}
quotient.push(std::char::from_digit(count, 10).unwrap());
idx += 1;
}
while quotient.len() > 1 && quotient.starts_with('0') {
quotient.remove(0);
}
if remainder.is_empty() {
remainder = "0".to_string();
}
Ok((quotient, remainder))
}