chika10's blog

By chika10, history, 2 months ago, In English

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.

 
 
 
 
  • Vote: I like it
  • +4
  • Vote: I do not like it

»
2 months ago, # |
  Vote: I like it 0 Vote: I do not like it

Auto comment: topic has been updated by chika10 (previous revision, new revision, compare).

»
2 months ago, # |
  Vote: I like it 0 Vote: I do not like it

Auto comment: topic has been updated by chika10 (previous revision, new revision, compare).

»
2 months ago, # |
  Vote: I like it 0 Vote: I do not like it

Auto comment: topic has been updated by chika10 (previous revision, new revision, compare).

»
2 months ago, # |
  Vote: I like it 0 Vote: I do not like it

Auto comment: topic has been updated by chika10 (previous revision, new revision, compare).

»
2 months ago, # |
  Vote: I like it 0 Vote: I do not like it

Auto comment: topic has been updated by chika10 (previous revision, new revision, compare).

»
2 months ago, # |
  Vote: I like it 0 Vote: I do not like it

Auto comment: topic has been updated by chika10 (previous revision, new revision, compare).

»
2 months ago, # |
  Vote: I like it +4 Vote: I do not like it

Is there a reason behind this particular expression? Or was it just random.

  • »
    »
    2 months ago, # ^ |
      Vote: I like it +3 Vote: I do not like it

    It's from mathematical finance.

    The vector $$$R$$$ is called the response function and the vector $$$\nu$$$ is the trading strategy.

»
2 months ago, # |
  Vote: I like it +14 Vote: I do not like it

$$$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.