46 lines
1.6 KiB
Plaintext
46 lines
1.6 KiB
Plaintext
;Task:
|
|
Provide code that produces a list of numbers which is the <big>n<sup>th</sup></big> order forward difference, given a non-negative integer (specifying the order) and a list of numbers.
|
|
|
|
|
|
The first-order forward difference of a list of numbers <big>'''A'''</big> is a new list <big>'''B'''</big>, where <big><b>B</b><sub>n</sub> = <b>A</b><sub>n+1</sub> - <b>A</b><sub>n</sub></big>.
|
|
|
|
List <big>'''B'''</big> should have one fewer element as a result.
|
|
|
|
The second-order forward difference of <big>'''A'''</big> will be:
|
|
<pre>
|
|
tdefmodule Diff do
|
|
def forward(arr,i\\1) do
|
|
forward(arr,[],i)
|
|
end
|
|
|
|
def forward([_|[]],diffs,i) do
|
|
if i == 1 do
|
|
IO.inspect diffs
|
|
else
|
|
forward(diffs,[],i-1)
|
|
end
|
|
end
|
|
|
|
def forward([val1|[val2|vals]],diffs,i) do
|
|
forward([val2|vals],diffs++[val2-val1],i)
|
|
end
|
|
end
|
|
</pre>
|
|
The same as the first-order forward difference of <big>'''B'''</big>.
|
|
|
|
That new list will have two fewer elements than <big>'''A'''</big> and one less than <big>'''B'''</big>.
|
|
|
|
The goal of this task is to repeat this process up to the desired order.
|
|
|
|
For a more formal description, see the related [http://mathworld.wolfram.com/ForwardDifference.html Mathworld article].
|
|
|
|
|
|
;Algorithmic options:
|
|
* Iterate through all previous forward differences and re-calculate a new array each time.
|
|
* Use this formula (from [[wp:Forward difference|Wikipedia]]):
|
|
<big><big>
|
|
::: <math>\Delta^n [f](x)= \sum_{k=0}^n {n \choose k} (-1)^{n-k} f(x+k)</math>
|
|
</big></big>
|
|
::: ([[Pascal's Triangle]] may be useful for this option.)
|
|
<br><br>
|