karatsuba_rs/
lib.rs

1use std::str::FromStr;
2use num_bigint::{BigInt};
3
4/// # Examples
5/// ```
6///  use num_bigint::{BigInt};
7///  use std::str::FromStr;
8///  let a = BigInt::from_str("1234567891011333456756333333333333335555555").unwrap();
9///  let b = BigInt::from_str("12345678910113333453456").unwrap();
10///  assert_eq!(BigInt::from(a.clone() * b.clone()).to_string(), multiply(a, b).to_string());
11/// ```
12///
13
14pub fn multiply(x: BigInt, y: BigInt) -> BigInt {
15    let x_len = x.to_string().len() as u32;
16    let y_len = y.to_string().len() as u32;
17
18
19    if x_len == 1 && y_len == 1 {
20        return x * y;
21    }
22    let half_x_len = x_len / 2;
23    let half_y_len = y_len / 2;
24    let x_multiplier = 10_u128.pow(half_x_len as u32);
25    let y_multiplier = 10_u128.pow(half_y_len as u32);
26
27
28    let b = x.clone() % (x_multiplier);
29    let d = y.clone() % (y_multiplier);
30    let a = x.clone() / (x_multiplier);
31    let c = y.clone() / (y_multiplier);
32
33
34    let ac = multiply(a.clone(), c.clone());
35    let bd = multiply(b.clone(), d.clone());
36    let ad = multiply(a.clone(), d.clone());
37    let bc = multiply(b.clone(), c.clone());
38
39    return 10_u128.pow((half_x_len + half_y_len) as u32) * ac + 10_u128.pow((half_x_len) as u32) * ad + 10_u128.pow((half_y_len) as u32) * bc + bd;
40}
41
42
43
44pub fn multiply_string(x_str:&str, y_str:&str) -> BigInt {
45    let x=BigInt::from_str(x_str).unwrap();
46    let y=BigInt::from_str(y_str).unwrap();
47    return multiply(x,y);
48
49}
50
51#[cfg(test)]
52mod tests {
53    use crate::{multiply, multiply_string};
54
55    use num_bigint::BigInt;
56    use std::str::FromStr;
57
58
59    #[test]
60    fn multiply_works() {
61        let a = BigInt::from_str("1234567891011333456756333333333333335555555").unwrap();
62        let b = BigInt::from_str("12345678910113333453456").unwrap();
63        assert_eq!(BigInt::from(a.clone() * b.clone()).to_string(), multiply(a, b).to_string());
64    }
65    #[test]
66    fn multiply_string_works() {
67        let a_str = "1234567891011333456756333333333333335555555";
68        let b_str = "12345678910113333453456";
69        let a=BigInt::from_str(a_str).unwrap();
70        let b=BigInt::from_str(b_str).unwrap();
71        assert_eq!(BigInt::from(a.clone() * b.clone()).to_string(), multiply_string(&a_str, &b_str).to_string());
72    }
73}
karatsuba_rs/lib.rs

karatsuba_rs/
lib.rs
