快速多项式移位

Question

我正在尝试实现“F. 卷积法”（第2.2节）：

来自Taylor移位和某些差分方程的快速算法（在底部，或这里）：

from math import factorial

def convolve(f, h):
    g = [0] * (len(f) + len(h) - 1)
    for hindex, hval in enumerate(h):
        for findex, fval in enumerate(f):
            g[hindex + findex] += fval * hval
    return g

def shift(f, a):
    n = len(f) - 1
    u = [factorial(i)*c for i, c in enumerate(f)]
    v = [factorial(n)*a**i//factorial(n-i) for i in range(n + 1)]
    g = convolve(u, v)
    g = [c//(factorial(n)*factorial(i)) for i, c in enumerate(g)]
    return g

f = [1, 2, 3, -4, 5, 6, -7, 8, 9]
print(shift(f, 1))

但是我只得到了零，而正确的结果应该是：

[1, 10, 45, 112, 170, 172, 116, 52, 23]

请问，有人知道我在这里做错了什么吗？

- Ecir Hana

---

请在此处发布算法以便于我们提供帮助。目前，您正在将小整数除以大整数（这就是0的原因），因此我们必须了解您期望convolve(u,v)返回什么。 - kabanus

你确定这是正确的输出吗？在isaac97中（以及我对2.2（F）的实现），我得到了{0: 23, 1: 132, 2: 396, 3: 720, 4: 840, 5: 636, 6: 301, 7: 80, 8: 9}。 - jedwards

@jedwards得到的也是我在修复代码后得到的（见下文，反转）。请再次确认。 - kabanus

@EcirHana 我两个都加了，但基本上是kabanus的（并使用defaultdict以便我能理解所有的索引操作）。由于kabanus的答案很好地解释了原始代码中的问题，所以我的代码基本上就是你要求的代码。 - jedwards

@jedwards 非常感谢你！ - Ecir Hana

Answer 1

我仍然无法完全掌握这个算法，但是你有一些错误：

1. u的幂从n开始到0结束。为了使卷积有效，您需要对其进行反转，因为您期望系数按照卷积函数中的顺序排列。
2. v多项式中的系数仅取决于j而不是n-j（您使用i）。
3. 只需要前n+1个元素的卷积（不需要n+1...2n的幂）。
4. 得出的卷积（它实际上不是卷积吧？）是“反向”的，即您的最终结果将从 i = 0 开始计算，因此x **（n-i = n）的幂。

将所有这些放在一起：

from math import factorial

def convolve(f, h):
    g = [0] * (len(f) + len(h) - 1)
    for hindex, hval in enumerate(h):
        for findex, fval in enumerate(f):
            g[hindex + findex] += fval * hval
    return g

def shift(f, a):
    n = len(f) - 1
    u = [factorial(i)*c for i, c in enumerate(f)][::-1]
    v = [factorial(n)*a**i//factorial(i) for i in range(n + 1)]
    g = convolve(u, v)
    g = [g[n-i]//(factorial(n)*factorial(i)) for i in range(n+1)][::-1]
    return g

f = [1, 2, 3, -4, 5, 6, -7, 8, 9]
print(shift(f, 1))

我明白了

[9, 80, 301, 636, 840, 720, 396, 132, 23]

我不知道为什么与你的期望不同，但我希望这能让你走上正轨。

- kabanus

---

看起来 OP 把列表反了（至少不是我们期望的顺序）。如果 f = f[::-1]，你的代码应该得到他们想要的输出（我的代码就是这样）。 - jedwards

@jedwards 我同意，我认为这是正确的版本。（注意我故意在f内部反转） - kabanus

我真是太蠢了！我的确把顺序搞反了！谢谢。 - Ecir Hana

Answer 2

由于您要求我的实现（这些都是反向的f）：

方程式2：

from math import factorial
from collections import defaultdict

def binomial(n, k):
    try:
        binom = factorial(n) // factorial(k) // factorial(n - k)
    except ValueError:
        binom = 0
    return binom

f = [1, 2, 3, -4, 5, 6, -7, 8, 9][::-1]
k=0
n = len(f) - 1

g = defaultdict(int)
for k in range(n+1):
    for i in range(k, n+1):
        g[i-k] += binomial(i,k) * f[i]

print(g)
# defaultdict(<class 'int'>, {0: 23, 1: 52, 2: 116, 3: 172, 4: 170, 5: 112, 6: 45, 7: 10, 8: 1})

2.2（F）中的方程式：

from math import factorial
from collections import defaultdict

def convolve(x, y):
    g = defaultdict(int)
    for (xi, xv) in x.items():
        for (yi, yv) in y.items():
            g[xi + yi] += xv * yv
    return g


def shift(f, a):
    n = len(f) - 1
    u = {n-i: factorial(i)*c for (i, c) in enumerate(f)}
    v = {j: factorial(n)*a**j//factorial(j) for j in range(n + 1)}
    uv = convolve(u, v)

    def g(k):
        ngk = uv[n-k]
        return ngk // factorial(n) // factorial(k)

    G = [g(k) for k in range(n+1)]
    return G

f = [1, 2, 3, -4, 5, 6, -7, 8, 9]

print(shift(f, 1))
# [23, 132, 396, 720, 840, 636, 301, 80, 9]

- jedwards