huge_number_calc.rs - a program to count (add/sub/mul/div (quotient)/remainder) with signed huge numbers.

huge_number_calc.rs

/*  huge_number_calc.rs - a program to count (add/sub/mul/div (quotient)/remainder) with signed huge numbers.
    Copyright (C) 2018 Yoxem Chen <chenjt30 #AT# gmail {DoT} com>

    This program is free software: you can redistribute it and/or modify
    it under the terms of the GNU General Public License as published by
    the Free Software Foundation, either version 3 of the License, or
    (at your option) any later version.

    This program is distributed in the hope that it will be useful,
    but WITHOUT ANY WARRANTY; without even the implied warranty of
    MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
    GNU General Public License for more details.

    You should have received a copy of the GNU General Public License
    along with this program.  If not, see <https://www.gnu.org/licenses/>.
*/

use std::ops;
use std::fmt;
use std::cmp::Ordering;

#[derive(Debug, Clone)]
struct HugeNum{
    is_not_neg: bool,
    abs: Vec<u32>,
}

fn huge_num_read_from_str(x: &str) -> HugeNum{
    let is_not_neg;
    let mut a;

    if x.get(..1).unwrap() == "-"{
        is_not_neg = false;
        a = x.get(1..).unwrap();
    }
    else{
    is_not_neg = true;
   
    if x.get(..1).unwrap() == "+"
        {a = x.get(1..).unwrap();}
    else
        {a = x;}
    }

    let a_len = a.len();
    let a_vec_len = ((a_len as f64)/4.0).ceil() as usize;
    let mut a_vec =  vec![0;a_vec_len];

    for i in 0..(a_vec_len){
        let item;
        let a_len = a.len();
       
        if a_len>=4{
            item = a.get((a.len()-4)..);
            a_vec[a_vec_len-1-i] =
                item.unwrap().parse::<u32>().unwrap();

            a = a.get(..(a.len()-4)).unwrap();
        }
        else{
            a_vec[a_vec_len-1-i] = a.parse::<u32>().unwrap();
        }
    }

    let abs = clear_zero(a_vec);
    HugeNum{is_not_neg, abs}
}

fn clear_zero(v: Vec<u32>) -> Vec<u32>{
    let mut vec = v;
    while (vec[0]==0) & (vec.len() > 1){
    vec.remove(0);
    }
    vec
}

fn get_int_length(a: u64) -> u64{
    if a == 0{
        1
    }
    else{
        ((a as f64).log(10.0).floor() + 1.0) as u64
    }
}

fn huge_num_read_from_int(x: i64) -> HugeNum{
    let mut a;       
    if x >= 0{
    a = x;
    }else{
    a = -x;
    }
   
    let a_len = get_int_length(a as u64);
    let a_vec_len = ((a_len as f64)/4.0).ceil() as usize;
    let mut a_vec = vec![0;a_vec_len];

    for i in 0..(a_vec_len){
        let item = a % 10000;
        a_vec[a_vec_len-1-i] = item as u32;

        a = a / 10000;
    }

    let is_not_neg;
    if x >= 0{
        is_not_neg = true;
    }
    else{
        is_not_neg = false;
    }
    let abs = a_vec;
    HugeNum{is_not_neg,abs}
}

fn huge_num_abs_gt(a: HugeNum, b: HugeNum) -> bool{
    let mut return_value;

    if a.abs.len() > b.abs.len(){
        return_value = true;
    }
    else if a.abs.len() < b.abs.len(){
        return_value = false;
    }
    else {
        return_value = false;
        for i in 0..(a.abs.len()){
            if a.abs[i]<b.abs[i]{
            	return_value = false;
            	break
            }
			else if a.abs[i]>b.abs[i]{
            	return_value = true;
            	break
			}
        }
    }
    return_value
}
// get |a|+|b|
fn huge_num_abs_add(a: HugeNum, b: HugeNum) -> Vec<u32>{
    let mut raw_result;
    let a_len = a.abs.len();
    let b_len = b.abs.len();

    if huge_num_abs_gt(a.clone(),b.clone()){
        raw_result = vec![0;a_len+1];
    }
    else{
        raw_result = vec![0;b_len+1];
}
    let raw_result_len = raw_result.len();

    for i in 0..(raw_result_len-1){
        let a_plus_b;
        if i>= b_len{
            a_plus_b = a.abs[a_len-1-i];
        }else if i >=a_len{
            a_plus_b = b.abs[b_len-1-i];
        }else{
            a_plus_b = a.abs[a_len-1-i] + b.abs[b_len-1-i];
        }
        let temp = (raw_result[raw_result_len-1-i] + a_plus_b) % 10000;

        raw_result[raw_result_len-2-i] = (raw_result[raw_result_len-1-i] + a_plus_b) / 10000;
        raw_result[raw_result_len-1-i] = temp;
    }
    let res = clear_zero(raw_result);
    res
}

