Fast Fourier Transform

// Complex FFT using JS complex arithmetic
function fft(a, invert) {
    const n = a.length;
    // Bit-reversal permutation
    for (let i = 1, j = 0; i < n; i++) {
        let bit = n >> 1;
        for (; j & bit; bit >>= 1) j ^= bit;
        j ^= bit;
        if (i < j) [a[i], a[j]] = [a[j], a[i]];
    }
    // Butterfly
    for (let len = 2; len <= n; len <<= 1) {
        const ang = 2 * Math.PI / len * (invert ? -1 : 1);
        const [wr, wi] = [Math.cos(ang), Math.sin(ang)];
        for (let i = 0; i < n; i += len) {
            let [cr, ci] = [1, 0];
            for (let j = 0; j < len / 2; j++) {
                const [ur, ui] = a[i + j];
                const [vr, vi] = a[i + j + len / 2];
                const tr = cr * vr - ci * vi, ti = cr * vi + ci * vr;
                a[i + j] = [ur + tr, ui + ti];
                a[i + j + len / 2] = [ur - tr, ui - ti];
                [cr, ci] = [cr * wr - ci * wi, cr * wi + ci * wr];
            }
        }
    }
    if (invert) for (let i = 0; i < n; i++) a[i] = [a[i][0] / n, a[i][1] / n];
}

function polyMul(a, b) {
    const result = new Array(a.length + b.length - 1).fill(0);
    let n = 1;
    while (n < a.length + b.length) n <<= 1;
    const fa = Array.from({length: n}, (_, i) => [a[i] || 0, 0]);
    const fb = Array.from({length: n}, (_, i) => [b[i] || 0, 0]);
    fft(fa, false); fft(fb, false);
    for (let i = 0; i < n; i++) {
        const [ar, ai] = fa[i], [br, bi] = fb[i];
        fa[i] = [ar * br - ai * bi, ar * bi + ai * br];
    }
    fft(fa, true);
    for (let i = 0; i < result.length; i++) result[i] = Math.round(fa[i][0]);
    return result;
}