Binomial transform: Difference between revisions

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