y*****x
发帖数: 3291 | 1 假设有 a， b两个 polynomials, 每个都是 degree from 0 to n,
padding n trailing zeros , get A(2N+1) B(2N+1),
用DFT求得A(2N+1), B(2N+1)的 vector,
假设 A l is the l th element of DFT A(2N+1), also for B l
Provide a constant time algorithm to evaluate the
expression
1/(2n+1)^2 * ( sum of (A l) * sum of (B l) ) |
|
