Binomial transform: Difference between revisions
m
→{{header|Phix}}: use pygments
Drkameleon (talk | contribs) (added Arturo) |
m (→{{header|Phix}}: use pygments) |
||
| (8 intermediate revisions by 6 users not shown) | |||
Line 208:
=={{header|Arturo}}==
<syntaxhighlight lang="arturo">
div div factorial n factorial n - k factorial k
]
Line 649 ⟶ 647:
selfinv selfinv (],+/@(_2 _3{]))^:([-3:)&1 0 0(15)
1 0 0 1 0 1 1 1 2 2 3 4 5 7 9</syntaxhighlight>
=={{header|jq}}==
'''Adapted from [[#Wren|Wren]]'''
'''Works with both jq and gojq, the C and Go implementations of jq'''
The following can also easily be adapted to work with jaq, the Rust implementation of jq.
<syntaxhighlight lang=jq>
# nCk assuming n >= k
def binomial(n; k):
if k > n / 2 then binomial(n; n-k)
else reduce range(1; k+1) as $i (1; . * (n - $i + 1) / $i)
end;
def forward:
. as $a
| reduce range(0; $a|length) as $n (null;
reduce range(0;$n+1) as $k (.;
.[$n] += binomial($n; $k) * $a[$k] ) );
def inverse:
. as $b
| reduce range (0; $b|length) as $n (null;
reduce range(0; $n+1) as $k (.;
(if (($n - $k) % 2 == 0) then 1 else -1 end) as $sign
| .[$n] += binomial($n; $k) * $b[$k] * $sign ));
def selfInverting:
. as $a
| reduce range(0; $a|length) as $n (null;
reduce range(0; $n+1) as $k (.;
(if $k % 2 == 0 then 1 else -1 end) as $sign
| .[$n] += binomial($n; $k) * $a[$k] * $sign ));
def seqs: [
[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]
];
def names: [
"Catalan number sequence:",
"Prime flip-flop sequence:",
"Fibonacci number sequence:",
"Padovan number sequence:"
];
def task:
range(0; seqs|length) as $i
| names[$i],
(seqs[$i]|join(" ")),
"Forward binomial transform:",
( (seqs[$i]|forward)
| join(" "),
"Inverse binomial transform:",
((seqs[$i]|inverse)|join(" ")),
"Round trip:",
(inverse|join(" ")) ),
"Self-inverting:",
( (seqs[$i]|selfInverting)
| join(" "),
"Re-inverted:",
(selfInverting|join(" ")) ),
(select($i < (seqs|length - 1) ) | "") ;
task
</syntaxhighlight>
{{output}}
Exactly as at [[#Wren|Wren]].
=={{header|Julia}}==
Line 719 ⟶ 787:
end
</syntaxhighlight>{{out}} Same as C, Go, etc.
=={{header|Nim}}==
<syntaxhighlight lang="Nim">import std/[math, strutils]
const
Sequences = {"Catalan":
[1, 1, 2, 5, 14, 42, 132, 429, 1430, 4862, 16796, 58786, 208012, 742900, 2674440],
"Prime flip-flop":
[0, 1, 1, 0, 1, 0, 1, 0, 0, 0, 1, 0, 1, 0, 0],
"Fibonacci":
[0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, 233, 377],
"Padovan":
[1, 0, 0, 1, 0, 1, 1, 1, 2, 2, 3, 4, 5, 7, 9]}
func binomialTransform(a: openArray[int]): seq[int] =
for n in 0..a.high:
var val = 0
for k in 0..n:
val += binom(n, k) * a[k]
result.add val
func invBinomialSequence(b: openArray[int]): seq[int] =
for n in 0..b.high:
var val = 0
var sign = ord((n and 1) == 0) shl 1 - 1
for k in 0..n:
val += binom(n, k) * b[k] * sign
sign = -sign
result.add val
for (name, sequence) in Sequences:
echo name, " sequence:"
echo sequence.join(" ")
let forward = binomialTransform(sequence)
echo "Forward binomial transform:"
echo forward.join(" ")
echo "Inverse binomial transform:"
let inverse = invBinomialSequence(sequence)
echo inverse.join(" ")
echo "Inverse of the forward transform:"
let invForward = invBinomialSequence(forward)
echo invForward.join(" ")
echo()
</syntaxhighlight>
{{out}}
<pre>Catalan sequence:
1 1 2 5 14 42 132 429 1430 4862 16796 58786 208012 742900 2674440
Forward binomial transform:
1 2 5 15 51 188 731 2950 12235 51822 223191 974427 4302645 19181100 86211885
Inverse binomial transform:
1 0 1 1 3 6 15 36 91 232 603 1585 4213 11298 30537
Inverse of the forward transform:
1 1 2 5 14 42 132 429 1430 4862 16796 58786 208012 742900 2674440
Prime flip-flop sequence:
0 1 1 0 1 0 1 0 0 0 1 0 1 0 0
Forward binomial transform:
0 1 3 6 11 20 37 70 134 255 476 869 1564 2821 5201
Inverse binomial transform:
0 1 -1 0 3 -10 25 -56 118 -237 456 -847 1540 -2795 5173
Inverse of the forward transform:
0 1 1 0 1 0 1 0 0 0 1 0 1 0 0
Fibonacci sequence:
0 1 1 2 3 5 8 13 21 34 55 89 144 233 377
Forward binomial transform:
0 1 3 8 21 55 144 377 987 2584 6765 17711 46368 121393 317811
Inverse binomial transform:
0 1 -1 2 -3 5 -8 13 -21 34 -55 89 -144 233 -377
Inverse of the forward transform:
0 1 1 2 3 5 8 13 21 34 55 89 144 233 377
Padovan sequence:
1 0 0 1 0 1 1 1 2 2 3 4 5 7 9
Forward binomial transform:
1 1 1 2 5 12 28 65 151 351 816 1897 4410 10252 23833
Inverse binomial transform:
1 -1 1 0 -3 10 -24 49 -89 145 -208 245 -174 -176 1121
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}},
{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}}}
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.
=={{header|Python}}==
Line 1,150 ⟶ 1,449:
{{libheader|Wren-long}}
This hard-codes the sequences to be tested as I couldn't see much point in repeating code from the related tasks.
<syntaxhighlight lang="
class BT {
| |||