>>102048155Let the following sequence represent the number of gecs between the ith meter
of the pavement and the (i+1)th meter, 0≤ i ≤100n−1:
A= <A_0, A_1,.., A_{100n−1}
And let the following sequence represent where the holes in a net of length
n are:
N=<N_0, N_1,...,N_{n−1i} where N_i can be equal to 1 or 0
Finding the spot where the net should be cast in order to catch the most gecs
requires us to compute the convolution C of sequences A and N_r
C=A N_r
1.From their corresponding sequences in
O(n) time:
P_A(x)=A_0 + A_1x +...+ A_{100n−1}x^{100n−1}
P_{N_r}(x)=N_{n−1}+ N_{n−2}x+...+N_1x_{n−2} + N_0x_{n−1}
2.Pad the sequences with 0s so that they are of same length, allowing us to
later multiply their DFTs
A'=<A_0, A_1,...,A_{100n−1},0,..., 0>| { repeated n−1}
N'=< N_{n−1}, N_{n−2},...,N_1, N_0,0,...,0>| {repeated 100n−1}
3.Using the FFT we can compute the DFT of A_0 and N_0 in O(nlogn) time
DFT(A_0)=<P_A(1), P_A(w_{101n−1}), P_A(w^2_{101n−1}),..., P_A(w^{101n-2}_{101n−1})>
DFT(N'_r)=<P_N_r(1),P_N_r(w_{101n−1}), P_N_r(w^2_{101n−1}),..,P_N_r(w^{101n−2}_{101n−1})>
We now have value representations of the polynomials P_A(x) and P_N_r(x):
A''_k= P_A(w^k_{101n−1})
N''_k= P_N_r(w^k_{101n−1})
4.Multiplying these polynomials requires no multiplication of large numbers, so it can be done in O(n) time:
C''_k= A''_k N''_k = P_C(w^k_{101n−1}) = {P_A(1) P_N_r(1), P_A(w_{101n−1}) P_N_r(w_{101n−1}), PA(w^2_{101n−1}) P_N_r(w^2_{101n−1}),...,P_A(w^{101n−2}_{101n−1}) P_N_r(w^{101n−2}_{101n−1} ) }
5.Applying the IDFT will recover the coefficients of P_C(x) in O(nlog(n))
time, giving us the convolution:
C= <Sum(j, i=0): A_i B_i>^{j=101n-2}_{j=0}
=<C_0, C_1, ..., C_{101n−2}>
6. In O(n) time we can traverse the sequence to find the index i of the largest value in the sequence. This index i will tell us where to place the left end of the net in order to catch the largest possible number of gecs.