//get |a - b|
fn huge_num_abs_sub(a: HugeNum, b: HugeNum) -> Vec<u32>{
    let greater;
    let lesser;

    if huge_num_abs_gt(a.clone(),b.clone()){
        greater = a;
        lesser = b;
    }
    else
    {
        greater = b;
        lesser = a;
    }

    let greater_len = greater.abs.len();
    let lesser_len = lesser.abs.len();
    let mut raw_result: Vec<i64> = vec![0;greater_len];
    let raw_result_len = greater_len;

    for i in 0..raw_result_len{
        if i>= lesser_len{
            raw_result[raw_result_len-1-i] +=greater.abs[greater_len-1-i] as i64;

            if raw_result[raw_result_len-1-i]<0{
                raw_result[raw_result_len-1-i] += 10000;
                raw_result[raw_result_len-2-i] -= 1;
            }
        }else{
            let a_minus_b : i64 =
                (greater.abs[greater_len-1-i] as i64) -
                (lesser.abs[lesser_len-1-i] as i64);

            if a_minus_b >= 0{
                raw_result[raw_result_len-1-i] += a_minus_b;
            }
            else{
                raw_result[raw_result_len-1-i] += ( a_minus_b + 10000);
                raw_result[raw_result_len-2-i] -= 1;
            }
        }
    }
    let raw_result_u32: Vec<u32> = raw_result.iter().map(|n|*n as u32).collect();
    let res = clear_zero(raw_result_u32);
    res
}

//get |a * b|
fn huge_num_abs_mul(a: HugeNum, b: HugeNum) -> Vec<u32>{
    let a_len = a.abs.len();
    let b_len = b.abs.len();
    let raw_result_len = a_len + b_len + 1;
    let mut raw_result = vec![0;raw_result_len];

    for i in 0..a_len{
        for j in 0..b_len{
        let temp =
            raw_result[raw_result_len-1-i-j] + a.abs[a_len-1-i] * b.abs[b_len-1-j];
        raw_result[raw_result_len-1-i-j] = temp % 10000;
        raw_result[raw_result_len-2-i-j] += temp / 10000;
    
        }
    }
    let res = clear_zero(raw_result);
    res
    
}

// get [|a| / |b| ,|a| % |b|] , b is a u32 and b < 1000.
// using binary search method
fn huge_num_abs_basic_div(a: HugeNum, b: u32) -> [Vec<u32>;2]{
    let a_len = a.abs.len();
    let raw_result_len = a_len;
    let mut raw_result = vec![0;raw_result_len];
    
    if b >= 1000{
        panic!("the divider can't be greater than 999");
    }
    
    let mut temp = 0;
    for i in 0..a_len{
        let temp2 = temp * 10000 + a.abs[i];
        raw_result[i] = temp2 / b;
        temp = temp2 % b;
    }
    let quotient = clear_zero(raw_result);
    let remainder = temp;
    
    [quotient,vec![remainder]]
    
}


impl ops::Rem<HugeNum> for HugeNum {
    type Output = HugeNum ;

    fn rem(self, _rhs: HugeNum) -> HugeNum {
        let abs_rem = huge_num_abs_div(self.clone(),_rhs.clone())[1].clone();

        if self.is_not_neg == _rhs.is_not_neg{
			if self.is_not_neg == true || abs_rem == vec![0]{
				HugeNum{
	            	is_not_neg: true,
    	        	abs: abs_rem,
            	}
			}
			else { // self < 0 and _rhs < 0
				HugeNum{
	            	is_not_neg: false,
    	        	abs: abs_rem,
            	}
			}
		}
		else{
			if abs_rem == vec![0]{
				HugeNum{is_not_neg:true,abs:abs_rem,}
			}
			else{
				let raw_result = HugeNum{is_not_neg:true,abs:_rhs.abs} -
				HugeNum{is_not_neg:true,abs:abs_rem,};

				if self.is_not_neg == true { // self > 0, _rhs < 0
					raw_result * huge_num_read_from_int(-1)
				}
				else { // self < 0, _rhs > 0
					raw_result
				}
			}
		}
    }    
}

