Instantly share code, notes, and snippets.

# huytd/big-number-multiply.rs Last active Feb 21, 2018

Multiply big numbers by base converting algorithm (https://play.rust-lang.org/?gist=50e4da80a076623ba5de3b04410c1739&version=stable)
 fn base_conv(a: &str, n: usize) -> Vec { let mut result = vec![]; let mut s = a.to_owned(); let mut len = s.len(); while len > 0 { let mut pos = 0; if n <= len { pos = len - n; } let n = s[pos..].to_string().parse::().unwrap(); result.push(n); s = s[..pos].to_string(); len = s.len(); } return result; } fn multiply_base(a: Vec, b: Vec, n: u32) -> Vec { let mut result = vec![]; result.resize(a.len() + b.len(), 0u64); let mut bot = 0; let mut up = 0; let mut flag = 0u64; let base = 10u64.pow(n); for i in 0..b.len() { for j in 0..a.len() { let mut t = (a[j] * b[i]) as u64 + flag + result[up]; flag = 0; if t >= base { flag = t / base; t = t % base; } result[up] = t; if j >= a.len()-1 { result[up+1] = flag; flag = 0; } up += 1; } bot += 1; up = bot; } result } fn convert_back(num: Vec, base: usize) -> String { let mut result = String::new(); let filtered: Vec = num.into_iter().filter(|x| *x > 0u64).collect(); for i in 0..filtered.len() { let n = filtered[i]; if n != 0 { if i >= filtered.len()-1 { result = format!("{}{}", n, result); } else { result = format!("{}{}", format!("{num:>0width\$}", num=n, width=base), result); } } } result } fn main() { let base = 9; println!("{:?}", convert_back(multiply_base( base_conv("1234", base), base_conv("3214", base), base as u32 ), base)); println!("{:?}", convert_back(multiply_base( base_conv("12", base), base_conv("13", base), base as u32 ), base)); println!("{:?}", convert_back(multiply_base( base_conv("2", base), base_conv("8", base), base as u32 ), base)); println!("{:?}", convert_back(multiply_base( base_conv("2", base), base_conv("2", base), base as u32 ), base)); println!("{:?}", convert_back(multiply_base( base_conv("29123841234812351239412", base), base_conv("3496123842341123491234123", base), base as u32 ), base)); }
Owner Author

### huytd commented Feb 21, 2018

 Run it directly here: https://play.rust-lang.org/?gist=50e4da80a076623ba5de3b04410c1739&version=stable