Forward difference: Difference between revisions
Added Easylang |
|||
(234 intermediate revisions by more than 100 users not shown) | |||
Line 1: | Line 1: | ||
{{task|Arithmetic operations}} |
{{task|Arithmetic operations}} |
||
Provide code that produces a list of numbers which is the n-th 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 (A) is a new list (B) where B<sub>n</sub> = A<sub>n+1</sub> - A<sub>n</sub>. List B should have one less element as a result. The second-order forward difference of A will be the same as the first-order forward difference of B. That new list will have two fewer elements than A and one less than B. The goal of this task is to repeat this process up to the desired order. |
|||
;Task: |
|||
For a more formal description, see the related [http://mathworld.wolfram.com/ForwardDifference.html Mathworld article]. |
|||
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> |
|||
=={{header|11l}}== |
|||
{{trans|Python}} |
|||
<syntaxhighlight lang="11l">V dif = s -> enumerate(s[1..]).map2((i, x) -> x - @s[i]) |
|||
F difn(s, n) -> [Int] |
|||
R I n != 0 {difn(dif(s), n - 1)} E s |
|||
V s = [90, 47, 58, 29, 22, 32, 55, 5, 55, 73] |
|||
L(i) 10 |
|||
print(difn(s, i))</syntaxhighlight> |
|||
{{out}} |
|||
<pre> |
|||
[90, 47, 58, 29, 22, 32, 55, 5, 55, 73] |
|||
[-43, 11, -29, -7, 10, 23, -50, 50, 18] |
|||
[54, -40, 22, 17, 13, -73, 100, -32] |
|||
[-94, 62, -5, -4, -86, 173, -132] |
|||
[156, -67, 1, -82, 259, -305] |
|||
[-223, 68, -83, 341, -564] |
|||
[291, -151, 424, -905] |
|||
[-442, 575, -1329] |
|||
[1017, -1904] |
|||
[-2921] |
|||
</pre> |
|||
=={{header|Ada}}== |
=={{header|Ada}}== |
||
<syntaxhighlight lang="ada">with Ada.Text_Io; |
|||
with Ada.Float_Text_Io; use Ada.Float_Text_Io; |
|||
with Ada.containers.Vectors; |
|||
procedure Forward_Difference is |
|||
package Flt_Vect is new Ada.Containers.Vectors(Positive, Float); |
|||
use Flt_Vect; |
|||
procedure Print(Item : Vector) is |
|||
begin |
|||
if not Item.Is_Empty then |
|||
Ada.Text_IO.Put('['); |
|||
for I in 1..Item.Length loop |
|||
Put(Item => Item.Element(Positive(I)), Fore => 1, Aft => 1, Exp => 0); |
|||
if Positive(I) < Positive(Item.Length) then |
|||
Ada.Text_Io.Put(", "); |
|||
end if; |
|||
end loop; |
|||
Ada.Text_Io.Put_line("]"); |
|||
else |
|||
Ada.Text_IO.Put_Line("Empty List"); |
|||
end if; |
|||
end Print; |
|||
function Diff(Item : Vector; Num_Passes : Natural) return Vector is |
|||
A : Vector := Item; |
|||
B : Vector := Empty_Vector; |
|||
begin |
|||
if not A.Is_Empty then |
|||
for I in 1..Num_Passes loop |
|||
for I in 1..Natural(A.Length) - 1 loop |
|||
B.Append(A.Element(I + 1) - A.Element(I)); |
|||
end loop; |
|||
Move(Target => A, Source => B); |
|||
end loop; |
|||
end if; |
|||
return A; |
|||
end Diff; |
|||
Values : array(1..10) of Float := (90.0, 47.0, 58.0, 29.0, 22.0, 32.0, 55.0, 5.0, 55.0, 73.0); |
|||
A : Vector; |
|||
begin |
|||
for I in Values'range loop |
|||
A.Append(Values(I)); -- Fill the vector |
|||
end loop; |
|||
Print(Diff(A, 1)); |
|||
Print(Diff(A, 2)); |
|||
Print(Diff(A, 9)); |
|||
Print(Diff(A, 10)); |
|||
print(Diff(A, 0)); |
|||
end Forward_Difference;</syntaxhighlight> |
|||
{{out}} |
|||
Output: |
|||
<pre> |
|||
[-43.0, 11.0, -29.0, -7.0, 10.0, 23.0, -50.0, 50.0, 18.0] |
[-43.0, 11.0, -29.0, -7.0, 10.0, 23.0, -50.0, 50.0, 18.0] |
||
[54.0, -40.0, 22.0, 17.0, 13.0, -73.0, 100.0, -32.0] |
[54.0, -40.0, 22.0, 17.0, 13.0, -73.0, 100.0, -32.0] |
||
Line 61: | Line 131: | ||
Empty List |
Empty List |
||
[90.0, 47.0, 58.0, 29.0, 22.0, 32.0, 55.0, 5.0, 55.0, 73.0] |
[90.0, 47.0, 58.0, 29.0, 22.0, 32.0, 55.0, 5.0, 55.0, 73.0] |
||
</pre> |
|||
=={{header|ALGOL 68}}== |
=={{header|ALGOL 68}}== |
||
{{works with|ALGOL 68|Revision 1 - no extensions to language used}} |
|||
main:( |
|||
MODE LISTREAL = [1:0]REAL; |
|||
{{works with|ALGOL 68G|Any - tested with release [http://sourceforge.net/projects/algol68/files/algol68g/algol68g-1.18.0/algol68g-1.18.0-9h.tiny.el5.centos.fc11.i386.rpm/download 1.18.0-9h.tiny]}} |
|||
{{wont work with|ELLA ALGOL 68|Any (with appropriate job cards) - tested with release [http://sourceforge.net/projects/algol68/files/algol68toc/algol68toc-1.8.8d/algol68toc-1.8-8d.fc9.i386.rpm/download 1.8-8d] - due to extensive use of FORMATted transput}} |
|||
<syntaxhighlight lang="algol68">main:( |
|||
MODE LISTREAL = [1:0]REAL; |
|||
OP - = (LISTREAL a,b)LISTREAL: ( |
|||
[UPB a]REAL out; |
|||
FOR i TO UPB out DO out[i]:=a[i]-b[i] OD; |
|||
out |
|||
); |
|||
FORMAT real fmt=$zzz-d.d$; |
|||
FORMAT repeat fmt = $n(UPB s-1)(f(real fmt)",")f(real fmt)$; |
|||
FORMAT list fmt = $"("f(UPB s=1|real fmt|repeat fmt)")"$; |
|||
FLEX [1:0] REAL s := (90, 47, 58, 29, 22, 32, 55, 5, 55, 73); |
|||
printf((list fmt,s,$";"l$)); |
|||
TO UPB s-1 DO |
|||
s := s[2:] - s[:UPB s-1]; |
|||
printf((list fmt,s,$";"l$)) |
|||
OD |
|||
)</syntaxhighlight> |
|||
{{out}} |
|||
<pre> |
|||
( 90.0, 47.0, 58.0, 29.0, 22.0, 32.0, 55.0, 5.0, 55.0, 73.0); |
|||
( -43.0, 11.0, -29.0, -7.0, 10.0, 23.0, -50.0, 50.0, 18.0); |
|||
( 54.0, -40.0, 22.0, 17.0, 13.0, -73.0, 100.0, -32.0); |
|||
( -94.0, 62.0, -5.0, -4.0, -86.0, 173.0, -132.0); |
|||
( 156.0, -67.0, 1.0, -82.0, 259.0, -305.0); |
|||
( -223.0, 68.0, -83.0, 341.0, -564.0); |
|||
( 291.0, -151.0, 424.0, -905.0); |
|||
( -442.0, 575.0,-1329.0); |
|||
( 1017.0,-1904.0); |
|||
(-2921.0); |
|||
</pre> |
|||
=={{header|ALGOL W}}== |
|||
<syntaxhighlight lang="algolw">begin |
|||
% calculate forward differences % |
|||
% sets elements of B to the first order forward differences of A % |
|||
% A should have bounds 1 :: n, B should have bounds 1 :: n - 1 % |
|||
procedure FirstOrderFDifference ( integer array A( * ) |
|||
; integer array B( * ) |
|||
; integer value n |
|||
) ; |
|||
for i := 2 until n do B( i - 1 ) := A( i ) - A( i - 1 ); |
|||
integer array v ( 1 :: 10 ); |
|||
integer array diff( 1 :: 9 ); |
|||
integer vPos, length; |
|||
% construct the initial values array % |
|||
vPos := 1; |
|||
for i := 90, 47, 58, 29, 22, 32, 55, 5, 55, 73 do begin |
|||
v( vPos ) := i; |
|||
vPos := vPos + 1 |
|||
end for_i ; |
|||
% calculate and show the differences % |
|||
i_w := 5; % set output format % |
|||
length := 10; |
|||
for order := 1 until length - 1 do begin |
|||
FirstOrderFDifference( v, diff, length ); |
|||
length := length - 1; |
|||
write( order, ": " ); for i := 1 until length do writeon( diff( i ) ); |
|||
for i := 1 until length do v( i ) := diff( i ) |
|||
end for_order |
|||
end.</syntaxhighlight> |
|||
{{out}} |
|||
<pre> |
|||
1 : -43 11 -29 -7 10 23 -50 50 18 |
|||
2 : 54 -40 22 17 13 -73 100 -32 |
|||
3 : -94 62 -5 -4 -86 173 -132 |
|||
4 : 156 -67 1 -82 259 -305 |
|||
5 : -223 68 -83 341 -564 |
|||
6 : 291 -151 424 -905 |
|||
7 : -442 575 -1329 |
|||
8 : 1017 -1904 |
|||
9 : -2921 |
|||
</pre> |
|||
=={{header|APL}}== |
|||
{{works with|Dyalog APL}}{{trans|J}} |
|||
<syntaxhighlight lang="apl"> list ← 90 47 58 29 22 32 55 5 55 73 |
|||
fd ← {⍺=0:⍵⋄(⍺-1)∇(1↓⍵)-(¯1↓⍵)} |
|||
1 fd list |
|||
¯43 11 ¯29 ¯7 10 23 ¯50 50 18 |
|||
2 fd list |
|||
54 ¯40 22 17 13 ¯73 100 ¯32</syntaxhighlight> |
|||
=={{header|AppleScript}}== |
|||
{{Trans|JavaScript}} |
|||
<syntaxhighlight lang="applescript">-- forwardDifference :: Num a => [a] -> [a] |
|||
on forwardDifference(xs) |
|||
zipWith(my subtract, xs, rest of xs) |
|||
end forwardDifference |
|||
-- nthForwardDifference :: Num a => Int -> [a] -> [a] |
|||
on nthForwardDifference(xs, i) |
|||
|index|(iterate(forwardDifference, xs), 1 + i) |
|||
end nthForwardDifference |
|||
-------------------------- TEST --------------------------- |
|||
on run |
|||
script show |
|||
on |λ|(xs, i) |
|||
((i - 1) as string) & " -> " & showList(xs) |
|||
end |λ| |
|||
end script |
|||
unlines(map(show, ¬ |
|||
take(10, ¬ |
|||
iterate(forwardDifference, ¬ |
|||
{90, 47, 58, 29, 22, 32, 55, 5, 55, 73})))) |
|||
end run |
|||
-------------------- GENERIC FUNCTIONS -------------------- |
|||
-- Just :: a -> Maybe a |
|||
on Just(x) |
|||
-- Constructor for an inhabited Maybe (option type) value. |
|||
-- Wrapper containing the result of a computation. |
|||
{type:"Maybe", Nothing:false, Just:x} |
|||
end Just |
|||
-- Nothing :: Maybe a |
|||
on Nothing() |
|||
-- Constructor for an empty Maybe (option type) value. |
|||
-- Empty wrapper returned where a computation is not possible. |
|||
{type:"Maybe", Nothing:true} |
|||
end Nothing |
|||
-- index (!!) :: [a] -> Int -> Maybe a |
|||
-- index (!!) :: Gen [a] -> Int -> Maybe a |
|||
-- index (!!) :: String -> Int -> Maybe Char |
|||
on |index|(xs, i) |
|||
if script is class of xs then |
|||
repeat with j from 1 to i |
|||
set v to |λ|() of xs |
|||
end repeat |
|||
if missing value is not v then |
|||
Just(v) |
|||
else |
|||
Nothing() |
|||
end if |
|||
else |
|||
if length of xs < i then |
|||
Nothing() |
|||
else |
|||
Just(item i of xs) |
|||
end if |
|||
end if |
|||
end |index| |
|||
-- intercalate :: String -> [String] -> String |
|||
on intercalate(delim, xs) |
|||
set {dlm, my text item delimiters} to ¬ |
|||
{my text item delimiters, delim} |
|||
set str to xs as text |
|||
set my text item delimiters to dlm |
|||
str |
|||
end intercalate |
|||
-- iterate :: (a -> a) -> a -> Gen [a] |
|||
on iterate(f, x) |
|||
script |
|||
property v : missing value |
|||
property g : mReturn(f)'s |λ| |
|||
on |λ|() |
|||
if missing value is v then |
|||
set v to x |
|||
else |
|||
set v to g(v) |
|||
end if |
|||
return v |
|||
end |λ| |
|||
end script |
|||
end iterate |
|||
-- length :: [a] -> Int |
|||
on |length|(xs) |
|||
set c to class of xs |
|||
if list is c or string is c then |
|||
length of xs |
|||
else |
|||
(2 ^ 29 - 1) -- (maxInt - simple proxy for non-finite) |
|||
end if |
|||
end |length| |
|||
-- map :: (a -> b) -> [a] -> [b] |
|||
on map(f, xs) |
|||
-- The list obtained by applying f |
|||
-- to each element of xs. |
|||
tell mReturn(f) |
|||
set lng to length of xs |
|||
set lst to {} |
|||
repeat with i from 1 to lng |
|||
set end of lst to |λ|(item i of xs, i, xs) |
|||
end repeat |
|||
return lst |
|||
end tell |
|||
end map |
|||
-- min :: Ord a => a -> a -> a |
|||
on min(x, y) |
|||
if y < x then |
|||
y |
|||
else |
|||
x |
|||
end if |
|||
end min |
|||
-- mReturn :: First-class m => (a -> b) -> m (a -> b) |
|||
on mReturn(f) |
|||
-- 2nd class handler function lifted into 1st class script wrapper. |
|||
if script is class of f then |
|||
f |
|||
else |
|||
script |
|||
property |λ| : f |
|||
end script |
|||
end if |
|||
end mReturn |
|||
-- showList :: [a] -> String |
|||
on showList(xs) |
|||
"[" & intercalate(", ", map(my str, xs)) & "]" |
|||
end showList |
|||
-- str :: a -> String |
|||
on str(x) |
|||
x as string |
|||
end str |
|||
-- subtract :: Num -> Num -> Num |
|||
on subtract(x, y) |
|||
y - x |
|||
end subtract |
|||
-- take :: Int -> [a] -> [a] |
|||
-- take :: Int -> String -> String |
|||
on take(n, xs) |
|||
set c to class of xs |
|||
if list is c then |
|||
if 0 < n then |
|||
items 1 thru min(n, length of xs) of xs |
|||
else |
|||
{} |
|||
end if |
|||
else if string is c then |
|||
if 0 < n then |
|||
text 1 thru min(n, length of xs) of xs |
|||
else |
|||
"" |
|||
end if |
|||
else if script is c then |
|||
set ys to {} |
|||
repeat with i from 1 to n |
|||
set v to |λ|() of xs |
|||
if missing value is v then |
|||
return ys |
|||
else |
|||
set end of ys to v |
|||
end if |
|||
end repeat |
|||
return ys |
|||
else |
|||
missing value |
|||
end if |
|||
end take |
|||
-- unlines :: [String] -> String |
|||
on unlines(xs) |
|||
-- A single string formed by the intercalation |
|||
-- of a list of strings with the newline character. |
|||
set {dlm, my text item delimiters} to ¬ |
|||
{my text item delimiters, linefeed} |
|||
set s to xs as text |
|||
set my text item delimiters to dlm |
|||
s |
|||
end unlines |
|||
-- zipWith :: (a -> b -> c) -> [a] -> [b] -> [c] |
|||
on zipWith(f, xs, ys) |
|||
set lng to min(|length|(xs), |length|(ys)) |
|||
if 1 > lng then return {} |
|||
set xs_ to take(lng, xs) -- Allow for non-finite |
|||
set ys_ to take(lng, ys) -- generators like cycle etc |
|||
set lst to {} |
|||
tell mReturn(f) |
|||
repeat with i from 1 to lng |
|||
set end of lst to |λ|(item i of xs_, item i of ys_) |
|||
end repeat |
|||
return lst |
|||
end tell |
|||
end zipWith</syntaxhighlight> |
|||
{{Out}} |
|||
<pre>0 -> [90, 47, 58, 29, 22, 32, 55, 5, 55, 73] |
|||
1 -> [-43, 11, -29, -7, 10, 23, -50, 50, 18] |
|||
2 -> [54, -40, 22, 17, 13, -73, 100, -32] |
|||
3 -> [-94, 62, -5, -4, -86, 173, -132] |
|||
4 -> [156, -67, 1, -82, 259, -305] |
|||
5 -> [-223, 68, -83, 341, -564] |
|||
6 -> [291, -151, 424, -905] |
|||
7 -> [-442, 575, -1329] |
|||
8 -> [1017, -1904] |
|||
9 -> [-2921]</pre> |
|||
=={{header|Arturo}}== |
|||
<syntaxhighlight lang="rebol">; element-wise subtraction of two blocks. e.g. |
|||
; vsub [1 2 3] [1 2 3] ; [0 0 0] |
|||
vsub: function [u v][ |
|||
map couple u v 'pair -> pair\0 - pair\1 |
|||
] |
|||
differences: function [block][ |
|||
order: attr "order" |
|||
if order = null -> order: 1 |
|||
loop 1..order 'n -> block: vsub block drop block |
|||
return block |
|||
] |
|||
print differences .order: 4 [90.5 47 58 29 22 32 55 5 55 73.5] |
|||
print differences [1 2 3 4 5 6 7]</syntaxhighlight> |
|||
{{out}} |
|||
<pre>156.5 -67 1 -82 259 -304.5 |
|||
-1 -1 -1 -1 -1 -1</pre> |
|||
=={{header|AutoHotkey}}== |
|||
contributed by Laszlo on the ahk [http://www.autohotkey.com/forum/post-276470.html#276470 forum] |
|||
<syntaxhighlight lang="autohotkey">MsgBox % diff("2,3,4,3",1) |
|||
MsgBox % diff("2,3,4,3",2) |
|||
MsgBox % diff("2,3,4,3",3) |
|||
MsgBox % diff("2,3,4,3",4) |
|||
diff(list,ord) { ; high order forward differences of a list |
|||
Loop %ord% { |
|||
L = |
|||
Loop Parse, list, `, %A_Space%%A_Tab% |
|||
If (A_Index=1) |
|||
p := A_LoopField |
|||
Else |
|||
L .= "," A_LoopField-p, p := A_LoopField |
|||
list := SubStr(L,2) |
|||
} |
|||
Return list |
|||
}</syntaxhighlight> |
|||
=={{header|AWK}}== |
|||
<syntaxhighlight lang="awk">#!/usr/bin/awk -f |
|||
BEGIN { |
|||
if (p<1) {p = 1}; |
|||
} |
|||
function diff(s, p) { |
|||
n = split(s, a, " "); |
|||
for (j = 1; j <= p; j++) { |
|||
for(i = 1; i <= n-j; i++) { |
|||
a[i] = a[i+1] - a[i]; |
|||
} |
|||
} |
|||
s = ""; |
|||
for (i = 1; i <= n-p; i++) s = s" "a[i]; |
|||
return s; |
|||
} |
|||
{ |
|||
print diff($0, p); |
|||
}</syntaxhighlight> |
|||
Using Pascal's triangle: |
|||
<syntaxhighlight lang="awk">#!/usr/bin/awk -f |
|||
OP - = (LISTREAL a,b)LISTREAL: ( |
|||
BEGIN { |
|||
[UPB a]REAL out; |
|||
if (p<1) {p = 1}; |
|||
FOR i TO UPB out DO out[i]:=a[i]-b[i] OD; |
|||
} |
|||
out |
|||
); |
|||
function diff(s, p) { |
|||
# pascal triangled with sign changes |
|||
FORMAT real fmt=$zzz-d.d$; |
|||
b[1] = (p%2) ? 1 : -1; |
|||
FORMAT repeat fmt = $n(UPB s-1)(f(real fmt)",")f(real fmt)$; |
|||
for (j=1; j < p; j++) { |
|||
FORMAT list fmt = $"("f(UPB s=1|real fmt|repeat fmt)")"$; |
|||
b[j+1] = -b[j]*(p-j)/j; |
|||
}; |
|||
n = split(s, a, " "); |
|||
s = ""; |
|||
for (j = 1; j <= n-p+1; j++) { |
|||
c = 0; |
|||
for(i = 1; i <= p; i++) { |
|||
c += b[i]*a[j+i-1]; |
|||
} |
|||
s = s" "c; |
|||
} |
|||
return s; |
|||
} |
|||
{ |
|||
FLEX [1:0] REAL s := (90, 47, 58, 29, 22, 32, 55, 5, 55, 73); |
|||
print diff($0, p); |
|||
}</syntaxhighlight> |
|||
printf((list fmt,s,$";"l$)); |
|||
TO UPB s-1 DO |
|||
{{out}} |
|||
s := s[2:] - s[:UPB s-1]; |
|||
<pre>$ echo '0 1 2 4 7 4 2 1 0' | ./diff.awk -v p=1 |
|||
printf((list fmt,s,$";"l$)) |
|||
1 1 2 3 -3 -2 -1 -1 |
|||
OD |
|||
$ echo '0 1 2 4 7 4 2 1 0' | ./diff.awk -v p=2 |
|||
) |
|||
0 1 1 -6 1 1 0 |
|||
Output: |
|||
$ echo '0 1 2 4 7 4 2 1 0' | ./diff.awk -v p=3 |
|||
( 90.0, 47.0, 58.0, 29.0, 22.0, 32.0, 55.0, 5.0, 55.0, 73.0); |
|||
1 0 -7 7 0 -1 |
|||
( -43.0, 11.0, -29.0, -7.0, 10.0, 23.0, -50.0, 50.0, 18.0); |
|||
$ echo '0 1 2 4 7 4 2 1 0' | ./diff.awk -v p=4 |
|||
-1 -7 14 -7 -1 |
|||
( -94.0, 62.0, -5.0, -4.0, -86.0, 173.0, -132.0); |
|||
$ echo '0 1 2 4 7 4 2 1 0' | ./diff.awk -v p=5 |
|||
-6 21 -21 6 |
|||
( -223.0, 68.0, -83.0, 341.0, -564.0); |
|||
$ echo '0 1 2 4 7 4 2 1 0' | ./diff.awk -v p=6 |
|||
( 291.0, -151.0, 424.0, -905.0); |
|||
27 -42 27 |
|||
( -442.0, 575.0,-1329.0); |
|||
$ echo '0 1 2 4 7 4 2 1 0' | ./diff.awk -v p=7 |
|||
( 1017.0,-1904.0); |
|||
-69 69 |
|||
(-2921.0); |
|||
$ echo '0 1 2 4 7 4 2 1 0' | ./diff.awk -v p=8 |
|||
138 |
|||
$ echo '0 1 2 4 7 4 2 1 0' | ./diff.awk -v p=9 |
|||
</pre> |
|||
=={{header|BBC BASIC}}== |
|||
{{works with|BBC BASIC for Windows}} |
|||
<syntaxhighlight lang="bbcbasic"> DIM A(9) |
|||
A() = 90.0, 47.0, 58.0, 29.0, 22.0, 32.0, 55.0, 5.0, 55.0, 73.0 |
|||
PRINT "Original array: " FNshowarray(A()) |
|||
PROCforward_difference(1, A(), B()) |
|||
PRINT "Forward diff 1: " FNshowarray(B()) |
|||
PROCforward_difference(2, A(), C()) |
|||
PRINT "Forward diff 2: " FNshowarray(C()) |
|||
PROCforward_difference(9, A(), D()) |
|||
PRINT "Forward diff 9: " FNshowarray(D()) |
|||
END |
|||
DEF PROCforward_difference(n%, a(), RETURN b()) |
|||
LOCAL c%, i%, j% |
|||
DIM b(DIM(a(),1) - n%) |
|||
FOR i% = 0 TO DIM(b(),1) |
|||
b(i%) = a(i% + n%) |
|||
c% = 1 |
|||
FOR j% = 1 TO n% |
|||
c% = -INT(c% * (n% - j% + 1) / j% + 0.5) |
|||
b(i%) += c% * a(i% + n% - j%) |
|||
NEXT |
|||
NEXT |
|||
ENDPROC |
|||
DEF FNshowarray(a()) |
|||
LOCAL i%, a$ |
|||
FOR i% = 0 TO DIM(a(),1) |
|||
a$ += STR$(a(i%)) + ", " |
|||
NEXT |
|||
= LEFT$(LEFT$(a$))</syntaxhighlight> |
|||
{{out}} |
|||
<pre> |
|||
Original array: 90, 47, 58, 29, 22, 32, 55, 5, 55, 73 |
|||
Forward diff 1: -43, 11, -29, -7, 10, 23, -50, 50, 18 |
|||
Forward diff 2: 54, -40, 22, 17, 13, -73, 100, -32 |
|||
Forward diff 9: -2921 |
|||
</pre> |
|||
=={{header|BQN}}== |
|||
Left argument is the order, right argument is the array. |
|||
<syntaxhighlight lang="bqn">FDiff ← {{-˜´˘2↕𝕩}⍟𝕨 𝕩} |
|||
•Show 1 FDiff 90‿47‿58‿29‿22‿32‿55‿5‿55‿73 |
|||
•Show 2 FDiff 90‿47‿58‿29‿22‿32‿55‿5‿55‿73</syntaxhighlight> |
|||
=={{header|C}}== |
|||
<syntaxhighlight lang="c">#include <stdlib.h> |
|||
#include <string.h> |
|||
#include <stdio.h> |
|||
double* fwd_diff(double* x, unsigned int len, unsigned int order) |
|||
{ |
|||
unsigned int i, j; |
|||
double* y; |
|||
/* handle two special cases */ |
|||
if (order >= len) return 0; |
|||
y = malloc(sizeof(double) * len); |
|||
if (!order) { |
|||
memcpy(y, x, sizeof(double) * len); |
|||
return y; |
|||
} |
|||
/* first order diff goes from x->y, later ones go from y->y */ |
|||
for (j = 0; j < order; j++, x = y) |
|||
for (i = 0, len--; i < len; i++) |
|||
y[i] = x[i + 1] - x[i]; |
|||
y = realloc(y, sizeof(double) * len); |
|||
return y; |
|||
} |
|||
int main(void) |
|||
{ |
|||
double *y, x[] = {90, 47, 58, 29, 22, 32, 55, 5, 55, 73}; |
|||
int i, len = sizeof(x) / sizeof(x[0]); |
|||
y = fwd_diff(x, len, 1); |
|||
for (i = 0; i < len - 1; i++) |
|||
printf("%g ", y[i]); |
|||
putchar('\n'); |
|||
return 0; |
|||
}</syntaxhighlight> |
|||
Use method with Pascal triangle, binomial coefficients are pre-computed |
|||
<syntaxhighlight lang="c">#include <stdio.h> |
|||
int* binomCoeff(int n) { |
|||
int *b = calloc(n+1,sizeof(int)); |
|||
int j; |
|||
b[0] = n%2 ? -1 : 1; |
|||
for (j=1 ; j<=n; j++) |
|||
b[j] = -b[j-1]*(n+1-j)/j; |
|||
return(b); |
|||
}; |
|||
main () { |
|||
double array[] = { 90, 47, 58, 29, 22, 32, 55, 5, 55, 73 }; |
|||
size_t lenArray = sizeof(array)/sizeof(array[0]); |
|||
int p = 4; // order |
|||
int *b = binomCoeff(p); // pre-compute binomial coefficients for order p |
|||
int j, k; |
|||
// compute p-th difference |
|||
for (k=0 ; k < lenArray; k++) |
|||
for (array[k] *= b[0], j=1 ; j<=p; j++) |
|||
array[k] += b[j] * array[k+j]; |
|||
free(b); |
|||
// resulting series is shorter by p elements |
|||
lenArray -= p; |
|||
for (k=0 ; k < lenArray; k++) printf("%f ",array[k]); |
|||
printf("\n"); |
|||
} |
|||
</syntaxhighlight> |
|||
=={{header|C sharp|C#}}== |
|||
<syntaxhighlight lang="csharp">using System; |
|||
using System.Collections.Generic; |
|||
using System.Linq; |
|||
class Program |
|||
{ |
|||
static IEnumerable<int> ForwardDifference(IEnumerable<int> sequence, uint order = 1u) |
|||
{ |
|||
switch (order) |
|||
{ |
|||
case 0u: |
|||
return sequence; |
|||
case 1u: |
|||
return sequence.Skip(1).Zip(sequence, (next, current) => next - current); |
|||
default: |
|||
return ForwardDifference(ForwardDifference(sequence), order - 1u); |
|||
} |
|||
} |
|||
static void Main() |
|||
{ |
|||
IEnumerable<int> sequence = new[] { 90, 47, 58, 29, 22, 32, 55, 5, 55, 73 }; |
|||
do |
|||
{ |
|||
Console.WriteLine(string.Join(", ", sequence)); |
|||
} while ((sequence = ForwardDifference(sequence)).Any()); |
|||
} |
|||
}</syntaxhighlight> |
|||
{{out}} |
|||
<pre>90, 47, 58, 29, 22, 32, 55, 5, 55, 73 |
|||
-43, 11, -29, -7, 10, 23, -50, 50, 18 |
|||
54, -40, 22, 17, 13, -73, 100, -32 |
|||
-94, 62, -5, -4, -86, 173, -132 |
|||
156, -67, 1, -82, 259, -305 |
|||
-223, 68, -83, 341, -564 |
|||
291, -151, 424, -905 |
|||
-442, 575, -1329 |
|||
1017, -1904 |
|||
-2921</pre> |
|||
=={{header|C++}}== |
=={{header|C++}}== |
||
{{works with|g++|4.1.2 20061115 (prerelease) (SUSE Linux)}} |
{{works with|g++|4.1.2 20061115 (prerelease) (SUSE Linux)}} |
||
This code uses a separate function to do a first-order forward difference, which is then called several times for calculating n-th order forward difference. No error checking is implemented. |
|||
This code uses a separate function to do a first-order forward difference, |
|||
#include <vector> |
|||
which is then called several times for calculating n-th order forward difference. |
|||
#include <iterator> |
|||
No error checking is implemented. |
|||
#include <algorithm> |
|||
<syntaxhighlight lang="cpp">#include <vector> |
|||
#include <iterator> |
|||
// calculate first order forward difference |
|||
#include <algorithm> |
|||
// requires: |
|||
// * InputIterator is an input iterator |
|||
// * OutputIterator is an output iterator |
|||
// * The value type of InputIterator is copy-constructible and assignable |
|||
// * The value type of InputIterator supports operator - |
|||
// * The result type of operator- is assignable to the value_type of OutputIterator |
|||
// returns: The iterator following the output sequence |
|||
template<typename InputIterator, typename OutputIterator> |
|||
OutputIterator forward_difference(InputIterator first, InputIterator last, |
|||
OutputIterator dest) |
|||
{ |
|||
// special case: for empty sequence, do nothing |
|||
if (first == last) |
|||
return dest; |
|||
typedef typename std::iterator_traits<InputIterator>::value_type value_type; |
|||
value_type temp = *first++; |
|||
while (first != last) |
|||
{ |
|||
value_type temp2 = *first++; |
|||
*dest++ = temp2 - temp; |
|||
temp = temp2; |
|||
} |
|||
return dest; |
|||
} |
|||
// calculate n-th order forward difference. |
|||
// requires: |
|||
// * InputIterator is an input iterator |
|||
// * OutputIterator is an output iterator |
|||
// * The value type of InputIterator is copy-constructible and assignable |
|||
// * The value type of InputIterator supports operator - |
|||
// * The result type of operator- is assignable to the value_type of InputIterator |
|||
// * The result type of operator- is assignable to the value_type of OutputIterator |
|||
// * order >= 0 |
|||
// returns: The iterator following the output sequence |
|||
template<typename InputIterator, typename OutputIterator> |
|||
OutputIterator nth_forward_difference(int order, |
|||
InputIterator first, InputIterator last, |
|||
OutputIterator dest) |
|||
{ |
|||
// special case: If order == 0, just copy input to output |
|||
if (order == 0) |
|||
return std::copy(first, last, dest); |
|||
// second special case: If order == 1, just forward to the first-order function |
|||
if (order == 1) |
|||
return forward_difference(first, last, dest); |
|||
// intermediate results are stored in a vector |
|||
typedef typename std::iterator_traits<InputIterator>::value_type value_type; |
|||
std::vector<value_type> temp_storage; |
|||
// fill the vector with the result of the first order forward difference |
|||
forward_difference(first, last, std::back_inserter(temp_storage)); |
|||
// the next n-2 iterations work directly on the vector |
|||
typename std::vector<value_type>::iterator begin = temp_storage.begin(), |
|||
end = temp_storage.end(); |
|||
for (int i = 1; i < order-1; ++i) |
|||
end = forward_difference(begin, end, begin); |
|||
// the final iteration writes directly to the output iterator |
|||
return forward_difference(begin, end, dest); |
|||
} |
|||
// example usage code |
|||
#include <iostream> |
|||
int main() |
|||
{ |
|||
double array[10] = { 90.0, 47.0, 58.0, 29.0, 22.0, 32.0, 55.0, 5.0, 55.0, 73.0 }; |
|||
// this stores the results in the vector dest |
|||
std::vector<double> dest; |
|||
nth_forward_difference(1, array, array+10, std::back_inserter(dest)); |
|||
// outut dest |
|||
std::copy(dest.begin(), dest.end(), std::ostream_iterator<double>(std::cout, " ")); |
|||
std::cout << std::endl; |
|||
// however, the results can also be output as they are calculated |
|||
nth_forward_difference(2, array, array+10, std::ostream_iterator<double>(std::cout, " ")); |
|||
std::cout << std::endl; |
|||
nth_forward_difference(9, array, array+10, std::ostream_iterator<double>(std::cout, " ")); |
|||
std::cout << std::endl; |
|||
nth_forward_difference(10, array, array+10, std::ostream_iterator<double>(std::cout, " ")); |
|||
std::cout << std::endl; |
|||
nth_forward_difference(0, array, array+10, std::ostream_iterator<double>(std::cout, " ")); |
|||
std::cout << std::endl; |
|||
// finally, the results can also be written into the original array |
|||
// (which of course destroys the original content) |
|||
double* end = nth_forward_difference(3, array, array+10, array); |
|||
for (double* p = array; p < end; ++p) |
|||
std::cout << *p << " "; |
|||
std::cout << std::endl; |
|||
} |
|||
// calculate first order forward difference |
|||
This gives the following output: |
|||
// requires: |
|||
// * InputIterator is an input iterator |
|||
// * OutputIterator is an output iterator |
|||
// * The value type of InputIterator is copy-constructible and assignable |
|||
// * The value type of InputIterator supports operator - |
|||
// * The result type of operator- is assignable to the value_type of OutputIterator |
|||
// returns: The iterator following the output sequence |
|||
template<typename InputIterator, typename OutputIterator> |
|||
OutputIterator forward_difference(InputIterator first, InputIterator last, |
|||
OutputIterator dest) |
|||
{ |
|||
// special case: for empty sequence, do nothing |
|||
if (first == last) |
|||
return dest; |
|||
typedef typename std::iterator_traits<InputIterator>::value_type value_type; |
|||
value_type temp = *first++; |
|||
while (first != last) |
|||
{ |
|||
value_type temp2 = *first++; |
|||
*dest++ = temp2 - temp; |
|||
temp = temp2; |
|||
} |
|||
return dest; |
|||
} |
|||
// calculate n-th order forward difference. |
|||
// requires: |
|||
// * InputIterator is an input iterator |
|||
// * OutputIterator is an output iterator |
|||
// * The value type of InputIterator is copy-constructible and assignable |
|||
// * The value type of InputIterator supports operator - |
|||
// * The result type of operator- is assignable to the value_type of InputIterator |
|||
// * The result type of operator- is assignable to the value_type of OutputIterator |
|||
// * order >= 0 |
|||
// returns: The iterator following the output sequence |
|||
template<typename InputIterator, typename OutputIterator> |
|||
OutputIterator nth_forward_difference(int order, |
|||
InputIterator first, InputIterator last, |
|||
OutputIterator dest) |
|||
{ |
|||
// special case: If order == 0, just copy input to output |
|||
if (order == 0) |
|||
return std::copy(first, last, dest); |
|||
// second special case: If order == 1, just forward to the first-order function |
|||
if (order == 1) |
|||
return forward_difference(first, last, dest); |
|||
// intermediate results are stored in a vector |
|||
typedef typename std::iterator_traits<InputIterator>::value_type value_type; |
|||
std::vector<value_type> temp_storage; |
|||
// fill the vector with the result of the first order forward difference |
|||
forward_difference(first, last, std::back_inserter(temp_storage)); |
|||
// the next n-2 iterations work directly on the vector |
|||
typename std::vector<value_type>::iterator begin = temp_storage.begin(), |
|||
end = temp_storage.end(); |
|||
for (int i = 1; i < order-1; ++i) |
|||
end = forward_difference(begin, end, begin); |
|||
// the final iteration writes directly to the output iterator |
|||
return forward_difference(begin, end, dest); |
|||
} |
|||
// example usage code |
|||
#include <iostream> |
|||
int main() |
|||
{ |
|||
double array[10] = { 90.0, 47.0, 58.0, 29.0, 22.0, 32.0, 55.0, 5.0, 55.0, 73.0 }; |
|||
// this stores the results in the vector dest |
|||
std::vector<double> dest; |
|||
nth_forward_difference(1, array, array+10, std::back_inserter(dest)); |
|||
// output dest |
|||
std::copy(dest.begin(), dest.end(), std::ostream_iterator<double>(std::cout, " ")); |
|||
std::cout << std::endl; |
|||
// however, the results can also be output as they are calculated |
|||
nth_forward_difference(2, array, array+10, std::ostream_iterator<double>(std::cout, " ")); |
|||
std::cout << std::endl; |
|||
nth_forward_difference(9, array, array+10, std::ostream_iterator<double>(std::cout, " ")); |
|||
std::cout << std::endl; |
|||
nth_forward_difference(10, array, array+10, std::ostream_iterator<double>(std::cout, " ")); |
|||
std::cout << std::endl; |
|||
nth_forward_difference(0, array, array+10, std::ostream_iterator<double>(std::cout, " ")); |
|||
std::cout << std::endl; |
|||
// finally, the results can also be written into the original array |
|||
// (which of course destroys the original content) |
|||
double* end = nth_forward_difference(3, array, array+10, array); |
|||
for (double* p = array; p < end; ++p) |
|||
std::cout << *p << " "; |
|||
std::cout << std::endl; |
|||
return 0; |
|||
}</syntaxhighlight> |
|||
{{out}} |
|||
<pre> |
|||
-43 11 -29 -7 10 23 -50 50 18 |
-43 11 -29 -7 10 23 -50 50 18 |
||
54 -40 22 17 13 -73 100 -32 |
54 -40 22 17 13 -73 100 -32 |
||
Line 216: | Line 877: | ||
90 47 58 29 22 32 55 5 55 73 |
90 47 58 29 22 32 55 5 55 73 |
||
-94 62 -5 -4 -86 173 -132 |
-94 62 -5 -4 -86 173 -132 |
||
</pre> |
|||
Note the empty line indicating the empty sequence for order 10. |
Note the empty line indicating the empty sequence for order 10. |
||
===Using Standard Template Library=== |
|||
<syntaxhighlight lang="cpp"> |
|||
#include <iostream> |
|||
#include <numeric> |
|||
// Calculate the Forward Difference of a series if integers showing each order |
|||
// |
|||
// Nigel Galloway. August 20th., 2012 |
|||
// |
|||
int main() { |
|||
int x[] = {NULL,-43,11,-29,-7,10,23,-50,50,18}; |
|||
const int N = sizeof(x) / sizeof(int) - 1; |
|||
for (int ord = 0; ord < N - 1; ord++) { |
|||
std::adjacent_difference(x+1, x + N + 1 - ord, x); |
|||
for (int i = 1; i < N - ord; i++) std::cout << x[i] << ' '; |
|||
std::cout << std::endl; |
|||
} |
|||
return 0; |
|||
} |
|||
</syntaxhighlight> |
|||
{{out}} |
|||
<pre> |
|||
54 -40 22 17 13 -73 100 -32 |
|||
-94 62 -5 -4 -86 173 -132 |
|||
156 -67 1 -82 259 -305 |
|||
-223 68 -83 341 -564 |
|||
291 -151 424 -905 |
|||
-442 575 -1329 |
|||
1017 -1904 |
|||
-2921 |
|||
</pre> |
|||
Usually one will not want the intermediate results, |
|||
in which case the following is sufficient: |
|||
<syntaxhighlight lang="cpp"> |
|||
#include <iostream> |
|||
#include <numeric> |
|||
// Calculate the Forward Difference of a series if integers |
|||
// |
|||
// Nigel Galloway. August 20th., 2012 |
|||
// |
|||
int main() { |
|||
int x[] = {NULL,-43,11,-29,-7,10,23,-50,50,18}; |
|||
const int N = sizeof(x) / sizeof(int) - 1; |
|||
for (int ord = 0; ord < N - 1; ord++) std::adjacent_difference(x+1, x + N + 1 - ord, x); |
|||
std::cout << x[1] << std::endl; |
|||
return 0; |
|||
} |
|||
</syntaxhighlight> |
|||
{{out}} |
|||
<pre> |
|||
-2921 |
|||
</pre> |
|||
===Using Pascal's Triangle=== |
|||
<syntaxhighlight lang="cpp"> |
|||
#include <iostream> |
|||
#include <algorithm> |
|||
// Calculate the Forward Difference of a series if integers using Pascal's Triangle |
|||
// For this example the 9th line of Pascal's Triangle is stored in P. |
|||
// |
|||
// Nigel Galloway. August 20th., 2012 |
|||
// |
|||
int main() { |
|||
const int P[] = {1,-8,28,-56,70,-56,28,-8,1}; |
|||
int x[] = {-43,11,-29,-7,10,23,-50,50,18}; |
|||
std::transform(x, x + sizeof(x) / sizeof(int), P, x, std::multiplies<int>()); |
|||
std::cout << std::accumulate(x, x + sizeof(x) / sizeof(int), 0) << std::endl; |
|||
return 0; |
|||
} |
|||
</syntaxhighlight> |
|||
{{out}} |
|||
<pre> |
|||
-2921 |
|||
</pre> |
|||
=={{header|Clojure}}== |
|||
<syntaxhighlight lang="lisp">(defn fwd-diff [nums order] |
|||
(nth (iterate #(map - (next %) %) nums) order))</syntaxhighlight> |
|||
=={{header|CoffeeScript}}== |
|||
<syntaxhighlight lang="coffeescript"> |
|||
forward_difference = (arr, n) -> |
|||
# Find the n-th order forward difference for arr using |
|||
# a straightforward recursive algorithm. |
|||
# Assume arr is integers and n <= arr.length. |
|||
return arr if n == 0 |
|||
arr = forward_difference(arr, n-1) |
|||
(arr[i+1] - arr[i] for i in [0...arr.length - 1]) |
|||
arr = [-1, 0, 1, 8, 27, 64, 125, 216] |
|||
for n in [0..arr.length] |
|||
console.log n, forward_difference arr, n |
|||
</syntaxhighlight> |
|||
{{out}} |
|||
<pre>> coffee forward_difference.coffee |
|||
0 [ -1, 0, 1, 8, 27, 64, 125, 216 ] |
|||
1 [ 1, 1, 7, 19, 37, 61, 91 ] |
|||
2 [ 0, 6, 12, 18, 24, 30 ] |
|||
3 [ 6, 6, 6, 6, 6 ] |
|||
4 [ 0, 0, 0, 0 ] |
|||
5 [ 0, 0, 0 ] |
|||
6 [ 0, 0 ] |
|||
7 [ 0 ] |
|||
8 []</pre> |
|||
=={{header|Common Lisp}}== |
|||
<syntaxhighlight lang="lisp">(defun forward-difference (list) |
|||
(mapcar #'- (rest list) list)) |
|||
(defun nth-forward-difference (list n) |
|||
(setf list (copy-list list)) |
|||
(loop repeat n do (map-into list #'- (rest list) list)) |
|||
(subseq list 0 (- (length list) n)))</syntaxhighlight> |
|||
=={{header|D}}== |
=={{header|D}}== |
||
===Basic Version=== |
|||
<pre>module fdiff ; |
|||
<syntaxhighlight lang="d">T[] forwardDifference(T)(in T[] data, in int level) pure nothrow |
|||
import std.stdio ; |
|||
in { |
|||
assert(level >= 0 && level < data.length); |
|||
} body { |
|||
auto result = data.dup; |
|||
foreach (immutable i; 0 .. level) |
|||
foreach (immutable j, ref el; result[0 .. $ - i - 1]) |
|||
el = result[j + 1] - el; |
|||
result.length -= level; |
|||
return result; |
|||
} |
|||
void main() { |
|||
import std.stdio; |
|||
const data = [90.5, 47, 58, 29, 22, 32, 55, 5, 55, 73.5]; |
|||
foreach (immutable level; 0 .. data.length) |
|||
forwardDifference(data, level).writeln; |
|||
}</syntaxhighlight> |
|||
{{out}} |
|||
<pre>[90.5, 47, 58, 29, 22, 32, 55, 5, 55, 73.5] |
|||
[-43.5, 11, -29, -7, 10, 23, -50, 50, 18.5] |
|||
[54.5, -40, 22, 17, 13, -73, 100, -31.5] |
|||
[-94.5, 62, -5, -4, -86, 173, -131.5] |
|||
[156.5, -67, 1, -82, 259, -304.5] |
|||
[-223.5, 68, -83, 341, -563.5] |
|||
[291.5, -151, 424, -904.5] |
|||
[-442.5, 575, -1328.5] |
|||
[1017.5, -1903.5] |
|||
[-2921]</pre> |
|||
===Alternative Version=== |
|||
Same output. |
|||
<syntaxhighlight lang="d">import std.stdio, std.algorithm, std.range, std.array; |
|||
auto forwardDifference(Range)(Range d, in int level) pure { |
|||
foreach (immutable _; 0 .. level) |
|||
T[] s ; |
|||
d = d.zip(d.dropOne).map!(a => a[0] - a[1]).array; |
|||
if(level < 0 || level >= a.length) |
|||
return d; |
|||
s = a.dup ; |
|||
for(int i = 0 ; i < level ;i++) |
|||
for(int j = 0 ; j < s.length - i - 1 ; j++) |
|||
s[j] = s[j+1] - s[j] ; |
|||
s.length = s.length - level ; |
|||
return s ; |
|||
} |
} |
||
void main() { |
void main() { |
||
const data = [90.5, 47, 58, 29, 22, 32, 55, 5, 55, 73.5]; |
|||
foreach (immutable level; 0 .. data.length) |
|||
forwardDifference(data, level).writeln; |
|||
}</ |
}</syntaxhighlight> |
||
Sampe output: |
|||
<pre>D:\00MY\dmd>fdiff |
|||
[90.5 47 58 29 22 32 55 5 55 73.5] |
|||
[-43.5 11 -29 -7 10 23 -50 50 18.5] |
|||
[54.5 -40 22 17 13 -73 100 -31.5] |
|||
[-94.5 62 -5 -4 -86 173 -131.5] |
|||
[156.5 -67 1 -82 259 -304.5] |
|||
[-223.5 68 -83 341 -563.5] |
|||
[291.5 -151 424 -904.5] |
|||
[-442.5 575 -1328.5] |
|||
[1017.5 -1903.5] |
|||
[-2921] |
|||
[]</pre> |
|||
===Using Vector Operations=== |
|||
=={{header|Common Lisp}}== |
|||
forwardDifference mutates the array in-place (same output): |
|||
<syntaxhighlight lang="d">import std.stdio; |
|||
T[] forwardDifference(T)(T[] s, in int n) pure nothrow @nogc { |
|||
(defun forward-difference (list) |
|||
foreach (immutable i; 0 .. n) |
|||
(mapcar #'- (rest list) list)) |
|||
s[0 .. $ - i - 1] = s[1 .. $ - i] - s[0 .. $ - i - 1]; |
|||
return s[0 .. $ - n]; |
|||
(defun nth-forward-difference (list n) |
|||
} |
|||
(setf list (copy-list list)) |
|||
void main() { |
|||
(loop repeat n do (map-into list #'- (rest list) list)) |
|||
immutable A = [90.5, 47, 58, 29, 22, 32, 55, 5, 55, 73.5]; |
|||
(subseq list 0 (- (length list) n))) |
|||
foreach (immutable level; 0 .. A.length) |
|||
forwardDifference(A.dup, level).writeln; |
|||
}</syntaxhighlight> |
|||
===Short Functional Version=== |
|||
Same output: |
|||
<syntaxhighlight lang="d">void main() { |
|||
import std.stdio, std.range; |
|||
auto D = [90.5, 47, 58, 29, 22, 32, 55, 5, 55, 73.5]; |
|||
writefln("%(%s\n%)", |
|||
recurrence!q{ (a[n - 1][0 .. $ - 1] = |
|||
a[n - 1][1 .. $] - |
|||
a[n - 1][0 .. $ - 1])[0 .. $] }(D) |
|||
.take(D.length)); |
|||
}</syntaxhighlight> |
|||
=={{header|Dart}}== |
|||
<syntaxhighlight lang="dart">List forwardDifference(List _list) { |
|||
for (int i = _list.length - 1; i > 0; i--) { |
|||
_list[i] = _list[i] - _list[i - 1]; |
|||
} |
|||
_list.removeRange(0, 1); |
|||
return _list; |
|||
} |
|||
void mainAlgorithms() { |
|||
List _intList = [90, 47, 58, 29, 22, 32, 55, 5, 55, 73]; |
|||
for (int i = _intList.length - 1; i >= 0; i--) { |
|||
List _list = forwardDifference(_intList); |
|||
print(_list); |
|||
} |
|||
}</syntaxhighlight> |
|||
{{out}} |
|||
<pre> |
|||
Restarted application in 1,143ms. |
|||
flutter: [-43, 11, -29, -7, 10, 23, -50, 50, 18] |
|||
flutter: [54, -40, 22, 17, 13, -73, 100, -32] |
|||
flutter: [-94, 62, -5, -4, -86, 173, -132] |
|||
flutter: [156, -67, 1, -82, 259, -305] |
|||
flutter: [-223, 68, -83, 341, -564] |
|||
flutter: [291, -151, 424, -905] |
|||
flutter: [-442, 575, -1329] |
|||
flutter: [1017, -1904] |
|||
flutter: [-2921] |
|||
flutter: [] |
|||
</pre> |
|||
=={{header|Delphi}}== |
|||
See [https://rosettacode.org/wiki/Forward_difference#Pascal Pascal]. |
|||
=={{header|E}}== |
=={{header|E}}== |
||
<syntaxhighlight lang="e">pragma.enable("accumulator") |
|||
/** Single step. */ |
|||
def forwardDifference(seq :List) { |
|||
return accum [] for i in 0..(seq.size() - 2) { |
|||
_.with(seq[i + 1] - seq[i]) |
|||
} |
|||
} |
|||
/** Iterative implementation of the goal. */ |
|||
def nthForwardDifference1(var seq :List, n :(int >= 0)) { |
|||
for _ in 1..n { seq := forwardDifference(seq) } |
|||
return seq |
|||
} |
|||
/** Imperative implementation of the goal. */ |
|||
def nthForwardDifference2(seq :List, n :(int >= 0)) { |
|||
def buf := seq.diverge() |
|||
def finalSize := seq.size() - n |
|||
for lim in (finalSize..!seq.size()).descending() { |
|||
for i in 0..!lim { |
|||
buf[i] := buf[i + 1] - buf[i] |
|||
} |
|||
} |
|||
return buf.run(0, finalSize) |
|||
} |
|||
? def sampleData := [90, 47, 58, 29, 22, 32, 55, 5, 55, 73] |
|||
> for n in 0..10 { |
|||
> def r1 := nthForwardDifference1(sampleData, n) |
|||
> require(r1 == nthForwardDifference2(sampleData, n)) |
|||
> println(r1) |
|||
> }</syntaxhighlight> |
|||
=={{header|EasyLang}}== |
|||
<syntaxhighlight lang=text> |
|||
func[] fwddiff s[] n . |
|||
for i to n |
|||
for j = 1 to len s[] - 1 |
|||
s[j] = s[j + 1] - s[j] |
|||
. |
|||
len s[] -1 |
|||
. |
|||
return s[] |
|||
. |
|||
s[] = [ 90 47 58 29 22 32 55 5 55 73 ] |
|||
print fwddiff s[] 1 |
|||
print fwddiff s[] 2 |
|||
print fwddiff s[] 9 |
|||
</syntaxhighlight> |
|||
{{out}} |
|||
<pre> |
|||
[ -43 11 -29 -7 10 23 -50 50 18 ] |
|||
[ 54 -40 22 17 13 -73 100 -32 ] |
|||
[ -2921 ] |
|||
</pre> |
|||
=={{header|EchoLisp}}== |
|||
Using the built-in function '''iterate''' which, given a function f and n, returns the function f°f°f....°f . |
|||
<syntaxhighlight lang="lisp"> |
|||
(define (Δ-1 list) |
|||
(for/list ([x (cdr list)] [y list]) (- x y))) |
|||
(define (Δ-n n) (iterate Δ-1 n)) |
|||
((Δ-n 9) '(90 47 58 29 22 32 55 5 55 73)) |
|||
→ (-2921) |
|||
</syntaxhighlight> |
|||
=={{header|Elixir}}== |
|||
<syntaxhighlight lang="elixir">defmodule Diff do |
|||
def forward(list,i\\1) do |
|||
forward(list,[],i) |
|||
end |
|||
def forward([_],diffs,1), do: IO.inspect diffs |
|||
def forward([_],diffs,i), do: forward(diffs,[],i-1) |
|||
def forward([val1,val2|vals],diffs,i) do |
|||
forward([val2|vals],diffs++[val2-val1],i) |
|||
end |
|||
end |
|||
Enum.each(1..9, fn i -> |
|||
Diff.forward([90, 47, 58, 29, 22, 32, 55, 5, 55, 73],i) |
|||
end)</syntaxhighlight> |
|||
{{out}} |
|||
<pre> |
|||
[-43, 11, -29, -7, 10, 23, -50, 50, 18] |
|||
[54, -40, 22, 17, 13, -73, 100, -32] |
|||
[-94, 62, -5, -4, -86, 173, -132] |
|||
[156, -67, 1, -82, 259, -305] |
|||
[-223, 68, -83, 341, -564] |
|||
[291, -151, 424, -905] |
|||
[-442, 575, -1329] |
|||
[1017, -1904] |
|||
[-2921] |
|||
</pre> |
|||
=={{header|Erlang}}== |
|||
<syntaxhighlight lang="erlang">-module(forward_difference). |
|||
-export([difference/1, difference/2]). |
|||
-export([task/0]). |
|||
-define(TEST_DATA,[90, 47, 58, 29, 22, 32, 55, 5, 55, 73]). |
|||
difference([X|Xs]) -> |
|||
{Result,_} = lists:mapfoldl(fun (N_2,N_1) -> {N_2 - N_1, N_2} end, X, Xs), |
|||
Result. |
|||
difference([],_) -> []; |
|||
difference(List,0) -> List; |
|||
difference(List,Order) -> difference(difference(List),Order-1). |
|||
task() -> |
|||
io:format("Initial: ~p~n",[?TEST_DATA]), |
|||
[io:format("~3b: ~p~n",[N,difference(?TEST_DATA,N)]) || N <- lists:seq(0,length(?TEST_DATA))], |
|||
ok.</syntaxhighlight> |
|||
{{out}} |
|||
<pre>80> forward_difference:task(). |
|||
Initial: [90,47,58,29,22,32,55,5,55,73] |
|||
0: [90,47,58,29,22,32,55,5,55,73] |
|||
1: [-43,11,-29,-7,10,23,-50,50,18] |
|||
2: [54,-40,22,17,13,-73,100,-32] |
|||
3: [-94,62,-5,-4,-86,173,-132] |
|||
4: [156,-67,1,-82,259,-305] |
|||
5: [-223,68,-83,341,-564] |
|||
6: [291,-151,424,-905] |
|||
7: [-442,575,-1329] |
|||
8: [1017,-1904] |
|||
9: [-2921] |
|||
10: [] |
|||
ok |
|||
</pre> |
|||
=={{header|F_Sharp|F#}}== |
|||
Straightforward recursive solution |
|||
<syntaxhighlight lang="fsharp">let rec ForwardDifference input n = |
|||
match n with |
|||
| _ when input = [] || n < 0 -> [] // If there's no more input, just return an empty list |
|||
| 0 -> input // If n is zero, we're done - return the input |
|||
| _ -> ForwardDifference // otherwise, recursively difference.. |
|||
(input.Tail // All but the first element |
|||
|> Seq.zip input // tupled with itself |
|||
|> Seq.map (fun (a, b) -> b-a) // Subtract the i'th element from the (i+1)'th |
|||
|> Seq.toList) (n-1) // Make into a list and do an n-1 difference on it</syntaxhighlight> |
|||
=={{header|Factor}}== |
|||
<syntaxhighlight lang="factor">USING: kernel math math.vectors sequences ; |
|||
IN: rosetacode |
|||
: 1-order ( seq -- seq' ) |
|||
[ rest-slice ] keep v- ; |
|||
: n-order ( seq n -- seq' ) |
|||
dup 0 <= |
|||
[ drop ] [ [ 1-order ] times ] if ; |
|||
</syntaxhighlight> |
|||
( scratchpad ) { 90.5 47 58 29 22 32 55 5 55 73.5 } 4 n-order . |
|||
{ 156.5 -67 1 -82 259 -304.5 } |
|||
=={{header|Forth}}== |
|||
<syntaxhighlight lang="forth">: forward-difference |
|||
dup 0 |
|||
?do |
|||
swap rot over i 1+ - 0 |
|||
?do dup i cells + dup cell+ @ over @ - swap ! loop |
|||
swap rot |
|||
loop - |
|||
; |
|||
create a |
|||
90 , 47 , 58 , 29 , 22 , 32 , 55 , 5 , 55 , 73 , |
|||
: test a 10 9 forward-difference bounds ?do i ? loop ; |
|||
test</syntaxhighlight> |
|||
=={{header|Fortran}}== |
|||
{{works with|Fortran|90 and later}} |
|||
<syntaxhighlight lang="fortran">MODULE DIFFERENCE |
|||
IMPLICIT NONE |
|||
CONTAINS |
|||
SUBROUTINE Fdiff(a, n) |
|||
/** Iterative implementation of the goal. */ |
|||
INTEGER, INTENT(IN) :: a(:), n |
|||
def nthForwardDifference1(var seq :List, n :(int >= 0)) { |
|||
INTEGER :: b(SIZE(a)) |
|||
for _ in 1..n { seq := forwardDifference(seq) } |
|||
INTEGER :: i, j, arraysize |
|||
return seq |
|||
} |
|||
b = a |
|||
arraysize = SIZE(b) |
|||
DO i = arraysize-1, arraysize-n, -1 |
|||
DO j = 1, i |
|||
b(j) = b(j+1) - b(j) |
|||
END DO |
|||
END DO |
|||
WRITE (*,*) b(1:arraysize-n) |
|||
END SUBROUTINE Fdiff |
|||
END MODULE DIFFERENCE</syntaxhighlight> |
|||
<syntaxhighlight lang="fortran">PROGRAM TEST |
|||
/** Imperative implementation of the goal. */ |
|||
def nthForwardDifference2(seq :List, n :(int >= 0)) { |
|||
def buf := seq.diverge() |
|||
def finalSize := seq.size() - n |
|||
for lim in (finalSize..!seq.size()).descending() { |
|||
for i in 0..!lim { |
|||
buf[i] := buf[i + 1] - buf[i] |
|||
} |
|||
} |
|||
return buf.run(0, finalSize) |
|||
} |
|||
USE DIFFERENCE |
|||
? def sampleData := [90, 47, 58, 29, 22, 32, 55, 5, 55, 73] |
|||
IMPLICIT NONE |
|||
> for n in 0..10 { |
|||
> def r1 := nthForwardDifference1(sampleData, n) |
|||
INTEGER :: array(10) = (/ 90, 47, 58, 29, 22, 32, 55, 5, 55, 73 /) |
|||
> require(r1 == nthForwardDifference2(sampleData, n)) |
|||
INTEGER :: i |
|||
> println(r1) |
|||
DO i = 1, 9 |
|||
CALL Fdiff(array, i) |
|||
END DO |
|||
END PROGRAM TEST</syntaxhighlight> |
|||
{{out}} |
|||
<pre> |
|||
-43 11 -29 -7 10 23 -50 50 18 |
|||
54 -40 22 17 13 -73 100 -32 |
|||
-94 62 -5 -4 -86 173 -132 |
|||
156 -67 1 -82 259 -305 |
|||
-223 68 -83 341 -564 |
|||
291 -151 424 -905 |
|||
-442 575 -1329 |
|||
1017 -1904 |
|||
-2921 |
|||
</pre> |
|||
=={{Header|FreeBASIC}}== |
|||
<syntaxhighlight lang="freebasic">function forward_difference( a() as uinteger ) as uinteger ptr |
|||
dim as uinteger ptr b = allocate( sizeof(uinteger) * (ubound(a)-1) ) |
|||
for i as uinteger = 0 to ubound(a)-1 |
|||
*(b+i) = a(i+1)-a(i) |
|||
next i |
|||
return b |
|||
end function |
|||
dim as uinteger a(0 to 15) = {2, 3, 5, 7, 11, 13, 17, 19,_ |
|||
23, 29, 31, 37, 41, 43, 47, 53} |
|||
dim as uinteger i |
|||
dim as uinteger ptr b = forward_difference( a() ) |
|||
for i = 0 to ubound(a)-1 |
|||
print *(b+i) |
|||
next i |
|||
</syntaxhighlight> |
|||
=={{header|Go}}== |
|||
<syntaxhighlight lang="go">package main |
|||
import "fmt" |
|||
func main() { |
|||
a := []int{90, 47, 58, 29, 22, 32, 55, 5, 55, 73} |
|||
fmt.Println(a) |
|||
fmt.Println(fd(a, 9)) |
|||
} |
|||
func fd(a []int, ord int) []int { |
|||
for i := 0; i < ord; i++ { |
|||
for j := 0; j < len(a)-i-1; j++ { |
|||
a[j] = a[j+1] - a[j] |
|||
} |
|||
} |
|||
return a[:len(a)-ord] |
|||
}</syntaxhighlight> |
|||
{{out}} |
|||
<pre> |
|||
[90 47 58 29 22 32 55 5 55 73] |
|||
[-2921] |
|||
</pre> |
|||
=={{header|Haskell}}== |
=={{header|Haskell}}== |
||
<syntaxhighlight lang="haskell">forwardDifference :: Num a => [a] -> [a] |
|||
forwardDifference = tail >>= zipWith (-) |
|||
nthForwardDifference xs n = iterate forwardDifference xs !! n |
|||
nthForwardDifference :: Num a => [a] -> Int -> [a] |
|||
> take 10 (iterate forwardDifference [90, 47, 58, 29, 22, 32, 55, 5, 55, 73]) |
|||
nthForwardDifference = (!!) . iterate forwardDifference |
|||
[[90,47,58,29,22,32,55,5,55,73], |
|||
[-43,11,-29,-7,10,23,-50,50,18], |
|||
main :: IO () |
|||
[54,-40,22,17,13,-73,100,-32], |
|||
main = |
|||
[-94,62,-5,-4,-86,173,-132], |
|||
mapM_ print $ |
|||
[156,-67,1,-82,259,-305], |
|||
take 10 (iterate forwardDifference [90, 47, 58, 29, 22, 32, 55, 5, 55, 73])</syntaxhighlight> |
|||
[-223,68,-83,341,-564], |
|||
{{Out}} |
|||
[291,-151,424,-905], |
|||
<pre>[90,47,58,29,22,32,55,5,55,73] |
|||
[-442,575,-1329], |
|||
[-43,11,-29,-7,10,23,-50,50,18] |
|||
[1017,-1904], |
|||
[54,-40,22,17,13,-73,100,-32] |
|||
[-2921]] |
|||
[-94,62,-5,-4,-86,173,-132] |
|||
[156,-67,1,-82,259,-305] |
|||
[-223,68,-83,341,-564] |
|||
[291,-151,424,-905] |
|||
[-442,575,-1329] |
|||
[1017,-1904] |
|||
[-2921]</pre> |
|||
=={{header|HicEst}}== |
|||
<syntaxhighlight lang="hicest">REAL :: n=10, list(n) |
|||
list = ( 90, 47, 58, 29, 22, 32, 55, 5, 55, 73 ) |
|||
WRITE(Format='i1, (i6)') 0, list |
|||
DO i = 1, n-1 |
|||
ALIAS(list,1, diff,n-i) ! rename list(1 ... n-i) with diff |
|||
diff = list($+1) - diff ! $ is the running left hand array index |
|||
WRITE(Format='i1, (i6)') i, diff |
|||
ENDDO |
|||
END</syntaxhighlight> |
|||
{{out}} |
|||
<pre>0 90 47 58 29 22 32 55 5 55 73 |
|||
1 -43 11 -29 -7 10 23 -50 50 18 |
|||
2 54 -40 22 17 13 -73 100 -32 |
|||
3 -94 62 -5 -4 -86 173 -132 |
|||
4 156 -67 1 -82 259 -305 |
|||
5 -223 68 -83 341 -564 |
|||
6 291 -151 424 -905 |
|||
7 -442 575 -1329 |
|||
8 1017 -1904 |
|||
9 -2921</pre> |
|||
=={{header|Icon}} and {{header|Unicon}}== |
|||
<syntaxhighlight lang="icon">procedure main(A) # Compute all forward difference orders for argument list |
|||
every order := 1 to (*A-1) do showList(order, fdiff(A, order)) |
|||
end |
|||
procedure fdiff(A, order) |
|||
every 1 to order do { |
|||
every put(B := [], A[i := 2 to *A] - A[i-1]) |
|||
A := B |
|||
} |
|||
return A |
|||
end |
|||
procedure showList(order, L) |
|||
writes(right(order,3),": ") |
|||
every writes(!L," ") |
|||
write() |
|||
end</syntaxhighlight> |
|||
{{out|A sample run}} |
|||
<pre> |
|||
->fdiff 3 1 4 1 5 9 2 6 3 |
|||
1: -2 3 -3 4 4 -7 4 -3 |
|||
2: 5 -6 7 0 -11 11 -7 |
|||
3: -11 13 -7 -11 22 -18 |
|||
4: 24 -20 -4 33 -40 |
|||
5: -44 16 37 -73 |
|||
6: 60 21 -110 |
|||
7: -39 -131 |
|||
8: -92 |
|||
-> |
|||
</pre> |
|||
=={{header|IDL}}== |
=={{header|IDL}}== |
||
Line 320: | Line 1,467: | ||
Standard IDL library function <tt>TS_diff(X,k,[/double])</tt>: |
Standard IDL library function <tt>TS_diff(X,k,[/double])</tt>: |
||
<syntaxhighlight lang="idl">print,(x = randomu(seed,8)*100) |
|||
15.1473 58.0953 82.7465 16.8637 97.7182 59.7856 17.7699 74.9154 |
|||
print,ts_diff(x,1) |
|||
-42.9479 -24.6513 65.8828 -80.8545 37.9326 42.0157 -57.1455 0.000000 |
|||
print,ts_diff(x,2) |
|||
-18.2967 -90.5341 146.737 -118.787 -4.08316 99.1613 0.000000 0.000000 |
|||
print,ts_diff(x,3) |
|||
72.2374 -237.271 265.524 -114.704 -103.244 0.000000 0.000000 0.000000</syntaxhighlight> |
|||
=={{header|J}}== |
=={{header|J}}== |
||
Of the many ways to code this in J, a particularly concise solution is: |
Of the many ways to code this in J, a particularly concise solution is: |
||
<syntaxhighlight lang="j">fd=: 2&(-~/\)</syntaxhighlight> |
|||
Alternatively, to reduce the number of J primitives |
Alternatively, to reduce the number of J primitives, use: |
||
<syntaxhighlight lang="j">fd=: }. - }: ^:</syntaxhighlight> |
|||
fd=: (}.-}:)^: |
|||
(which is also elegant, because the open-ended power conjunction reads like "to the power of anything"). |
(which is also elegant, because the open-ended power conjunction reads like "to the power of anything"). |
||
For example: |
For example: |
||
list |
<syntaxhighlight lang="j"> list=: 90 47 58 29 22 32 55 5 55 73 NB. Some numbers |
||
1 fd list |
|||
_43 11 _29 _7 10 23 _50 50 18 |
|||
2 fd list |
|||
54 _40 22 17 13 _73 100 _32</syntaxhighlight> |
|||
J is array oriented, so you can even ask for more than one forward difference at a time (i.e. <tt>N</tt> can be a list, instead of a single number): |
J is array oriented, so you can even ask for more than one forward difference at a time (i.e. <tt>N</tt> can be a list, instead of a single number): |
||
1 2 3 fd list NB. First, second, and third forward differences (simultaneously) |
<syntaxhighlight lang="j"> 1 2 3 fd list NB. First, second, and third forward differences (simultaneously) |
||
43 _11 29 7 _10 _23 50 _50 _18 |
|||
54 _40 22 17 13 _73 100 _32 0 |
|||
94 _62 5 4 86 _173 132 0 0 |
|||
a: fd list NB. All forward differences |
|||
90 47 58 29 22 32 55 5 55 73 |
|||
43 _11 29 7 _10 _23 50 _50 _18 0 |
|||
54 _40 22 17 13 _73 100 _32 0 0 |
|||
94 _62 5 4 86 _173 132 0 0 0 |
|||
156 _67 1 _82 259 _305 0 0 0 0 |
|||
223 _68 83 _341 564 0 0 0 0 0 |
|||
291 _151 424 _905 0 0 0 0 0 0 |
|||
442 _575 1329 0 0 0 0 0 0 0 |
|||
1017 _1904 0 0 0 0 0 0 0 0 |
|||
2921 0 0 0 0 0 0 0 0 0 |
|||
0 0 0 0 0 0 0 0 0 0</syntaxhighlight> |
|||
=={{header|Java}}== |
=={{header|Java}}== |
||
{{works with|Java|1.5+}} |
{{works with|Java|1.5+}} |
||
<syntaxhighlight lang="java">import java.util.Arrays; |
|||
public class FD { |
|||
public static void main(String args[]) { |
|||
double[] a = {90, 47, 58, 29, 22, 32, 55, 5, 55, 73}; |
|||
System.out.println(Arrays.toString(dif(a, 1))); |
|||
System.out.println(Arrays.toString(dif(a, 2))); |
|||
System.out.println(Arrays.toString(dif(a, 9))); |
|||
System.out.println(Arrays.toString(dif(a, 10))); //let's test |
|||
System.out.println(Arrays.toString(dif(a, 11))); |
|||
System.out.println(Arrays.toString(dif(a, -1))); |
|||
System.out.println(Arrays.toString(dif(a, 0))); |
|||
} |
|||
public static double[] dif(double[] a, int n) { |
|||
if (n < 0) |
|||
return null; // if the programmer was dumb |
|||
for (int i = 0; i < n && a.length > 0; i++) { |
|||
double[] b = new double[a.length - 1]; |
|||
for (int j = 0; j < b.length; j++){ |
|||
b[j] = a[j+1] - a[j]; |
|||
} |
|||
a = b; //"recurse" |
|||
} |
|||
return a; |
|||
} |
|||
} |
|||
public static double[] dif(double[] a, int n) { |
|||
Output: |
|||
if (n < 0) |
|||
return null; // if the programmer was dumb |
|||
for (int i = 0; i < n && a.length > 0; i++) { |
|||
double[] b = new double[a.length - 1]; |
|||
for (int j = 0; j < b.length; j++){ |
|||
b[j] = a[j+1] - a[j]; |
|||
} |
|||
a = b; //"recurse" |
|||
} |
|||
return a; |
|||
} |
|||
}</syntaxhighlight> |
|||
{{out}} |
|||
[-43.0, 11.0, -29.0, -7.0, 10.0, 23.0, -50.0, 50.0, 18.0] |
[-43.0, 11.0, -29.0, -7.0, 10.0, 23.0, -50.0, 50.0, 18.0] |
||
[54.0, -40.0, 22.0, 17.0, 13.0, -73.0, 100.0, -32.0] |
[54.0, -40.0, 22.0, 17.0, 13.0, -73.0, 100.0, -32.0] |
||
Line 404: | Line 1,551: | ||
null |
null |
||
[90.0, 47.0, 58.0, 29.0, 22.0, 32.0, 55.0, 5.0, 55.0, 73.0] |
[90.0, 47.0, 58.0, 29.0, 22.0, 32.0, 55.0, 5.0, 55.0, 73.0] |
||
=={{header|JavaScript}}== |
|||
===ES6=== |
|||
<syntaxhighlight lang="javascript">(() => { |
|||
'use strict'; |
|||
// forwardDifference :: Num a => [a] -> [a] |
|||
const forwardDifference = xs => |
|||
zipWith(subtract)(xs)(tail(xs)); |
|||
// nthForwardDifference :: Num a => [a] -> Int -> [a] |
|||
const nthForwardDifference = xs => |
|||
index(iterate(forwardDifference)(xs)).Just; |
|||
//----------------------- TEST ------------------------ |
|||
// main :: IO () |
|||
const main = () => |
|||
unlines( |
|||
take(10)( |
|||
iterate(forwardDifference)( |
|||
[90, 47, 58, 29, 22, 32, 55, 5, 55, 73] |
|||
) |
|||
).map((x, i) => justifyRight(2)('x')(i) + ( |
|||
' -> ' |
|||
) + JSON.stringify(x)) |
|||
); |
|||
//----------------- GENERIC FUNCTIONS ----------------- |
|||
// Just :: a -> Maybe a |
|||
const Just = x => ({ |
|||
type: 'Maybe', |
|||
Nothing: false, |
|||
Just: x |
|||
}); |
|||
// Nothing :: Maybe a |
|||
const Nothing = () => ({ |
|||
type: 'Maybe', |
|||
Nothing: true, |
|||
}); |
|||
// Tuple (,) :: a -> b -> (a, b) |
|||
const Tuple = a => |
|||
b => ({ |
|||
type: 'Tuple', |
|||
'0': a, |
|||
'1': b, |
|||
length: 2 |
|||
}); |
|||
// index (!!) :: [a] -> Int -> Maybe a |
|||
// index (!!) :: Generator (Int, a) -> Int -> Maybe a |
|||
// index (!!) :: String -> Int -> Maybe Char |
|||
const index = xs => i => { |
|||
const s = xs.constructor.constructor.name; |
|||
return 'GeneratorFunction' !== s ? (() => { |
|||
const v = xs[i]; |
|||
return undefined !== v ? Just(v) : Nothing(); |
|||
})() : Just(take(i)(xs), xs.next().value); |
|||
}; |
|||
// iterate :: (a -> a) -> a -> Gen [a] |
|||
const iterate = f => |
|||
function*(x) { |
|||
let v = x; |
|||
while (true) { |
|||
yield(v); |
|||
v = f(v); |
|||
} |
|||
}; |
|||
// justifyRight :: Int -> Char -> String -> String |
|||
const justifyRight = n => |
|||
// The string s, preceded by enough padding (with |
|||
// the character c) to reach the string length n. |
|||
c => s => n > s.length ? ( |
|||
s.padStart(n, c) |
|||
) : s; |
|||
// length :: [a] -> Int |
|||
const length = xs => |
|||
// Returns Infinity over objects without finite |
|||
// length. This enables zip and zipWith to choose |
|||
// the shorter argument when one is non-finite, |
|||
// like cycle, repeat etc |
|||
(Array.isArray(xs) || 'string' === typeof xs) ? ( |
|||
xs.length |
|||
) : Infinity; |
|||
// map :: (a -> b) -> [a] -> [b] |
|||
const map = f => |
|||
// The list obtained by applying f |
|||
// to each element of xs. |
|||
// (The image of xs under f). |
|||
xs => ( |
|||
Array.isArray(xs) ? ( |
|||
xs |
|||
) : xs.split('') |
|||
).map(f); |
|||
// subtract :: Num -> Num -> Num |
|||
const subtract = x => |
|||
y => y - x; |
|||
// tail :: [a] -> [a] |
|||
const tail = xs => |
|||
// A new list consisting of all |
|||
// items of xs except the first. |
|||
0 < xs.length ? xs.slice(1) : []; |
|||
// take :: Int -> [a] -> [a] |
|||
// take :: Int -> String -> String |
|||
const take = n => |
|||
// The first n elements of a list, |
|||
// string of characters, or stream. |
|||
xs => 'GeneratorFunction' !== xs |
|||
.constructor.constructor.name ? ( |
|||
xs.slice(0, n) |
|||
) : [].concat.apply([], Array.from({ |
|||
length: n |
|||
}, () => { |
|||
const x = xs.next(); |
|||
return x.done ? [] : [x.value]; |
|||
})); |
|||
// unlines :: [String] -> String |
|||
const unlines = xs => |
|||
// A single string formed by the intercalation |
|||
// of a list of strings with the newline character. |
|||
xs.join('\n'); |
|||
// zipWith :: (a -> b -> c) -> [a] -> [b] -> [c] |
|||
const zipWith = f => xs => ys => { |
|||
const |
|||
lng = Math.min(length(xs), length(ys)), |
|||
[as, bs] = [xs, ys].map(take(lng)); |
|||
return Array.from({ |
|||
length: lng |
|||
}, (_, i) => f(as[i])( |
|||
bs[i] |
|||
)); |
|||
}; |
|||
// MAIN --- |
|||
return main(); |
|||
})();</syntaxhighlight> |
|||
{{Out}} |
|||
<pre>0 -> [90,47,58,29,22,32,55,5,55,73] |
|||
1 -> [-43,11,-29,-7,10,23,-50,50,18] |
|||
2 -> [54,-40,22,17,13,-73,100,-32] |
|||
3 -> [-94,62,-5,-4,-86,173,-132] |
|||
4 -> [156,-67,1,-82,259,-305] |
|||
5 -> [-223,68,-83,341,-564] |
|||
6 -> [291,-151,424,-905] |
|||
7 -> [-442,575,-1329] |
|||
8 -> [1017,-1904] |
|||
9 -> [-2921]</pre> |
|||
=={{header|jq}}== |
|||
{{works with|jq|1.4}} |
|||
<syntaxhighlight lang="jq"># If n is a non-negative number and if input is |
|||
# a (possibly empty) array of numbers, |
|||
# emit an array, even if the input list is too short: |
|||
def ndiff(n): |
|||
if n==0 then . |
|||
elif n == 1 then . as $in | [range(1;length) | $in[.] - $in[.-1]] |
|||
else ndiff(1) | ndiff(n-1) |
|||
end;</syntaxhighlight> |
|||
'''Example''': |
|||
<syntaxhighlight lang="jq">def s: [90, 47, 58, 29, 22, 32, 55, 5, 55, 73]; |
|||
range(0;12) as $i | (s|ndiff($i))</syntaxhighlight> |
|||
{{out}} |
|||
<syntaxhighlight lang="sh">$ jq -c -n -f forward-difference.jq |
|||
[90,47,58,29,22,32,55,5,55,73] |
|||
[-43,11,-29,-7,10,23,-50,50,18] |
|||
[54,-40,22,17,13,-73,100,-32] |
|||
[-94,62,-5,-4,-86,173,-132] |
|||
[156,-67,1,-82,259,-305] |
|||
[-223,68,-83,341,-564] |
|||
[291,-151,424,-905] |
|||
[-442,575,-1329] |
|||
[1017,-1904] |
|||
[-2921] |
|||
[] |
|||
[]</syntaxhighlight> |
|||
=={{header|Julia}}== |
|||
{{works with|Julia|0.6}} |
|||
Using the built-in <code>diff</code> function, which returns the 1st forward difference: |
|||
<syntaxhighlight lang="julia">ndiff(A::Array, n::Integer) = n < 1 ? A : diff(ndiff(A, n-1)) |
|||
s = [90, 47, 58, 29, 22, 32, 55, 5, 55, 73] |
|||
println.(collect(ndiff(s, i) for i in 0:9))</syntaxhighlight> |
|||
{{out}} |
|||
<pre>[90, 47, 58, 29, 22, 32, 55, 5, 55, 73] |
|||
[-43, 11, -29, -7, 10, 23, -50, 50, 18] |
|||
[54, -40, 22, 17, 13, -73, 100, -32] |
|||
[-94, 62, -5, -4, -86, 173, -132] |
|||
[156, -67, 1, -82, 259, -305] |
|||
[-223, 68, -83, 341, -564] |
|||
[291, -151, 424, -905] |
|||
[-442, 575, -1329] |
|||
[1017, -1904] |
|||
[-2921]</pre> |
|||
=={{header|K4}}== |
|||
<syntaxhighlight lang="k4">fd:1_-':</syntaxhighlight> |
|||
To compute the ''n''th forward difference, call as: |
|||
<syntaxhighlight lang="k4">n fd/</syntaxhighlight> |
|||
In order to obtain all intermediate results, call as: |
|||
<syntaxhighlight lang="k4">n fd\</syntaxhighlight> |
|||
{{out|Examples}} |
|||
<pre> fd 1 2 4 7 11 16 |
|||
1 2 3 4 5 |
|||
2 fd/1 2 4 7 11 16 |
|||
1 1 1 1 |
|||
3 fd\1 2 4 7 11 16 |
|||
(1 2 4 7 11 16;1 2 3 4 5;1 1 1 1;0 0 0)</pre> |
|||
=={{header|Kotlin}}== |
|||
<syntaxhighlight lang="scala">// version 1.1.2 |
|||
fun forwardDifference(ia: IntArray, order: Int): IntArray { |
|||
if (order < 0) throw IllegalArgumentException("Order must be non-negative") |
|||
if (order == 0) return ia |
|||
val size = ia.size |
|||
if (size == 0) return ia // same empty array |
|||
if (order >= size) return intArrayOf() // new empty array |
|||
var old = ia |
|||
var new = old |
|||
var count = order |
|||
while (count-- >= 1) { |
|||
new = IntArray(old.size - 1) |
|||
for (i in 0 until new.size) new[i] = old[i + 1] - old[i] |
|||
old = new |
|||
} |
|||
return new |
|||
} |
|||
fun printArray(ia: IntArray) { |
|||
print("[") |
|||
for (i in 0 until ia.size) { |
|||
print("%5d".format(ia[i])) |
|||
if (i < ia .size - 1) print(", ") |
|||
} |
|||
println("]") |
|||
} |
|||
fun main(args: Array<String>) { |
|||
val ia = intArrayOf(90, 47, 58, 29, 22, 32, 55, 5, 55, 73) |
|||
for (order in 0..ia.size) { |
|||
val fd = forwardDifference(ia, order) |
|||
print("%2d".format(order) + ": ") |
|||
printArray(fd) |
|||
} |
|||
}</syntaxhighlight> |
|||
{{out}} |
|||
<pre> |
|||
0: [ 90, 47, 58, 29, 22, 32, 55, 5, 55, 73] |
|||
1: [ -43, 11, -29, -7, 10, 23, -50, 50, 18] |
|||
2: [ 54, -40, 22, 17, 13, -73, 100, -32] |
|||
3: [ -94, 62, -5, -4, -86, 173, -132] |
|||
4: [ 156, -67, 1, -82, 259, -305] |
|||
5: [ -223, 68, -83, 341, -564] |
|||
6: [ 291, -151, 424, -905] |
|||
7: [ -442, 575, -1329] |
|||
8: [ 1017, -1904] |
|||
9: [-2921] |
|||
10: [] |
|||
</pre> |
|||
=={{header|Lambdatalk}}== |
|||
<syntaxhighlight lang="scheme"> |
|||
{def fdiff |
|||
{lambda {:l} |
|||
{A.new |
|||
{S.map {{lambda {:l :i} {- {A.get {+ :i 1} :l} {A.get :i :l}} } :l} |
|||
{S.serie 0 {- {A.length :l} 2}}}}}} |
|||
-> fdiff |
|||
{def disp |
|||
{lambda {:l} |
|||
{if {A.empty? {A.rest :l}} |
|||
then else {let { {:l {fdiff :l}} } {br}:l {disp :l}}}}} |
|||
-> disp |
|||
{def L {A.new 90 47 58 29 22 32 55 5 55 73}} |
|||
-> L |
|||
{disp {L}} |
|||
-> |
|||
[-43,11,-29,-7,10,23,-50,50,18] |
|||
[54,-40,22,17,13,-73,100,-32] |
|||
[-94,62,-5,-4,-86,173,-132] |
|||
[156,-67,1,-82,259,-305] |
|||
[-223,68,-83,341,-564] |
|||
[291,-151,424,-905] |
|||
[-442,575,-1329] |
|||
[1017,-1904] |
|||
[-2921] |
|||
</syntaxhighlight> |
|||
=={{header|Lasso}}== |
|||
<syntaxhighlight lang="lasso">#!/usr/bin/lasso9 |
|||
define forwardDiff(values, order::integer=1) => { |
|||
!#order ? return #values->asArray |
|||
local(result = array) |
|||
iterate(#values) => { |
|||
loop_count < #values->size ? |
|||
#result->insert(#values->get(loop_count+1) - #values->get(loop_count)) |
|||
} |
|||
#order > 1 ? #result = forwardDiff(#result, #order-1) |
|||
return #result |
|||
} |
|||
local(data = (:90, 47, 58, 29, 22, 32, 55, 5, 55, 73)) |
|||
with x in generateSeries(0, #data->size-1) |
|||
do stdoutnl(#x + ': ' + forwardDiff(#data, #x))</syntaxhighlight> |
|||
{{out}} |
|||
<pre>0: array(90, 47, 58, 29, 22, 32, 55, 5, 55, 73) |
|||
1: array(-43, 11, -29, -7, 10, 23, -50, 50, 18) |
|||
2: array(54, -40, 22, 17, 13, -73, 100, -32) |
|||
3: array(-94, 62, -5, -4, -86, 173, -132) |
|||
4: array(156, -67, 1, -82, 259, -305) |
|||
5: array(-223, 68, -83, 341, -564) |
|||
6: array(291, -151, 424, -905) |
|||
7: array(-442, 575, -1329) |
|||
8: array(1017, -1904) |
|||
9: array(-2921)</pre> |
|||
=={{header|Logo}}== |
=={{header|Logo}}== |
||
<syntaxhighlight lang="logo">to fwd.diff :l |
|||
if empty? :l [output []] |
|||
if empty? bf :l [output []] |
|||
output fput (first bf :l)-(first :l) fwd.diff bf :l |
|||
end |
|||
to nth.fwd.diff :n :l |
|||
if :n = 0 [output :l] |
|||
output nth.fwd.diff :n-1 fwd.diff :l |
|||
end |
|||
show nth.fwd.diff 9 [90 47 58 29 22 32 55 5 55 73] |
|||
[-2921]</syntaxhighlight> |
|||
=={{header|Lua}}== |
|||
<syntaxhighlight lang="lua">function dif(a, b, ...) |
|||
if(b) then return b-a, dif(b, ...) end |
|||
end |
|||
function dift(t) return {dif(unpack(t))} end |
|||
print(unpack(dift{1,3,6,10,15}))</syntaxhighlight> |
|||
=={{header|M2000 Interpreter}}== |
|||
Function Diff(a()) get an array by value (a shallow copy) |
|||
<syntaxhighlight lang="m2000 interpreter"> |
|||
Form 80, 40 |
|||
Module Forward_difference { |
|||
Print $(0,6) ' 6 characters column |
|||
Dim a(), b() |
|||
a()=(90,47,58,29,22,32,55,5,55,73) |
|||
Function Diff(a()) { |
|||
for i=0 to len(a())-2: a(i)=a(i+1)-a(i):Next i |
|||
Dim a(len(a())-1) ' redim one less |
|||
=a() |
|||
} |
|||
Print "Original:","",a() |
|||
b()=a() ' copy a() to b() |
|||
k=1 |
|||
While len(b())>1 { |
|||
b()=Diff(b()) ' copy returned array to b() |
|||
Print "Difference ";k;":",b() |
|||
k++ |
|||
} |
|||
} |
|||
Forward_difference |
|||
</syntaxhighlight> |
|||
{{out}} |
|||
<pre style="height:30ex;overflow:scroll"> |
|||
Original: 90 47 58 29 22 32 55 5 55 73 |
|||
Difference 1: -43 11 -29 -7 10 23 -50 50 18 |
|||
Difference 2: 54 -40 22 17 13 -73 100 -32 |
|||
Difference 3: -94 62 -5 -4 -86 173 -132 |
|||
Difference 4: 156 -67 1 -82 259 -305 |
|||
Difference 5: -223 68 -83 341 -564 |
|||
Difference 6: 291 -151 424 -905 |
|||
Difference 7: -442 575 -1329 |
|||
Difference 8: 1017 -1904 |
|||
Difference 9: -2921 |
|||
</pre > |
|||
=={{header|Mathematica}} / {{header|Wolfram Language}}== |
|||
Built-in function: |
|||
<syntaxhighlight lang="mathematica">i={3,5,12,1,6,19,6,2,4,9}; |
|||
Differences[i]</syntaxhighlight> |
|||
{{out|gives back}} |
|||
<syntaxhighlight lang="mathematica">{2, 7, -11, 5, 13, -13, -4, 2, 5}</syntaxhighlight> |
|||
The n<sup>th</sup> difference can be done as follows: |
|||
<syntaxhighlight lang="mathematica">i={3,5,12,1,6,19,6,2,4,9}; |
|||
Differences[i,n]</syntaxhighlight> |
|||
=={{header|MATLAB}} / {{header|Octave}}== |
|||
This is a built-in function. |
|||
X is the list of numbers, |
|||
n is the order of the forward difference. |
|||
<syntaxhighlight lang="matlab">Y = diff(X,n);</syntaxhighlight> |
|||
{{out}} 1st order forward difference. |
|||
<pre>diff([1 2 3 4 5]) |
|||
ans = |
|||
1 1 1 1</pre> |
|||
=={{header|Maxima}}== |
|||
<syntaxhighlight lang="maxima">ldiff(u, n) := block([m: length(u)], for j thru n do u: makelist(u[i + 1] - u[i], i, 1, m - j), u);</syntaxhighlight> |
|||
=={{header|NetRexx}}== |
|||
<syntaxhighlight lang="netrexx">/* NetRexx************************************************************* |
|||
* Forward differences |
|||
* 18.08.2012 Walter Pachl derived from Rexx |
|||
**********************************************************************/ |
|||
Loop n=-1 To 11 |
|||
differences('90 47 58 29 22 32 55 5 55 73',n) |
|||
End |
|||
method differences(a,n) public static |
|||
--arr=Rexx[11] -- array must be declared (zero based) |
|||
arr='' -- alternative: indexed string |
|||
m=a.words |
|||
Select |
|||
When n<0 Then Say 'n is negative:' n '<' 0 |
|||
When n>m Then Say 'n is too large:' n '>' m |
|||
Otherwise Do |
|||
Loop i=1 To m |
|||
arr[i]=a.word(i) |
|||
End |
|||
Loop i = 1 to n |
|||
t = arr[i] |
|||
Loop j = i+1 to m |
|||
u = arr[j] |
|||
arr[j] = arr[j]-t |
|||
t = u |
|||
end |
|||
end |
|||
ol='' |
|||
Loop i=n+1 to m |
|||
ol=ol arr[i] |
|||
End |
|||
Say n ol |
|||
End |
|||
End</syntaxhighlight> |
|||
Output is the same as for Rexx |
|||
=={{header|Nial}}== |
=={{header|Nial}}== |
||
Define forward difference for order 1 |
Define forward difference for order 1 |
||
<syntaxhighlight lang="nial">fd is - [rest, front]</syntaxhighlight> |
|||
forward difference of 4th order |
|||
{{out}} forward difference of 4th order |
|||
b := 90 47 58 29 22 32 55 5 55 73 |
|||
<syntaxhighlight lang="nial">b := 90 47 58 29 22 32 55 5 55 73 |
|||
4 fold fd b |
|||
4 fold fd b |
|||
= 156 -67 1 -82 259 -305 |
|||
= 156 -67 1 -82 259 -305</syntaxhighlight> |
|||
=={{header|Nim}}== |
|||
<syntaxhighlight lang="nim">proc dif(s: seq[int]): seq[int] = |
|||
result = newSeq[int](s.len-1) |
|||
for i in 0..<s.high: |
|||
result[i] = s[i+1] - s[i] |
|||
proc difn(s: seq[int]; n: int): seq[int] = |
|||
if n > 0: difn(dif(s), n-1) |
|||
else: s |
|||
const s = @[90, 47, 58, 29, 22, 32, 55, 5, 55, 73] |
|||
echo difn(s, 0) |
|||
echo difn(s, 1) |
|||
echo difn(s, 2)</syntaxhighlight> |
|||
{{out}} |
|||
<pre>@[90, 47, 58, 29, 22, 32, 55, 5, 55, 73] |
|||
@[-43, 11, -29, -7, 10, 23, -50, 50, 18] |
|||
@[54, -40, 22, 17, 13, -73, 100, -32]</pre> |
|||
=={{header|Objeck}}== |
|||
{{trans|Java}} |
|||
<syntaxhighlight lang="objeck"> |
|||
bundle Default { |
|||
class Test { |
|||
function : Main(args : String[]) ~ Nil { |
|||
a := [90.0, 47.0, 58.0, 29.0, 22.0, 32.0, 55.0, 5.0, 55.0, 73.0]; |
|||
Print(Diff(a, 1)); |
|||
Print(Diff(a, 2)); |
|||
Print(Diff(a, 9)); |
|||
} |
|||
function : Print(a : Float[]) ~ Nil { |
|||
if(a <> Nil) { |
|||
'['->Print(); |
|||
each(i : a) { |
|||
a[i]->Print(); ','->Print(); |
|||
}; |
|||
']'->PrintLine(); |
|||
}; |
|||
} |
|||
function : Diff(a : Float[], n : Int) ~ Float[] { |
|||
if (n < 0) { |
|||
return Nil; |
|||
}; |
|||
for(i := 0; i < n & a->Size() > 0; i += 1;) { |
|||
b := Float->New[a->Size() - 1]; |
|||
for(j := 0; j < b->Size(); j += 1;){ |
|||
b[j] := a[j+1] - a[j]; |
|||
}; |
|||
a := b; |
|||
}; |
|||
return a; |
|||
} |
|||
} |
|||
} |
|||
</syntaxhighlight> |
|||
=={{header|OCaml}}== |
=={{header|OCaml}}== |
||
<ocaml>let rec forward_difference = function |
<syntaxhighlight lang="ocaml">let rec forward_difference = function |
||
a :: (b :: _ as xs) -> |
a :: (b :: _ as xs) -> |
||
b - a :: forward_difference xs |
b - a :: forward_difference xs |
||
Line 439: | Line 2,111: | ||
xs |
xs |
||
else |
else |
||
nth_forward_difference (pred n) (forward_difference xs)</ |
nth_forward_difference (pred n) (forward_difference xs)</syntaxhighlight> |
||
Output: |
|||
{{out}} |
|||
<pre> |
<pre> |
||
# nth_forward_difference 9 [90; 47; 58; 29; 22; 32; 55; 5; 55; 73];; |
# nth_forward_difference 9 [90; 47; 58; 29; 22; 32; 55; 5; 55; 73];; |
||
Line 448: | Line 2,119: | ||
</pre> |
</pre> |
||
=={{header| |
=={{header|Oforth}}== |
||
<syntaxhighlight lang="oforth">: forwardDiff(l) l right(l size 1 -) l zipWith(#-) ; |
|||
: forwardDiffN(n, l) l #[ forwardDiff dup println ] times(n) ;</syntaxhighlight> |
|||
{{out}} |
|||
<pre> |
<pre> |
||
10 [ 90, 47, 58, 29, 22, 32, 55, 5, 55, 73] forwardDiffN |
|||
define forward_difference(l); |
|||
[-43, 11, -29, -7, 10, 23, -50, 50, 18] |
|||
[54, -40, 22, 17, 13, -73, 100, -32] |
|||
[-94, 62, -5, -4, -86, 173, -132] |
|||
[156, -67, 1, -82, 259, -305] |
|||
[-223, 68, -83, 341, -564] |
|||
[291, -151, 424, -905] |
|||
[-442, 575, -1329] |
|||
[1017, -1904] |
|||
[-2921] |
|||
[] |
|||
</pre> |
|||
=={{header|PARI/GP}}== |
|||
<syntaxhighlight lang="parigp">fd(v)=vector(#v-1,i,v[i+1]-v[i]);</syntaxhighlight> |
|||
=={{header|Pascal}}== |
|||
<syntaxhighlight lang="pascal">Program ForwardDifferenceDemo(output); |
|||
procedure fowardDifference(list: array of integer); |
|||
var |
|||
b: array of integer; |
|||
i, newlength: integer; |
|||
begin |
|||
newlength := length(list) - 1; |
|||
if newlength > 0 then |
|||
begin |
|||
setlength(b, newlength); |
|||
for i := low(b) to high(b) do |
|||
begin |
|||
b[i] := list[i+1] - list[i]; |
|||
write (b[i]:6); |
|||
end; |
|||
writeln; |
|||
fowardDifference(b); |
|||
end; |
|||
end; |
|||
var |
|||
a: array [1..10] of integer = (90, 47, 58, 29, 22, 32, 55, 5, 55, 73); |
|||
begin |
|||
fowardDifference(a); |
|||
end.</syntaxhighlight> |
|||
{{out}} |
|||
<pre>:> ./ForwardDifference |
|||
-43 11 -29 -7 10 23 -50 50 18 |
|||
54 -40 22 17 13 -73 100 -32 |
|||
-94 62 -5 -4 -86 173 -132 |
|||
156 -67 1 -82 259 -305 |
|||
-223 68 -83 341 -564 |
|||
291 -151 424 -905 |
|||
-442 575 -1329 |
|||
1017 -1904 |
|||
-2921 |
|||
</pre> |
|||
=={{header|PascalABC.NET}}== |
|||
<syntaxhighlight lang="delphi"> |
|||
function Convert(a: array of integer): array of integer; |
|||
begin |
|||
var n := a.Length; |
|||
var res := new integer[n-1]; |
|||
for var i:=0 to n-2 do |
|||
res[i] := a[i+1]-a[i]; |
|||
Result := res; |
|||
end; |
|||
begin |
|||
var a := |90, 47, 58, 29, 22, 32, 55, 5, 55, 73|; |
|||
while a.Length > 0 do |
|||
begin |
|||
Println(a); |
|||
a := Convert(a); |
|||
end; |
|||
end. |
|||
</syntaxhighlight> |
|||
{{out}} |
|||
<pre> |
|||
[90,47,58,29,22,32,55,5,55,73] |
|||
[-43,11,-29,-7,10,23,-50,50,18] |
|||
[54,-40,22,17,13,-73,100,-32] |
|||
[-94,62,-5,-4,-86,173,-132] |
|||
[156,-67,1,-82,259,-305] |
|||
[-223,68,-83,341,-564] |
|||
[291,-151,424,-905] |
|||
[-442,575,-1329] |
|||
[1017,-1904] |
|||
[-2921] |
|||
</pre> |
|||
=={{header|Perl}}== |
|||
<syntaxhighlight lang="perl">sub dif { |
|||
my @s = @_; |
|||
map { $s[$_+1] - $s[$_] } 0 .. $#s-1 |
|||
} |
|||
@a = qw<90 47 58 29 22 32 55 5 55 73>; |
|||
while (@a) { printf('%6d', $_) for @a = dif @a; print "\n" }</syntaxhighlight> |
|||
{{out}} |
|||
<pre> -43 11 -29 -7 10 23 -50 50 18 |
|||
54 -40 22 17 13 -73 100 -32 |
|||
-94 62 -5 -4 -86 173 -132 |
|||
156 -67 1 -82 259 -305 |
|||
-223 68 -83 341 -564 |
|||
291 -151 424 -905 |
|||
-442 575 -1329 |
|||
1017 -1904 |
|||
-2921</pre> |
|||
=={{header|Phix}}== |
|||
<!--<syntaxhighlight lang="phix">(phixonline)--> |
|||
<span style="color: #008080;">with</span> <span style="color: #008080;">javascript_semantics</span> |
|||
<span style="color: #008080;">function</span> <span style="color: #000000;">fwd_diff_n</span><span style="color: #0000FF;">(</span><span style="color: #004080;">sequence</span> <span style="color: #000000;">s</span><span style="color: #0000FF;">,</span> <span style="color: #004080;">integer</span> <span style="color: #000000;">order</span><span style="color: #0000FF;">)</span> |
|||
<span style="color: #7060A8;">assert</span><span style="color: #0000FF;">(</span><span style="color: #000000;">order</span><span style="color: #0000FF;"><</span><span style="color: #7060A8;">length</span><span style="color: #0000FF;">(</span><span style="color: #000000;">s</span><span style="color: #0000FF;">))</span> |
|||
<span style="color: #000000;">s</span> <span style="color: #0000FF;">=</span> <span style="color: #7060A8;">deep_copy</span><span style="color: #0000FF;">(</span><span style="color: #000000;">s</span><span style="color: #0000FF;">)</span> |
|||
<span style="color: #008080;">for</span> <span style="color: #000000;">i</span><span style="color: #0000FF;">=</span><span style="color: #000000;">1</span> <span style="color: #008080;">to</span> <span style="color: #000000;">order</span> <span style="color: #008080;">do</span> |
|||
<span style="color: #008080;">for</span> <span style="color: #000000;">j</span><span style="color: #0000FF;">=</span><span style="color: #000000;">1</span> <span style="color: #008080;">to</span> <span style="color: #7060A8;">length</span><span style="color: #0000FF;">(</span><span style="color: #000000;">s</span><span style="color: #0000FF;">)-</span><span style="color: #000000;">1</span> <span style="color: #008080;">do</span> |
|||
<span style="color: #000000;">s</span><span style="color: #0000FF;">[</span><span style="color: #000000;">j</span><span style="color: #0000FF;">]</span> <span style="color: #0000FF;">=</span> <span style="color: #000000;">s</span><span style="color: #0000FF;">[</span><span style="color: #000000;">j</span><span style="color: #0000FF;">+</span><span style="color: #000000;">1</span><span style="color: #0000FF;">]-</span><span style="color: #000000;">s</span><span style="color: #0000FF;">[</span><span style="color: #000000;">j</span><span style="color: #0000FF;">]</span> |
|||
<span style="color: #008080;">end</span> <span style="color: #008080;">for</span> |
|||
<span style="color: #000000;">s</span> <span style="color: #0000FF;">=</span> <span style="color: #000000;">s</span><span style="color: #0000FF;">[</span><span style="color: #000000;">1</span><span style="color: #0000FF;">..-</span><span style="color: #000000;">2</span><span style="color: #0000FF;">]</span> |
|||
<span style="color: #008080;">end</span> <span style="color: #008080;">for</span> |
|||
<span style="color: #008080;">return</span> <span style="color: #000000;">s</span> |
|||
<span style="color: #008080;">end</span> <span style="color: #008080;">function</span> |
|||
<span style="color: #008080;">constant</span> <span style="color: #000000;">s</span> <span style="color: #0000FF;">=</span> <span style="color: #0000FF;">{</span><span style="color: #000000;">90</span><span style="color: #0000FF;">,</span> <span style="color: #000000;">47</span><span style="color: #0000FF;">,</span> <span style="color: #000000;">58</span><span style="color: #0000FF;">,</span> <span style="color: #000000;">29</span><span style="color: #0000FF;">,</span> <span style="color: #000000;">22</span><span style="color: #0000FF;">,</span> <span style="color: #000000;">32</span><span style="color: #0000FF;">,</span> <span style="color: #000000;">55</span><span style="color: #0000FF;">,</span> <span style="color: #000000;">5</span><span style="color: #0000FF;">,</span> <span style="color: #000000;">55</span><span style="color: #0000FF;">,</span> <span style="color: #000000;">73</span><span style="color: #0000FF;">}</span> |
|||
<span style="color: #008080;">for</span> <span style="color: #000000;">i</span><span style="color: #0000FF;">=</span><span style="color: #000000;">1</span> <span style="color: #008080;">to</span> <span style="color: #000000;">9</span> <span style="color: #008080;">do</span> |
|||
<span style="color: #0000FF;">?</span><span style="color: #000000;">fwd_diff_n</span><span style="color: #0000FF;">(</span><span style="color: #000000;">s</span><span style="color: #0000FF;">,</span><span style="color: #000000;">i</span><span style="color: #0000FF;">)</span> |
|||
<span style="color: #008080;">end</span> <span style="color: #008080;">for</span> |
|||
<!--</syntaxhighlight>--> |
|||
{{out}} |
|||
<pre> |
|||
{-43,11,-29,-7,10,23,-50,50,18} |
|||
{54,-40,22,17,13,-73,100,-32} |
|||
{-94,62,-5,-4,-86,173,-132} |
|||
{156,-67,1,-82,259,-305} |
|||
{-223,68,-83,341,-564} |
|||
{291,-151,424,-905} |
|||
{-442,575,-1329} |
|||
{1017,-1904} |
|||
{-2921} |
|||
</pre> |
|||
=={{header|PHP}}== |
|||
<syntaxhighlight lang="php"><?php |
|||
function forwardDiff($anArray, $times = 1) { |
|||
if ($times <= 0) { return $anArray; } |
|||
for ($accumilation = array(), $i = 1, $j = count($anArray); $i < $j; ++$i) { |
|||
$accumilation[] = $anArray[$i] - $anArray[$i - 1]; |
|||
} |
|||
if ($times === 1) { return $accumilation; } |
|||
return forwardDiff($accumilation, $times - 1); |
|||
} |
|||
class ForwardDiffExample extends PweExample { |
|||
function _should_run_empty_array_for_single_elem() { |
|||
$expected = array($this->rand()->int()); |
|||
$this->spec(forwardDiff($expected))->shouldEqual(array()); |
|||
} |
|||
function _should_give_diff_of_two_elem_as_single_elem() { |
|||
$twoNums = array($this->rand()->int(), $this->rand()->int()); |
|||
$expected = array($twoNums[1] - $twoNums[0]); |
|||
$this->spec(forwardDiff($twoNums))->shouldEqual($expected); |
|||
} |
|||
function _should_compute_correct_forward_diff_for_longer_arrays() { |
|||
$diffInput = array(10, 2, 9, 6, 5); |
|||
$expected = array(-8, 7, -3, -1); |
|||
$this->spec(forwardDiff($diffInput))->shouldEqual($expected); |
|||
} |
|||
function _should_apply_more_than_once_if_specified() { |
|||
$diffInput = array(4, 6, 9, 3, 4); |
|||
$expectedAfter1 = array(2, 3, -6, 1); |
|||
$expectedAfter2 = array(1, -9, 7); |
|||
$this->spec(forwardDiff($diffInput, 1))->shouldEqual($expectedAfter1); |
|||
$this->spec(forwardDiff($diffInput, 2))->shouldEqual($expectedAfter2); |
|||
} |
|||
function _should_return_array_unaltered_if_no_times() { |
|||
$this->spec(forwardDiff($expected = array(1,2,3), 0))->shouldEqual($expected); |
|||
} |
|||
}</syntaxhighlight> |
|||
=={{header|Picat}}== |
|||
<syntaxhighlight lang="picat">go => |
|||
L = [90, 47, 58, 29, 22, 32, 55, 5, 55, 73], |
|||
foreach(I in 1..L.length-1) |
|||
println([d=I,diffi(L,I)]) |
|||
end, |
|||
nl, |
|||
% All differences (a sublist to save space) |
|||
println(alldiffs(L[1..6])), |
|||
nl. |
|||
% Difference of the list |
|||
diff(L) = Diff => |
|||
Diff = [L[I]-L[I-1] : I in 2..L.length]. |
|||
% The i'th list difference |
|||
diffi(L,D) = Diff => |
|||
Diff1 = L, |
|||
foreach(_I in 1..D) |
|||
Diff1 := diff(Diff1) |
|||
end, |
|||
Diff = Diff1. |
|||
% all differences |
|||
alldiffs(L) = Diffs => |
|||
Diffs1 = [], |
|||
Diff = L, |
|||
foreach(_I in 1..L.length-1) |
|||
Diff := diff(Diff), |
|||
Diffs1 := Diffs1 ++ [Diff] |
|||
end, |
|||
Diffs = Diffs1.</syntaxhighlight> |
|||
{{out}} |
|||
<pre>[d = 1,[-43,11,-29,-7,10,23,-50,50,18]] |
|||
[d = 2,[54,-40,22,17,13,-73,100,-32]] |
|||
[d = 3,[-94,62,-5,-4,-86,173,-132]] |
|||
[d = 4,[156,-67,1,-82,259,-305]] |
|||
[d = 5,[-223,68,-83,341,-564]] |
|||
[d = 6,[291,-151,424,-905]] |
|||
[d = 7,[-442,575,-1329]] |
|||
[d = 8,[1017,-1904]] |
|||
[d = 9,[-2921]] |
|||
[[-43,11,-29,-7,10],[54,-40,22,17],[-94,62,-5],[156,-67],[-223]]</pre> |
|||
=={{header|PicoLisp}}== |
|||
<syntaxhighlight lang="picolisp">(de fdiff (Lst) |
|||
(mapcar - (cdr Lst) Lst) ) |
|||
(for (L (90 47 58 29 22 32 55 5 55 73) L (fdiff L)) |
|||
(println L) )</syntaxhighlight> |
|||
{{out}} |
|||
<pre>(90 47 58 29 22 32 55 5 55 73) |
|||
(-43 11 -29 -7 10 23 -50 50 18) |
|||
(54 -40 22 17 13 -73 100 -32) |
|||
(-94 62 -5 -4 -86 173 -132) |
|||
(156 -67 1 -82 259 -305) |
|||
(-223 68 -83 341 -564) |
|||
(291 -151 424 -905) |
|||
(-442 575 -1329) |
|||
(1017 -1904) |
|||
(-2921)</pre> |
|||
=={{header|PL/I}}== |
|||
<syntaxhighlight lang="pl/i"> |
|||
/* Forward differences. */ /* 23 April 2010 */ |
|||
differences: procedure options (main); |
|||
declare a(10) fixed(10) static initial |
|||
(7, 3, 9, 250, 300, 4, 68, 72, 154, 601); |
|||
declare (i, j, m, n, t, u) fixed binary; |
|||
m = hbound(a,1); |
|||
get (n); if n > m then signal error; |
|||
put skip edit (a) (F(7)); |
|||
do i = 1 to n; |
|||
t = a(i); |
|||
do j = i+1 to m; |
|||
u = a(j); |
|||
a(j) = a(j) - t; |
|||
t = u; |
|||
end; |
|||
put skip edit (a) (F(7)); |
|||
end; |
|||
put skip edit ((a(i) do i = n+1 to m)) (F(9)); |
|||
end differences; |
|||
</syntaxhighlight> |
|||
=={{header|Plain English}}== |
|||
<syntaxhighlight lang="plainenglish">To add a fraction to some fraction things: |
|||
Allocate memory for a fraction thing. |
|||
Put the fraction into the fraction thing's fraction. |
|||
Append the fraction thing to the fraction things. |
|||
To create some fraction things: |
|||
Add 90-1/2 to the fraction things. |
|||
Add 47/1 to the fraction things. |
|||
Add 58/1 to the fraction things. |
|||
Add 29/1 to the fraction things. |
|||
Add 22/1 to the fraction things. |
|||
Add 32/1 to the fraction things. |
|||
Add 55/1 to the fraction things. |
|||
Add 5/1 to the fraction things. |
|||
Add 55/1 to the fraction things. |
|||
Add 73-1/2 to the fraction things. |
|||
To find the difference of some fraction things: |
|||
If the fraction things' count is less than 2, exit. |
|||
Get a fraction thing from the fraction things. |
|||
Loop. |
|||
If the fraction thing's next is nil, remove the fraction thing from the fraction things; destroy the fraction thing; exit. |
|||
Put the fraction thing's next's fraction minus the fraction thing's fraction into the fraction thing's fraction. |
|||
Put the fraction thing's next into the fraction thing. |
|||
Repeat. |
|||
To find the difference of some fraction things given an order: |
|||
If a counter is past the order, exit. |
|||
Find the difference of the fraction things. |
|||
Repeat. |
|||
A fraction thing is a thing with a fraction. |
|||
An order is a number. |
|||
To run: |
|||
Start up. |
|||
Create some fraction things. |
|||
Write "Original list:" on the console. |
|||
Show the fraction things. |
|||
Find the difference of the fraction things given 4. |
|||
Write "Order 4 forward difference:" on the console. |
|||
Show the fraction things. |
|||
Destroy the fraction things. |
|||
Wait for the escape key. |
|||
Shut down. |
|||
To show some fraction things: |
|||
Get a fraction thing from the fraction things. |
|||
Loop. |
|||
If the fraction thing is nil, write "" on the console; exit. |
|||
Write "" then the fraction thing's fraction on the console without advancing. |
|||
If the fraction thing's next is not nil, write ", " on the console without advancing. |
|||
Put the fraction thing's next into the fraction thing. |
|||
Repeat.</syntaxhighlight> |
|||
{{out}} |
|||
<pre> |
|||
Original list: |
|||
90-1/2, 47, 58, 29, 22, 32, 55, 5, 55, 73-1/2 |
|||
Order 4 forward difference: |
|||
156-1/2, -67, 1, -82, 259, -304-1/2 |
|||
</pre> |
|||
=={{header|Pop11}}== |
|||
<syntaxhighlight lang="pop11">define forward_difference(l); |
|||
lvars res = [], prev, el; |
lvars res = [], prev, el; |
||
if l = [] then |
if l = [] then |
||
Line 469: | Line 2,488: | ||
endfor; |
endfor; |
||
res; |
res; |
||
enddefine; |
enddefine;</syntaxhighlight> |
||
</pre> |
|||
=={{header|PowerShell}}== |
|||
<math>\Delta^n [f](x)= \sum_{k=0}^n \left ({\prod_{i=1}^k \frac{n-k+i}{i}}\right ) (-1)^{n-k} f(x+k)</math> |
|||
<syntaxhighlight lang="powershell">function Forward-Difference( [UInt64] $n, [Array] $f ) |
|||
{ |
|||
$flen = $f.length |
|||
if( $flen -gt [Math]::Max( 1, $n ) ) |
|||
{ |
|||
0..( $flen - $n - 1 ) | ForEach-Object { |
|||
$l=0; |
|||
for( $k = 0; $k -le $n; $k++ ) |
|||
{ |
|||
$j = 1 |
|||
for( $i = 1; $i -le $k; $i++ ) |
|||
{ |
|||
$j *= ( ( $n - $k + $i ) / $i ) |
|||
} |
|||
$l += $j * ( 1 - 2 * ( ( $n - $k ) % 2 ) ) * $f[ $_ + $k ] |
|||
} |
|||
$l |
|||
} |
|||
} |
|||
} |
|||
Forward-Difference 2 1,2,4,5</syntaxhighlight> |
|||
=={{header|PureBasic}}== |
|||
<syntaxhighlight lang="purebasic">Procedure forward_difference(List a()) |
|||
If ListSize(a()) <= 1 |
|||
ClearList(a()): ProcedureReturn |
|||
EndIf |
|||
Protected NewList b() |
|||
CopyList(a(), b()) |
|||
LastElement(a()): DeleteElement(a()) |
|||
SelectElement(b(), 1) |
|||
ForEach a() |
|||
a() - b(): NextElement(b()) |
|||
Next |
|||
EndProcedure |
|||
Procedure nth_difference(List a(), List b(), n) |
|||
Protected i |
|||
CopyList(a(), b()) |
|||
For i = 1 To n |
|||
forward_difference(b()) |
|||
Next |
|||
EndProcedure |
|||
Procedure.s display(List a()) |
|||
Protected output.s |
|||
ForEach a() |
|||
output + Str(a()) + "," |
|||
Next |
|||
ProcedureReturn RTrim(output,",") |
|||
EndProcedure |
|||
DataSection |
|||
;list data |
|||
Data.i 10 ;element count |
|||
Data.i 90, 47, 58, 29, 22, 32, 55, 5, 55, 73 |
|||
EndDataSection |
|||
;create and fill list |
|||
Define i |
|||
NewList a() |
|||
Read.i i |
|||
While i > 0 |
|||
AddElement(a()): Read.i a(): i - 1 |
|||
Wend |
|||
If OpenConsole() |
|||
NewList b() |
|||
For i = 1 To 10 |
|||
nth_difference(a(), b(), i) |
|||
PrintN(Str(i) + " [" + display(b()) + "]") |
|||
Next |
|||
Print(#CRLF$ + #CRLF$ + "Press ENTER to exit"): Input() |
|||
CloseConsole() |
|||
EndIf |
|||
</syntaxhighlight> |
|||
{{out}} |
|||
<pre>1 [43,-11,29,7,-10,-23,50,-50,-18] |
|||
2 [54,-40,22,17,13,-73,100,-32] |
|||
3 [94,-62,5,4,86,-173,132] |
|||
4 [156,-67,1,-82,259,-305] |
|||
5 [223,-68,83,-341,564] |
|||
6 [291,-151,424,-905] |
|||
7 [442,-575,1329] |
|||
8 [1017,-1904] |
|||
9 [2921] |
|||
10 []</pre> |
|||
=={{header|Python}}== |
=={{header|Python}}== |
||
===Python 2=== |
|||
<python> |
|||
<syntaxhighlight lang="python">>>> dif = lambda s: [x-s[i] for i,x in enumerate(s[1:])] |
|||
>>> # or, dif = lambda s: [x-y for x,y in zip(s[1:],s)] |
|||
>>> difn = lambda s, n: difn(dif(s), n-1) if n else s |
|||
>>> s = [90, 47, 58, 29, 22, 32, 55, 5, 55, 73] |
|||
>>> difn(s, 0) |
|||
[90, 47, 58, 29, 22, 32, 55, 5, 55, 73] |
|||
>>> difn(s, 1) |
|||
[-43, 11, -29, -7, 10, 23, -50, 50, 18] |
|||
>>> difn(s, 2) |
|||
[54, -40, 22, 17, 13, -73, 100, -32] |
|||
>>> from pprint import pprint |
|||
>>> pprint( [difn(s, i) for i in xrange(10)] ) |
|||
[[90, 47, 58, 29, 22, 32, 55, 5, 55, 73], |
|||
[-43, 11, -29, -7, 10, 23, -50, 50, 18], |
|||
[54, -40, 22, 17, 13, -73, 100, -32], |
|||
[-94, 62, -5, -4, -86, 173, -132], |
|||
[156, -67, 1, -82, 259, -305], |
|||
[-223, 68, -83, 341, -564], |
|||
[291, -151, 424, -905], |
|||
[-442, 575, -1329], |
|||
[1017, -1904], |
|||
[-2921]]</syntaxhighlight> |
|||
===Python 3=== |
|||
Defining functions for first order and nth order forward difference: |
|||
{{Works with|Python|3.7}} |
|||
<syntaxhighlight lang="python">'''Forward difference''' |
|||
from itertools import islice |
|||
from operator import sub |
|||
# forwardDifference :: Num a => [a] -> [a] |
|||
def forwardDifference(xs): |
|||
'''1st order forward difference of xs. |
|||
''' |
|||
return [sub(*x) for x in zip(xs[1:], xs)] |
|||
# nthForwardDifference :: Num a => [a] -> Int -> [a] |
|||
def nthForwardDifference(xs): |
|||
'''Nth order forward difference of xs. |
|||
''' |
|||
return index(iterate(forwardDifference)(xs)) |
|||
# ------------------------- TEST -------------------------- |
|||
# main :: IO () |
|||
def main(): |
|||
'''Nth order forward difference.''' |
|||
xs = [90, 47, 58, 29, 22, 32, 55, 5, 55, 73] |
|||
print('9th order forward difference of:') |
|||
print(xs) |
|||
print('') |
|||
print( |
|||
' -> ' + repr(nthForwardDifference(xs)(9)) |
|||
) |
|||
print('\nSuccessive orders of forward difference:') |
|||
print(unlines([ |
|||
str(i) + ' -> ' + repr(x) for i, x in |
|||
enumerate(take(10)( |
|||
iterate(forwardDifference)(xs) |
|||
)) |
|||
])) |
|||
# ------------------- GENERIC FUNCTIONS ------------------- |
|||
# index (!!) :: [a] -> Int -> a |
|||
def index(xs): |
|||
'''Item at given (zero-based) index.''' |
|||
return lambda n: None if 0 > n else ( |
|||
xs[n] if ( |
|||
hasattr(xs, "__getitem__") |
|||
) else next(islice(xs, n, None)) |
|||
) |
|||
# iterate :: (a -> a) -> a -> Gen [a] |
|||
def iterate(f): |
|||
'''An infinite list of repeated |
|||
applications of f to x. |
|||
''' |
|||
def go(x): |
|||
v = x |
|||
while True: |
|||
yield v |
|||
v = f(v) |
|||
return go |
|||
# take :: Int -> [a] -> [a] |
|||
# take :: Int -> String -> String |
|||
def take(n): |
|||
'''The prefix of xs of length n, |
|||
or xs itself if n > length xs. |
|||
''' |
|||
return lambda xs: ( |
|||
xs[0:n] |
|||
if isinstance(xs, (list, tuple)) |
|||
else list(islice(xs, n)) |
|||
) |
|||
# unlines :: [String] -> String |
|||
def unlines(xs): |
|||
'''A single string formed by the intercalation |
|||
of a list of strings with the newline character. |
|||
''' |
|||
return '\n'.join(xs) |
|||
# MAIN --- |
|||
if __name__ == '__main__': |
|||
main()</syntaxhighlight> |
|||
{{Out}} |
|||
<pre>9th order forward difference of: |
|||
[90, 47, 58, 29, 22, 32, 55, 5, 55, 73] |
|||
-> [-2921] |
|||
Successive orders of forward difference: |
|||
0 -> [90, 47, 58, 29, 22, 32, 55, 5, 55, 73] |
|||
1 -> [-43, 11, -29, -7, 10, 23, -50, 50, 18] |
|||
2 -> [54, -40, 22, 17, 13, -73, 100, -32] |
|||
3 -> [-94, 62, -5, -4, -86, 173, -132] |
|||
4 -> [156, -67, 1, -82, 259, -305] |
|||
5 -> [-223, 68, -83, 341, -564] |
|||
6 -> [291, -151, 424, -905] |
|||
7 -> [-442, 575, -1329] |
|||
8 -> [1017, -1904] |
|||
9 -> [-2921]</pre> |
|||
=={{header|Quackery}}== |
|||
<syntaxhighlight lang="quackery"> [ times |
|||
[ [] swap behead |
|||
swap witheach |
|||
[ tuck dip [ - join ] ] |
|||
drop ] ] is f-diff ( [ n --> [ ) |
|||
' [ 90 47 58 29 22 32 55 5 55 73 ] |
|||
dup size times |
|||
[ dup i^ |
|||
dup echo say ": " |
|||
f-diff echo cr ] |
|||
drop</syntaxhighlight> |
|||
{{out}} |
|||
<pre>0: [ 90 47 58 29 22 32 55 5 55 73 ] |
|||
1: [ -43 11 -29 -7 10 23 -50 50 18 ] |
|||
2: [ 54 -40 22 17 13 -73 100 -32 ] |
|||
3: [ -94 62 -5 -4 -86 173 -132 ] |
|||
4: [ 156 -67 1 -82 259 -305 ] |
|||
5: [ -223 68 -83 341 -564 ] |
|||
6: [ 291 -151 424 -905 ] |
|||
7: [ -442 575 -1329 ] |
|||
8: [ 1017 -1904 ] |
|||
9: [ -2921 ] |
|||
</pre> |
|||
=={{header|R}}== |
|||
<syntaxhighlight lang="r">forwarddif <- function(a, n) { |
|||
if ( n == 1 ) |
|||
a[2:length(a)] - a[1:length(a)-1] |
|||
else { |
|||
r <- forwarddif(a, 1) |
|||
forwarddif(r, n-1) |
|||
} |
|||
} |
|||
fdiff <- function(a, n) { |
|||
r <- a |
|||
for(i in 1:n) { |
|||
r <- r[2:length(r)] - r[1:length(r)-1] |
|||
} |
|||
r |
|||
} |
|||
v <- c(90, 47, 58, 29, 22, 32, 55, 5, 55, 73) |
|||
print(forwarddif(v, 9)) |
|||
print(fdiff(v, 9))</syntaxhighlight> |
|||
=={{header|Racket}}== |
|||
<syntaxhighlight lang="racket"> |
|||
#lang racket |
|||
(define (forward-difference list) |
|||
(for/list ([x (cdr list)] [y list]) (- x y))) |
|||
(define (nth-forward-difference n list) |
|||
(for/fold ([list list]) ([n n]) (forward-difference list))) |
|||
(nth-forward-difference 9 '(90 47 58 29 22 32 55 5 55 73)) |
|||
;; -> '(-2921) |
|||
</syntaxhighlight> |
|||
=={{header|Raku}}== |
|||
(formerly Perl 6) |
|||
{{works with|Rakudo Star|2010-07}} |
|||
<p>Here we use signature matching to bind both an entire array and a version missing the head. |
|||
The Z- operator is a zip metaoperator with a minus to subtract the two lists pairwise. |
|||
It's almost a shame to define difn, since the series and subscript are hardly longer than the call itself would be, and arguably more self-documenting than the name of the function would be. |
|||
<syntaxhighlight lang="raku" line>sub dif(@array [$, *@tail]) { @tail Z- @array } |
|||
sub difn($array, $n) { ($array, &dif ... *)[$n] }</syntaxhighlight> |
|||
=={{header|REXX}}== |
|||
===no error checking=== |
|||
The REXX version uses the same (input) numbers (for the default) as the '''Ada''' example. |
|||
This version allows a specification of the list of numbers and/or which ''order'' to process. |
|||
<syntaxhighlight lang="rexx">/*REXX program computes the forward difference of a list of numbers. */ |
|||
numeric digits 100 /*ensure enough accuracy (decimal digs)*/ |
|||
parse arg e ',' N /*get a list: ε1 ε2 ε3 ε4 ··· , order */ |
|||
if e=='' then e=90 47 58 29 22 32 55 5 55 73 /*Not specified? Then use the default.*/ |
|||
#=words(e) /*# is the number of elements in list.*/ |
|||
/* [↓] assign list numbers to @ array.*/ |
|||
do i=1 for #; @.i=word(e, i)/1; end /*i*/ /*process each number one at a time. */ |
|||
/* [↓] process the optional order. */ |
|||
if N=='' then parse value 0 # # with bot top N /*define the default order range. */ |
|||
else parse var N bot 1 top /*Not specified? Then use only 1 order*/ |
|||
say right(# 'numbers:', 44) e /*display the header title and ··· */ |
|||
say left('', 44)copies('─', length(e)+2) /* " " " fence. */ |
|||
/* [↓] where da rubber meets da road. */ |
|||
do o=bot to top; do r=1 for #; !.r=@.r; end /*r*/; $= |
|||
do j=1 for o; d=!.j; do k=j+1 to #; parse value !.k !.k-d with d !.k; end /*k*/ |
|||
end /*j*/ |
|||
do i=o+1 to #; $=$ !.i/1; end /*i*/ |
|||
if $=='' then $=' [null]' |
|||
say right(o, 7)th(o)'─order forward difference vector =' $ |
|||
end /*o*/ |
|||
exit /*stick a fork in it, we're all done. */ |
|||
/*──────────────────────────────────────────────────────────────────────────────────────*/ |
|||
th: procedure; x=abs(arg(1)); return word('th st nd rd',1+x//10*(x//100%10\==1)*(x//10<4))</syntaxhighlight> |
|||
'''output''' when using the default input: |
|||
<pre> |
|||
10 numbers: 90 47 58 29 22 32 55 5 55 73 |
|||
────────────────────────────── |
|||
0th-order forward difference vector = 90 47 58 29 22 32 55 5 55 73 |
|||
1st-order forward difference vector = -43 11 -29 -7 10 23 -50 50 18 |
|||
2nd-order forward difference vector = 54 -40 22 17 13 -73 100 -32 |
|||
3rd-order forward difference vector = -94 62 -5 -4 -86 173 -132 |
|||
4th-order forward difference vector = 156 -67 1 -82 259 -305 |
|||
5th-order forward difference vector = -223 68 -83 341 -564 |
|||
6th-order forward difference vector = 291 -151 424 -905 |
|||
7th-order forward difference vector = -442 575 -1329 |
|||
8th-order forward difference vector = 1017 -1904 |
|||
9th-order forward difference vector = -2921 |
|||
10th-order forward difference vector = [null] |
|||
</pre> |
|||
'''output''' when the '''Tcl''''s input was used: <tt> 90.5 47 58 29 22 32 55 5 55 73.5 </tt> |
|||
<pre> |
|||
10 numbers: 90.5 47 58 29 22 32 55 5 55 73.5 |
|||
────────────────────────────────── |
|||
0th-order forward difference vector = 90.5 47 58 29 22 32 55 5 55 73.5 |
|||
1st-order forward difference vector = -43.5 11 -29 -7 10 23 -50 50 18.5 |
|||
2nd-order forward difference vector = 54.5 -40 22 17 13 -73 100 -31.5 |
|||
3rd-order forward difference vector = -94.5 62 -5 -4 -86 173 -131.5 |
|||
4th-order forward difference vector = 156.5 -67 1 -82 259 -304.5 |
|||
5th-order forward difference vector = -223.5 68 -83 341 -563.5 |
|||
6th-order forward difference vector = 291.5 -151 424 -904.5 |
|||
7th-order forward difference vector = -442.5 575 -1328.5 |
|||
8th-order forward difference vector = 1017.5 -1903.5 |
|||
9th-order forward difference vector = -2921 |
|||
10th-order forward difference vector = [null] |
|||
</pre> |
|||
===with error checking=== |
|||
<syntaxhighlight lang="rexx">/*REXX program computes the forward difference of a list of numbers. */ |
|||
numeric digits 100 /*ensure enough accuracy (decimal digs)*/ |
|||
parse arg e ',' N /*get a list: ε1 ε2 ε3 ε4 ··· , order */ |
|||
if e=='' then e=90 47 58 29 22 32 55 5 55 73 /*Not specified? Then use the default.*/ |
|||
#=words(e) /*# is the number of elements in list.*/ |
|||
/* [↓] verify list items are numeric. */ |
|||
do i=1 for #; _=word(e, i) /*process each number one at a time. */ |
|||
if \datatype(_, 'N') then call ser _ "isn't a valid number"; @.i=_/1 |
|||
end /*i*/ /* [↑] removes superfluous stuff. */ |
|||
/* [↓] process the optional order. */ |
|||
if N=='' then parse value 0 # # with bot top N /*define the default order range. */ |
|||
else parse var N bot 1 top /*Not specified? Then use only 1 order*/ |
|||
if #==0 then call ser "no numbers were specified." |
|||
if N<0 then call ser N "(order) can't be negative." |
|||
if N># then call ser N "(order) can't be greater than" # |
|||
say right(# 'numbers:', 44) e /*display the header (title) and ··· */ |
|||
say left('', 44)copies('─', length(e)+2) /*display the header fence. */ |
|||
/* [↓] where da rubber meets da road. */ |
|||
do o=bot to top; do r=1 for #; !.r=@.r; end /*r*/; $= |
|||
do j=1 for o; d=!.j; do k=j+1 to #; parse value !.k !.k-d with d !.k; end /*k*/ |
|||
end /*j*/ |
|||
do i=o+1 to #; $=$ !.i/1; end /*i*/ |
|||
if $=='' then $=' [null]' |
|||
say right(o, 7)th(o)'─order forward difference vector =' $ |
|||
end /*o*/ |
|||
exit /*stick a fork in it, we're all done. */ |
|||
/*──────────────────────────────────────────────────────────────────────────────────────*/ |
|||
ser: say; say '***error***'; say arg(1); say; exit 13 |
|||
th: procedure; x=abs(arg(1)); return word('th st nd rd',1+x//10*(x//100%10\==1)*(x//10<4))</syntaxhighlight> |
|||
'''output''' is the same as the REXX entry above. |
|||
===with output alignment=== |
|||
<syntaxhighlight lang="rexx">/*REXX program computes the forward difference of a list of numbers. */ |
|||
numeric digits 100 /*ensure enough accuracy (decimal digs)*/ |
|||
parse arg e ',' N /*get a list: ε1 ε2 ε3 ε4 ··· , order */ |
|||
if e=='' then e=90 47 58 29 22 32 55 5 55 73 /*Not specified? Then use the default.*/ |
|||
#=words(e); w=5 /*# is the number of elements in list.*/ |
|||
/* [↓] verify list items are numeric. */ |
|||
do i=1 for #; _=word(e, i) /*process each number one at a time. */ |
|||
if \datatype(_, 'N') then call ser _ "isn't a valid number"; @.i=_/1 |
|||
w=max(w, length(@.i)) /*use the maximum length of an element.*/ |
|||
end /*i*/ /* [↑] removes superfluous stuff. */ |
|||
/* [↓] process the optional order. */ |
|||
if N=='' then parse value 0 # # with bot top N /*define the default order range. */ |
|||
else parse var N bot 1 top /*Not specified? Then use only 1 order*/ |
|||
if #==0 then call ser "no numbers were specified." |
|||
if N<0 then call ser N "(order) can't be negative." |
|||
if N># then call ser N "(order) can't be greater than" # |
|||
_=; do k=1 for #; _=_ right(@.k, w); end /*k*/; _=substr(_, 2) |
|||
say right(# 'numbers:', 44) _ /*display the header title and ··· */ |
|||
say left('', 44)copies('─', w*#+#) /* " " " fence. */ |
|||
/* [↓] where da rubber meets da road. */ |
|||
do o=bot to top; do r=1 for #; !.r=@.r; end /*r*/; $= |
|||
do j=1 for o; d=!.j; do k=j+1 to #; parse value !.k !.k-d with d !.k |
|||
w=max(w, length(!.k)) |
|||
end /*k*/ |
|||
end /*j*/ |
|||
do i=o+1 to #; $=$ right(!.i/1, w); end /*i*/ |
|||
if $=='' then $=' [null]' |
|||
say right(o, 7)th(o)'─order forward difference vector =' $ |
|||
end /*o*/ |
|||
exit /*stick a fork in it, we're all done. */ |
|||
/*──────────────────────────────────────────────────────────────────────────────────────*/ |
|||
ser: say; say '***error***'; say arg(1); say; exit 13 |
|||
th: procedure; x=abs(arg(1)); return word('th st nd rd',1+x//10*(x//100%10\==1)*(x//10<4))</syntaxhighlight> |
|||
'''output''' when using the default input: |
|||
<pre> |
|||
10 numbers: 90 47 58 29 22 32 55 5 55 73 |
|||
──────────────────────────────────────────────────────────── |
|||
0th─order forward difference vector = 90 47 58 29 22 32 55 5 55 73 |
|||
1st─order forward difference vector = -43 11 -29 -7 10 23 -50 50 18 |
|||
2nd─order forward difference vector = 54 -40 22 17 13 -73 100 -32 |
|||
3rd─order forward difference vector = -94 62 -5 -4 -86 173 -132 |
|||
4th─order forward difference vector = 156 -67 1 -82 259 -305 |
|||
5th─order forward difference vector = -223 68 -83 341 -564 |
|||
6th─order forward difference vector = 291 -151 424 -905 |
|||
7th─order forward difference vector = -442 575 -1329 |
|||
8th─order forward difference vector = 1017 -1904 |
|||
9th─order forward difference vector = -2921 |
|||
10th─order forward difference vector = [null] |
|||
</pre> |
|||
===Version 2=== |
|||
<syntaxhighlight lang="rexx">/* REXX *************************************************************** |
|||
* Forward differences |
|||
* 18.08.2012 Walter Pachl derived from PL/I |
|||
**********************************************************************/ |
|||
Do n=-1 To 11 |
|||
Call differences '90 47 58 29 22 32 55 5 55 73',n |
|||
End |
|||
Exit |
|||
differences: Procedure |
|||
Parse Arg a,n |
|||
m=words(a) |
|||
Select |
|||
When n<0 Then Say 'n is negative:' n '<' 0 |
|||
When n>m Then Say 'n is too large:' n '>' m |
|||
Otherwise Do |
|||
Do i=1 By 1 while a<>'' |
|||
Parse Var a a.i a |
|||
End |
|||
Do i = 1 to n; |
|||
t = a.i; |
|||
Do j = i+1 to m; |
|||
u = a.j |
|||
a.j = a.j-t; |
|||
t = u; |
|||
end; |
|||
end; |
|||
ol='' |
|||
Do k=n+1 to m |
|||
ol=ol a.k |
|||
End |
|||
Say n ol |
|||
End |
|||
End |
|||
Return</syntaxhighlight> |
|||
{{out}} for Java's input |
|||
<pre> |
|||
n is negative: -1 < 0 |
|||
0 90 47 58 29 22 32 55 5 55 73 |
|||
1 -43 11 -29 -7 10 23 -50 50 18 |
|||
2 54 -40 22 17 13 -73 100 -32 |
|||
3 -94 62 -5 -4 -86 173 -132 |
|||
4 156 -67 1 -82 259 -305 |
|||
5 -223 68 -83 341 -564 |
|||
6 291 -151 424 -905 |
|||
7 -442 575 -1329 |
|||
8 1017 -1904 |
|||
9 -2921 |
|||
10 |
|||
n is too large: 11 > 10 |
|||
</pre> |
|||
=={{header|Ring}}== |
|||
<syntaxhighlight lang="ring"> |
|||
# Project : Forward difference |
|||
s = [90, 47, 58, 29, 22, 32, 55, 5, 55, 73] |
|||
for p = 1 to 9 |
|||
s = fwddiff(s) |
|||
showarray(s) |
|||
next |
|||
func fwddiff(s) |
|||
for j=1 to len(s)-1 |
|||
s[j] = s[j+1]-s[j] |
|||
next |
|||
n = len(s) |
|||
del(s, n) |
|||
return s |
|||
func showarray(vect) |
|||
see "{" |
|||
svect = "" |
|||
for n = 1 to len(vect) |
|||
svect = svect + vect[n] + ", " |
|||
next |
|||
svect = left(svect, len(svect) - 2) |
|||
see svect |
|||
see "}" + nl |
|||
</syntaxhighlight> |
|||
Output: |
|||
<pre> |
|||
{-43, 11, -29, -7, 10, 23, -50, 50, 18} |
|||
{54, -40, 22, 17, 13, -73, 100, -32} |
|||
{-94, 62, -5, -4, -86, 173, -132} |
|||
{156, -67, 1, -82, 259, -305} |
|||
{-223, 68, -83, 341, -564} |
|||
{291, -151, 424, -905} |
|||
{-442, 575, -1329} |
|||
{1017, -1904} |
|||
{-2921} |
|||
</pre> |
|||
=={{header|RPL}}== |
|||
===Iterative approach=== |
|||
{| class="wikitable" ≪ |
|||
! RPL code |
|||
! Comment |
|||
|- |
|||
| |
|||
≪ |
|||
'''IF''' OVER SIZE OVER > '''THEN''' |
|||
'''WHILE''' DUP '''REPEAT''' |
|||
SWAP { } 2 3 PICK SIZE '''FOR''' j |
|||
OVER j GET + '''NEXT''' |
|||
LIST→ →ARRY |
|||
SWAP OVER SIZE { } + RDM - |
|||
SWAP 1 - '''END''' |
|||
DROP '''END''' |
|||
≫ ‘<span style="color:blue">DIFFN</span>’ STO |
|||
| |
|||
<span style="color:blue">DIFFN</span> ''( [array] order → [nth_difference] ) '' |
|||
if order < array size |
|||
while order > 0 |
|||
initialize loop |
|||
to build { array[2]...array[n] } |
|||
convert list into array |
|||
pop last item of array and substract |
|||
order -= 1 |
|||
clean stack |
|||
|} |
|||
[90, 47, 58, 29, 22, 32, 55, 5, 55, 73] 1 <span style="color:blue">DIFFN</span> |
|||
[90, 47, 58, 29, 22, 32, 55, 5, 55, 73] 3 <span style="color:blue">DIFFN</span> |
|||
{{out}} |
|||
<pre> |
|||
2: [-43, 11, -29, -7, 10, 23, -50, 50, 18] |
|||
1: [-94, 62, -5, -4, -86, 173, -132] |
|||
</pre> |
|||
===Direct approach=== |
|||
We use here local variables and algebraic notation to increase code readability. |
|||
{| class="wikitable" ≪ |
|||
! RPL code |
|||
! Comment |
|||
|- |
|||
| |
|||
≪ → n |
|||
≪ '<span style="color:green">F</span>' STO |
|||
{ } 1 <span style="color:green">F</span> SIZE 1 - '''FOR''' j |
|||
-1 n ^ '<span style="color:green">F</span>' j GET * |
|||
1 n '''FOR''' k |
|||
'COMB(n,k)*(-1)^(n-k)*<span style="color:green">F</span>(j+k)' EVAL + |
|||
'''NEXT''' |
|||
+ '''NEXT''' |
|||
LIST→ →ARRY '<span style="color:green">F</span>' PURGE |
|||
≫ ≫ ‘<span style="color:blue">DIFFN</span>’ STO |
|||
| |
|||
<span style="color:blue">DIFFN</span> ''( [array] order → [nth_difference] ) '' |
|||
store array in global variable F |
|||
initialize output array building loop |
|||
put 1st term of sum (k=0) in stack // reverse Polish notation |
|||
loop |
|||
add terms for 0<k≤n // algebraic notation |
|||
add sum to list |
|||
>>> s = [90, 47, 58, 29, 22, 32, 55, 5, 55, 73] |
|||
convert list into array, clean memory |
|||
>>> difn(s, 0) |
|||
[90, 47, 58, 29, 22, 32, 55, 5, 55, 73] |
|||
|} |
|||
>>> difn(s, 1) |
|||
Postfix fans can replace the following line |
|||
[-43, 11, -29, -7, 10, 23, -50, 50, 18] |
|||
'COMB(n,k)*(-1)^(n-k)*<span style="color:green">F</span>(j+k)' EVAL + '''NEXT''' |
|||
>>> difn(s, 2) |
|||
by |
|||
[54, -40, 22, 17, 13, -73, 100, -32] |
|||
n k COMB -1 n k - ^ * '<span style="color:green">F</span>' j k + GET * + '''NEXT''' |
|||
On HP-48G and newer models, first difference is directly returned by the <code>ΔLIST</code> instruction, so we can simplify the above code, provided that input is given as a list { } instead of an array [ ]: |
|||
>>> from pprint import pprint |
|||
≪ 1 SWAP '''START''' ΔLIST '''NEXT''' ≫ ‘<span style="color:blue">DIFFN</span>’ STO |
|||
>>> pprint( [difn(s, i) for i in xrange(10)] ) |
|||
[[90, 47, 58, 29, 22, 32, 55, 5, 55, 73], |
|||
[-43, 11, -29, -7, 10, 23, -50, 50, 18], |
|||
=={{header|Ruby}}== |
|||
[54, -40, 22, 17, 13, -73, 100, -32], |
|||
This code uses new features from Ruby 1.8.7: |
|||
[-94, 62, -5, -4, -86, 173, -132], |
|||
[156, -67, 1, -82, 259, -305], |
|||
* Enumerable#each_cons is a new method. |
|||
[-223, 68, -83, 341, -564], |
|||
* Integer#times, without a block, returns an enumerator. |
|||
[291, -151, 424, -905], |
|||
[-442, 575, -1329], |
|||
{{works with|Ruby|1.8.7}} |
|||
[1017, -1904], |
|||
<syntaxhighlight lang="ruby">def dif(s) |
|||
[-2921]] |
|||
s.each_cons(2).collect { |x, y| y - x } |
|||
</python> |
|||
end |
|||
def difn(s, n) |
|||
n.times.inject(s) { |s, | dif(s) } |
|||
end</syntaxhighlight> |
|||
{{out|Example usage}} |
|||
<syntaxhighlight lang="ruby">p dif([1, 23, 45, 678]) # => [22, 22, 633] |
|||
p difn([1, 23, 45, 678], 2) # => [0, 611]</syntaxhighlight> |
|||
=={{header|Rust}}== |
|||
<syntaxhighlight lang="rust"> |
|||
fn forward_difference(input_seq: Vec<i32>, order: u32) -> Vec<i32> { |
|||
match order { |
|||
0 => input_seq, |
|||
1 => { |
|||
let input_seq_iter = input_seq.into_iter(); |
|||
let clone_of_input_seq_iter = input_seq_iter.clone(); |
|||
input_seq_iter.zip(clone_of_input_seq_iter.skip(1)).map(|(current, next)| next - current).collect() |
|||
}, |
|||
_ => forward_difference(forward_difference(input_seq, order - 1), 1), |
|||
} |
|||
} |
|||
fn main() { |
|||
let mut sequence = vec![90, 47, 58, 29, 22, 32, 55, 5, 55, 73]; |
|||
loop { |
|||
println!("{:?}", sequence); |
|||
sequence = forward_difference(sequence, 1); |
|||
if sequence.is_empty() { |
|||
break; |
|||
} |
|||
} |
|||
} |
|||
</syntaxhighlight> |
|||
{{out}} |
|||
<pre> |
|||
[90, 47, 58, 29, 22, 32, 55, 5, 55, 73] |
|||
[-43, 11, -29, -7, 10, 23, -50, 50, 18] |
|||
[54, -40, 22, 17, 13, -73, 100, -32] |
|||
[-94, 62, -5, -4, -86, 173, -132] |
|||
[156, -67, 1, -82, 259, -305] |
|||
[-223, 68, -83, 341, -564] |
|||
[291, -151, 424, -905] |
|||
[-442, 575, -1329] |
|||
[1017, -1904] |
|||
[-2921] |
|||
</pre> |
|||
=={{header|Scala}}== |
|||
<syntaxhighlight lang="scala">def fdiff(xs: List[Int]) = (xs.tail, xs).zipped.map(_ - _) |
|||
def fdiffn(i: Int, xs: List[Int]): List[Int] = if (i == 1) fdiff(xs) else fdiffn(i - 1, fdiff(xs))</syntaxhighlight> |
|||
{{out|Example}} |
|||
<syntaxhighlight lang="scala">val l=List(90,47,58,29,22,32,55,5,55,73) |
|||
(1 to 9)foreach(x=>println(fdiffn(x,l)))</syntaxhighlight> |
|||
{{out}} |
|||
<pre> |
|||
List(-43, 11, -29, -7, 10, 23, -50, 50, 18) |
|||
List(54, -40, 22, 17, 13, -73, 100, -32) |
|||
List(-94, 62, -5, -4, -86, 173, -132) |
|||
List(156, -67, 1, -82, 259, -305) |
|||
List(-223, 68, -83, 341, -564) |
|||
List(291, -151, 424, -905) |
|||
List(-442, 575, -1329) |
|||
List(1017, -1904) |
|||
List(-2921) |
|||
</pre> |
|||
=={{header|Scheme}}== |
=={{header|Scheme}}== |
||
<scheme>(define (forward-diff lst) |
<syntaxhighlight lang="scheme">(define (forward-diff lst) |
||
(if (or (null? lst) (null? (cdr lst))) |
(if (or (null? lst) (null? (cdr lst))) |
||
'() |
'() |
||
Line 510: | Line 3,205: | ||
xs |
xs |
||
(nth-forward-diff (- n 1) |
(nth-forward-diff (- n 1) |
||
(forward-diff xs))))</ |
(forward-diff xs))))</syntaxhighlight> |
||
Output: |
|||
{{out}} |
|||
<pre> |
<pre> |
||
> (nth-forward-diff 9 '(90 47 58 29 22 32 55 5 55 73)) |
> (nth-forward-diff 9 '(90 47 58 29 22 32 55 5 55 73)) |
||
(-2921) |
(-2921) |
||
</pre> |
</pre> |
||
=={{header|Seed7}}== |
|||
<syntaxhighlight lang="seed7">$ include "seed7_05.s7i"; |
|||
const func array integer: forwardDifference (in array integer: data) is func |
|||
result |
|||
var array integer: diffResult is 0 times 0; |
|||
local |
|||
var integer: index is 0; |
|||
begin |
|||
for index range 1 to pred(length(data)) do |
|||
diffResult &:= -data[index] + data[succ(index)]; |
|||
end for; |
|||
end func; |
|||
const proc: main is func |
|||
local |
|||
var array integer: data is [] (90, 47, 58, 29, 22, 32, 55, 5, 55, 73); |
|||
var integer: level is 0; |
|||
var integer: number is 0; |
|||
var boolean: firstElement is TRUE; |
|||
begin |
|||
for level range 0 to length(data) do |
|||
firstElement := TRUE; |
|||
for number range data do |
|||
if not firstElement then |
|||
write(", "); |
|||
end if; |
|||
firstElement := FALSE; |
|||
write(number); |
|||
end for; |
|||
writeln; |
|||
data := forwardDifference(data); |
|||
end for; |
|||
end func;</syntaxhighlight> |
|||
{{out}} |
|||
<pre> |
|||
90, 47, 58, 29, 22, 32, 55, 5, 55, 73 |
|||
-43, 11, -29, -7, 10, 23, -50, 50, 18 |
|||
54, -40, 22, 17, 13, -73, 100, -32 |
|||
-94, 62, -5, -4, -86, 173, -132 |
|||
156, -67, 1, -82, 259, -305 |
|||
-223, 68, -83, 341, -564 |
|||
291, -151, 424, -905 |
|||
-442, 575, -1329 |
|||
1017, -1904 |
|||
-2921 |
|||
</pre> |
|||
=={{header|SequenceL}}== |
|||
Solution that keeps track of intermediate values: |
|||
<syntaxhighlight lang="sequencel"> |
|||
forwardDifference(x(1), n) := forwardDifferenceHelper(x, n, [x]); |
|||
forwardDifferenceHelper(x(1), n, result(2)) := |
|||
let |
|||
difference := tail(x) - x[1 ... size(x) - 1]; |
|||
in |
|||
result when n = 0 or size(x) = 1 else |
|||
forwardDifferenceHelper(difference, n - 1, result ++ [difference]); |
|||
</syntaxhighlight> |
|||
If no intermediate values are needed, the following is sufficient: |
|||
<syntaxhighlight lang="sequencel"> |
|||
forwardDifference(x(1),n) := |
|||
x when n = 0 or size(x) = 1 else |
|||
forwardDifference(tail(x) - x[1 ... size(x) - 1], n - 1); |
|||
</syntaxhighlight> |
|||
=={{header|Sidef}}== |
|||
<syntaxhighlight lang="ruby">func dif(arr) { |
|||
gather { |
|||
for i (0 ..^ arr.end) { |
|||
take(arr[i+1] - arr[i]) |
|||
} |
|||
} |
|||
} |
|||
func difn(n, arr) { |
|||
{ arr = dif(arr) } * n |
|||
arr |
|||
} |
|||
say dif([1, 23, 45, 678]) # => [22, 22, 633] |
|||
say difn(2, [1, 23, 45, 678]) # => [0, 611]</syntaxhighlight> |
|||
=={{header|Slate}}== |
|||
<syntaxhighlight lang="slate">s@(Sequence traits) forwardDifference |
|||
[ |
|||
s allButFirst with: s allButLast collect: #- `er |
|||
]. |
|||
s@(Sequence traits) forwardDifference |
|||
"Without creating two intermediate throwaway Sequences." |
|||
[ |
|||
result ::= s allButFirst. |
|||
result doWithIndex: [| :nextValue :index | result at: index infect: [| :oldValue | oldValue - (s at: index)]. |
|||
result |
|||
]. |
|||
s@(Sequence traits) forwardDifference: n |
|||
[ |
|||
(0 below: n) inject: s into: [| :seq :_ | seq forwardDifference] |
|||
].</syntaxhighlight> |
|||
{{out|Usage}} |
|||
<syntaxhighlight lang="slate">#data := ##(90 47 58 29 22 32 55 5 55 73). |
|||
data keysDo: [| :index | inform: (data forwardDifference: index) printString].</syntaxhighlight> |
|||
=={{header|Smalltalk}}== |
=={{header|Smalltalk}}== |
||
{{works with|GNU Smalltalk}} |
|||
<syntaxhighlight lang="smalltalk">Array extend [ |
|||
This version runs on [[GNU Smalltalk]]. Other implementations might lack some of the utility methods we use: |
|||
difference [ |
|||
^self allButFirst with: self allButLast collect: [ :a :b | a - b ] |
|||
] |
|||
nthOrderDifference: n [ |
|||
Array extend [ |
|||
^(1 to: n) inject: self into: [ :old :unused | old difference ] |
|||
difference [ |
|||
] |
|||
^self allButFirst with: self allButLast collect: [ :a :b | a - b ] |
|||
] |
|||
] |
|||
s := #(90 47 58 29 22 32 55 5 55 73) |
|||
nthOrderDifference: n [ |
|||
1 to: s size - 1 do: [ :i | |
|||
(s nthOrderDifference: i) printNl ]</syntaxhighlight> |
|||
] |
|||
] |
|||
=={{header|SQL}}== |
|||
s := #(90 47 58 29 22 32 55 5 55 73) |
|||
{{works with|SQLite|3.13.0}} |
|||
1 to: s size - 1 do: [ :i | |
|||
(s nthOrderDifference: i) printNl ] |
|||
<syntaxhighlight lang="sql">WITH RECURSIVE |
|||
T0 (N, ITEM, LIST, NEW_LIST) AS |
|||
( |
|||
SELECT 1, |
|||
NULL, |
|||
'90,47,58,29,22,32,55,5,55,73' || ',', |
|||
NULL |
|||
UNION ALL |
|||
SELECT CASE |
|||
WHEN SUBSTR(LIST, INSTR(LIST, ',') + 1, LENGTH(LIST)) = '' |
|||
THEN N + 1 |
|||
ELSE N |
|||
END, |
|||
CASE |
|||
WHEN SUBSTR(LIST, INSTR(LIST, ',') + 1, LENGTH(LIST)) <> '' |
|||
THEN SUBSTR(LIST, 1, INSTR(LIST, ',') - 1) |
|||
ELSE NULL |
|||
END, |
|||
CASE |
|||
WHEN SUBSTR(LIST, INSTR(LIST, ',') + 1, LENGTH(LIST)) = '' |
|||
THEN IFNULL(NEW_LIST || (SUBSTR(LIST, 1, INSTR(LIST, ',') - 1) - ITEM) || ',', '') |
|||
ELSE SUBSTR(LIST, INSTR(LIST, ',') + 1, LENGTH(LIST)) |
|||
END, |
|||
CASE |
|||
WHEN SUBSTR(LIST, INSTR(LIST, ',') + 1, LENGTH(LIST)) <> '' |
|||
THEN IFNULL(NEW_LIST, '') || IFNULL((SUBSTR(LIST, 1, INSTR(LIST, ',') - 1) - ITEM) || ',', '') |
|||
ELSE NULL |
|||
END |
|||
FROM T0 |
|||
WHERE INSTR(LIST, ',') > 0 |
|||
) |
|||
SELECT N, |
|||
TRIM(LIST, ',') LIST |
|||
FROM T0 |
|||
WHERE NEW_LIST IS NULL |
|||
AND LIST <> '' |
|||
ORDER BY N;</syntaxhighlight> |
|||
=={{header|Standard ML}}== |
|||
<syntaxhighlight lang="sml">fun forward_difference xs = ListPair.map op- (tl xs, xs) |
|||
fun nth_forward_difference n xs = |
|||
if n = 0 then |
|||
xs |
|||
else |
|||
nth_forward_difference (n-1) (forward_difference xs)</syntaxhighlight> |
|||
{{out}} |
|||
<pre> |
|||
- nth_forward_difference 9 [90, 47, 58, 29, 22, 32, 55, 5, 55, 73]; |
|||
val it = [~2921] : int list |
|||
</pre> |
|||
=={{header|Stata}}== |
|||
It's possible to implement differences using row indices. For instance, first forward differences of a variable x can be defined by: |
|||
<syntaxhighlight lang="stata">gen y=x[_n+1]-x[_n]</syntaxhighlight> |
|||
However, it's much more natural to use [http://www.stata.com/help.cgi?tsvarlist time-series varlists]. In order to use them, it's necessary to first set a ''time'' variable, which may be simply an index variable. |
|||
<syntaxhighlight lang="stata">* First create a dataset |
|||
clear all |
|||
set obs 100 |
|||
gen i=_n |
|||
tsset i |
|||
gen x=rnormal() |
|||
* Differences |
|||
display "Difference order?" _request(k) |
|||
gen y=D${k}F${k}.x</syntaxhighlight> |
|||
=={{header|Swift}}== |
|||
<syntaxhighlight lang="swift">func forwardsDifference<T: SignedNumeric>(of arr: [T]) -> [T] { |
|||
return zip(arr.dropFirst(), arr).map({ $0.0 - $0.1 }) |
|||
} |
|||
func nthForwardsDifference<T: SignedNumeric>(of arr: [T], n: Int) -> [T] { |
|||
assert(n >= 0) |
|||
switch (arr, n) { |
|||
case ([], _): |
|||
return [] |
|||
case let (arr, 0): |
|||
return arr |
|||
case let (arr, i): |
|||
return nthForwardsDifference(of: forwardsDifference(of: arr), n: i - 1) |
|||
} |
|||
} |
|||
for diff in (0...9).map({ nthForwardsDifference(of: [90, 47, 58, 29, 22, 32, 55, 5, 55, 73], n: $0) }) { |
|||
print(diff) |
|||
}</syntaxhighlight> |
|||
{{out}} |
|||
<pre>[90, 47, 58, 29, 22, 32, 55, 5, 55, 73] |
|||
[-43, 11, -29, -7, 10, 23, -50, 50, 18] |
|||
[54, -40, 22, 17, 13, -73, 100, -32] |
|||
[-94, 62, -5, -4, -86, 173, -132] |
|||
[156, -67, 1, -82, 259, -305] |
|||
[-223, 68, -83, 341, -564] |
|||
[291, -151, 424, -905] |
|||
[-442, 575, -1329] |
|||
[1017, -1904] |
|||
[-2921]</pre> |
|||
=={{header|Tcl}}== |
|||
<syntaxhighlight lang="tcl">proc do_fwd_diff {list} { |
|||
set previous [lindex $list 0] |
|||
set new [list] |
|||
foreach current [lrange $list 1 end] { |
|||
lappend new [expr {$current - $previous}] |
|||
set previous $current |
|||
} |
|||
return $new |
|||
} |
|||
proc fwd_diff {list order} { |
|||
while {$order >= 1} { |
|||
set list [do_fwd_diff $list] |
|||
incr order -1 |
|||
} |
|||
return $list |
|||
} |
|||
set a {90.5 47 58 29 22 32 55 5 55 73.5} |
|||
for {set order 0} {$order <= 10} {incr order} { |
|||
puts [format "%d\t%s" $order [fwd_diff $a $order]] |
|||
}</syntaxhighlight> |
|||
{{out}} |
|||
<pre>0 90.5 47 58 29 22 32 55 5 55 73.5 |
|||
1 -43.5 11 -29 -7 10 23 -50 50 18.5 |
|||
2 54.5 -40 22 17 13 -73 100 -31.5 |
|||
3 -94.5 62 -5 -4 -86 173 -131.5 |
|||
4 156.5 -67 1 -82 259 -304.5 |
|||
5 -223.5 68 -83 341 -563.5 |
|||
6 291.5 -151 424 -904.5 |
|||
7 -442.5 575 -1328.5 |
|||
8 1017.5 -1903.5 |
|||
9 -2921.0 |
|||
10 </pre> |
|||
=={{header|Ursala}}== |
|||
This function doesn't need to be defined because it's in a library already, |
|||
but it could be defined like this: |
|||
<syntaxhighlight lang="ursala">#import std |
|||
#import nat |
|||
#import flo |
|||
nth_diff "n" = rep"n" minus*typ</syntaxhighlight> |
|||
test program: |
|||
<syntaxhighlight lang="ursala">test_data = <90.,47.,58.,29.,22.,32.,55.,5.,55.,73.> |
|||
#show+ |
|||
examples = |
|||
printf/*=*' %0.0f' < |
|||
nth_diff6 test_data, |
|||
nth_diff7 test_data></syntaxhighlight> |
|||
{{out}} |
|||
<pre> 291 -151 424 -905 |
|||
-442 575 -1329</pre> |
|||
=={{header|Visual Basic .NET}}== |
|||
{{works with|Visual Basic .NET|2008+}} |
|||
<syntaxhighlight lang="vbnet">Module ForwardDifference |
|||
Sub Main() |
|||
Dim lNum As New List(Of Integer)(New Integer() {90, 47, 58, 29, 22, 32, 55, 5, 55, 73}) |
|||
For i As UInteger = 0 To 9 |
|||
Console.WriteLine(String.Join(" ", (From n In Difference(i, lNum) Select String.Format("{0,5}", n)).ToArray())) |
|||
Next |
|||
Console.ReadKey() |
|||
End Sub |
|||
Private Function Difference(ByVal Level As UInteger, ByVal Numbers As List(Of Integer)) As List(Of Integer) |
|||
If Level >= Numbers.Count Then Throw New ArgumentOutOfRangeException("Level", "Level must be less than number of items in Numbers") |
|||
For i As Integer = 1 To Level |
|||
Numbers = (From n In Enumerable.Range(0, Numbers.Count - 1) _ |
|||
Select Numbers(n + 1) - Numbers(n)).ToList() |
|||
Next |
|||
Return Numbers |
|||
End Function |
|||
End Module</syntaxhighlight> |
|||
{{out}} |
|||
<pre> |
|||
90 47 58 29 22 32 55 5 55 73 |
|||
-43 11 -29 -7 10 23 -50 50 18 |
|||
54 -40 22 17 13 -73 100 -32 |
|||
-94 62 -5 -4 -86 173 -132 |
|||
156 -67 1 -82 259 -305 |
|||
-223 68 -83 341 -564 |
|||
291 -151 424 -905 |
|||
-442 575 -1329 |
|||
1017 -1904 |
|||
-2921 |
|||
</pre> |
|||
=={{header|Visual FoxPro}}== |
|||
<syntaxhighlight lang="vfp"> |
|||
#DEFINE CTAB CHR(9) |
|||
LOCAL lcList As String, i As Integer, n As Integer |
|||
n = 10 |
|||
LOCAL ARRAY aa[n] |
|||
CLEAR |
|||
lcList = "90,47,58,29,22,32,55,5,55,73" |
|||
FOR i = 1 TO n |
|||
aa[i] = VAL(GETWORDNUM(lcList, i, ",")) |
|||
ENDFOR |
|||
ShowOutput("Original", @aa) |
|||
k = n - 1 |
|||
FOR i = 1 TO n - 1 |
|||
ForwardDiff(@aa) |
|||
ShowOutput("Difference " + TRANSFORM(i), @aa) |
|||
ENDFOR |
|||
PROCEDURE ForwardDiff(a) |
|||
LOCAL i As Integer, n As Integer |
|||
n = ALEN(a) |
|||
LOCAL ARRAY b[n-1] |
|||
FOR i = 1 TO n - 1 |
|||
b[i] = a[i+1] - a[i] |
|||
ENDFOR |
|||
DIMENSION a[n-1] |
|||
ACOPY(b, a) |
|||
ENDPROC |
|||
PROCEDURE ShowOutput(lcLabel, zz) |
|||
LOCAL i As Integer, n As Integer, lcTxt As String |
|||
n = ALEN(zz) |
|||
lcTxt = lcLabel + ":" + CTAB |
|||
FOR i = 1 TO n |
|||
lcTxt = lcTxt + TRANSFORM(zz[i]) + CTAB |
|||
ENDFOR |
|||
lcTxt = LEFT(lcTxt, LEN(lcTxt) - 1) |
|||
? lcTxt |
|||
ENDPROC |
|||
</syntaxhighlight> |
|||
{{out}} |
|||
<pre> |
|||
Original: 90 47 58 29 22 32 55 5 55 73 |
|||
Difference 1: -43 11 -29 -7 10 23 -50 50 18 |
|||
Difference 2: 54 -40 22 17 13 -73 100 -32 |
|||
Difference 3: -94 62 -5 -4 -86 173 -132 |
|||
Difference 4: 156 -67 1 -82 259 -305 |
|||
Difference 5: -223 68 -83 341 -564 |
|||
Difference 6: 291 -151 424 -905 |
|||
Difference 7: -442 575 -1329 |
|||
Difference 8: 1017 -1904 |
|||
Difference 9: -2921 |
|||
</pre> |
|||
=={{header|Wren}}== |
|||
{{libheader|Wren-fmt}} |
|||
<syntaxhighlight lang="wren">import "./fmt" for Fmt |
|||
var forwardDiff = Fn.new { |a, order| |
|||
if (order < 0) Fiber.abort("Order must be a non-negative integer.") |
|||
if (a.count == 0) return |
|||
Fmt.print(" 0: $5d", a) |
|||
if (a.count == 1) return |
|||
if (order == 0) return |
|||
for (o in 1..order) { |
|||
var b = List.filled(a.count-1, 0) |
|||
for (i in 0...b.count) b[i] = a[i+1] - a[i] |
|||
Fmt.print("$2d: $5d", o, b) |
|||
if (b.count == 1) return |
|||
a = b |
|||
} |
|||
} |
|||
forwardDiff.call([90, 47, 58, 29, 22, 32, 55, 5, 55, 73], 9)</syntaxhighlight> |
|||
{{out}} |
|||
<pre> |
|||
0: 90 47 58 29 22 32 55 5 55 73 |
|||
1: -43 11 -29 -7 10 23 -50 50 18 |
|||
2: 54 -40 22 17 13 -73 100 -32 |
|||
3: -94 62 -5 -4 -86 173 -132 |
|||
4: 156 -67 1 -82 259 -305 |
|||
5: -223 68 -83 341 -564 |
|||
6: 291 -151 424 -905 |
|||
7: -442 575 -1329 |
|||
8: 1017 -1904 |
|||
9: -2921 |
|||
</pre> |
|||
=={{header|XPL0}}== |
|||
{{trans|ALGOL W}} |
|||
<syntaxhighlight lang "XPL0">\Calculate forward differences |
|||
\Sets elements of B to the first order forward differences of A. |
|||
\A should have bounds 1 :: N, B should have bounds 1 :: N - 1. |
|||
procedure FirstOrderFDifference ( A, B, N ); |
|||
integer A, B, N, I; |
|||
for I := 2 to N do B( I - 1 ) := A( I ) - A( I - 1 ); |
|||
integer V ( 1 + 10 ); |
|||
integer Diff( 1 + 9 ); |
|||
integer VPos, Length, List, I, Order; |
|||
begin |
|||
\construct the initial values array |
|||
VPos := 1; |
|||
List:= [90, 47, 58, 29, 22, 32, 55, 5, 55, 73]; |
|||
for I := 0 to 10-1 do begin |
|||
V( VPos ) := List( I ); |
|||
VPos := VPos + 1 |
|||
end; |
|||
\calculate and show the differences |
|||
Format(8, 0); \set output format |
|||
Length := 10; |
|||
for Order := 1 to Length - 1 do begin |
|||
FirstOrderFDifference( V, Diff, Length ); |
|||
Length := Length - 1; |
|||
IntOut(0, Order); Text(0, " : "); |
|||
for I := 1 to Length do RlOut(0, float(Diff( I ) )); |
|||
CrLf(0); |
|||
for I := 1 to Length do V( I ) := Diff( I ) |
|||
end |
|||
end</syntaxhighlight> |
|||
{{out}} |
|||
<pre> |
|||
1 : -43 11 -29 -7 10 23 -50 50 18 |
|||
2 : 54 -40 22 17 13 -73 100 -32 |
|||
3 : -94 62 -5 -4 -86 173 -132 |
|||
4 : 156 -67 1 -82 259 -305 |
|||
5 : -223 68 -83 341 -564 |
|||
6 : 291 -151 424 -905 |
|||
7 : -442 575 -1329 |
|||
8 : 1017 -1904 |
|||
9 : -2921 |
|||
</pre> |
|||
=={{header|zkl}}== |
|||
{{trans|Scheme}} |
|||
<syntaxhighlight lang="zkl">fcn forwardDiff(lst){ |
|||
if(lst.len()<2) |
|||
return(T); |
|||
return(T(lst[1]-lst[0]).extend(forwardDiff(lst[1,*]))) |
|||
} |
|||
fcn nthForwardDiff(n,xs){ |
|||
if(n==0) |
|||
return(xs); |
|||
return(nthForwardDiff(n-1,forwardDiff(xs))) // tail recursion |
|||
}</syntaxhighlight> |
|||
<syntaxhighlight lang="zkl">nthForwardDiff(9,T(90, 47, 58, 29, 22, 32, 55, 5, 55, 73)).println();</syntaxhighlight> |
|||
{{out}} |
|||
<pre> |
|||
L(-2921) |
|||
</pre> |
|||
=={{header|ZX Spectrum Basic}}== |
|||
<syntaxhighlight lang="zxbasic">10 DATA 9,0,1,2,4,7,4,2,1,0 |
|||
20 LET p=1 |
|||
30 READ n: DIM b(n) |
|||
40 FOR i=1 TO n |
|||
50 READ b(i) |
|||
60 NEXT i |
|||
70 FOR j=1 TO p |
|||
80 FOR i=1 TO n-j |
|||
90 LET b(i)=b(i+1)-b(i) |
|||
100 NEXT i |
|||
110 NEXT j |
|||
120 FOR i=1 TO n-p |
|||
130 PRINT b(i);" "; |
|||
140 NEXT i</syntaxhighlight> |
Latest revision as of 21:54, 26 July 2024
![Task](http://static.miraheze.org/rosettacodewiki/thumb/b/ba/Rcode-button-task-crushed.png/64px-Rcode-button-task-crushed.png)
You are encouraged to solve this task according to the task description, using any language you may know.
- Task
Provide code that produces a list of numbers which is the nth 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 A is a new list B, where Bn = An+1 - An.
List B should have one fewer element as a result.
The second-order forward difference of A will be:
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
The same as the first-order forward difference of B.
That new list will have two fewer elements than A and one less than B.
The goal of this task is to repeat this process up to the desired order.
For a more formal description, see the related Mathworld article.
- Algorithmic options
- Iterate through all previous forward differences and re-calculate a new array each time.
- Use this formula (from Wikipedia):
- (Pascal's Triangle may be useful for this option.)
11l
V dif = s -> enumerate(s[1..]).map2((i, x) -> x - @s[i])
F difn(s, n) -> [Int]
R I n != 0 {difn(dif(s), n - 1)} E s
V s = [90, 47, 58, 29, 22, 32, 55, 5, 55, 73]
L(i) 10
print(difn(s, i))
- Output:
[90, 47, 58, 29, 22, 32, 55, 5, 55, 73] [-43, 11, -29, -7, 10, 23, -50, 50, 18] [54, -40, 22, 17, 13, -73, 100, -32] [-94, 62, -5, -4, -86, 173, -132] [156, -67, 1, -82, 259, -305] [-223, 68, -83, 341, -564] [291, -151, 424, -905] [-442, 575, -1329] [1017, -1904] [-2921]
Ada
with Ada.Text_Io;
with Ada.Float_Text_Io; use Ada.Float_Text_Io;
with Ada.containers.Vectors;
procedure Forward_Difference is
package Flt_Vect is new Ada.Containers.Vectors(Positive, Float);
use Flt_Vect;
procedure Print(Item : Vector) is
begin
if not Item.Is_Empty then
Ada.Text_IO.Put('[');
for I in 1..Item.Length loop
Put(Item => Item.Element(Positive(I)), Fore => 1, Aft => 1, Exp => 0);
if Positive(I) < Positive(Item.Length) then
Ada.Text_Io.Put(", ");
end if;
end loop;
Ada.Text_Io.Put_line("]");
else
Ada.Text_IO.Put_Line("Empty List");
end if;
end Print;
function Diff(Item : Vector; Num_Passes : Natural) return Vector is
A : Vector := Item;
B : Vector := Empty_Vector;
begin
if not A.Is_Empty then
for I in 1..Num_Passes loop
for I in 1..Natural(A.Length) - 1 loop
B.Append(A.Element(I + 1) - A.Element(I));
end loop;
Move(Target => A, Source => B);
end loop;
end if;
return A;
end Diff;
Values : array(1..10) of Float := (90.0, 47.0, 58.0, 29.0, 22.0, 32.0, 55.0, 5.0, 55.0, 73.0);
A : Vector;
begin
for I in Values'range loop
A.Append(Values(I)); -- Fill the vector
end loop;
Print(Diff(A, 1));
Print(Diff(A, 2));
Print(Diff(A, 9));
Print(Diff(A, 10));
print(Diff(A, 0));
end Forward_Difference;
- Output:
[-43.0, 11.0, -29.0, -7.0, 10.0, 23.0, -50.0, 50.0, 18.0] [54.0, -40.0, 22.0, 17.0, 13.0, -73.0, 100.0, -32.0] [-2921.0] Empty List [90.0, 47.0, 58.0, 29.0, 22.0, 32.0, 55.0, 5.0, 55.0, 73.0]
ALGOL 68
main:(
MODE LISTREAL = [1:0]REAL;
OP - = (LISTREAL a,b)LISTREAL: (
[UPB a]REAL out;
FOR i TO UPB out DO out[i]:=a[i]-b[i] OD;
out
);
FORMAT real fmt=$zzz-d.d$;
FORMAT repeat fmt = $n(UPB s-1)(f(real fmt)",")f(real fmt)$;
FORMAT list fmt = $"("f(UPB s=1|real fmt|repeat fmt)")"$;
FLEX [1:0] REAL s := (90, 47, 58, 29, 22, 32, 55, 5, 55, 73);
printf((list fmt,s,$";"l$));
TO UPB s-1 DO
s := s[2:] - s[:UPB s-1];
printf((list fmt,s,$";"l$))
OD
)
- Output:
( 90.0, 47.0, 58.0, 29.0, 22.0, 32.0, 55.0, 5.0, 55.0, 73.0); ( -43.0, 11.0, -29.0, -7.0, 10.0, 23.0, -50.0, 50.0, 18.0); ( 54.0, -40.0, 22.0, 17.0, 13.0, -73.0, 100.0, -32.0); ( -94.0, 62.0, -5.0, -4.0, -86.0, 173.0, -132.0); ( 156.0, -67.0, 1.0, -82.0, 259.0, -305.0); ( -223.0, 68.0, -83.0, 341.0, -564.0); ( 291.0, -151.0, 424.0, -905.0); ( -442.0, 575.0,-1329.0); ( 1017.0,-1904.0); (-2921.0);
ALGOL W
begin
% calculate forward differences %
% sets elements of B to the first order forward differences of A %
% A should have bounds 1 :: n, B should have bounds 1 :: n - 1 %
procedure FirstOrderFDifference ( integer array A( * )
; integer array B( * )
; integer value n
) ;
for i := 2 until n do B( i - 1 ) := A( i ) - A( i - 1 );
integer array v ( 1 :: 10 );
integer array diff( 1 :: 9 );
integer vPos, length;
% construct the initial values array %
vPos := 1;
for i := 90, 47, 58, 29, 22, 32, 55, 5, 55, 73 do begin
v( vPos ) := i;
vPos := vPos + 1
end for_i ;
% calculate and show the differences %
i_w := 5; % set output format %
length := 10;
for order := 1 until length - 1 do begin
FirstOrderFDifference( v, diff, length );
length := length - 1;
write( order, ": " ); for i := 1 until length do writeon( diff( i ) );
for i := 1 until length do v( i ) := diff( i )
end for_order
end.
- Output:
1 : -43 11 -29 -7 10 23 -50 50 18 2 : 54 -40 22 17 13 -73 100 -32 3 : -94 62 -5 -4 -86 173 -132 4 : 156 -67 1 -82 259 -305 5 : -223 68 -83 341 -564 6 : 291 -151 424 -905 7 : -442 575 -1329 8 : 1017 -1904 9 : -2921
APL
list ← 90 47 58 29 22 32 55 5 55 73
fd ← {⍺=0:⍵⋄(⍺-1)∇(1↓⍵)-(¯1↓⍵)}
1 fd list
¯43 11 ¯29 ¯7 10 23 ¯50 50 18
2 fd list
54 ¯40 22 17 13 ¯73 100 ¯32
AppleScript
-- forwardDifference :: Num a => [a] -> [a]
on forwardDifference(xs)
zipWith(my subtract, xs, rest of xs)
end forwardDifference
-- nthForwardDifference :: Num a => Int -> [a] -> [a]
on nthForwardDifference(xs, i)
|index|(iterate(forwardDifference, xs), 1 + i)
end nthForwardDifference
-------------------------- TEST ---------------------------
on run
script show
on |λ|(xs, i)
((i - 1) as string) & " -> " & showList(xs)
end |λ|
end script
unlines(map(show, ¬
take(10, ¬
iterate(forwardDifference, ¬
{90, 47, 58, 29, 22, 32, 55, 5, 55, 73}))))
end run
-------------------- GENERIC FUNCTIONS --------------------
-- Just :: a -> Maybe a
on Just(x)
-- Constructor for an inhabited Maybe (option type) value.
-- Wrapper containing the result of a computation.
{type:"Maybe", Nothing:false, Just:x}
end Just
-- Nothing :: Maybe a
on Nothing()
-- Constructor for an empty Maybe (option type) value.
-- Empty wrapper returned where a computation is not possible.
{type:"Maybe", Nothing:true}
end Nothing
-- index (!!) :: [a] -> Int -> Maybe a
-- index (!!) :: Gen [a] -> Int -> Maybe a
-- index (!!) :: String -> Int -> Maybe Char
on |index|(xs, i)
if script is class of xs then
repeat with j from 1 to i
set v to |λ|() of xs
end repeat
if missing value is not v then
Just(v)
else
Nothing()
end if
else
if length of xs < i then
Nothing()
else
Just(item i of xs)
end if
end if
end |index|
-- intercalate :: String -> [String] -> String
on intercalate(delim, xs)
set {dlm, my text item delimiters} to ¬
{my text item delimiters, delim}
set str to xs as text
set my text item delimiters to dlm
str
end intercalate
-- iterate :: (a -> a) -> a -> Gen [a]
on iterate(f, x)
script
property v : missing value
property g : mReturn(f)'s |λ|
on |λ|()
if missing value is v then
set v to x
else
set v to g(v)
end if
return v
end |λ|
end script
end iterate
-- length :: [a] -> Int
on |length|(xs)
set c to class of xs
if list is c or string is c then
length of xs
else
(2 ^ 29 - 1) -- (maxInt - simple proxy for non-finite)
end if
end |length|
-- map :: (a -> b) -> [a] -> [b]
on map(f, xs)
-- The list obtained by applying f
-- to each element of xs.
tell mReturn(f)
set lng to length of xs
set lst to {}
repeat with i from 1 to lng
set end of lst to |λ|(item i of xs, i, xs)
end repeat
return lst
end tell
end map
-- min :: Ord a => a -> a -> a
on min(x, y)
if y < x then
y
else
x
end if
end min
-- mReturn :: First-class m => (a -> b) -> m (a -> b)
on mReturn(f)
-- 2nd class handler function lifted into 1st class script wrapper.
if script is class of f then
f
else
script
property |λ| : f
end script
end if
end mReturn
-- showList :: [a] -> String
on showList(xs)
"[" & intercalate(", ", map(my str, xs)) & "]"
end showList
-- str :: a -> String
on str(x)
x as string
end str
-- subtract :: Num -> Num -> Num
on subtract(x, y)
y - x
end subtract
-- take :: Int -> [a] -> [a]
-- take :: Int -> String -> String
on take(n, xs)
set c to class of xs
if list is c then
if 0 < n then
items 1 thru min(n, length of xs) of xs
else
{}
end if
else if string is c then
if 0 < n then
text 1 thru min(n, length of xs) of xs
else
""
end if
else if script is c then
set ys to {}
repeat with i from 1 to n
set v to |λ|() of xs
if missing value is v then
return ys
else
set end of ys to v
end if
end repeat
return ys
else
missing value
end if
end take
-- unlines :: [String] -> String
on unlines(xs)
-- A single string formed by the intercalation
-- of a list of strings with the newline character.
set {dlm, my text item delimiters} to ¬
{my text item delimiters, linefeed}
set s to xs as text
set my text item delimiters to dlm
s
end unlines
-- zipWith :: (a -> b -> c) -> [a] -> [b] -> [c]
on zipWith(f, xs, ys)
set lng to min(|length|(xs), |length|(ys))
if 1 > lng then return {}
set xs_ to take(lng, xs) -- Allow for non-finite
set ys_ to take(lng, ys) -- generators like cycle etc
set lst to {}
tell mReturn(f)
repeat with i from 1 to lng
set end of lst to |λ|(item i of xs_, item i of ys_)
end repeat
return lst
end tell
end zipWith
- Output:
0 -> [90, 47, 58, 29, 22, 32, 55, 5, 55, 73] 1 -> [-43, 11, -29, -7, 10, 23, -50, 50, 18] 2 -> [54, -40, 22, 17, 13, -73, 100, -32] 3 -> [-94, 62, -5, -4, -86, 173, -132] 4 -> [156, -67, 1, -82, 259, -305] 5 -> [-223, 68, -83, 341, -564] 6 -> [291, -151, 424, -905] 7 -> [-442, 575, -1329] 8 -> [1017, -1904] 9 -> [-2921]
Arturo
; element-wise subtraction of two blocks. e.g.
; vsub [1 2 3] [1 2 3] ; [0 0 0]
vsub: function [u v][
map couple u v 'pair -> pair\0 - pair\1
]
differences: function [block][
order: attr "order"
if order = null -> order: 1
loop 1..order 'n -> block: vsub block drop block
return block
]
print differences .order: 4 [90.5 47 58 29 22 32 55 5 55 73.5]
print differences [1 2 3 4 5 6 7]
- Output:
156.5 -67 1 -82 259 -304.5 -1 -1 -1 -1 -1 -1
AutoHotkey
contributed by Laszlo on the ahk forum
MsgBox % diff("2,3,4,3",1)
MsgBox % diff("2,3,4,3",2)
MsgBox % diff("2,3,4,3",3)
MsgBox % diff("2,3,4,3",4)
diff(list,ord) { ; high order forward differences of a list
Loop %ord% {
L =
Loop Parse, list, `, %A_Space%%A_Tab%
If (A_Index=1)
p := A_LoopField
Else
L .= "," A_LoopField-p, p := A_LoopField
list := SubStr(L,2)
}
Return list
}
AWK
#!/usr/bin/awk -f
BEGIN {
if (p<1) {p = 1};
}
function diff(s, p) {
n = split(s, a, " ");
for (j = 1; j <= p; j++) {
for(i = 1; i <= n-j; i++) {
a[i] = a[i+1] - a[i];
}
}
s = "";
for (i = 1; i <= n-p; i++) s = s" "a[i];
return s;
}
{
print diff($0, p);
}
Using Pascal's triangle:
#!/usr/bin/awk -f
BEGIN {
if (p<1) {p = 1};
}
function diff(s, p) {
# pascal triangled with sign changes
b[1] = (p%2) ? 1 : -1;
for (j=1; j < p; j++) {
b[j+1] = -b[j]*(p-j)/j;
};
n = split(s, a, " ");
s = "";
for (j = 1; j <= n-p+1; j++) {
c = 0;
for(i = 1; i <= p; i++) {
c += b[i]*a[j+i-1];
}
s = s" "c;
}
return s;
}
{
print diff($0, p);
}
- Output:
$ echo '0 1 2 4 7 4 2 1 0' | ./diff.awk -v p=1 1 1 2 3 -3 -2 -1 -1 $ echo '0 1 2 4 7 4 2 1 0' | ./diff.awk -v p=2 0 1 1 -6 1 1 0 $ echo '0 1 2 4 7 4 2 1 0' | ./diff.awk -v p=3 1 0 -7 7 0 -1 $ echo '0 1 2 4 7 4 2 1 0' | ./diff.awk -v p=4 -1 -7 14 -7 -1 $ echo '0 1 2 4 7 4 2 1 0' | ./diff.awk -v p=5 -6 21 -21 6 $ echo '0 1 2 4 7 4 2 1 0' | ./diff.awk -v p=6 27 -42 27 $ echo '0 1 2 4 7 4 2 1 0' | ./diff.awk -v p=7 -69 69 $ echo '0 1 2 4 7 4 2 1 0' | ./diff.awk -v p=8 138 $ echo '0 1 2 4 7 4 2 1 0' | ./diff.awk -v p=9
BBC BASIC
DIM A(9)
A() = 90.0, 47.0, 58.0, 29.0, 22.0, 32.0, 55.0, 5.0, 55.0, 73.0
PRINT "Original array: " FNshowarray(A())
PROCforward_difference(1, A(), B())
PRINT "Forward diff 1: " FNshowarray(B())
PROCforward_difference(2, A(), C())
PRINT "Forward diff 2: " FNshowarray(C())
PROCforward_difference(9, A(), D())
PRINT "Forward diff 9: " FNshowarray(D())
END
DEF PROCforward_difference(n%, a(), RETURN b())
LOCAL c%, i%, j%
DIM b(DIM(a(),1) - n%)
FOR i% = 0 TO DIM(b(),1)
b(i%) = a(i% + n%)
c% = 1
FOR j% = 1 TO n%
c% = -INT(c% * (n% - j% + 1) / j% + 0.5)
b(i%) += c% * a(i% + n% - j%)
NEXT
NEXT
ENDPROC
DEF FNshowarray(a())
LOCAL i%, a$
FOR i% = 0 TO DIM(a(),1)
a$ += STR$(a(i%)) + ", "
NEXT
= LEFT$(LEFT$(a$))
- Output:
Original array: 90, 47, 58, 29, 22, 32, 55, 5, 55, 73 Forward diff 1: -43, 11, -29, -7, 10, 23, -50, 50, 18 Forward diff 2: 54, -40, 22, 17, 13, -73, 100, -32 Forward diff 9: -2921
BQN
Left argument is the order, right argument is the array.
FDiff ← {{-˜´˘2↕𝕩}⍟𝕨 𝕩}
•Show 1 FDiff 90‿47‿58‿29‿22‿32‿55‿5‿55‿73
•Show 2 FDiff 90‿47‿58‿29‿22‿32‿55‿5‿55‿73
C
#include <stdlib.h>
#include <string.h>
#include <stdio.h>
double* fwd_diff(double* x, unsigned int len, unsigned int order)
{
unsigned int i, j;
double* y;
/* handle two special cases */
if (order >= len) return 0;
y = malloc(sizeof(double) * len);
if (!order) {
memcpy(y, x, sizeof(double) * len);
return y;
}
/* first order diff goes from x->y, later ones go from y->y */
for (j = 0; j < order; j++, x = y)
for (i = 0, len--; i < len; i++)
y[i] = x[i + 1] - x[i];
y = realloc(y, sizeof(double) * len);
return y;
}
int main(void)
{
double *y, x[] = {90, 47, 58, 29, 22, 32, 55, 5, 55, 73};
int i, len = sizeof(x) / sizeof(x[0]);
y = fwd_diff(x, len, 1);
for (i = 0; i < len - 1; i++)
printf("%g ", y[i]);
putchar('\n');
return 0;
}
Use method with Pascal triangle, binomial coefficients are pre-computed
#include <stdio.h>
int* binomCoeff(int n) {
int *b = calloc(n+1,sizeof(int));
int j;
b[0] = n%2 ? -1 : 1;
for (j=1 ; j<=n; j++)
b[j] = -b[j-1]*(n+1-j)/j;
return(b);
};
main () {
double array[] = { 90, 47, 58, 29, 22, 32, 55, 5, 55, 73 };
size_t lenArray = sizeof(array)/sizeof(array[0]);
int p = 4; // order
int *b = binomCoeff(p); // pre-compute binomial coefficients for order p
int j, k;
// compute p-th difference
for (k=0 ; k < lenArray; k++)
for (array[k] *= b[0], j=1 ; j<=p; j++)
array[k] += b[j] * array[k+j];
free(b);
// resulting series is shorter by p elements
lenArray -= p;
for (k=0 ; k < lenArray; k++) printf("%f ",array[k]);
printf("\n");
}
C#
using System;
using System.Collections.Generic;
using System.Linq;
class Program
{
static IEnumerable<int> ForwardDifference(IEnumerable<int> sequence, uint order = 1u)
{
switch (order)
{
case 0u:
return sequence;
case 1u:
return sequence.Skip(1).Zip(sequence, (next, current) => next - current);
default:
return ForwardDifference(ForwardDifference(sequence), order - 1u);
}
}
static void Main()
{
IEnumerable<int> sequence = new[] { 90, 47, 58, 29, 22, 32, 55, 5, 55, 73 };
do
{
Console.WriteLine(string.Join(", ", sequence));
} while ((sequence = ForwardDifference(sequence)).Any());
}
}
- Output:
90, 47, 58, 29, 22, 32, 55, 5, 55, 73 -43, 11, -29, -7, 10, 23, -50, 50, 18 54, -40, 22, 17, 13, -73, 100, -32 -94, 62, -5, -4, -86, 173, -132 156, -67, 1, -82, 259, -305 -223, 68, -83, 341, -564 291, -151, 424, -905 -442, 575, -1329 1017, -1904 -2921
C++
This code uses a separate function to do a first-order forward difference, which is then called several times for calculating n-th order forward difference. No error checking is implemented.
#include <vector>
#include <iterator>
#include <algorithm>
// calculate first order forward difference
// requires:
// * InputIterator is an input iterator
// * OutputIterator is an output iterator
// * The value type of InputIterator is copy-constructible and assignable
// * The value type of InputIterator supports operator -
// * The result type of operator- is assignable to the value_type of OutputIterator
// returns: The iterator following the output sequence
template<typename InputIterator, typename OutputIterator>
OutputIterator forward_difference(InputIterator first, InputIterator last,
OutputIterator dest)
{
// special case: for empty sequence, do nothing
if (first == last)
return dest;
typedef typename std::iterator_traits<InputIterator>::value_type value_type;
value_type temp = *first++;
while (first != last)
{
value_type temp2 = *first++;
*dest++ = temp2 - temp;
temp = temp2;
}
return dest;
}
// calculate n-th order forward difference.
// requires:
// * InputIterator is an input iterator
// * OutputIterator is an output iterator
// * The value type of InputIterator is copy-constructible and assignable
// * The value type of InputIterator supports operator -
// * The result type of operator- is assignable to the value_type of InputIterator
// * The result type of operator- is assignable to the value_type of OutputIterator
// * order >= 0
// returns: The iterator following the output sequence
template<typename InputIterator, typename OutputIterator>
OutputIterator nth_forward_difference(int order,
InputIterator first, InputIterator last,
OutputIterator dest)
{
// special case: If order == 0, just copy input to output
if (order == 0)
return std::copy(first, last, dest);
// second special case: If order == 1, just forward to the first-order function
if (order == 1)
return forward_difference(first, last, dest);
// intermediate results are stored in a vector
typedef typename std::iterator_traits<InputIterator>::value_type value_type;
std::vector<value_type> temp_storage;
// fill the vector with the result of the first order forward difference
forward_difference(first, last, std::back_inserter(temp_storage));
// the next n-2 iterations work directly on the vector
typename std::vector<value_type>::iterator begin = temp_storage.begin(),
end = temp_storage.end();
for (int i = 1; i < order-1; ++i)
end = forward_difference(begin, end, begin);
// the final iteration writes directly to the output iterator
return forward_difference(begin, end, dest);
}
// example usage code
#include <iostream>
int main()
{
double array[10] = { 90.0, 47.0, 58.0, 29.0, 22.0, 32.0, 55.0, 5.0, 55.0, 73.0 };
// this stores the results in the vector dest
std::vector<double> dest;
nth_forward_difference(1, array, array+10, std::back_inserter(dest));
// output dest
std::copy(dest.begin(), dest.end(), std::ostream_iterator<double>(std::cout, " "));
std::cout << std::endl;
// however, the results can also be output as they are calculated
nth_forward_difference(2, array, array+10, std::ostream_iterator<double>(std::cout, " "));
std::cout << std::endl;
nth_forward_difference(9, array, array+10, std::ostream_iterator<double>(std::cout, " "));
std::cout << std::endl;
nth_forward_difference(10, array, array+10, std::ostream_iterator<double>(std::cout, " "));
std::cout << std::endl;
nth_forward_difference(0, array, array+10, std::ostream_iterator<double>(std::cout, " "));
std::cout << std::endl;
// finally, the results can also be written into the original array
// (which of course destroys the original content)
double* end = nth_forward_difference(3, array, array+10, array);
for (double* p = array; p < end; ++p)
std::cout << *p << " ";
std::cout << std::endl;
return 0;
}
- Output:
-43 11 -29 -7 10 23 -50 50 18 54 -40 22 17 13 -73 100 -32 -2921 90 47 58 29 22 32 55 5 55 73 -94 62 -5 -4 -86 173 -132
Note the empty line indicating the empty sequence for order 10.
Using Standard Template Library
#include <iostream>
#include <numeric>
// Calculate the Forward Difference of a series if integers showing each order
//
// Nigel Galloway. August 20th., 2012
//
int main() {
int x[] = {NULL,-43,11,-29,-7,10,23,-50,50,18};
const int N = sizeof(x) / sizeof(int) - 1;
for (int ord = 0; ord < N - 1; ord++) {
std::adjacent_difference(x+1, x + N + 1 - ord, x);
for (int i = 1; i < N - ord; i++) std::cout << x[i] << ' ';
std::cout << std::endl;
}
return 0;
}
- Output:
54 -40 22 17 13 -73 100 -32 -94 62 -5 -4 -86 173 -132 156 -67 1 -82 259 -305 -223 68 -83 341 -564 291 -151 424 -905 -442 575 -1329 1017 -1904 -2921
Usually one will not want the intermediate results, in which case the following is sufficient:
#include <iostream>
#include <numeric>
// Calculate the Forward Difference of a series if integers
//
// Nigel Galloway. August 20th., 2012
//
int main() {
int x[] = {NULL,-43,11,-29,-7,10,23,-50,50,18};
const int N = sizeof(x) / sizeof(int) - 1;
for (int ord = 0; ord < N - 1; ord++) std::adjacent_difference(x+1, x + N + 1 - ord, x);
std::cout << x[1] << std::endl;
return 0;
}
- Output:
-2921
Using Pascal's Triangle
#include <iostream>
#include <algorithm>
// Calculate the Forward Difference of a series if integers using Pascal's Triangle
// For this example the 9th line of Pascal's Triangle is stored in P.
//
// Nigel Galloway. August 20th., 2012
//
int main() {
const int P[] = {1,-8,28,-56,70,-56,28,-8,1};
int x[] = {-43,11,-29,-7,10,23,-50,50,18};
std::transform(x, x + sizeof(x) / sizeof(int), P, x, std::multiplies<int>());
std::cout << std::accumulate(x, x + sizeof(x) / sizeof(int), 0) << std::endl;
return 0;
}
- Output:
-2921
Clojure
(defn fwd-diff [nums order]
(nth (iterate #(map - (next %) %) nums) order))
CoffeeScript
forward_difference = (arr, n) ->
# Find the n-th order forward difference for arr using
# a straightforward recursive algorithm.
# Assume arr is integers and n <= arr.length.
return arr if n == 0
arr = forward_difference(arr, n-1)
(arr[i+1] - arr[i] for i in [0...arr.length - 1])
arr = [-1, 0, 1, 8, 27, 64, 125, 216]
for n in [0..arr.length]
console.log n, forward_difference arr, n
- Output:
> coffee forward_difference.coffee 0 [ -1, 0, 1, 8, 27, 64, 125, 216 ] 1 [ 1, 1, 7, 19, 37, 61, 91 ] 2 [ 0, 6, 12, 18, 24, 30 ] 3 [ 6, 6, 6, 6, 6 ] 4 [ 0, 0, 0, 0 ] 5 [ 0, 0, 0 ] 6 [ 0, 0 ] 7 [ 0 ] 8 []
Common Lisp
(defun forward-difference (list)
(mapcar #'- (rest list) list))
(defun nth-forward-difference (list n)
(setf list (copy-list list))
(loop repeat n do (map-into list #'- (rest list) list))
(subseq list 0 (- (length list) n)))
D
Basic Version
T[] forwardDifference(T)(in T[] data, in int level) pure nothrow
in {
assert(level >= 0 && level < data.length);
} body {
auto result = data.dup;
foreach (immutable i; 0 .. level)
foreach (immutable j, ref el; result[0 .. $ - i - 1])
el = result[j + 1] - el;
result.length -= level;
return result;
}
void main() {
import std.stdio;
const data = [90.5, 47, 58, 29, 22, 32, 55, 5, 55, 73.5];
foreach (immutable level; 0 .. data.length)
forwardDifference(data, level).writeln;
}
- Output:
[90.5, 47, 58, 29, 22, 32, 55, 5, 55, 73.5] [-43.5, 11, -29, -7, 10, 23, -50, 50, 18.5] [54.5, -40, 22, 17, 13, -73, 100, -31.5] [-94.5, 62, -5, -4, -86, 173, -131.5] [156.5, -67, 1, -82, 259, -304.5] [-223.5, 68, -83, 341, -563.5] [291.5, -151, 424, -904.5] [-442.5, 575, -1328.5] [1017.5, -1903.5] [-2921]
Alternative Version
Same output.
import std.stdio, std.algorithm, std.range, std.array;
auto forwardDifference(Range)(Range d, in int level) pure {
foreach (immutable _; 0 .. level)
d = d.zip(d.dropOne).map!(a => a[0] - a[1]).array;
return d;
}
void main() {
const data = [90.5, 47, 58, 29, 22, 32, 55, 5, 55, 73.5];
foreach (immutable level; 0 .. data.length)
forwardDifference(data, level).writeln;
}
Using Vector Operations
forwardDifference mutates the array in-place (same output):
import std.stdio;
T[] forwardDifference(T)(T[] s, in int n) pure nothrow @nogc {
foreach (immutable i; 0 .. n)
s[0 .. $ - i - 1] = s[1 .. $ - i] - s[0 .. $ - i - 1];
return s[0 .. $ - n];
}
void main() {
immutable A = [90.5, 47, 58, 29, 22, 32, 55, 5, 55, 73.5];
foreach (immutable level; 0 .. A.length)
forwardDifference(A.dup, level).writeln;
}
Short Functional Version
Same output:
void main() {
import std.stdio, std.range;
auto D = [90.5, 47, 58, 29, 22, 32, 55, 5, 55, 73.5];
writefln("%(%s\n%)",
recurrence!q{ (a[n - 1][0 .. $ - 1] =
a[n - 1][1 .. $] -
a[n - 1][0 .. $ - 1])[0 .. $] }(D)
.take(D.length));
}
Dart
List forwardDifference(List _list) {
for (int i = _list.length - 1; i > 0; i--) {
_list[i] = _list[i] - _list[i - 1];
}
_list.removeRange(0, 1);
return _list;
}
void mainAlgorithms() {
List _intList = [90, 47, 58, 29, 22, 32, 55, 5, 55, 73];
for (int i = _intList.length - 1; i >= 0; i--) {
List _list = forwardDifference(_intList);
print(_list);
}
}
- Output:
Restarted application in 1,143ms. flutter: [-43, 11, -29, -7, 10, 23, -50, 50, 18] flutter: [54, -40, 22, 17, 13, -73, 100, -32] flutter: [-94, 62, -5, -4, -86, 173, -132] flutter: [156, -67, 1, -82, 259, -305] flutter: [-223, 68, -83, 341, -564] flutter: [291, -151, 424, -905] flutter: [-442, 575, -1329] flutter: [1017, -1904] flutter: [-2921] flutter: []
Delphi
See Pascal.
E
pragma.enable("accumulator")
/** Single step. */
def forwardDifference(seq :List) {
return accum [] for i in 0..(seq.size() - 2) {
_.with(seq[i + 1] - seq[i])
}
}
/** Iterative implementation of the goal. */
def nthForwardDifference1(var seq :List, n :(int >= 0)) {
for _ in 1..n { seq := forwardDifference(seq) }
return seq
}
/** Imperative implementation of the goal. */
def nthForwardDifference2(seq :List, n :(int >= 0)) {
def buf := seq.diverge()
def finalSize := seq.size() - n
for lim in (finalSize..!seq.size()).descending() {
for i in 0..!lim {
buf[i] := buf[i + 1] - buf[i]
}
}
return buf.run(0, finalSize)
}
? def sampleData := [90, 47, 58, 29, 22, 32, 55, 5, 55, 73]
> for n in 0..10 {
> def r1 := nthForwardDifference1(sampleData, n)
> require(r1 == nthForwardDifference2(sampleData, n))
> println(r1)
> }
EasyLang
func[] fwddiff s[] n .
for i to n
for j = 1 to len s[] - 1
s[j] = s[j + 1] - s[j]
.
len s[] -1
.
return s[]
.
s[] = [ 90 47 58 29 22 32 55 5 55 73 ]
print fwddiff s[] 1
print fwddiff s[] 2
print fwddiff s[] 9
- Output:
[ -43 11 -29 -7 10 23 -50 50 18 ] [ 54 -40 22 17 13 -73 100 -32 ] [ -2921 ]
EchoLisp
Using the built-in function iterate which, given a function f and n, returns the function f°f°f....°f .
(define (Δ-1 list)
(for/list ([x (cdr list)] [y list]) (- x y)))
(define (Δ-n n) (iterate Δ-1 n))
((Δ-n 9) '(90 47 58 29 22 32 55 5 55 73))
→ (-2921)
Elixir
defmodule Diff do
def forward(list,i\\1) do
forward(list,[],i)
end
def forward([_],diffs,1), do: IO.inspect diffs
def forward([_],diffs,i), do: forward(diffs,[],i-1)
def forward([val1,val2|vals],diffs,i) do
forward([val2|vals],diffs++[val2-val1],i)
end
end
Enum.each(1..9, fn i ->
Diff.forward([90, 47, 58, 29, 22, 32, 55, 5, 55, 73],i)
end)
- Output:
[-43, 11, -29, -7, 10, 23, -50, 50, 18] [54, -40, 22, 17, 13, -73, 100, -32] [-94, 62, -5, -4, -86, 173, -132] [156, -67, 1, -82, 259, -305] [-223, 68, -83, 341, -564] [291, -151, 424, -905] [-442, 575, -1329] [1017, -1904] [-2921]
Erlang
-module(forward_difference).
-export([difference/1, difference/2]).
-export([task/0]).
-define(TEST_DATA,[90, 47, 58, 29, 22, 32, 55, 5, 55, 73]).
difference([X|Xs]) ->
{Result,_} = lists:mapfoldl(fun (N_2,N_1) -> {N_2 - N_1, N_2} end, X, Xs),
Result.
difference([],_) -> [];
difference(List,0) -> List;
difference(List,Order) -> difference(difference(List),Order-1).
task() ->
io:format("Initial: ~p~n",[?TEST_DATA]),
[io:format("~3b: ~p~n",[N,difference(?TEST_DATA,N)]) || N <- lists:seq(0,length(?TEST_DATA))],
ok.
- Output:
80> forward_difference:task(). Initial: [90,47,58,29,22,32,55,5,55,73] 0: [90,47,58,29,22,32,55,5,55,73] 1: [-43,11,-29,-7,10,23,-50,50,18] 2: [54,-40,22,17,13,-73,100,-32] 3: [-94,62,-5,-4,-86,173,-132] 4: [156,-67,1,-82,259,-305] 5: [-223,68,-83,341,-564] 6: [291,-151,424,-905] 7: [-442,575,-1329] 8: [1017,-1904] 9: [-2921] 10: [] ok
F#
Straightforward recursive solution
let rec ForwardDifference input n =
match n with
| _ when input = [] || n < 0 -> [] // If there's no more input, just return an empty list
| 0 -> input // If n is zero, we're done - return the input
| _ -> ForwardDifference // otherwise, recursively difference..
(input.Tail // All but the first element
|> Seq.zip input // tupled with itself
|> Seq.map (fun (a, b) -> b-a) // Subtract the i'th element from the (i+1)'th
|> Seq.toList) (n-1) // Make into a list and do an n-1 difference on it
Factor
USING: kernel math math.vectors sequences ;
IN: rosetacode
: 1-order ( seq -- seq' )
[ rest-slice ] keep v- ;
: n-order ( seq n -- seq' )
dup 0 <=
[ drop ] [ [ 1-order ] times ] if ;
( scratchpad ) { 90.5 47 58 29 22 32 55 5 55 73.5 } 4 n-order . { 156.5 -67 1 -82 259 -304.5 }
Forth
: forward-difference
dup 0
?do
swap rot over i 1+ - 0
?do dup i cells + dup cell+ @ over @ - swap ! loop
swap rot
loop -
;
create a
90 , 47 , 58 , 29 , 22 , 32 , 55 , 5 , 55 , 73 ,
: test a 10 9 forward-difference bounds ?do i ? loop ;
test
Fortran
MODULE DIFFERENCE
IMPLICIT NONE
CONTAINS
SUBROUTINE Fdiff(a, n)
INTEGER, INTENT(IN) :: a(:), n
INTEGER :: b(SIZE(a))
INTEGER :: i, j, arraysize
b = a
arraysize = SIZE(b)
DO i = arraysize-1, arraysize-n, -1
DO j = 1, i
b(j) = b(j+1) - b(j)
END DO
END DO
WRITE (*,*) b(1:arraysize-n)
END SUBROUTINE Fdiff
END MODULE DIFFERENCE
PROGRAM TEST
USE DIFFERENCE
IMPLICIT NONE
INTEGER :: array(10) = (/ 90, 47, 58, 29, 22, 32, 55, 5, 55, 73 /)
INTEGER :: i
DO i = 1, 9
CALL Fdiff(array, i)
END DO
END PROGRAM TEST
- Output:
-43 11 -29 -7 10 23 -50 50 18 54 -40 22 17 13 -73 100 -32 -94 62 -5 -4 -86 173 -132 156 -67 1 -82 259 -305 -223 68 -83 341 -564 291 -151 424 -905 -442 575 -1329 1017 -1904 -2921
FreeBASIC
function forward_difference( a() as uinteger ) as uinteger ptr
dim as uinteger ptr b = allocate( sizeof(uinteger) * (ubound(a)-1) )
for i as uinteger = 0 to ubound(a)-1
*(b+i) = a(i+1)-a(i)
next i
return b
end function
dim as uinteger a(0 to 15) = {2, 3, 5, 7, 11, 13, 17, 19,_
23, 29, 31, 37, 41, 43, 47, 53}
dim as uinteger i
dim as uinteger ptr b = forward_difference( a() )
for i = 0 to ubound(a)-1
print *(b+i)
next i
Go
package main
import "fmt"
func main() {
a := []int{90, 47, 58, 29, 22, 32, 55, 5, 55, 73}
fmt.Println(a)
fmt.Println(fd(a, 9))
}
func fd(a []int, ord int) []int {
for i := 0; i < ord; i++ {
for j := 0; j < len(a)-i-1; j++ {
a[j] = a[j+1] - a[j]
}
}
return a[:len(a)-ord]
}
- Output:
[90 47 58 29 22 32 55 5 55 73] [-2921]
Haskell
forwardDifference :: Num a => [a] -> [a]
forwardDifference = tail >>= zipWith (-)
nthForwardDifference :: Num a => [a] -> Int -> [a]
nthForwardDifference = (!!) . iterate forwardDifference
main :: IO ()
main =
mapM_ print $
take 10 (iterate forwardDifference [90, 47, 58, 29, 22, 32, 55, 5, 55, 73])
- Output:
[90,47,58,29,22,32,55,5,55,73] [-43,11,-29,-7,10,23,-50,50,18] [54,-40,22,17,13,-73,100,-32] [-94,62,-5,-4,-86,173,-132] [156,-67,1,-82,259,-305] [-223,68,-83,341,-564] [291,-151,424,-905] [-442,575,-1329] [1017,-1904] [-2921]
HicEst
REAL :: n=10, list(n)
list = ( 90, 47, 58, 29, 22, 32, 55, 5, 55, 73 )
WRITE(Format='i1, (i6)') 0, list
DO i = 1, n-1
ALIAS(list,1, diff,n-i) ! rename list(1 ... n-i) with diff
diff = list($+1) - diff ! $ is the running left hand array index
WRITE(Format='i1, (i6)') i, diff
ENDDO
END
- Output:
0 90 47 58 29 22 32 55 5 55 73 1 -43 11 -29 -7 10 23 -50 50 18 2 54 -40 22 17 13 -73 100 -32 3 -94 62 -5 -4 -86 173 -132 4 156 -67 1 -82 259 -305 5 -223 68 -83 341 -564 6 291 -151 424 -905 7 -442 575 -1329 8 1017 -1904 9 -2921
Icon and Unicon
- A sample run:
->fdiff 3 1 4 1 5 9 2 6 3 1: -2 3 -3 4 4 -7 4 -3 2: 5 -6 7 0 -11 11 -7 3: -11 13 -7 -11 22 -18 4: 24 -20 -4 33 -40 5: -44 16 37 -73 6: 60 21 -110 7: -39 -131 8: -92 ->
IDL
Standard IDL library function TS_diff(X,k,[/double]):
print,(x = randomu(seed,8)*100)
15.1473 58.0953 82.7465 16.8637 97.7182 59.7856 17.7699 74.9154
print,ts_diff(x,1)
-42.9479 -24.6513 65.8828 -80.8545 37.9326 42.0157 -57.1455 0.000000
print,ts_diff(x,2)
-18.2967 -90.5341 146.737 -118.787 -4.08316 99.1613 0.000000 0.000000
print,ts_diff(x,3)
72.2374 -237.271 265.524 -114.704 -103.244 0.000000 0.000000 0.000000
J
Of the many ways to code this in J, a particularly concise solution is:
fd=: 2&(-~/\)
Alternatively, to reduce the number of J primitives, use:
fd=: }. - }: ^:
(which is also elegant, because the open-ended power conjunction reads like "to the power of anything").
For example:
list=: 90 47 58 29 22 32 55 5 55 73 NB. Some numbers
1 fd list
_43 11 _29 _7 10 23 _50 50 18
2 fd list
54 _40 22 17 13 _73 100 _32
J is array oriented, so you can even ask for more than one forward difference at a time (i.e. N can be a list, instead of a single number):
1 2 3 fd list NB. First, second, and third forward differences (simultaneously)
43 _11 29 7 _10 _23 50 _50 _18
54 _40 22 17 13 _73 100 _32 0
94 _62 5 4 86 _173 132 0 0
a: fd list NB. All forward differences
90 47 58 29 22 32 55 5 55 73
43 _11 29 7 _10 _23 50 _50 _18 0
54 _40 22 17 13 _73 100 _32 0 0
94 _62 5 4 86 _173 132 0 0 0
156 _67 1 _82 259 _305 0 0 0 0
223 _68 83 _341 564 0 0 0 0 0
291 _151 424 _905 0 0 0 0 0 0
442 _575 1329 0 0 0 0 0 0 0
1017 _1904 0 0 0 0 0 0 0 0
2921 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0
Java
import java.util.Arrays;
public class FD {
public static void main(String args[]) {
double[] a = {90, 47, 58, 29, 22, 32, 55, 5, 55, 73};
System.out.println(Arrays.toString(dif(a, 1)));
System.out.println(Arrays.toString(dif(a, 2)));
System.out.println(Arrays.toString(dif(a, 9)));
System.out.println(Arrays.toString(dif(a, 10))); //let's test
System.out.println(Arrays.toString(dif(a, 11)));
System.out.println(Arrays.toString(dif(a, -1)));
System.out.println(Arrays.toString(dif(a, 0)));
}
public static double[] dif(double[] a, int n) {
if (n < 0)
return null; // if the programmer was dumb
for (int i = 0; i < n && a.length > 0; i++) {
double[] b = new double[a.length - 1];
for (int j = 0; j < b.length; j++){
b[j] = a[j+1] - a[j];
}
a = b; //"recurse"
}
return a;
}
}
- Output:
[-43.0, 11.0, -29.0, -7.0, 10.0, 23.0, -50.0, 50.0, 18.0] [54.0, -40.0, 22.0, 17.0, 13.0, -73.0, 100.0, -32.0] [-2921.0] [] [] null [90.0, 47.0, 58.0, 29.0, 22.0, 32.0, 55.0, 5.0, 55.0, 73.0]
JavaScript
ES6
(() => {
'use strict';
// forwardDifference :: Num a => [a] -> [a]
const forwardDifference = xs =>
zipWith(subtract)(xs)(tail(xs));
// nthForwardDifference :: Num a => [a] -> Int -> [a]
const nthForwardDifference = xs =>
index(iterate(forwardDifference)(xs)).Just;
//----------------------- TEST ------------------------
// main :: IO ()
const main = () =>
unlines(
take(10)(
iterate(forwardDifference)(
[90, 47, 58, 29, 22, 32, 55, 5, 55, 73]
)
).map((x, i) => justifyRight(2)('x')(i) + (
' -> '
) + JSON.stringify(x))
);
//----------------- GENERIC FUNCTIONS -----------------
// Just :: a -> Maybe a
const Just = x => ({
type: 'Maybe',
Nothing: false,
Just: x
});
// Nothing :: Maybe a
const Nothing = () => ({
type: 'Maybe',
Nothing: true,
});
// Tuple (,) :: a -> b -> (a, b)
const Tuple = a =>
b => ({
type: 'Tuple',
'0': a,
'1': b,
length: 2
});
// index (!!) :: [a] -> Int -> Maybe a
// index (!!) :: Generator (Int, a) -> Int -> Maybe a
// index (!!) :: String -> Int -> Maybe Char
const index = xs => i => {
const s = xs.constructor.constructor.name;
return 'GeneratorFunction' !== s ? (() => {
const v = xs[i];
return undefined !== v ? Just(v) : Nothing();
})() : Just(take(i)(xs), xs.next().value);
};
// iterate :: (a -> a) -> a -> Gen [a]
const iterate = f =>
function*(x) {
let v = x;
while (true) {
yield(v);
v = f(v);
}
};
// justifyRight :: Int -> Char -> String -> String
const justifyRight = n =>
// The string s, preceded by enough padding (with
// the character c) to reach the string length n.
c => s => n > s.length ? (
s.padStart(n, c)
) : s;
// length :: [a] -> Int
const length = xs =>
// Returns Infinity over objects without finite
// length. This enables zip and zipWith to choose
// the shorter argument when one is non-finite,
// like cycle, repeat etc
(Array.isArray(xs) || 'string' === typeof xs) ? (
xs.length
) : Infinity;
// map :: (a -> b) -> [a] -> [b]
const map = f =>
// The list obtained by applying f
// to each element of xs.
// (The image of xs under f).
xs => (
Array.isArray(xs) ? (
xs
) : xs.split('')
).map(f);
// subtract :: Num -> Num -> Num
const subtract = x =>
y => y - x;
// tail :: [a] -> [a]
const tail = xs =>
// A new list consisting of all
// items of xs except the first.
0 < xs.length ? xs.slice(1) : [];
// take :: Int -> [a] -> [a]
// take :: Int -> String -> String
const take = n =>
// The first n elements of a list,
// string of characters, or stream.
xs => 'GeneratorFunction' !== xs
.constructor.constructor.name ? (
xs.slice(0, n)
) : [].concat.apply([], Array.from({
length: n
}, () => {
const x = xs.next();
return x.done ? [] : [x.value];
}));
// unlines :: [String] -> String
const unlines = xs =>
// A single string formed by the intercalation
// of a list of strings with the newline character.
xs.join('\n');
// zipWith :: (a -> b -> c) -> [a] -> [b] -> [c]
const zipWith = f => xs => ys => {
const
lng = Math.min(length(xs), length(ys)),
[as, bs] = [xs, ys].map(take(lng));
return Array.from({
length: lng
}, (_, i) => f(as[i])(
bs[i]
));
};
// MAIN ---
return main();
})();
- Output:
0 -> [90,47,58,29,22,32,55,5,55,73] 1 -> [-43,11,-29,-7,10,23,-50,50,18] 2 -> [54,-40,22,17,13,-73,100,-32] 3 -> [-94,62,-5,-4,-86,173,-132] 4 -> [156,-67,1,-82,259,-305] 5 -> [-223,68,-83,341,-564] 6 -> [291,-151,424,-905] 7 -> [-442,575,-1329] 8 -> [1017,-1904] 9 -> [-2921]
jq
# If n is a non-negative number and if input is
# a (possibly empty) array of numbers,
# emit an array, even if the input list is too short:
def ndiff(n):
if n==0 then .
elif n == 1 then . as $in | [range(1;length) | $in[.] - $in[.-1]]
else ndiff(1) | ndiff(n-1)
end;
Example:
def s: [90, 47, 58, 29, 22, 32, 55, 5, 55, 73];
range(0;12) as $i | (s|ndiff($i))
- Output:
$ jq -c -n -f forward-difference.jq
[90,47,58,29,22,32,55,5,55,73]
[-43,11,-29,-7,10,23,-50,50,18]
[54,-40,22,17,13,-73,100,-32]
[-94,62,-5,-4,-86,173,-132]
[156,-67,1,-82,259,-305]
[-223,68,-83,341,-564]
[291,-151,424,-905]
[-442,575,-1329]
[1017,-1904]
[-2921]
[]
[]
Julia
Using the built-in diff
function, which returns the 1st forward difference:
ndiff(A::Array, n::Integer) = n < 1 ? A : diff(ndiff(A, n-1))
s = [90, 47, 58, 29, 22, 32, 55, 5, 55, 73]
println.(collect(ndiff(s, i) for i in 0:9))
- Output:
[90, 47, 58, 29, 22, 32, 55, 5, 55, 73] [-43, 11, -29, -7, 10, 23, -50, 50, 18] [54, -40, 22, 17, 13, -73, 100, -32] [-94, 62, -5, -4, -86, 173, -132] [156, -67, 1, -82, 259, -305] [-223, 68, -83, 341, -564] [291, -151, 424, -905] [-442, 575, -1329] [1017, -1904] [-2921]
K4
fd:1_-':
To compute the nth forward difference, call as:
n fd/
In order to obtain all intermediate results, call as:
n fd\
- Examples:
fd 1 2 4 7 11 16 1 2 3 4 5 2 fd/1 2 4 7 11 16 1 1 1 1 3 fd\1 2 4 7 11 16 (1 2 4 7 11 16;1 2 3 4 5;1 1 1 1;0 0 0)
Kotlin
// version 1.1.2
fun forwardDifference(ia: IntArray, order: Int): IntArray {
if (order < 0) throw IllegalArgumentException("Order must be non-negative")
if (order == 0) return ia
val size = ia.size
if (size == 0) return ia // same empty array
if (order >= size) return intArrayOf() // new empty array
var old = ia
var new = old
var count = order
while (count-- >= 1) {
new = IntArray(old.size - 1)
for (i in 0 until new.size) new[i] = old[i + 1] - old[i]
old = new
}
return new
}
fun printArray(ia: IntArray) {
print("[")
for (i in 0 until ia.size) {
print("%5d".format(ia[i]))
if (i < ia .size - 1) print(", ")
}
println("]")
}
fun main(args: Array<String>) {
val ia = intArrayOf(90, 47, 58, 29, 22, 32, 55, 5, 55, 73)
for (order in 0..ia.size) {
val fd = forwardDifference(ia, order)
print("%2d".format(order) + ": ")
printArray(fd)
}
}
- Output:
0: [ 90, 47, 58, 29, 22, 32, 55, 5, 55, 73] 1: [ -43, 11, -29, -7, 10, 23, -50, 50, 18] 2: [ 54, -40, 22, 17, 13, -73, 100, -32] 3: [ -94, 62, -5, -4, -86, 173, -132] 4: [ 156, -67, 1, -82, 259, -305] 5: [ -223, 68, -83, 341, -564] 6: [ 291, -151, 424, -905] 7: [ -442, 575, -1329] 8: [ 1017, -1904] 9: [-2921] 10: []
Lambdatalk
{def fdiff
{lambda {:l}
{A.new
{S.map {{lambda {:l :i} {- {A.get {+ :i 1} :l} {A.get :i :l}} } :l}
{S.serie 0 {- {A.length :l} 2}}}}}}
-> fdiff
{def disp
{lambda {:l}
{if {A.empty? {A.rest :l}}
then else {let { {:l {fdiff :l}} } {br}:l {disp :l}}}}}
-> disp
{def L {A.new 90 47 58 29 22 32 55 5 55 73}}
-> L
{disp {L}}
->
[-43,11,-29,-7,10,23,-50,50,18]
[54,-40,22,17,13,-73,100,-32]
[-94,62,-5,-4,-86,173,-132]
[156,-67,1,-82,259,-305]
[-223,68,-83,341,-564]
[291,-151,424,-905]
[-442,575,-1329]
[1017,-1904]
[-2921]
Lasso
#!/usr/bin/lasso9
define forwardDiff(values, order::integer=1) => {
!#order ? return #values->asArray
local(result = array)
iterate(#values) => {
loop_count < #values->size ?
#result->insert(#values->get(loop_count+1) - #values->get(loop_count))
}
#order > 1 ? #result = forwardDiff(#result, #order-1)
return #result
}
local(data = (:90, 47, 58, 29, 22, 32, 55, 5, 55, 73))
with x in generateSeries(0, #data->size-1)
do stdoutnl(#x + ': ' + forwardDiff(#data, #x))
- Output:
0: array(90, 47, 58, 29, 22, 32, 55, 5, 55, 73) 1: array(-43, 11, -29, -7, 10, 23, -50, 50, 18) 2: array(54, -40, 22, 17, 13, -73, 100, -32) 3: array(-94, 62, -5, -4, -86, 173, -132) 4: array(156, -67, 1, -82, 259, -305) 5: array(-223, 68, -83, 341, -564) 6: array(291, -151, 424, -905) 7: array(-442, 575, -1329) 8: array(1017, -1904) 9: array(-2921)
Logo
to fwd.diff :l
if empty? :l [output []]
if empty? bf :l [output []]
output fput (first bf :l)-(first :l) fwd.diff bf :l
end
to nth.fwd.diff :n :l
if :n = 0 [output :l]
output nth.fwd.diff :n-1 fwd.diff :l
end
show nth.fwd.diff 9 [90 47 58 29 22 32 55 5 55 73]
[-2921]
Lua
function dif(a, b, ...)
if(b) then return b-a, dif(b, ...) end
end
function dift(t) return {dif(unpack(t))} end
print(unpack(dift{1,3,6,10,15}))
M2000 Interpreter
Function Diff(a()) get an array by value (a shallow copy)
Form 80, 40
Module Forward_difference {
Print $(0,6) ' 6 characters column
Dim a(), b()
a()=(90,47,58,29,22,32,55,5,55,73)
Function Diff(a()) {
for i=0 to len(a())-2: a(i)=a(i+1)-a(i):Next i
Dim a(len(a())-1) ' redim one less
=a()
}
Print "Original:","",a()
b()=a() ' copy a() to b()
k=1
While len(b())>1 {
b()=Diff(b()) ' copy returned array to b()
Print "Difference ";k;":",b()
k++
}
}
Forward_difference
- Output:
Original: 90 47 58 29 22 32 55 5 55 73 Difference 1: -43 11 -29 -7 10 23 -50 50 18 Difference 2: 54 -40 22 17 13 -73 100 -32 Difference 3: -94 62 -5 -4 -86 173 -132 Difference 4: 156 -67 1 -82 259 -305 Difference 5: -223 68 -83 341 -564 Difference 6: 291 -151 424 -905 Difference 7: -442 575 -1329 Difference 8: 1017 -1904 Difference 9: -2921
Mathematica / Wolfram Language
Built-in function:
i={3,5,12,1,6,19,6,2,4,9};
Differences[i]
- gives back:
{2, 7, -11, 5, 13, -13, -4, 2, 5}
The nth difference can be done as follows:
i={3,5,12,1,6,19,6,2,4,9};
Differences[i,n]
MATLAB / Octave
This is a built-in function. X is the list of numbers, n is the order of the forward difference.
Y = diff(X,n);
- Output:
1st order forward difference.
diff([1 2 3 4 5]) ans = 1 1 1 1
Maxima
ldiff(u, n) := block([m: length(u)], for j thru n do u: makelist(u[i + 1] - u[i], i, 1, m - j), u);
NetRexx
/* NetRexx*************************************************************
* Forward differences
* 18.08.2012 Walter Pachl derived from Rexx
**********************************************************************/
Loop n=-1 To 11
differences('90 47 58 29 22 32 55 5 55 73',n)
End
method differences(a,n) public static
--arr=Rexx[11] -- array must be declared (zero based)
arr='' -- alternative: indexed string
m=a.words
Select
When n<0 Then Say 'n is negative:' n '<' 0
When n>m Then Say 'n is too large:' n '>' m
Otherwise Do
Loop i=1 To m
arr[i]=a.word(i)
End
Loop i = 1 to n
t = arr[i]
Loop j = i+1 to m
u = arr[j]
arr[j] = arr[j]-t
t = u
end
end
ol=''
Loop i=n+1 to m
ol=ol arr[i]
End
Say n ol
End
End
Output is the same as for Rexx
Nial
Define forward difference for order 1
fd is - [rest, front]
- Output:
forward difference of 4th order
b := 90 47 58 29 22 32 55 5 55 73
4 fold fd b
= 156 -67 1 -82 259 -305
Nim
proc dif(s: seq[int]): seq[int] =
result = newSeq[int](s.len-1)
for i in 0..<s.high:
result[i] = s[i+1] - s[i]
proc difn(s: seq[int]; n: int): seq[int] =
if n > 0: difn(dif(s), n-1)
else: s
const s = @[90, 47, 58, 29, 22, 32, 55, 5, 55, 73]
echo difn(s, 0)
echo difn(s, 1)
echo difn(s, 2)
- Output:
@[90, 47, 58, 29, 22, 32, 55, 5, 55, 73] @[-43, 11, -29, -7, 10, 23, -50, 50, 18] @[54, -40, 22, 17, 13, -73, 100, -32]
Objeck
bundle Default {
class Test {
function : Main(args : String[]) ~ Nil {
a := [90.0, 47.0, 58.0, 29.0, 22.0, 32.0, 55.0, 5.0, 55.0, 73.0];
Print(Diff(a, 1));
Print(Diff(a, 2));
Print(Diff(a, 9));
}
function : Print(a : Float[]) ~ Nil {
if(a <> Nil) {
'['->Print();
each(i : a) {
a[i]->Print(); ','->Print();
};
']'->PrintLine();
};
}
function : Diff(a : Float[], n : Int) ~ Float[] {
if (n < 0) {
return Nil;
};
for(i := 0; i < n & a->Size() > 0; i += 1;) {
b := Float->New[a->Size() - 1];
for(j := 0; j < b->Size(); j += 1;){
b[j] := a[j+1] - a[j];
};
a := b;
};
return a;
}
}
}
OCaml
let rec forward_difference = function
a :: (b :: _ as xs) ->
b - a :: forward_difference xs
| _ ->
[]
let rec nth_forward_difference n xs =
if n = 0 then
xs
else
nth_forward_difference (pred n) (forward_difference xs)
- Output:
# nth_forward_difference 9 [90; 47; 58; 29; 22; 32; 55; 5; 55; 73];; - : int list = [-2921]
Oforth
: forwardDiff(l) l right(l size 1 -) l zipWith(#-) ;
: forwardDiffN(n, l) l #[ forwardDiff dup println ] times(n) ;
- Output:
10 [ 90, 47, 58, 29, 22, 32, 55, 5, 55, 73] forwardDiffN [-43, 11, -29, -7, 10, 23, -50, 50, 18] [54, -40, 22, 17, 13, -73, 100, -32] [-94, 62, -5, -4, -86, 173, -132] [156, -67, 1, -82, 259, -305] [-223, 68, -83, 341, -564] [291, -151, 424, -905] [-442, 575, -1329] [1017, -1904] [-2921] []
PARI/GP
fd(v)=vector(#v-1,i,v[i+1]-v[i]);
Pascal
Program ForwardDifferenceDemo(output);
procedure fowardDifference(list: array of integer);
var
b: array of integer;
i, newlength: integer;
begin
newlength := length(list) - 1;
if newlength > 0 then
begin
setlength(b, newlength);
for i := low(b) to high(b) do
begin
b[i] := list[i+1] - list[i];
write (b[i]:6);
end;
writeln;
fowardDifference(b);
end;
end;
var
a: array [1..10] of integer = (90, 47, 58, 29, 22, 32, 55, 5, 55, 73);
begin
fowardDifference(a);
end.
- Output:
:> ./ForwardDifference -43 11 -29 -7 10 23 -50 50 18 54 -40 22 17 13 -73 100 -32 -94 62 -5 -4 -86 173 -132 156 -67 1 -82 259 -305 -223 68 -83 341 -564 291 -151 424 -905 -442 575 -1329 1017 -1904 -2921
PascalABC.NET
function Convert(a: array of integer): array of integer;
begin
var n := a.Length;
var res := new integer[n-1];
for var i:=0 to n-2 do
res[i] := a[i+1]-a[i];
Result := res;
end;
begin
var a := |90, 47, 58, 29, 22, 32, 55, 5, 55, 73|;
while a.Length > 0 do
begin
Println(a);
a := Convert(a);
end;
end.
- Output:
[90,47,58,29,22,32,55,5,55,73] [-43,11,-29,-7,10,23,-50,50,18] [54,-40,22,17,13,-73,100,-32] [-94,62,-5,-4,-86,173,-132] [156,-67,1,-82,259,-305] [-223,68,-83,341,-564] [291,-151,424,-905] [-442,575,-1329] [1017,-1904] [-2921]
Perl
sub dif {
my @s = @_;
map { $s[$_+1] - $s[$_] } 0 .. $#s-1
}
@a = qw<90 47 58 29 22 32 55 5 55 73>;
while (@a) { printf('%6d', $_) for @a = dif @a; print "\n" }
- Output:
-43 11 -29 -7 10 23 -50 50 18 54 -40 22 17 13 -73 100 -32 -94 62 -5 -4 -86 173 -132 156 -67 1 -82 259 -305 -223 68 -83 341 -564 291 -151 424 -905 -442 575 -1329 1017 -1904 -2921
Phix
with javascript_semantics function fwd_diff_n(sequence s, integer order) assert(order<length(s)) s = deep_copy(s) for i=1 to order do for j=1 to length(s)-1 do s[j] = s[j+1]-s[j] end for s = s[1..-2] end for return s end function constant s = {90, 47, 58, 29, 22, 32, 55, 5, 55, 73} for i=1 to 9 do ?fwd_diff_n(s,i) end for
- Output:
{-43,11,-29,-7,10,23,-50,50,18} {54,-40,22,17,13,-73,100,-32} {-94,62,-5,-4,-86,173,-132} {156,-67,1,-82,259,-305} {-223,68,-83,341,-564} {291,-151,424,-905} {-442,575,-1329} {1017,-1904} {-2921}
PHP
<?php
function forwardDiff($anArray, $times = 1) {
if ($times <= 0) { return $anArray; }
for ($accumilation = array(), $i = 1, $j = count($anArray); $i < $j; ++$i) {
$accumilation[] = $anArray[$i] - $anArray[$i - 1];
}
if ($times === 1) { return $accumilation; }
return forwardDiff($accumilation, $times - 1);
}
class ForwardDiffExample extends PweExample {
function _should_run_empty_array_for_single_elem() {
$expected = array($this->rand()->int());
$this->spec(forwardDiff($expected))->shouldEqual(array());
}
function _should_give_diff_of_two_elem_as_single_elem() {
$twoNums = array($this->rand()->int(), $this->rand()->int());
$expected = array($twoNums[1] - $twoNums[0]);
$this->spec(forwardDiff($twoNums))->shouldEqual($expected);
}
function _should_compute_correct_forward_diff_for_longer_arrays() {
$diffInput = array(10, 2, 9, 6, 5);
$expected = array(-8, 7, -3, -1);
$this->spec(forwardDiff($diffInput))->shouldEqual($expected);
}
function _should_apply_more_than_once_if_specified() {
$diffInput = array(4, 6, 9, 3, 4);
$expectedAfter1 = array(2, 3, -6, 1);
$expectedAfter2 = array(1, -9, 7);
$this->spec(forwardDiff($diffInput, 1))->shouldEqual($expectedAfter1);
$this->spec(forwardDiff($diffInput, 2))->shouldEqual($expectedAfter2);
}
function _should_return_array_unaltered_if_no_times() {
$this->spec(forwardDiff($expected = array(1,2,3), 0))->shouldEqual($expected);
}
}
Picat
go =>
L = [90, 47, 58, 29, 22, 32, 55, 5, 55, 73],
foreach(I in 1..L.length-1)
println([d=I,diffi(L,I)])
end,
nl,
% All differences (a sublist to save space)
println(alldiffs(L[1..6])),
nl.
% Difference of the list
diff(L) = Diff =>
Diff = [L[I]-L[I-1] : I in 2..L.length].
% The i'th list difference
diffi(L,D) = Diff =>
Diff1 = L,
foreach(_I in 1..D)
Diff1 := diff(Diff1)
end,
Diff = Diff1.
% all differences
alldiffs(L) = Diffs =>
Diffs1 = [],
Diff = L,
foreach(_I in 1..L.length-1)
Diff := diff(Diff),
Diffs1 := Diffs1 ++ [Diff]
end,
Diffs = Diffs1.
- Output:
[d = 1,[-43,11,-29,-7,10,23,-50,50,18]] [d = 2,[54,-40,22,17,13,-73,100,-32]] [d = 3,[-94,62,-5,-4,-86,173,-132]] [d = 4,[156,-67,1,-82,259,-305]] [d = 5,[-223,68,-83,341,-564]] [d = 6,[291,-151,424,-905]] [d = 7,[-442,575,-1329]] [d = 8,[1017,-1904]] [d = 9,[-2921]] [[-43,11,-29,-7,10],[54,-40,22,17],[-94,62,-5],[156,-67],[-223]]
PicoLisp
(de fdiff (Lst)
(mapcar - (cdr Lst) Lst) )
(for (L (90 47 58 29 22 32 55 5 55 73) L (fdiff L))
(println L) )
- Output:
(90 47 58 29 22 32 55 5 55 73) (-43 11 -29 -7 10 23 -50 50 18) (54 -40 22 17 13 -73 100 -32) (-94 62 -5 -4 -86 173 -132) (156 -67 1 -82 259 -305) (-223 68 -83 341 -564) (291 -151 424 -905) (-442 575 -1329) (1017 -1904) (-2921)
PL/I
/* Forward differences. */ /* 23 April 2010 */
differences: procedure options (main);
declare a(10) fixed(10) static initial
(7, 3, 9, 250, 300, 4, 68, 72, 154, 601);
declare (i, j, m, n, t, u) fixed binary;
m = hbound(a,1);
get (n); if n > m then signal error;
put skip edit (a) (F(7));
do i = 1 to n;
t = a(i);
do j = i+1 to m;
u = a(j);
a(j) = a(j) - t;
t = u;
end;
put skip edit (a) (F(7));
end;
put skip edit ((a(i) do i = n+1 to m)) (F(9));
end differences;
Plain English
To add a fraction to some fraction things:
Allocate memory for a fraction thing.
Put the fraction into the fraction thing's fraction.
Append the fraction thing to the fraction things.
To create some fraction things:
Add 90-1/2 to the fraction things.
Add 47/1 to the fraction things.
Add 58/1 to the fraction things.
Add 29/1 to the fraction things.
Add 22/1 to the fraction things.
Add 32/1 to the fraction things.
Add 55/1 to the fraction things.
Add 5/1 to the fraction things.
Add 55/1 to the fraction things.
Add 73-1/2 to the fraction things.
To find the difference of some fraction things:
If the fraction things' count is less than 2, exit.
Get a fraction thing from the fraction things.
Loop.
If the fraction thing's next is nil, remove the fraction thing from the fraction things; destroy the fraction thing; exit.
Put the fraction thing's next's fraction minus the fraction thing's fraction into the fraction thing's fraction.
Put the fraction thing's next into the fraction thing.
Repeat.
To find the difference of some fraction things given an order:
If a counter is past the order, exit.
Find the difference of the fraction things.
Repeat.
A fraction thing is a thing with a fraction.
An order is a number.
To run:
Start up.
Create some fraction things.
Write "Original list:" on the console.
Show the fraction things.
Find the difference of the fraction things given 4.
Write "Order 4 forward difference:" on the console.
Show the fraction things.
Destroy the fraction things.
Wait for the escape key.
Shut down.
To show some fraction things:
Get a fraction thing from the fraction things.
Loop.
If the fraction thing is nil, write "" on the console; exit.
Write "" then the fraction thing's fraction on the console without advancing.
If the fraction thing's next is not nil, write ", " on the console without advancing.
Put the fraction thing's next into the fraction thing.
Repeat.
- Output:
Original list: 90-1/2, 47, 58, 29, 22, 32, 55, 5, 55, 73-1/2 Order 4 forward difference: 156-1/2, -67, 1, -82, 259, -304-1/2
Pop11
define forward_difference(l);
lvars res = [], prev, el;
if l = [] then
return([]);
endif;
front(l) -> prev;
for el in back(l) do
cons(el - prev, res) -> res;
el -> prev;
endfor;
rev(res);
enddefine;
define nth_difference(l, n);
lvars res = l, i;
for i from 1 to n do
forward_difference(res) -> res;
endfor;
res;
enddefine;
PowerShell
function Forward-Difference( [UInt64] $n, [Array] $f )
{
$flen = $f.length
if( $flen -gt [Math]::Max( 1, $n ) )
{
0..( $flen - $n - 1 ) | ForEach-Object {
$l=0;
for( $k = 0; $k -le $n; $k++ )
{
$j = 1
for( $i = 1; $i -le $k; $i++ )
{
$j *= ( ( $n - $k + $i ) / $i )
}
$l += $j * ( 1 - 2 * ( ( $n - $k ) % 2 ) ) * $f[ $_ + $k ]
}
$l
}
}
}
Forward-Difference 2 1,2,4,5
PureBasic
Procedure forward_difference(List a())
If ListSize(a()) <= 1
ClearList(a()): ProcedureReturn
EndIf
Protected NewList b()
CopyList(a(), b())
LastElement(a()): DeleteElement(a())
SelectElement(b(), 1)
ForEach a()
a() - b(): NextElement(b())
Next
EndProcedure
Procedure nth_difference(List a(), List b(), n)
Protected i
CopyList(a(), b())
For i = 1 To n
forward_difference(b())
Next
EndProcedure
Procedure.s display(List a())
Protected output.s
ForEach a()
output + Str(a()) + ","
Next
ProcedureReturn RTrim(output,",")
EndProcedure
DataSection
;list data
Data.i 10 ;element count
Data.i 90, 47, 58, 29, 22, 32, 55, 5, 55, 73
EndDataSection
;create and fill list
Define i
NewList a()
Read.i i
While i > 0
AddElement(a()): Read.i a(): i - 1
Wend
If OpenConsole()
NewList b()
For i = 1 To 10
nth_difference(a(), b(), i)
PrintN(Str(i) + " [" + display(b()) + "]")
Next
Print(#CRLF$ + #CRLF$ + "Press ENTER to exit"): Input()
CloseConsole()
EndIf
- Output:
1 [43,-11,29,7,-10,-23,50,-50,-18] 2 [54,-40,22,17,13,-73,100,-32] 3 [94,-62,5,4,86,-173,132] 4 [156,-67,1,-82,259,-305] 5 [223,-68,83,-341,564] 6 [291,-151,424,-905] 7 [442,-575,1329] 8 [1017,-1904] 9 [2921] 10 []
Python
Python 2
>>> dif = lambda s: [x-s[i] for i,x in enumerate(s[1:])]
>>> # or, dif = lambda s: [x-y for x,y in zip(s[1:],s)]
>>> difn = lambda s, n: difn(dif(s), n-1) if n else s
>>> s = [90, 47, 58, 29, 22, 32, 55, 5, 55, 73]
>>> difn(s, 0)
[90, 47, 58, 29, 22, 32, 55, 5, 55, 73]
>>> difn(s, 1)
[-43, 11, -29, -7, 10, 23, -50, 50, 18]
>>> difn(s, 2)
[54, -40, 22, 17, 13, -73, 100, -32]
>>> from pprint import pprint
>>> pprint( [difn(s, i) for i in xrange(10)] )
[[90, 47, 58, 29, 22, 32, 55, 5, 55, 73],
[-43, 11, -29, -7, 10, 23, -50, 50, 18],
[54, -40, 22, 17, 13, -73, 100, -32],
[-94, 62, -5, -4, -86, 173, -132],
[156, -67, 1, -82, 259, -305],
[-223, 68, -83, 341, -564],
[291, -151, 424, -905],
[-442, 575, -1329],
[1017, -1904],
[-2921]]
Python 3
Defining functions for first order and nth order forward difference:
'''Forward difference'''
from itertools import islice
from operator import sub
# forwardDifference :: Num a => [a] -> [a]
def forwardDifference(xs):
'''1st order forward difference of xs.
'''
return [sub(*x) for x in zip(xs[1:], xs)]
# nthForwardDifference :: Num a => [a] -> Int -> [a]
def nthForwardDifference(xs):
'''Nth order forward difference of xs.
'''
return index(iterate(forwardDifference)(xs))
# ------------------------- TEST --------------------------
# main :: IO ()
def main():
'''Nth order forward difference.'''
xs = [90, 47, 58, 29, 22, 32, 55, 5, 55, 73]
print('9th order forward difference of:')
print(xs)
print('')
print(
' -> ' + repr(nthForwardDifference(xs)(9))
)
print('\nSuccessive orders of forward difference:')
print(unlines([
str(i) + ' -> ' + repr(x) for i, x in
enumerate(take(10)(
iterate(forwardDifference)(xs)
))
]))
# ------------------- GENERIC FUNCTIONS -------------------
# index (!!) :: [a] -> Int -> a
def index(xs):
'''Item at given (zero-based) index.'''
return lambda n: None if 0 > n else (
xs[n] if (
hasattr(xs, "__getitem__")
) else next(islice(xs, n, None))
)
# iterate :: (a -> a) -> a -> Gen [a]
def iterate(f):
'''An infinite list of repeated
applications of f to x.
'''
def go(x):
v = x
while True:
yield v
v = f(v)
return go
# take :: Int -> [a] -> [a]
# take :: Int -> String -> String
def take(n):
'''The prefix of xs of length n,
or xs itself if n > length xs.
'''
return lambda xs: (
xs[0:n]
if isinstance(xs, (list, tuple))
else list(islice(xs, n))
)
# unlines :: [String] -> String
def unlines(xs):
'''A single string formed by the intercalation
of a list of strings with the newline character.
'''
return '\n'.join(xs)
# MAIN ---
if __name__ == '__main__':
main()
- Output:
9th order forward difference of: [90, 47, 58, 29, 22, 32, 55, 5, 55, 73] -> [-2921] Successive orders of forward difference: 0 -> [90, 47, 58, 29, 22, 32, 55, 5, 55, 73] 1 -> [-43, 11, -29, -7, 10, 23, -50, 50, 18] 2 -> [54, -40, 22, 17, 13, -73, 100, -32] 3 -> [-94, 62, -5, -4, -86, 173, -132] 4 -> [156, -67, 1, -82, 259, -305] 5 -> [-223, 68, -83, 341, -564] 6 -> [291, -151, 424, -905] 7 -> [-442, 575, -1329] 8 -> [1017, -1904] 9 -> [-2921]
Quackery
[ times
[ [] swap behead
swap witheach
[ tuck dip [ - join ] ]
drop ] ] is f-diff ( [ n --> [ )
' [ 90 47 58 29 22 32 55 5 55 73 ]
dup size times
[ dup i^
dup echo say ": "
f-diff echo cr ]
drop
- Output:
0: [ 90 47 58 29 22 32 55 5 55 73 ] 1: [ -43 11 -29 -7 10 23 -50 50 18 ] 2: [ 54 -40 22 17 13 -73 100 -32 ] 3: [ -94 62 -5 -4 -86 173 -132 ] 4: [ 156 -67 1 -82 259 -305 ] 5: [ -223 68 -83 341 -564 ] 6: [ 291 -151 424 -905 ] 7: [ -442 575 -1329 ] 8: [ 1017 -1904 ] 9: [ -2921 ]
R
forwarddif <- function(a, n) {
if ( n == 1 )
a[2:length(a)] - a[1:length(a)-1]
else {
r <- forwarddif(a, 1)
forwarddif(r, n-1)
}
}
fdiff <- function(a, n) {
r <- a
for(i in 1:n) {
r <- r[2:length(r)] - r[1:length(r)-1]
}
r
}
v <- c(90, 47, 58, 29, 22, 32, 55, 5, 55, 73)
print(forwarddif(v, 9))
print(fdiff(v, 9))
Racket
#lang racket
(define (forward-difference list)
(for/list ([x (cdr list)] [y list]) (- x y)))
(define (nth-forward-difference n list)
(for/fold ([list list]) ([n n]) (forward-difference list)))
(nth-forward-difference 9 '(90 47 58 29 22 32 55 5 55 73))
;; -> '(-2921)
Raku
(formerly Perl 6)
Here we use signature matching to bind both an entire array and a version missing the head. The Z- operator is a zip metaoperator with a minus to subtract the two lists pairwise. It's almost a shame to define difn, since the series and subscript are hardly longer than the call itself would be, and arguably more self-documenting than the name of the function would be.
sub dif(@array [$, *@tail]) { @tail Z- @array }
sub difn($array, $n) { ($array, &dif ... *)[$n] }
REXX
no error checking
The REXX version uses the same (input) numbers (for the default) as the Ada example.
This version allows a specification of the list of numbers and/or which order to process.
/*REXX program computes the forward difference of a list of numbers. */
numeric digits 100 /*ensure enough accuracy (decimal digs)*/
parse arg e ',' N /*get a list: ε1 ε2 ε3 ε4 ··· , order */
if e=='' then e=90 47 58 29 22 32 55 5 55 73 /*Not specified? Then use the default.*/
#=words(e) /*# is the number of elements in list.*/
/* [↓] assign list numbers to @ array.*/
do i=1 for #; @.i=word(e, i)/1; end /*i*/ /*process each number one at a time. */
/* [↓] process the optional order. */
if N=='' then parse value 0 # # with bot top N /*define the default order range. */
else parse var N bot 1 top /*Not specified? Then use only 1 order*/
say right(# 'numbers:', 44) e /*display the header title and ··· */
say left('', 44)copies('─', length(e)+2) /* " " " fence. */
/* [↓] where da rubber meets da road. */
do o=bot to top; do r=1 for #; !.r=@.r; end /*r*/; $=
do j=1 for o; d=!.j; do k=j+1 to #; parse value !.k !.k-d with d !.k; end /*k*/
end /*j*/
do i=o+1 to #; $=$ !.i/1; end /*i*/
if $=='' then $=' [null]'
say right(o, 7)th(o)'─order forward difference vector =' $
end /*o*/
exit /*stick a fork in it, we're all done. */
/*──────────────────────────────────────────────────────────────────────────────────────*/
th: procedure; x=abs(arg(1)); return word('th st nd rd',1+x//10*(x//100%10\==1)*(x//10<4))
output when using the default input:
10 numbers: 90 47 58 29 22 32 55 5 55 73 ────────────────────────────── 0th-order forward difference vector = 90 47 58 29 22 32 55 5 55 73 1st-order forward difference vector = -43 11 -29 -7 10 23 -50 50 18 2nd-order forward difference vector = 54 -40 22 17 13 -73 100 -32 3rd-order forward difference vector = -94 62 -5 -4 -86 173 -132 4th-order forward difference vector = 156 -67 1 -82 259 -305 5th-order forward difference vector = -223 68 -83 341 -564 6th-order forward difference vector = 291 -151 424 -905 7th-order forward difference vector = -442 575 -1329 8th-order forward difference vector = 1017 -1904 9th-order forward difference vector = -2921 10th-order forward difference vector = [null]
output when the Tcl's input was used: 90.5 47 58 29 22 32 55 5 55 73.5
10 numbers: 90.5 47 58 29 22 32 55 5 55 73.5 ────────────────────────────────── 0th-order forward difference vector = 90.5 47 58 29 22 32 55 5 55 73.5 1st-order forward difference vector = -43.5 11 -29 -7 10 23 -50 50 18.5 2nd-order forward difference vector = 54.5 -40 22 17 13 -73 100 -31.5 3rd-order forward difference vector = -94.5 62 -5 -4 -86 173 -131.5 4th-order forward difference vector = 156.5 -67 1 -82 259 -304.5 5th-order forward difference vector = -223.5 68 -83 341 -563.5 6th-order forward difference vector = 291.5 -151 424 -904.5 7th-order forward difference vector = -442.5 575 -1328.5 8th-order forward difference vector = 1017.5 -1903.5 9th-order forward difference vector = -2921 10th-order forward difference vector = [null]
with error checking
/*REXX program computes the forward difference of a list of numbers. */
numeric digits 100 /*ensure enough accuracy (decimal digs)*/
parse arg e ',' N /*get a list: ε1 ε2 ε3 ε4 ··· , order */
if e=='' then e=90 47 58 29 22 32 55 5 55 73 /*Not specified? Then use the default.*/
#=words(e) /*# is the number of elements in list.*/
/* [↓] verify list items are numeric. */
do i=1 for #; _=word(e, i) /*process each number one at a time. */
if \datatype(_, 'N') then call ser _ "isn't a valid number"; @.i=_/1
end /*i*/ /* [↑] removes superfluous stuff. */
/* [↓] process the optional order. */
if N=='' then parse value 0 # # with bot top N /*define the default order range. */
else parse var N bot 1 top /*Not specified? Then use only 1 order*/
if #==0 then call ser "no numbers were specified."
if N<0 then call ser N "(order) can't be negative."
if N># then call ser N "(order) can't be greater than" #
say right(# 'numbers:', 44) e /*display the header (title) and ··· */
say left('', 44)copies('─', length(e)+2) /*display the header fence. */
/* [↓] where da rubber meets da road. */
do o=bot to top; do r=1 for #; !.r=@.r; end /*r*/; $=
do j=1 for o; d=!.j; do k=j+1 to #; parse value !.k !.k-d with d !.k; end /*k*/
end /*j*/
do i=o+1 to #; $=$ !.i/1; end /*i*/
if $=='' then $=' [null]'
say right(o, 7)th(o)'─order forward difference vector =' $
end /*o*/
exit /*stick a fork in it, we're all done. */
/*──────────────────────────────────────────────────────────────────────────────────────*/
ser: say; say '***error***'; say arg(1); say; exit 13
th: procedure; x=abs(arg(1)); return word('th st nd rd',1+x//10*(x//100%10\==1)*(x//10<4))
output is the same as the REXX entry above.
with output alignment
/*REXX program computes the forward difference of a list of numbers. */
numeric digits 100 /*ensure enough accuracy (decimal digs)*/
parse arg e ',' N /*get a list: ε1 ε2 ε3 ε4 ··· , order */
if e=='' then e=90 47 58 29 22 32 55 5 55 73 /*Not specified? Then use the default.*/
#=words(e); w=5 /*# is the number of elements in list.*/
/* [↓] verify list items are numeric. */
do i=1 for #; _=word(e, i) /*process each number one at a time. */
if \datatype(_, 'N') then call ser _ "isn't a valid number"; @.i=_/1
w=max(w, length(@.i)) /*use the maximum length of an element.*/
end /*i*/ /* [↑] removes superfluous stuff. */
/* [↓] process the optional order. */
if N=='' then parse value 0 # # with bot top N /*define the default order range. */
else parse var N bot 1 top /*Not specified? Then use only 1 order*/
if #==0 then call ser "no numbers were specified."
if N<0 then call ser N "(order) can't be negative."
if N># then call ser N "(order) can't be greater than" #
_=; do k=1 for #; _=_ right(@.k, w); end /*k*/; _=substr(_, 2)
say right(# 'numbers:', 44) _ /*display the header title and ··· */
say left('', 44)copies('─', w*#+#) /* " " " fence. */
/* [↓] where da rubber meets da road. */
do o=bot to top; do r=1 for #; !.r=@.r; end /*r*/; $=
do j=1 for o; d=!.j; do k=j+1 to #; parse value !.k !.k-d with d !.k
w=max(w, length(!.k))
end /*k*/
end /*j*/
do i=o+1 to #; $=$ right(!.i/1, w); end /*i*/
if $=='' then $=' [null]'
say right(o, 7)th(o)'─order forward difference vector =' $
end /*o*/
exit /*stick a fork in it, we're all done. */
/*──────────────────────────────────────────────────────────────────────────────────────*/
ser: say; say '***error***'; say arg(1); say; exit 13
th: procedure; x=abs(arg(1)); return word('th st nd rd',1+x//10*(x//100%10\==1)*(x//10<4))
output when using the default input:
10 numbers: 90 47 58 29 22 32 55 5 55 73 ──────────────────────────────────────────────────────────── 0th─order forward difference vector = 90 47 58 29 22 32 55 5 55 73 1st─order forward difference vector = -43 11 -29 -7 10 23 -50 50 18 2nd─order forward difference vector = 54 -40 22 17 13 -73 100 -32 3rd─order forward difference vector = -94 62 -5 -4 -86 173 -132 4th─order forward difference vector = 156 -67 1 -82 259 -305 5th─order forward difference vector = -223 68 -83 341 -564 6th─order forward difference vector = 291 -151 424 -905 7th─order forward difference vector = -442 575 -1329 8th─order forward difference vector = 1017 -1904 9th─order forward difference vector = -2921 10th─order forward difference vector = [null]
Version 2
/* REXX ***************************************************************
* Forward differences
* 18.08.2012 Walter Pachl derived from PL/I
**********************************************************************/
Do n=-1 To 11
Call differences '90 47 58 29 22 32 55 5 55 73',n
End
Exit
differences: Procedure
Parse Arg a,n
m=words(a)
Select
When n<0 Then Say 'n is negative:' n '<' 0
When n>m Then Say 'n is too large:' n '>' m
Otherwise Do
Do i=1 By 1 while a<>''
Parse Var a a.i a
End
Do i = 1 to n;
t = a.i;
Do j = i+1 to m;
u = a.j
a.j = a.j-t;
t = u;
end;
end;
ol=''
Do k=n+1 to m
ol=ol a.k
End
Say n ol
End
End
Return
- Output:
for Java's input
n is negative: -1 < 0 0 90 47 58 29 22 32 55 5 55 73 1 -43 11 -29 -7 10 23 -50 50 18 2 54 -40 22 17 13 -73 100 -32 3 -94 62 -5 -4 -86 173 -132 4 156 -67 1 -82 259 -305 5 -223 68 -83 341 -564 6 291 -151 424 -905 7 -442 575 -1329 8 1017 -1904 9 -2921 10 n is too large: 11 > 10
Ring
# Project : Forward difference
s = [90, 47, 58, 29, 22, 32, 55, 5, 55, 73]
for p = 1 to 9
s = fwddiff(s)
showarray(s)
next
func fwddiff(s)
for j=1 to len(s)-1
s[j] = s[j+1]-s[j]
next
n = len(s)
del(s, n)
return s
func showarray(vect)
see "{"
svect = ""
for n = 1 to len(vect)
svect = svect + vect[n] + ", "
next
svect = left(svect, len(svect) - 2)
see svect
see "}" + nl
Output:
{-43, 11, -29, -7, 10, 23, -50, 50, 18} {54, -40, 22, 17, 13, -73, 100, -32} {-94, 62, -5, -4, -86, 173, -132} {156, -67, 1, -82, 259, -305} {-223, 68, -83, 341, -564} {291, -151, 424, -905} {-442, 575, -1329} {1017, -1904} {-2921}
RPL
Iterative approach
RPL code | Comment |
---|---|
≪
IF OVER SIZE OVER > THEN
WHILE DUP REPEAT
SWAP { } 2 3 PICK SIZE FOR j
OVER j GET + NEXT
LIST→ →ARRY
SWAP OVER SIZE { } + RDM -
SWAP 1 - END
DROP END
≫ ‘DIFFN’ STO
|
DIFFN ( [array] order → [nth_difference] )
if order < array size
while order > 0
initialize loop
to build { array[2]...array[n] }
convert list into array
pop last item of array and substract
order -= 1
clean stack
|
[90, 47, 58, 29, 22, 32, 55, 5, 55, 73] 1 DIFFN [90, 47, 58, 29, 22, 32, 55, 5, 55, 73] 3 DIFFN
- Output:
2: [-43, 11, -29, -7, 10, 23, -50, 50, 18] 1: [-94, 62, -5, -4, -86, 173, -132]
Direct approach
We use here local variables and algebraic notation to increase code readability.
RPL code | Comment |
---|---|
≪ → n ≪ 'F' STO { } 1 F SIZE 1 - FOR j -1 n ^ 'F' j GET * 1 n FOR k 'COMB(n,k)*(-1)^(n-k)*F(j+k)' EVAL + NEXT + NEXT LIST→ →ARRY 'F' PURGE ≫ ≫ ‘DIFFN’ STO |
DIFFN ( [array] order → [nth_difference] )
store array in global variable F
initialize output array building loop
put 1st term of sum (k=0) in stack // reverse Polish notation
loop
add terms for 0<k≤n // algebraic notation
add sum to list
convert list into array, clean memory
|
Postfix fans can replace the following line
'COMB(n,k)*(-1)^(n-k)*F(j+k)' EVAL + NEXT
by
n k COMB -1 n k - ^ * 'F' j k + GET * + NEXT
On HP-48G and newer models, first difference is directly returned by the ΔLIST
instruction, so we can simplify the above code, provided that input is given as a list { } instead of an array [ ]:
≪ 1 SWAP START ΔLIST NEXT ≫ ‘DIFFN’ STO
Ruby
This code uses new features from Ruby 1.8.7:
- Enumerable#each_cons is a new method.
- Integer#times, without a block, returns an enumerator.
def dif(s)
s.each_cons(2).collect { |x, y| y - x }
end
def difn(s, n)
n.times.inject(s) { |s, | dif(s) }
end
- Example usage:
p dif([1, 23, 45, 678]) # => [22, 22, 633]
p difn([1, 23, 45, 678], 2) # => [0, 611]
Rust
fn forward_difference(input_seq: Vec<i32>, order: u32) -> Vec<i32> {
match order {
0 => input_seq,
1 => {
let input_seq_iter = input_seq.into_iter();
let clone_of_input_seq_iter = input_seq_iter.clone();
input_seq_iter.zip(clone_of_input_seq_iter.skip(1)).map(|(current, next)| next - current).collect()
},
_ => forward_difference(forward_difference(input_seq, order - 1), 1),
}
}
fn main() {
let mut sequence = vec![90, 47, 58, 29, 22, 32, 55, 5, 55, 73];
loop {
println!("{:?}", sequence);
sequence = forward_difference(sequence, 1);
if sequence.is_empty() {
break;
}
}
}
- Output:
[90, 47, 58, 29, 22, 32, 55, 5, 55, 73] [-43, 11, -29, -7, 10, 23, -50, 50, 18] [54, -40, 22, 17, 13, -73, 100, -32] [-94, 62, -5, -4, -86, 173, -132] [156, -67, 1, -82, 259, -305] [-223, 68, -83, 341, -564] [291, -151, 424, -905] [-442, 575, -1329] [1017, -1904] [-2921]
Scala
def fdiff(xs: List[Int]) = (xs.tail, xs).zipped.map(_ - _)
def fdiffn(i: Int, xs: List[Int]): List[Int] = if (i == 1) fdiff(xs) else fdiffn(i - 1, fdiff(xs))
- Example:
val l=List(90,47,58,29,22,32,55,5,55,73)
(1 to 9)foreach(x=>println(fdiffn(x,l)))
- Output:
List(-43, 11, -29, -7, 10, 23, -50, 50, 18) List(54, -40, 22, 17, 13, -73, 100, -32) List(-94, 62, -5, -4, -86, 173, -132) List(156, -67, 1, -82, 259, -305) List(-223, 68, -83, 341, -564) List(291, -151, 424, -905) List(-442, 575, -1329) List(1017, -1904) List(-2921)
Scheme
(define (forward-diff lst)
(if (or (null? lst) (null? (cdr lst)))
'()
(cons (- (cadr lst) (car lst))
(forward-diff (cdr lst)))))
(define (nth-forward-diff n xs)
(if (= n 0)
xs
(nth-forward-diff (- n 1)
(forward-diff xs))))
- Output:
> (nth-forward-diff 9 '(90 47 58 29 22 32 55 5 55 73)) (-2921)
Seed7
$ include "seed7_05.s7i";
const func array integer: forwardDifference (in array integer: data) is func
result
var array integer: diffResult is 0 times 0;
local
var integer: index is 0;
begin
for index range 1 to pred(length(data)) do
diffResult &:= -data[index] + data[succ(index)];
end for;
end func;
const proc: main is func
local
var array integer: data is [] (90, 47, 58, 29, 22, 32, 55, 5, 55, 73);
var integer: level is 0;
var integer: number is 0;
var boolean: firstElement is TRUE;
begin
for level range 0 to length(data) do
firstElement := TRUE;
for number range data do
if not firstElement then
write(", ");
end if;
firstElement := FALSE;
write(number);
end for;
writeln;
data := forwardDifference(data);
end for;
end func;
- Output:
90, 47, 58, 29, 22, 32, 55, 5, 55, 73 -43, 11, -29, -7, 10, 23, -50, 50, 18 54, -40, 22, 17, 13, -73, 100, -32 -94, 62, -5, -4, -86, 173, -132 156, -67, 1, -82, 259, -305 -223, 68, -83, 341, -564 291, -151, 424, -905 -442, 575, -1329 1017, -1904 -2921
SequenceL
Solution that keeps track of intermediate values:
forwardDifference(x(1), n) := forwardDifferenceHelper(x, n, [x]);
forwardDifferenceHelper(x(1), n, result(2)) :=
let
difference := tail(x) - x[1 ... size(x) - 1];
in
result when n = 0 or size(x) = 1 else
forwardDifferenceHelper(difference, n - 1, result ++ [difference]);
If no intermediate values are needed, the following is sufficient:
forwardDifference(x(1),n) :=
x when n = 0 or size(x) = 1 else
forwardDifference(tail(x) - x[1 ... size(x) - 1], n - 1);
Sidef
func dif(arr) {
gather {
for i (0 ..^ arr.end) {
take(arr[i+1] - arr[i])
}
}
}
func difn(n, arr) {
{ arr = dif(arr) } * n
arr
}
say dif([1, 23, 45, 678]) # => [22, 22, 633]
say difn(2, [1, 23, 45, 678]) # => [0, 611]
Slate
s@(Sequence traits) forwardDifference
[
s allButFirst with: s allButLast collect: #- `er
].
s@(Sequence traits) forwardDifference
"Without creating two intermediate throwaway Sequences."
[
result ::= s allButFirst.
result doWithIndex: [| :nextValue :index | result at: index infect: [| :oldValue | oldValue - (s at: index)].
result
].
s@(Sequence traits) forwardDifference: n
[
(0 below: n) inject: s into: [| :seq :_ | seq forwardDifference]
].
- Usage:
#data := ##(90 47 58 29 22 32 55 5 55 73).
data keysDo: [| :index | inform: (data forwardDifference: index) printString].
Smalltalk
Array extend [
difference [
^self allButFirst with: self allButLast collect: [ :a :b | a - b ]
]
nthOrderDifference: n [
^(1 to: n) inject: self into: [ :old :unused | old difference ]
]
]
s := #(90 47 58 29 22 32 55 5 55 73)
1 to: s size - 1 do: [ :i |
(s nthOrderDifference: i) printNl ]
SQL
WITH RECURSIVE
T0 (N, ITEM, LIST, NEW_LIST) AS
(
SELECT 1,
NULL,
'90,47,58,29,22,32,55,5,55,73' || ',',
NULL
UNION ALL
SELECT CASE
WHEN SUBSTR(LIST, INSTR(LIST, ',') + 1, LENGTH(LIST)) = ''
THEN N + 1
ELSE N
END,
CASE
WHEN SUBSTR(LIST, INSTR(LIST, ',') + 1, LENGTH(LIST)) <> ''
THEN SUBSTR(LIST, 1, INSTR(LIST, ',') - 1)
ELSE NULL
END,
CASE
WHEN SUBSTR(LIST, INSTR(LIST, ',') + 1, LENGTH(LIST)) = ''
THEN IFNULL(NEW_LIST || (SUBSTR(LIST, 1, INSTR(LIST, ',') - 1) - ITEM) || ',', '')
ELSE SUBSTR(LIST, INSTR(LIST, ',') + 1, LENGTH(LIST))
END,
CASE
WHEN SUBSTR(LIST, INSTR(LIST, ',') + 1, LENGTH(LIST)) <> ''
THEN IFNULL(NEW_LIST, '') || IFNULL((SUBSTR(LIST, 1, INSTR(LIST, ',') - 1) - ITEM) || ',', '')
ELSE NULL
END
FROM T0
WHERE INSTR(LIST, ',') > 0
)
SELECT N,
TRIM(LIST, ',') LIST
FROM T0
WHERE NEW_LIST IS NULL
AND LIST <> ''
ORDER BY N;
Standard ML
fun forward_difference xs = ListPair.map op- (tl xs, xs)
fun nth_forward_difference n xs =
if n = 0 then
xs
else
nth_forward_difference (n-1) (forward_difference xs)
- Output:
- nth_forward_difference 9 [90, 47, 58, 29, 22, 32, 55, 5, 55, 73]; val it = [~2921] : int list
Stata
It's possible to implement differences using row indices. For instance, first forward differences of a variable x can be defined by:
gen y=x[_n+1]-x[_n]
However, it's much more natural to use time-series varlists. In order to use them, it's necessary to first set a time variable, which may be simply an index variable.
* First create a dataset
clear all
set obs 100
gen i=_n
tsset i
gen x=rnormal()
* Differences
display "Difference order?" _request(k)
gen y=D${k}F${k}.x
Swift
func forwardsDifference<T: SignedNumeric>(of arr: [T]) -> [T] {
return zip(arr.dropFirst(), arr).map({ $0.0 - $0.1 })
}
func nthForwardsDifference<T: SignedNumeric>(of arr: [T], n: Int) -> [T] {
assert(n >= 0)
switch (arr, n) {
case ([], _):
return []
case let (arr, 0):
return arr
case let (arr, i):
return nthForwardsDifference(of: forwardsDifference(of: arr), n: i - 1)
}
}
for diff in (0...9).map({ nthForwardsDifference(of: [90, 47, 58, 29, 22, 32, 55, 5, 55, 73], n: $0) }) {
print(diff)
}
- Output:
[90, 47, 58, 29, 22, 32, 55, 5, 55, 73] [-43, 11, -29, -7, 10, 23, -50, 50, 18] [54, -40, 22, 17, 13, -73, 100, -32] [-94, 62, -5, -4, -86, 173, -132] [156, -67, 1, -82, 259, -305] [-223, 68, -83, 341, -564] [291, -151, 424, -905] [-442, 575, -1329] [1017, -1904] [-2921]
Tcl
proc do_fwd_diff {list} {
set previous [lindex $list 0]
set new [list]
foreach current [lrange $list 1 end] {
lappend new [expr {$current - $previous}]
set previous $current
}
return $new
}
proc fwd_diff {list order} {
while {$order >= 1} {
set list [do_fwd_diff $list]
incr order -1
}
return $list
}
set a {90.5 47 58 29 22 32 55 5 55 73.5}
for {set order 0} {$order <= 10} {incr order} {
puts [format "%d\t%s" $order [fwd_diff $a $order]]
}
- Output:
0 90.5 47 58 29 22 32 55 5 55 73.5 1 -43.5 11 -29 -7 10 23 -50 50 18.5 2 54.5 -40 22 17 13 -73 100 -31.5 3 -94.5 62 -5 -4 -86 173 -131.5 4 156.5 -67 1 -82 259 -304.5 5 -223.5 68 -83 341 -563.5 6 291.5 -151 424 -904.5 7 -442.5 575 -1328.5 8 1017.5 -1903.5 9 -2921.0 10
Ursala
This function doesn't need to be defined because it's in a library already, but it could be defined like this:
#import std
#import nat
#import flo
nth_diff "n" = rep"n" minus*typ
test program:
test_data = <90.,47.,58.,29.,22.,32.,55.,5.,55.,73.>
#show+
examples =
printf/*=*' %0.0f' <
nth_diff6 test_data,
nth_diff7 test_data>
- Output:
291 -151 424 -905 -442 575 -1329
Visual Basic .NET
Module ForwardDifference
Sub Main()
Dim lNum As New List(Of Integer)(New Integer() {90, 47, 58, 29, 22, 32, 55, 5, 55, 73})
For i As UInteger = 0 To 9
Console.WriteLine(String.Join(" ", (From n In Difference(i, lNum) Select String.Format("{0,5}", n)).ToArray()))
Next
Console.ReadKey()
End Sub
Private Function Difference(ByVal Level As UInteger, ByVal Numbers As List(Of Integer)) As List(Of Integer)
If Level >= Numbers.Count Then Throw New ArgumentOutOfRangeException("Level", "Level must be less than number of items in Numbers")
For i As Integer = 1 To Level
Numbers = (From n In Enumerable.Range(0, Numbers.Count - 1) _
Select Numbers(n + 1) - Numbers(n)).ToList()
Next
Return Numbers
End Function
End Module
- Output:
90 47 58 29 22 32 55 5 55 73 -43 11 -29 -7 10 23 -50 50 18 54 -40 22 17 13 -73 100 -32 -94 62 -5 -4 -86 173 -132 156 -67 1 -82 259 -305 -223 68 -83 341 -564 291 -151 424 -905 -442 575 -1329 1017 -1904 -2921
Visual FoxPro
#DEFINE CTAB CHR(9)
LOCAL lcList As String, i As Integer, n As Integer
n = 10
LOCAL ARRAY aa[n]
CLEAR
lcList = "90,47,58,29,22,32,55,5,55,73"
FOR i = 1 TO n
aa[i] = VAL(GETWORDNUM(lcList, i, ","))
ENDFOR
ShowOutput("Original", @aa)
k = n - 1
FOR i = 1 TO n - 1
ForwardDiff(@aa)
ShowOutput("Difference " + TRANSFORM(i), @aa)
ENDFOR
PROCEDURE ForwardDiff(a)
LOCAL i As Integer, n As Integer
n = ALEN(a)
LOCAL ARRAY b[n-1]
FOR i = 1 TO n - 1
b[i] = a[i+1] - a[i]
ENDFOR
DIMENSION a[n-1]
ACOPY(b, a)
ENDPROC
PROCEDURE ShowOutput(lcLabel, zz)
LOCAL i As Integer, n As Integer, lcTxt As String
n = ALEN(zz)
lcTxt = lcLabel + ":" + CTAB
FOR i = 1 TO n
lcTxt = lcTxt + TRANSFORM(zz[i]) + CTAB
ENDFOR
lcTxt = LEFT(lcTxt, LEN(lcTxt) - 1)
? lcTxt
ENDPROC
- Output:
Original: 90 47 58 29 22 32 55 5 55 73 Difference 1: -43 11 -29 -7 10 23 -50 50 18 Difference 2: 54 -40 22 17 13 -73 100 -32 Difference 3: -94 62 -5 -4 -86 173 -132 Difference 4: 156 -67 1 -82 259 -305 Difference 5: -223 68 -83 341 -564 Difference 6: 291 -151 424 -905 Difference 7: -442 575 -1329 Difference 8: 1017 -1904 Difference 9: -2921
Wren
import "./fmt" for Fmt
var forwardDiff = Fn.new { |a, order|
if (order < 0) Fiber.abort("Order must be a non-negative integer.")
if (a.count == 0) return
Fmt.print(" 0: $5d", a)
if (a.count == 1) return
if (order == 0) return
for (o in 1..order) {
var b = List.filled(a.count-1, 0)
for (i in 0...b.count) b[i] = a[i+1] - a[i]
Fmt.print("$2d: $5d", o, b)
if (b.count == 1) return
a = b
}
}
forwardDiff.call([90, 47, 58, 29, 22, 32, 55, 5, 55, 73], 9)
- Output:
0: 90 47 58 29 22 32 55 5 55 73 1: -43 11 -29 -7 10 23 -50 50 18 2: 54 -40 22 17 13 -73 100 -32 3: -94 62 -5 -4 -86 173 -132 4: 156 -67 1 -82 259 -305 5: -223 68 -83 341 -564 6: 291 -151 424 -905 7: -442 575 -1329 8: 1017 -1904 9: -2921
XPL0
\Calculate forward differences
\Sets elements of B to the first order forward differences of A.
\A should have bounds 1 :: N, B should have bounds 1 :: N - 1.
procedure FirstOrderFDifference ( A, B, N );
integer A, B, N, I;
for I := 2 to N do B( I - 1 ) := A( I ) - A( I - 1 );
integer V ( 1 + 10 );
integer Diff( 1 + 9 );
integer VPos, Length, List, I, Order;
begin
\construct the initial values array
VPos := 1;
List:= [90, 47, 58, 29, 22, 32, 55, 5, 55, 73];
for I := 0 to 10-1 do begin
V( VPos ) := List( I );
VPos := VPos + 1
end;
\calculate and show the differences
Format(8, 0); \set output format
Length := 10;
for Order := 1 to Length - 1 do begin
FirstOrderFDifference( V, Diff, Length );
Length := Length - 1;
IntOut(0, Order); Text(0, " : ");
for I := 1 to Length do RlOut(0, float(Diff( I ) ));
CrLf(0);
for I := 1 to Length do V( I ) := Diff( I )
end
end
- Output:
1 : -43 11 -29 -7 10 23 -50 50 18 2 : 54 -40 22 17 13 -73 100 -32 3 : -94 62 -5 -4 -86 173 -132 4 : 156 -67 1 -82 259 -305 5 : -223 68 -83 341 -564 6 : 291 -151 424 -905 7 : -442 575 -1329 8 : 1017 -1904 9 : -2921
zkl
fcn forwardDiff(lst){
if(lst.len()<2)
return(T);
return(T(lst[1]-lst[0]).extend(forwardDiff(lst[1,*])))
}
fcn nthForwardDiff(n,xs){
if(n==0)
return(xs);
return(nthForwardDiff(n-1,forwardDiff(xs))) // tail recursion
}
nthForwardDiff(9,T(90, 47, 58, 29, 22, 32, 55, 5, 55, 73)).println();
- Output:
L(-2921)
ZX Spectrum Basic
10 DATA 9,0,1,2,4,7,4,2,1,0
20 LET p=1
30 READ n: DIM b(n)
40 FOR i=1 TO n
50 READ b(i)
60 NEXT i
70 FOR j=1 TO p
80 FOR i=1 TO n-j
90 LET b(i)=b(i+1)-b(i)
100 NEXT i
110 NEXT j
120 FOR i=1 TO n-p
130 PRINT b(i);" ";
140 NEXT i
- Programming Tasks
- Arithmetic operations
- 11l
- Ada
- ALGOL 68
- ALGOL W
- APL
- AppleScript
- Arturo
- AutoHotkey
- AWK
- BBC BASIC
- BQN
- C
- C sharp
- C++
- Clojure
- CoffeeScript
- Common Lisp
- D
- Dart
- Delphi
- E
- EasyLang
- EchoLisp
- Elixir
- Erlang
- F Sharp
- Factor
- Forth
- Fortran
- FreeBASIC
- Go
- Haskell
- HicEst
- Icon
- Unicon
- IDL
- J
- Java
- JavaScript
- Jq
- Julia
- K4
- Kotlin
- Lambdatalk
- Lasso
- Logo
- Lua
- M2000 Interpreter
- Mathematica
- Wolfram Language
- MATLAB
- Octave
- Maxima
- NetRexx
- Nial
- Nim
- Objeck
- OCaml
- Oforth
- PARI/GP
- Pascal
- PascalABC.NET
- Perl
- Phix
- PHP
- Picat
- PicoLisp
- PL/I
- Plain English
- Pop11
- PowerShell
- PureBasic
- Python
- Quackery
- R
- Racket
- Raku
- REXX
- Ring
- RPL
- Ruby
- Rust
- Scala
- Scheme
- Seed7
- SequenceL
- Sidef
- Slate
- Smalltalk
- SQL
- Standard ML
- Stata
- Swift
- Tcl
- Ursala
- Visual Basic .NET
- Visual FoxPro
- Wren
- Wren-fmt
- XPL0
- Zkl
- ZX Spectrum Basic