Binomial transform: Difference between revisions
→{{header|Wren}}: Added self-inverting variant.
(Added XPL0 example.) |
(→{{header|Wren}}: Added self-inverting variant.) |
||
Line 598:
}
return a
}
static selfInverting(a) {
var c = a.count
var b = List.filled(c, null)
for (n in 0...c) {
b[n] = Long.zero
for (k in 0..n) {
var sign = k % 2 == 0 ? 1 : -1
b[n] = b[n] + ULong.binomial(n, k).toLong * a[k] * sign
}
}
return b
}
}
Line 615 ⟶ 628:
]
var
for (i in 0...seqs.count) {
System.print(names[i])
System.print(seqs[i].join(" "))
System.print("Forward binomial transform:")
System.print((
System.print("Inverse binomial transform:")
System.print(BT.inverse(seqs[i]).join(" "))
System.print("Round trip:")
System.print(BT.inverse(
System.print("Self-inverting:")
System.print((saved = BT.selfInverting(seqs[i])).join(" "))
System.print("Re-inverted:")
System.print(BT.selfInverting(saved).join(" "))
if (i < seqs.count - 1) System.print()
}</syntaxhighlight>
Line 637 ⟶ 654:
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
Line 646 ⟶ 667:
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
Line 655 ⟶ 680:
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
Line 664 ⟶ 693:
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>
| |||