chika10's blog

By chika10, history, 2 months ago,

Consider

$R_k = \sum_{j = 0}^{ j = k - 1} \sqrt\nu_j(\sqrt{k - j} - \sqrt{k - 1 - j})$ $\newline$ Can we compute $\sum_{j = 1}^{j = K} \nu_kR_k$ in less than O(K^2) ? $\newline$ $\nu$ and $R$ are arrays of double of size $K$ $\newline$ The answer is a double.

• +4

 » 2 months ago, # |   0 Auto comment: topic has been updated by chika10 (previous revision, new revision, compare).
 » 2 months ago, # |   0 Auto comment: topic has been updated by chika10 (previous revision, new revision, compare).
 » 2 months ago, # |   0 Auto comment: topic has been updated by chika10 (previous revision, new revision, compare).
 » 2 months ago, # |   0 Auto comment: topic has been updated by chika10 (previous revision, new revision, compare).
 » 2 months ago, # |   0 Auto comment: topic has been updated by chika10 (previous revision, new revision, compare).
 » 2 months ago, # |   0 Auto comment: topic has been updated by chika10 (previous revision, new revision, compare).
 » 2 months ago, # |   +4 Is there a reason behind this particular expression? Or was it just random.
•  » » 2 months ago, # ^ |   +3 It's from mathematical finance.The vector $R$ is called the response function and the vector $\nu$ is the trading strategy.
 » 2 months ago, # |   +14 $R$ is just a convolution of two polynomials.First is $A[X] = \sum_{j=0}^{k-1} \sqrt{\nu_j} X^j$.Second is $B[X] = \sum_{j=0}^{k-1} (\sqrt{j + 1} - \sqrt{j}) X^j$.use FFT to compute $R$ in $O(K \log K)$, and then you can compute the sum that you require.
•  » » 2 months ago, # ^ |   0 Wow! Thank you!!