impl ops::Mul<HugeNum> for HugeNum {
    type Output = HugeNum ;

    fn mul(self, _rhs: HugeNum) -> HugeNum {
        let abs = huge_num_abs_mul(self.clone(),_rhs.clone());
        if self.is_not_neg == _rhs.is_not_neg{
        HugeNum{
            is_not_neg: true,
            abs: abs,
            }
        }else{
            let mut is_not_neg = false;
            if abs == vec![0]{
                is_not_neg = true;
            }
            HugeNum{
                is_not_neg: is_not_neg,
                abs: abs,
            }
        }
    }    
}


impl ops::Div<HugeNum> for HugeNum {
    type Output = HugeNum ;

    fn div(self, _rhs: HugeNum) -> HugeNum {

        let quo_rem_pair = huge_num_abs_div(self.clone(),_rhs.clone());
		let abs_quo = &quo_rem_pair[0];
		let abs_rem = &quo_rem_pair[1];
        if (self.is_not_neg == _rhs.is_not_neg) ||
			 (self.abs == vec![0]){ // dividend = 0 => quotient = 0
        HugeNum{
            is_not_neg: true,
            abs: abs_quo.clone(),
            }
		}
		else{
        	let raw_result = HugeNum{
	            is_not_neg: false,
    	        abs: abs_quo.clone(),
            };
			if abs_rem != &vec![0 as u32]{ // remainder > 0
				raw_result - huge_num_read_from_int(1)
			}
			else{
				raw_result
			}
		}
    }    
}




impl ops::Add<HugeNum> for HugeNum {
    type Output = HugeNum ;

    fn add(self, _rhs: HugeNum) -> HugeNum {
        if self.is_not_neg == _rhs.is_not_neg{
        HugeNum{
            is_not_neg: self.is_not_neg,
            abs: huge_num_abs_add(self,_rhs),
            }
        }else if (self.is_not_neg == true &&
            huge_num_abs_gt(self.clone(),_rhs.clone())) ||
            (self.is_not_neg == false && 
            !huge_num_abs_gt(self.clone(),_rhs.clone())){
            HugeNum{
                is_not_neg: true,
                abs: huge_num_abs_sub(self,_rhs),
            }
        }else{
            let abs = huge_num_abs_sub(self,_rhs);
            let mut is_not_neg = false;
            if abs == vec![0]{
                is_not_neg = true;
            }
            HugeNum{is_not_neg,abs}
        }
    }    
}


impl ops::Sub<HugeNum> for HugeNum  {
    type Output = HugeNum ;

    fn sub(self, _rhs: HugeNum) -> HugeNum {
        if self.is_not_neg != _rhs.is_not_neg{
        	let abs = huge_num_abs_add(self.clone(),_rhs.clone());
	        if abs == vec![0]{
    	        HugeNum{
    	            is_not_neg: true,
    	            abs: abs,
                }
    	    }
			else{
            	HugeNum{
            	    is_not_neg: self.is_not_neg,
            	    abs: abs,
				}
        	}
        }
		else if (self.is_not_neg == true &&
        huge_num_abs_gt(self.clone(),_rhs.clone())) ||
            (self.is_not_neg == false &&
                !huge_num_abs_gt(self.clone(),_rhs.clone())){
            HugeNum{
                is_not_neg: true,
                abs: huge_num_abs_sub(self,_rhs),
            }
        }else{
            let abs = huge_num_abs_sub(self,_rhs);
            let mut is_not_neg = false;
            if abs == vec![0]{
                is_not_neg = true;
            }
            HugeNum{is_not_neg,abs}
        }
    }    
}

// get floor(|a| + |b|) / 2]
fn huge_num_average(a: HugeNum, b: HugeNum) -> Vec<u32>{

    // let x = |a|, y = |b|
    let mut x = HugeNum {is_not_neg: true, abs: a.clone().abs};
    let mut y = HugeNum {is_not_neg: true, abs: b.clone().abs};
    
    let z = huge_num_abs_basic_div((x + y), 2);
    
    let result = z[0].clone();
    result
}


