Calculus

[e-]

Definitions

$size(arr)$: the length of array $arr$, often abbreviated as $n$

$Inst_i(EXPR)$: the approximate value of $EXPR$ at iteration $i$

$accum_n(EXPR)$: the approximate accumulated value of $EXPR$ with $n$ iterations. $n$ can be omitted if it is clear from the context.

$BQ_i(EXPR)$: the accumulation of $EXPR$ represented as an expression of base quantities.

$BQ(EXPR)|i=k$: the actual approximate value of EXPR by plugging in the iteration number to $BQ(EXPR)$

Axioms

$Inst_i(1)$ = 1

$Inst_i(accum_n(1)) = n$

$Inst_i(Inst_j(accum_n(1))) = Inst_i(n) = n^2$

$Inst_i(accum(each(arr))) = \frac{\Sigma_{k=1}^i arr[k]}{i} \cdot size(arr) $

$Inst_i(accum(each(arr)^2)) = \frac{\Sigma_{k=1}^i arr[k]^2}{i} \cdot size(arr) $

$Inst_i(accum(each(arr)^m)) = \frac{\Sigma_{k=1}^i arr[k]^m}{i} \cdot size(arr) $

$Inst_i(accum(\frac{each(arr)}{each(arr2)})) = \frac{\Sigma_{k=1}^i \frac{arr[k]}{arr2[k]}}{i} \cdot size(arr) $

$Inst_i(EXPR_1 + EXPR_2) = Inst_i(EXPR_1) + Inst_i(EXPR_2)$

$Inst_i(c \cdot EXPR) = c \cdot Inst_i(EXPR)$

Examples

Example 1

$Inst_i(accum((each(arr) + 1) ^ 2)) = Inst_i(accum(each(arr)^2 + 2 \cdot each(arr) + 1))$

$= Inst_i(accum(each(arr)^2)) + 2 \cdot Inst_i(accum(each(arr))) + Inst_i(accum_n(1))$

$= \frac{\Sigma_{k=1}^i arr[k]^2}{i} \cdot size(arr) + 2 \cdot \frac{\Sigma_{k=1}^i arr[k]}{i} \cdot size(arr) + i$

Example 2

$Inst_i(accum((each(data) - \frac{accum(each(data))}{n}) ^ 2))$

$= Inst_i(accum(each(data)^2 - 2 \cdot each(data) \cdot \frac{accum(each(data))}{n} + \frac{accum(each(data))^2}{n^2}))$

$= Inst_i(accum(each(data)^2)) - 2 \cdot Inst_i(accum(each(data) \cdot \frac{accum(each(data))}{n}) + Inst_i(accum(\frac{accum(each(data))^2}{n^2}))$

$= \frac{\Sigma_{k=1}^i data[k]^2}{i} \cdot n - 2 \cdot \frac{\Sigma_{k=1}^i data[k] \cdot \Sigma_{k=1}^i data[k]}{i^2} \cdot n + \Sigma_{k=1}^i data[k]$