Instantly share code, notes, and snippets.

Embed
What would you like to do?
Multiply big numbers by base converting algorithm (https://play.rust-lang.org/?gist=50e4da80a076623ba5de3b04410c1739&version=stable)
fn base_conv(a: &str, n: usize) -> Vec<u64> {
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::<u64>().unwrap();
result.push(n);
s = s[..pos].to_string();
len = s.len();
}
return result;
}
fn multiply_base(a: Vec<u64>, b: Vec<u64>, n: u32) -> Vec<u64> {
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<u64>, base: usize) -> String {
let mut result = String::new();
let filtered: Vec<u64> = 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));
}
@huytd

This comment has been minimized.

Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment