Binomial transform: Difference between revisions
Content added Content deleted
Thundergnat (talk | contribs) m (→{{header|Raku}}: Slightly more accurate comment) |
(Added Wren) |
||
Line 123: | Line 123: | ||
Round trip: |
Round trip: |
||
1 0 0 1 0 1 1 1 2 2 3 4 5 7 9 12 16 21 28 37</pre> |
1 0 0 1 0 1 1 1 2 2 3 4 5 7 9 12 16 21 28 37</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="ecmascript">import "./math" for Int |
|||
import "./long" for Long, ULong |
|||
class BT { |
|||
static forward(a) { |
|||
var c = a.count |
|||
var b = List.filled(c, null) |
|||
for (n in 0...c) { |
|||
var sum = ULong.zero |
|||
for (k in 0..n) sum = sum + ULong.binomial(n, k) * a[k] |
|||
b[n] = sum.toNum |
|||
} |
|||
return b |
|||
} |
|||
static inverse(b) { |
|||
var c = b.count |
|||
var a = List.filled(c, null) |
|||
for (n in 0...c) { |
|||
var sum = Long.zero |
|||
for (k in 0..n) { |
|||
var sign = (-1).pow(n-k) |
|||
sum = sum + ULong.binomial(n, k).toLong * b[k] * sign |
|||
a[n] = sum.toNum |
|||
} |
|||
} |
|||
return a |
|||
} |
|||
} |
|||
var 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] |
|||
] |
|||
var names = [ |
|||
"Catalan number sequence:", |
|||
"Prime flip-flop sequence:", |
|||
"Fibonacci number sequence:", |
|||
"Padovan number sequence:" |
|||
] |
|||
var fwd |
|||
for (i in 0...seqs.count) { |
|||
System.print(names[i]) |
|||
System.print(seqs[i].join(" ")) |
|||
System.print("Forward binomial transform:") |
|||
System.print((fwd = BT.forward(seqs[i])).join(" ")) |
|||
System.print("Inverse binomial transform:") |
|||
System.print(BT.inverse(seqs[i]).join(" ")) |
|||
System.print("Round trip:") |
|||
System.print(BT.inverse(fwd).join(" ")) |
|||
if (i < seqs.count - 1) System.print() |
|||
}</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> |