// get |a| / |b| return quotient and remainder
fn huge_num_abs_div(a: HugeNum, b: HugeNum) -> [Vec<u32>;2]{
    let mut n = a; // dividend
    let mut d = b; //divisor
    let mut q = huge_num_read_from_int(0); // quotient
    let mut r = huge_num_read_from_int(0); // remainder
    if (n.is_not_neg == false){n.is_not_neg = true;} // let n = |a|
    if (d.is_not_neg == false){d.is_not_neg = true;} // let n = |a|
    if d == huge_num_read_from_int(0){
        panic!("Error: devided by 0");
    }
    else if (n < d){
        r = n;
        [q.abs,r.abs]
    }
    else if d == huge_num_read_from_int(1){
        
        q = n;
        [q.abs,r.abs]
    }
    else{
        huge_num_abs_div_iter(n.clone(),d,huge_num_read_from_int(0),n.clone())
    }
}

// l: lower bound, u: upper_bound
fn huge_num_abs_div_iter(n: HugeNum, d: HugeNum, l: HugeNum, u:HugeNum) 
    -> [Vec<u32>;2]{
    let q = HugeNum{is_not_neg:true, abs:huge_num_average(l.clone(),u.clone())};
    let r = n.clone() - q.clone() * d.clone();

    if r >= d{
        huge_num_abs_div_iter(n,d,q,u)
    }
    else if r.is_not_neg == false { // r < 0
        huge_num_abs_div_iter(n,d,l,q+huge_num_read_from_int(1))
    }
    else{
    [q.abs,r.abs]
    }
    
    
}


impl fmt::Display for HugeNum {
    fn fmt(&self, f: &mut fmt::Formatter) -> fmt::Result {
        let mut abs_output = "".to_owned();
        for i in 0..self.abs.len(){
            let item = self.abs[i];
            let item_length = get_int_length(item as u64);
            if i == 0{
                abs_output = [abs_output,item.to_string()].join("");
            }
            else{
                let temp =
                ["0".repeat((4-item_length)as usize),item.to_string()].join("");
                abs_output = [abs_output,temp].join("");
            }
        }

        if self.is_not_neg == true{
            write!(f, "{}", abs_output)
        }
        else{
            write!(f,"-{}", abs_output)
        }
    }
}        


impl PartialOrd for HugeNum {
    fn partial_cmp(&self, other: &HugeNum) -> Option<Ordering> {
    
    if self.eq(&other){
        Some(Ordering::Equal)}
    else if (self.is_not_neg == true && other.is_not_neg == false){
        Some(Ordering::Greater)
        }
    else if (self.is_not_neg == false && other.is_not_neg == true){
        Some(Ordering::Less)
        }
    else if (self.is_not_neg == true && other.is_not_neg == true){
        if huge_num_abs_gt(self.clone(),other.clone()){
            Some(Ordering::Greater)
        }
        else{
            Some(Ordering::Less)
        }
    }
    else{
        if huge_num_abs_gt(self.clone(),other.clone()){
            Some(Ordering::Less)
        }
        else{
            Some(Ordering::Greater)
        }
    }
}

}

impl PartialEq for HugeNum {
    fn eq(&self, other: &HugeNum) -> bool {
        self.is_not_neg == other.is_not_neg &&
        self.abs == other.abs
    }
}

fn main() {

    let X = huge_num_read_from_str("5123156456456123");
    let Y = huge_num_read_from_str("12153");


    println!("{}",X.clone()%Y.clone());
    println!("{:?}",huge_num_read_from_str("1")*X.clone());
    println!("{:?}",huge_num_read_from_str("-1")*X.clone()+X.clone());
    println!("{:?}",huge_num_abs_add(X.clone(),Y.clone()));
    println!("{:?}",huge_num_abs_sub(X.clone(),Y.clone()));
    println!("{:?}",huge_num_abs_mul(X.clone(),Y.clone()));
    println!("{:?}",huge_num_abs_div(X.clone(),Y.clone()));
    println!("{:?}",huge_num_average(X.clone(),Y.clone()));
    println!("{:?}",X==Y);
}