Function nekolib::algo::convolve

pub fn convolve<T>(a: &[T], b: &[T]) -> Vec<T>where
    T: AddAssign + SubAssign + Mul<Output = T> + Default + Clone,

Karatsuba 法。Карацуба 法？

$a = (a_i)$ と $b = (b_i)$ の積 $a * b$ を求める。 ただし、$a * b$ は以下のように定義される。 $$ (a * b)_i = \sum_{j=0}^i a_j \cdot b_{i-j}. $$

Idea

todo!()

Complexity

$O(n^{\log_2(3)}) \subset O(n^{1.585})$ time.

Examples

use nekolib::algo::convolve;

let a = vec![0_i32, 1, 2, 3, 4];
let b = vec![0, 1, 2, 4, 8];
assert_eq!(convolve(&a, &b), [0, 0, 1, 4, 11, 26, 36, 40, 32]);