fn convolve_u64_fft(a: Vec<u64>, b: Vec<u64>) -> Vec<u64>Examples found in repository?
crates/competitive/src/math/number_theoretic_transform.rs (line 1090)
1067 fn convolve(a: Self::T, b: Self::T) -> Self::T {
1068 let max_len = Self::length(&a).max(Self::length(&b));
1069 let min_len = Self::length(&a).min(Self::length(&b));
1070 let (balanced, short) = crate::avx_helper!(@dispatch_avx2_fma (300, 64), (1536, 512));
1071 if max_len <= balanced || min_len <= short {
1072 let a_wrapping: &[Wrapping<u64>] =
1073 unsafe { std::slice::from_raw_parts(a.as_ptr().cast(), a.len()) };
1074 let b_wrapping: &[Wrapping<u64>] =
1075 unsafe { std::slice::from_raw_parts(b.as_ptr().cast(), b.len()) };
1076 let mut c = std::mem::ManuallyDrop::new(if max_len <= 300 || min_len > 60 {
1077 convolve_karatsuba(a_wrapping, b_wrapping)
1078 } else {
1079 convolve_naive(a_wrapping, b_wrapping)
1080 });
1081 return unsafe { Vec::from_raw_parts(c.as_mut_ptr().cast(), c.len(), c.capacity()) };
1082 }
1083 let len = (Self::length(&a) + Self::length(&b)).saturating_sub(1);
1084 let block_len = if min_len >= 1 << 20 {
1085 1 << 20
1086 } else {
1087 (min_len.next_power_of_two() * 8).min(1 << 21) - min_len + 1
1088 };
1089 if max_len <= block_len {
1090 return convolve_u64_fft(a, b);
1091 }
1092 let mut result = vec![0u64; len];
1093 for (i, a) in a.chunks(block_len).enumerate() {
1094 for (j, b) in b.chunks(block_len).enumerate() {
1095 if a.len().min(b.len()) <= 60 {
1096 for (x, &a) in a.iter().enumerate() {
1097 for (y, &b) in b.iter().enumerate() {
1098 let value = &mut result[(i + j) * block_len + x + y];
1099 *value = value.wrapping_add(a.wrapping_mul(b));
1100 }
1101 }
1102 continue;
1103 }
1104 let product = convolve_u64_fft(a.to_vec(), b.to_vec());
1105 for (value, product) in result[(i + j) * block_len..].iter_mut().zip(product) {
1106 *value = value.wrapping_add(product);
1107 }
1108 }
1109 }
1110 result
1111 }