Binomial transform: Difference between revisions
m
→{{header|Phix}}: use pygments
m (→{{header|Wren}}: Changed to Wren S/H) |
m (→{{header|Phix}}: use pygments) |
||
| (One intermediate revision by one other user not shown) | |||
Line 868:
Inverse of the forward transform:
1 0 0 1 0 1 1 1 2 2 3 4 5 7 9
</pre>
=={{header|Pascal}}==
==={{header|Free Pascal}}===
{{Trans|C}}
<syntaxhighlight lang="pascal">
program BinomialTransforms;
{$mode objfpc}{$H+}
uses
SysUtils;
type
Int64Array = array[0..19] of Int64;
const
facs: array[1..20] of UInt64 = (
1, 2, 6, 24, 120, 720, 5040, 40320, 362880, 3628800,
39916800, 479001600, 6227020800, 87178291200, 1307674368000,
20922789888000, 355687428096000, 6402373705728000, 121645100408832000,
2432902008176640000
);
Seqs: array[0..3] of Int64Array = (
(1, 1, 2, 5, 14, 42, 132, 429, 1430, 4862, 16796, 58786, 208012, 742900,
2674440, 9694845, 35357670, 129644790, 477638700, 1767263190),
(0, 1, 1, 0, 1, 0, 1, 0, 0, 0, 1, 0, 1, 0, 0, 0, 1, 0, 1, 0),
(0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, 233, 377, 610, 987, 1597, 2584, 4181),
(1, 0, 0, 1, 0, 1, 1, 1, 2, 2, 3, 4, 5, 7, 9, 12, 16, 21, 28, 37)
);
Names: array[0..3] of string = (
'Catalan number sequence:',
'Prime flip-flop sequence:',
'Fibonacci number sequence:',
'Padovan number sequence:'
);
function Factorial(N: Integer): UInt64;
begin
if (N > 20) or (N < 2) then
Exit(1);
Result := facs[N];
end;
function Binomial(N, K: Integer): UInt64;
begin
Result := Factorial(N) div (Factorial(N - K) * Factorial(K));
end;
procedure BtForward(var B: Int64Array; const A: Int64Array; C: Integer);
var
N, K: Integer;
begin
for N := 0 to C - 1 do
begin
B[N] := 0;
for K := 0 to N do
B[N] := B[N] + Binomial(N, K) * A[K];
end;
end;
procedure BtInverse(var A: Int64Array; const B: Int64Array; C: Integer);
var
N, K, Sign: Integer;
begin
for N := 0 to C - 1 do
begin
A[N] := 0;
for K := 0 to N do
begin
Sign := Ord((N - K) and 1 <> 0) * -2 + 1;
A[N] := A[N] + Binomial(N, K) * B[K] * Sign;
end;
end;
end;
procedure BtSelfInverting(var B: Int64Array; const A: Int64Array; C: Integer);
var
N, K, Sign: Integer;
begin
for N := 0 to C - 1 do
begin
B[N] := 0;
for K := 0 to N do
begin
Sign := Ord(K and 1 <> 0) * -2 + 1;
B[N] := B[N] + Binomial(N, K) * A[K] * Sign;
end;
end;
end;
function LeastSquareDiff(Limit: UInt32): UInt32;
var
N: UInt32;
begin
N := Trunc(Sqrt(Limit)) + 1;
while (N * N) - ((N - 1) * (N - 1)) <= Limit do
Inc(N);
Result := N;
end;
var
I, J: Integer;
Fwd, Res: Int64Array;
begin
for I := 0 to 3 do
begin
WriteLn(Names[I]);
for J := 0 to 19 do
Write(Seqs[I][J], ' ');
WriteLn;
WriteLn('Forward binomial transform:');
BtForward(Fwd, Seqs[I], 20);
for J := 0 to 19 do
Write(Fwd[J], ' ');
WriteLn;
WriteLn('Inverse binomial transform:');
BtInverse(Res, Seqs[I], 20);
for J := 0 to 19 do
Write(Res[J], ' ');
WriteLn;
WriteLn('Round trip:');
BtInverse(Res, Fwd, 20);
for J := 0 to 19 do
Write(Res[J], ' ');
WriteLn;
WriteLn('Self-inverting:');
BtSelfInverting(Fwd, Seqs[I], 20);
for J := 0 to 19 do
Write(Fwd[J], ' ');
WriteLn;
WriteLn('Re-inverted:');
BtSelfInverting(Res, Fwd, 20);
for J := 0 to 19 do
Write(Res[J], ' ');
end;
end.
</syntaxhighlight>
{{out}}
<pre>
Same as C
</pre>
=={{header|Phix}}==
{{trans|C}}
<!--
<syntaxhighlight lang="phix">
with javascript_semantics
function bt_forward(sequence a)
sequence b = {}
for n=1 to length(a) do
atom bn = 0
for k=1 to n do
bn += choose(n-1, k-1) * a[k]
end for
b &= bn
end for
return b
end function
function bt_inverse(sequence b)
sequence a = {}
for n=1 to length(b) do
atom an = 0
for k=1 to n do
integer sgn = iff(odd(n-k) ? -1 : 1)
an += choose(n-1, k-1) * b[k] * sgn
end for
a &= an
end for
return a
end function
function bt_self_inverting(sequence a)
sequence b = {}
for n=1 to length(a) do
atom bn = 0
for k=1 to n do
integer sgn = iff(even(k) ? -1 : 1)
bn += choose(n-1, k-1) * a[k] * sgn
end for
b &= bn
end for
return b
end function
sequence tests = {{"Catalan number sequence:",
{1, 1, 2, 5, 14, 42, 132, 429, 1430, 4862, 16796, 58786, 208012,
742900, 2674440, 9694845, 35357670, 129644790, 477638700, 1767263190}},
{"Prime flip-flop sequence:",
{0, 1, 1, 0, 1, 0, 1, 0, 0, 0, 1, 0, 1, 0, 0, 0, 1, 0, 1, 0}},
{"Fibonacci number sequence:",
{0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, 233, 377, 610, 987, 1597, 2584, 4181}},
{"Padovan number sequence:",
{1, 0, 0, 1, 0, 1, 1, 1, 2, 2, 3, 4, 5, 7, 9, 12, 16, 21, 28, 37}}}
function jd(sequence s) return join(s," ",fmt:="%d") end function
for t in tests do
sequence {name, s} = t, fwd = bt_forward(s), inv = bt_inverse(s),
si = bt_self_inverting(s)
printf(1,"%s\n%s\n", {name,jd(s)})
printf(1,"Forward binomial transform:\n%s\n",jd(fwd))
printf(1,"Inverse binomial transform:\n%s\n",jd(inv))
printf(1,"Round trip:\n%s\n",jd(bt_inverse(fwd)))
printf(1,"Self-inverting:\n%s\n",jd(si))
printf(1,"Re-inverted:\n%s\n\n",jd(bt_self_inverting(si)))
end for
</syntaxhighlight>
{{out}}
Same as C, etc.
| |||