Rosetta Code

Binomial transform: Difference between revisions

Page Discussion

Binomial transform (view source)

Revision as of 19:35, 6 April 2024

22,716 bytes added ,  1 month ago
m
→‎{{header|Phix}}: use pygments
(J draft)
m (→‎{{header|Phix}}: use pygments)
 
(14 intermediate revisions by 9 users not shown)
Line 60:
 
 
 
=={{header|ALGOL 68}}==
{{Trans|C}}
Assumes LONG INT is at least 64 bits, as in Algol 68G.
<syntaxhighlight lang="algol68">
BEGIN # binomial transform - translation of the C sample #
# returns factorial n, n must be at most 20 #
PROC factorial = ( INT n )LONG INT:
IF n > 20 THEN 0 # too big for LONG INT #
ELSE
LONG INT fact := 1;
FOR i FROM 2 TO n DO fact *:= i OD;
fact
FI # factorial # ;
# returns the binomial coefficient ( n k ) #
PROC binomial = ( INT n, k )LONG INT:
factorial( n ) OVER factorial( n - k ) OVER factorial( k );
# sets n to the forward transform of a #
PROC bt forward = ( REF[]LONG INT b, []LONG INT a )VOID:
BEGIN
REF[]LONG INT b0 = b[ AT 0 ];
[]LONG INT a0 = a[ AT 0 ];
FOR n FROM 0 TO UPB b0 DO
b0[ n ] := 0;
FOR k FROM 0 TO n DO b0[ n ] +:= binomial( n, k ) * a0[ k ] OD
OD
END # bt forward # ;
# sets a to the inverse transform of b #
PROC bt inverse = ( REF[]LONG INT a, []LONG INT b )VOID:
BEGIN
REF[]LONG INT a0 = a[ AT 0 ];
[]LONG INT b0 = b[ AT 0 ];
FOR n FROM 0 TO UPB a0 DO
a0[ n ] := 0;
FOR k FROM 0 TO n DO
a0[ n ] +:= binomial( n, k ) * b0[ k ] * IF ODD ( n - k ) THEN -1 ELSE 1 FI
OD
OD
END # bt inverse # ;
# sets b to the self inverse of a #
PROC bt self inverting = ( REF[]LONG INT b, []LONG INT a )VOID:
BEGIN
REF[]LONG INT b0 = b[ AT 0 ];
[]LONG INT a0 = a[ AT 0 ];
FOR n FROM 0 TO UPB b0 DO
b0[ n ] := 0;
FOR k FROM 0 TO n DO
b0[ n ] +:= binomial( n, k ) * a0[ k ] * IF ODD k THEN -1 ELSE 1 FI
OD
OD
END # bt self inverse # ;
 
