algostru/arithmetic/multiplication/
karatsuba.rs

1use std::cmp;
2
3use num_integer::Integer;
4use num_bigint::BigInt;
5
6/// Karatsuba implementation
7fn karatsuba(x: BigInt, y: BigInt) -> BigInt {
8    let x_len = x.to_str_radix(10).len() as u32;
9    let y_len = y.to_str_radix(10).len() as u32;
10    let n = cmp::min(x_len, y_len);
11
12    if n == 1 {
13        return x * y;
14    }
15
16    let midpoint = n / 2;
17    let base = BigInt::from(10);
18    let midnum = base.pow(midpoint);
19
20    let a = x.div_floor(&midnum);
21    let b = x.mod_floor(&midnum);
22    let c = y.div_floor(&midnum);
23    let d = y.mod_floor(&midnum);
24
25    let p = &a + &b;
26    let q = &c + &d;
27
28    let ac = karatsuba(a, c);
29    let bd = karatsuba(b, d);
30    let pq = karatsuba(p, q);
31
32    let adbc = &pq - &ac - &bd;
33
34    base.pow(2 * midpoint) * ac + base.pow(midpoint) * adbc + bd
35}
36
37/// Karatsuba Multiplication
38///
39/// Input: two n-digit positive integers x and y
40/// Output: product of x * y
41/// Assumption: n is power of 2
42///
43/// ================================================================================================
44///
45/// ```ignore
46/// n = max length of x or y
47///
48/// if n equals 1 then
49///     base case: return product of x * y
50/// else
51///     a, b = first and second halves (n/2) of x
52///     c, d = first and second halves (n/2) of y
53///
54///     p = sum of a and b
55///     q = sum of c and d
56///
57///     recursive karatsuba:
58///     ac = product of a * c
59///     bd = product of b * d
60///     pq = product of p * q
61///
62///     adbc = pq - ac - bd
63///
64///     return result: 10^n * ac + (10^n/2) * adbc + bd
65/// ```
66pub fn multiply(x: BigInt, y: BigInt) -> BigInt {
67    karatsuba(x, y)
68}
algostru/arithmetic/multiplication/karatsuba.rs

algostru/arithmetic/multiplication/
karatsuba.rs
