Binomial transform: Difference between revisions
Content added Content deleted
Thundergnat (talk | contribs) m (Add some whitespace, undo an ill-advised twiddle) |
(Added XPL0 example.) |
||
Line 665: | Line 665: | ||
Round trip: |
Round trip: |
||
1 0 0 1 0 1 1 1 2 2 3 4 5 7 9 12 16 21 28 37 |
1 0 0 1 0 1 1 1 2 2 3 4 5 7 9 12 16 21 28 37 |
||
</pre> |
|||
=={{header|XPL0}}== |
|||
{{trans|C}} |
|||
<syntaxhighlight lang "XPL0">func real Factorial(N); |
|||
int N, I; |
|||
real F; |
|||
[F:= 1.; |
|||
for I:= 2 to N do F:= F * float(I); |
|||
return F; |
|||
]; |
|||
func real Binomial(N, K); |
|||
int N, K; |
|||
return Factorial(N) / Factorial(N-K) / Factorial(K); |
|||
proc BinomialFwd(A, B, M); |
|||
real A, B; int M; |
|||
int N, K; |
|||
[for N:= 0 to M-1 do |
|||
[B(N):= 0.; |
|||
for K:= 0 to N do |
|||
B(N):= B(N) + Binomial(N, K) * A(K); |
|||
]; |
|||
]; |
|||
proc BinomialInv(A, B, M); |
|||
real A, B; int M; |
|||
int N, K, Sign; |
|||
[for N:= 0 to M-1 do |
|||
[A(N):= 0.; |
|||
for K:= 0 to N do |
|||
[Sign:= if N-K & 1 then -1 else 1; |
|||
A(N):= A(N) + float(Sign) * Binomial(N, K) * B(K); |
|||
]; |
|||
]; |
|||
]; |
|||
real Fwd(20), Inv(20), Seqs; |
|||
int Title, I, J; |
|||
[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.]]; |
|||
Title:= [ |
|||
"Catalan number sequence:", |
|||
"Prime flip-flop sequence:", |
|||
"Fibonacci number sequence:", |
|||
"Padovan number sequence:" ]; |
|||
Format(1,0); |
|||
for I:= 0 to 4-1 do |
|||
[Text(0, Title(I)); CrLf(0); |
|||
for J:= 0 to 20-1 do [RlOut(0, Seqs(I,J)); ChOut(0, ^ )]; |
|||
Text(0, "^m^jForward binomial transform:^m^j"); |
|||
BinomialFwd(Seqs(I), Fwd, 20); |
|||
for J:= 0 to 20-1 do [RlOut(0, Fwd(J)); ChOut(0, ^ )]; |
|||
Text(0, "^m^jInverse binomial transform:^m^j"); |
|||
BinomialInv(Inv, Seqs(I), 20); |
|||
for J:= 0 to 20-1 do [RlOut(0, Inv(J)); ChOut(0, ^ )]; |
|||
Text(0, "^m^jRound trip:^m^j"); |
|||
BinomialInv(Inv, Fwd, 20); |
|||
for J:= 0 to 20-1 do [RlOut(0, Inv(J)); ChOut(0, ^ )]; |
|||
if I < 3 then CrLf(0); |
|||
CrLf(0); |
|||
]; |
|||
]</syntaxhighlight> |
|||
{{out}} |
|||
<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 |
|||
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 |
|||
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 |
|||
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 |
|||
</pre> |
</pre> |