# task test cases #
[][]LONG INT 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 )
);
[ 1 : UPB seqs[ LWB seqs ] ]LONG INT fwd, res;
[]STRING names = ( "Catalan number sequence:"
, "Prime flip-flop sequence:"
, "Fibonacci number sequence:"
, "Padovan number sequence:"
);
FOR i TO UPB seqs DO
print( ( names[ i ], newline ) );
FOR j TO UPB seqs[ i ] DO print( ( whole( seqs[ i ][ j ], 0 ), " " ) ) OD;
print( ( newline, "Forward binomial transform:", newline ) );
bt forward( fwd, seqs[ i ] );
FOR j TO UPB fwd DO print( ( whole( fwd[ j ], 0 ), " " ) ) OD;
print( ( newline, "Inverse binomial transform:", newline ) );
bt inverse( res, seqs[ i ] );
FOR j TO UPB res DO print( ( whole( res[ j ], 0 ), " " ) ) OD;
print( ( newline, "Round trip:", newline ) );
bt inverse( res, fwd );
FOR j TO UPB res DO print( ( whole( res[ j ], 0 ), " " ) ) OD;
print( ( newline, "Self-inverting:", newline ) );
bt self inverting( fwd, seqs[ i ] );
FOR j TO UPB fwd DO print( ( whole( fwd[ j ], 0 ), " " ) ) OD;
print( ( newline, "Re-inverted:", newline ) );
bt self inverting( res, fwd );
FOR j TO UPB res DO print( ( whole( res[ j ], 0 ), " " ) ) OD;
IF i < UPB seqs THEN print( ( newline, newline ) ) ELSE print( ( newline ) ) FI
OD
END
</syntaxhighlight>
{{out}} (same as the C sample):
<pre>
Catalan number sequence:
1 1 2 5 14 42 132 429 1430 4862 16796 58786 208012 742900 2674440 9694845 35357670 129644790 477638700 1767263190
Forward binomial transform:
1 2 5 15 51 188 731 2950 12235 51822 223191 974427 4302645 19181100 86211885 390248055 1777495635 8140539950 37463689775 173164232965
Inverse binomial transform:
1 0 1 1 3 6 15 36 91 232 603 1585 4213 11298 30537 83097 227475 625992 1730787 4805595
Round trip:
1 1 2 5 14 42 132 429 1430 4862 16796 58786 208012 742900 2674440 9694845 35357670 129644790 477638700 1767263190
Self-inverting:
1 0 1 -1 3 -6 15 -36 91 -232 603 -1585 4213 -11298 30537 -83097 227475 -625992 1730787 -4805595
Re-inverted:
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
Forward binomial transform:
0 1 3 6 11 20 37 70 134 255 476 869 1564 2821 5201 9948 19793 40562 84271 174952
Inverse binomial transform:
0 1 -1 0 3 -10 25 -56 118 -237 456 -847 1540 -2795 5173 -9918 19761 -40528 84235 -174914
Round trip:
0 1 1 0 1 0 1 0 0 0 1 0 1 0 0 0 1 0 1 0
Self-inverting:
0 -1 -1 0 3 10 25 56 118 237 456 847 1540 2795 5173 9918 19761 40528 84235 174914
Re-inverted:
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
Forward binomial transform:
0 1 3 8 21 55 144 377 987 2584 6765 17711 46368 121393 317811 832040 2178309 5702887 14930352 39088169
Inverse binomial transform:
0 1 -1 2 -3 5 -8 13 -21 34 -55 89 -144 233 -377 610 -987 1597 -2584 4181
Round trip:
0 1 1 2 3 5 8 13 21 34 55 89 144 233 377 610 987 1597 2584 4181
Self-inverting:
0 -1 -1 -2 -3 -5 -8 -13 -21 -34 -55 -89 -144 -233 -377 -610 -987 -1597 -2584 -4181
Re-inverted:
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
Forward binomial transform:
1 1 1 2 5 12 28 65 151 351 816 1897 4410 10252 23833 55405 128801 299426 696081 1618192
Inverse binomial transform:
1 -1 1 0 -3 10 -24 49 -89 145 -208 245 -174 -176 1121 -3185 7137 -13920 24301 -37926
Round trip:
1 0 0 1 0 1 1 1 2 2 3 4 5 7 9 12 16 21 28 37
Self-inverting:
1 1 1 0 -3 -10 -24 -49 -89 -145 -208 -245 -174 176 1121 3185 7137 13920 24301 37926
Re-inverted:
1 0 0 1 0 1 1 1 2 2 3 4 5 7 9 12 16 21 28 37
</pre>
 
=={{header|Arturo}}==
 
<syntaxhighlight lang="arturo">choose: function [n k][
div div factorial n factorial n - k factorial k
]
 
forward: function [a][
map 0..dec size a 'n ->
sum map 0..n 'k ->
a\[k] * choose n k
]
 
inverse: function [b][
map 0..dec size b 'n ->
sum map 0..n 'k ->
b\[k] * mul choose n k pow neg 1 n - k
]
 
loop [
"Catalan" [1 1 2 5 14 42 132 429 1430 4862 16796 58786 208012 742900 2674440 9694845 35357670 129644790 477638700 1767263190]
"Prime flip-flop" [0 1 1 0 1 0 1 0 0 0 1 0 1 0 0 0 1 0 1 0]
"Fibonacci" [0 1 1 2 3 5 8 13 21 34 55 89 144 233 377 610 987 1597 2584 4181]
"Padovan" [1 0 0 1 0 1 1 1 2 2 3 4 5 7 9 12 16 21 28 37]
] [name seq] [
print ~« -~~=====<{ |name| }>=====~~-
print seq
print "Forward binomial transform:"
print fwd: <= forward seq
print "Inverse binomial transform:"
print inverse seq
print "Round trip:"
print inverse fwd
print ""
]</syntaxhighlight>
 
{{out}}
 
