Skip to content

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.

Copy link
Owner Author

huytd commented Feb 21, 2018

Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment
You can’t perform that action at this time.
You signed in with another tab or window. Reload to refresh your session. You signed out in another tab or window. Reload to refresh your session.