Binomial transform: Difference between revisions

=={{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>