<pre>-~~=====<{ Catalan }>=====~~-
1 1 2 5 14 42 132 429 1430 4862 16796 58786 208012 742900 2674440 9694845 35357670 129644790 477638700 1767263190
Forward binomial transform:
1 2 5 15 51 188 731 2950 12235 51822 223191 974427 4302645 19181100 86211885 390248055 1777495635 8140539950 37463689775 173164232965
Inverse binomial transform:
1 0 1 1 3 6 15 36 91 232 603 1585 4213 11298 30537 83097 227475 625992 1730787 4805595
Round trip:
1 1 2 5 14 42 132 429 1430 4862 16796 58786 208012 742900 2674440 9694845 35357670 129644790 477638700 1767263190
 
-~~=====<{ Prime flip-flop }>=====~~-
0 1 1 0 1 0 1 0 0 0 1 0 1 0 0 0 1 0 1 0
Forward binomial transform:
0 1 3 6 11 20 37 70 134 255 476 869 1564 2821 5201 9948 19793 40562 84271 174952
Inverse binomial transform:
0 1 -1 0 3 -10 25 -56 118 -237 456 -847 1540 -2795 5173 -9918 19761 -40528 84235 -174914
Round trip:
0 1 1 0 1 0 1 0 0 0 1 0 1 0 0 0 1 0 1 0
 
-~~=====<{ Fibonacci }>=====~~-
0 1 1 2 3 5 8 13 21 34 55 89 144 233 377 610 987 1597 2584 4181
Forward binomial transform:
0 1 3 8 21 55 144 377 987 2584 6765 17711 46368 121393 317811 832040 2178309 5702887 14930352 39088169
Inverse binomial transform:
0 1 -1 2 -3 5 -8 13 -21 34 -55 89 -144 233 -377 610 -987 1597 -2584 4181
Round trip:
0 1 1 2 3 5 8 13 21 34 55 89 144 233 377 610 987 1597 2584 4181
 
-~~=====<{ Padovan }>=====~~-
1 0 0 1 0 1 1 1 2 2 3 4 5 7 9 12 16 21 28 37
Forward binomial transform:
1 1 1 2 5 12 28 65 151 351 816 1897 4410 10252 23833 55405 128801 299426 696081 1618192
Inverse binomial transform:
1 -1 1 0 -3 10 -24 49 -89 145 -208 245 -174 -176 1121 -3185 7137 -13920 24301 -37926
Round trip:
1 0 0 1 0 1 1 1 2 2 3 4 5 7 9 12 16 21 28 37</pre>
 
=={{header|C}}==
Line 383 ⟶ 601:
selfinv ((! +:) % >:) i.15x
1 0 1 _1 3 _6 15 _36 91 _232 603 _1585 4213 _11298 30537
reverse forward ((! +:) % >:) i.15x
1 1 2 5 14 42 132 429 1430 4862 16796 58786 208012 742900 2674440
selfinv selfinv ((! +:) % >:) i.15x
1 1 2 5 14 42 132 429 1430 4862 16796 58786 208012 742900 2674440
NB. natural number is prime
Line 393 ⟶ 615:
selfinv 1 p: 1+i.15
0 _1 _1 0 3 10 25 56 118 237 456 847 1540 2795 5173
reverse forward 1 p: 1+i.15
0 1 1 0 1 0 1 0 0 0 1 0 1 0 0
selfinv selfinv 1 p: 1+i.15
0 1 1 0 1 0 1 0 0 0 1 0 1 0 0
NB. Fibonacci
Line 403 ⟶ 629:
selfinv (, _1 _2 +/@:{ ])^:15] 0 1
0 _1 _1 _2 _3 _5 _8 _13 _21 _34 _55 _89 _144 _233 _377 _610 _987
reverse forward (, _1 _2 +/@:{ ])^:15] 0 1
0 1 1 2 3 5 8 13 21 34 55 89 144 233 377 610 987
selfinv selfinv (, _1 _2 +/@:{ ])^:15] 0 1
0 1 1 2 3 5 8 13 21 34 55 89 144 233 377 610 987
NB. Padovan
Line 412 ⟶ 642:
1 _1 1 0 _3 10 _24 49 _89 145 _208 245 _174 _176 1121
selfinv (],+/@(_2 _3{]))^:([-3:)&1 0 0(15)
1 1 1 0 _3 _10 _24 _49 _89 _145 _208 _245 _174 176 1121</syntaxhighlight>
reverse forward (],+/@(_2 _3{]))^:([-3:)&1 0 0(15)
1 0 0 1 0 1 1 1 2 2 3 4 5 7 9
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 483 ⟶ 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}}
<!--(phixonline)-->
<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.
 
=={{header|Python}}==
Line 760 ⟶ 1,367:
Re inverted:
1 0 0 1 0 1 1 1 2 2 3 4 5 7 9 12 16 21 28 37</pre>
 
=={{header|RPL}}==
We use here the <code>SEQ</code> and <code>∑LIST</code>instructions, available for HP-48G or newer models only.
{| class="wikitable"
! RPL code
! Comment
|-
|
≪ DUP SIZE → seq n
≪ { 1 } 2 n '''FOR''' j
'COMB(j-1,k)' 'k' 0 j 1 - 1 SEQ
seq 1 j SUB
* ∑LIST +
'''NEXT'''
≫ ≫ ‘'''FBITR'''’ STO
≪ DUP SIZE → seq n
≪ { 1 } 2 n '''FOR''' j
'(-1)^(j-k-1)*COMB(j-1,k)' 'k' 0 j 1 - 1 SEQ
seq 1 j SUB * ∑LIST +
'''NEXT'''
≫ ≫ ‘'''RBITR'''’ STO
|
'''FBITR''' ''( { a(n) } -- { b(n) } ) ''
output = { 2 } ; loop for j=2 to n
get a j-list of c(j-1,k) with k from 0 to j-1
get a j-list of a(k)
multiply the 2 lists, reduce and append result to output
end loop
return list
'''RBITR''' ''( { b(n) } -- { a(n) } )''
same implementation as '''FBITR'''
only the formula for kth term is different here
|}
If wanting to stick to the basic HP-28 instruction set and no algebraic expressions:
≪ DUP SIZE → seq n
≪ { } 1 n '''FOR''' j
0 1 j '''FOR''' k
seq k GET j 1 - k 1 - COMB * +
'''NEXT''' + '''NEXT'''
≫ ≫ ‘'''FBITR'''’ STO
≪ DUP SIZE → seq n
≪ { } 1 n '''FOR''' j
0 1 j '''FOR''' k
seq k GET j 1 - k 1 - COMB * -1 j k - ^ * +
'''NEXT''' + '''NEXT'''
≫ ≫ ‘'''RBITR'''’ STO
{{in}}
<pre>
{ 1 1 2 5 14 42 132 429 1430 4862 16796 58786 208012 742900 2674440 } 'ZCAT' STO
{ 0 1 1 0 1 0 1 0 0 0 1 0 1 0 0 } 'ZPFF' STO
{ 0 1 1 2 3 5 8 13 21 34 55 89 144 233 377 } 'ZFIB' STO
{ 1 0 0 1 0 1 1 1 2 2 3 4 5 7 9 } 'ZPAD' STO
ZCAT FBITR ZCAT RBITR ZCAT FBITR RBITR
ZPFF FBITR ZPFF RBITR ZPFF FBITR RBITR
ZFIB FBITR ZFIB RBITR ZFIB FBITR RBITR
ZPAD FBITR ZPAD RBITR ZPAD FBITR RBITR
</pre>
{{out}}
<pre>
12: { 1 2 5 15 51 188 731 2950 12235 51822 223191 974427 4302645 19181100 86211885 }
11: { 1 0 1 1 3 6 15 36 91 232 603 1585 4213 11298 30537 }
10: { 1 1 2 5 14 42 132 429 1430 4862 16796 58786 208012 742900 2674440 }
9: { 0 1 3 6 11 20 37 70 134 255 476 869 1564 2821 5201 }
8: { 0 1 -1 0 3 -10 25 -56 118 -237 456 -847 1540 -2795 5173 }
7: { 0 1 1 0 1 0 1 0 0 0 1 0 1 0 0 }
6: { 0 1 3 8 21 55 144 377 987 2584 6765 17711 46368 121393 317811 }
5: { 0 1 -1 2 -3 5 -8 13 -21 34 -55 89 -144 233 -377 }
4: { 0 1 1 2 3 5 8 13 21 34 55 89 144 233 377 }
3: { 1 1 1 2 5 12 28 65 151 351 816 1897 4410 10252 23833 }
2: { 1 -1 1 0 -3 10 -24 49 -89 145 -208 245 -174 -176 1121 }
1: { 1 0 0 1 0 1 1 1 2 2 3 4 5 7 9 }
</pre>
 
=={{header|Wren}}==
{{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="ecmascriptwren">import "./long" for Long, ULong
 
class BT {
Petelomax
7,794

edits

Retrieved from "https://rosettacode.org/wiki/Special:MobileDiff/341698...363339"