离散的#

这个 discrete SymPy中的模块实现了计算有限序列的离散变换和卷积的方法。

此模块包含对离散序列进行操作的函数。

变换- fft ， ifft ， ntt ， intt ， fwht ， ifwht ，

mobius_transform, inverse_mobius_transform

卷积- convolution ， convolution_fft ， convolution_ntt ，

convolution_fwht, convolution_subset, covering_product, intersecting_product

由于离散变换可以用来降低离散卷积的计算复杂度，因此 convolutions 模块利用 transforms 用于高效计算的模块（以长输入序列著称）。

转换#

本节列出了实现离散序列基本变换的方法。

快速傅里叶变换#

sympy.discrete.transforms.fft(seq, dps=None)[源代码]#

执行离散傅里叶变换( DFT )在复杂领域。

序列会自动在右侧填充零，如 radix-2 FFT 要求采样点的数量是2的幂次方。

由于表达式的复杂性随序列的大小而增加，因此仅应将此方法与默认参数一起使用。

参数:

seq ：i可读取

顺序 DFT 将被应用。

dps ：整数

指定精度的小数位数。

实例

>>> from sympy import fft, ifft

>>> fft([1, 2, 3, 4])
[10, -2 - 2*I, -2, -2 + 2*I]
>>> ifft(_)
[1, 2, 3, 4]

>>> ifft([1, 2, 3, 4])
[5/2, -1/2 + I/2, -1/2, -1/2 - I/2]
>>> fft(_)
[1, 2, 3, 4]

>>> ifft([1, 7, 3, 4], dps=15)
[3.75, -0.5 - 0.75*I, -1.75, -0.5 + 0.75*I]
>>> fft(_)
[1.0, 7.0, 3.0, 4.0]

工具书类

sympy.discrete.transforms.ifft(seq, dps=None)[源代码]#

执行离散傅里叶变换( DFT )在复杂领域。

序列会自动在右侧填充零，如 radix-2 FFT 要求采样点的数量是2的幂次方。

由于表达式的复杂性随序列的大小而增加，因此仅应将此方法与默认参数一起使用。

参数:

seq ：i可读取

顺序 DFT 将被应用。

dps ：整数

指定精度的小数位数。

实例

>>> from sympy import fft, ifft

>>> fft([1, 2, 3, 4])
[10, -2 - 2*I, -2, -2 + 2*I]
>>> ifft(_)
[1, 2, 3, 4]

>>> ifft([1, 2, 3, 4])
[5/2, -1/2 + I/2, -1/2, -1/2 - I/2]
>>> fft(_)
[1, 2, 3, 4]

>>> ifft([1, 7, 3, 4], dps=15)
[3.75, -0.5 - 0.75*I, -1.75, -0.5 + 0.75*I]
>>> fft(_)
[1.0, 7.0, 3.0, 4.0]

工具书类

数论变换#

sympy.discrete.transforms.ntt(seq, prime)[源代码]#

执行数论变换( NTT )，专门研究离散傅里叶变换( DFT )过商环 \(Z/pZ\) 对于prime \(p\) 而不是复数 \(C\) .

序列会自动在右侧填充零，如 radix-2 NTT 要求采样点的数量是2的幂次方。

参数:

seq ：i可读取

顺序 DFT 将被应用。

首要的 ：整数

形式素模 \((m 2^k + 1)\) 用于表演 NTT 按顺序。

实例

>>> from sympy import ntt, intt
>>> ntt([1, 2, 3, 4], prime=3*2**8 + 1)
[10, 643, 767, 122]
>>> intt(_, 3*2**8 + 1)
[1, 2, 3, 4]
>>> intt([1, 2, 3, 4], prime=3*2**8 + 1)
[387, 415, 384, 353]
>>> ntt(_, prime=3*2**8 + 1)
[1, 2, 3, 4]

工具书类

sympy.discrete.transforms.intt(seq, prime)[源代码]#

执行数论变换( NTT )，专门研究离散傅里叶变换( DFT )过商环 \(Z/pZ\) 对于prime \(p\) 而不是复数 \(C\) .

序列会自动在右侧填充零，如 radix-2 NTT 要求采样点的数量是2的幂次方。

参数:

seq ：i可读取

顺序 DFT 将被应用。

首要的 ：整数

形式素模 \((m 2^k + 1)\) 用于表演 NTT 按顺序。

实例

>>> from sympy import ntt, intt
>>> ntt([1, 2, 3, 4], prime=3*2**8 + 1)
[10, 643, 767, 122]
>>> intt(_, 3*2**8 + 1)
[1, 2, 3, 4]
>>> intt([1, 2, 3, 4], prime=3*2**8 + 1)
[387, 415, 384, 353]
>>> ntt(_, prime=3*2**8 + 1)
[1, 2, 3, 4]

工具书类

快速Walsh-Hadamard变换#

sympy.discrete.transforms.fwht(seq)[源代码]#

执行Walsh-Hadamard变换( WHT )，并对序列使用Hadamard排序。

序列会自动在右侧填充零，如 radix-2 FWHT 要求采样点的数量是2的幂次方。

参数:

seq ：i可读取

应用WHT的顺序。

实例

>>> from sympy import fwht, ifwht
>>> fwht([4, 2, 2, 0, 0, 2, -2, 0])
[8, 0, 8, 0, 8, 8, 0, 0]
>>> ifwht(_)
[4, 2, 2, 0, 0, 2, -2, 0]

>>> ifwht([19, -1, 11, -9, -7, 13, -15, 5])
[2, 0, 4, 0, 3, 10, 0, 0]
>>> fwht(_)
[19, -1, 11, -9, -7, 13, -15, 5]

工具书类

sympy.discrete.transforms.ifwht(seq)[源代码]#

执行Walsh-Hadamard变换( WHT )，并对序列使用Hadamard排序。

序列会自动在右侧填充零，如 radix-2 FWHT 要求采样点的数量是2的幂次方。

参数:

seq ：i可读取

应用WHT的顺序。

实例

>>> from sympy import fwht, ifwht
>>> fwht([4, 2, 2, 0, 0, 2, -2, 0])
[8, 0, 8, 0, 8, 8, 0, 0]
>>> ifwht(_)
[4, 2, 2, 0, 0, 2, -2, 0]

>>> ifwht([19, -1, 11, -9, -7, 13, -15, 5])
[2, 0, 4, 0, 3, 10, 0, 0]
>>> fwht(_)
[19, -1, 11, -9, -7, 13, -15, 5]

工具书类

莫比乌斯变换#

sympy.discrete.transforms.mobius_transform(seq, subset=True)[源代码]#

使用序列索引作为位掩码对子集格执行Mobius变换。

每个参数的索引被视为位串，对应于一个有限集的子集。

序列的右边会自动填充零，因为基于位掩码（索引）的子集/超集定义要求序列的大小是2的幂次。

参数:

seq ：i可读取

应用Mobius变换的序列。

子集 布尔

指定是否通过枚举给定集的子集或父集来应用Mobius变换。

实例

>>> from sympy import symbols
>>> from sympy import mobius_transform, inverse_mobius_transform
>>> x, y, z = symbols('x y z')

>>> mobius_transform([x, y, z])
[x, x + y, x + z, x + y + z]
>>> inverse_mobius_transform(_)
[x, y, z, 0]

>>> mobius_transform([x, y, z], subset=False)
[x + y + z, y, z, 0]
>>> inverse_mobius_transform(_, subset=False)
[x, y, z, 0]

>>> mobius_transform([1, 2, 3, 4])
[1, 3, 4, 10]
>>> inverse_mobius_transform(_)
[1, 2, 3, 4]
>>> mobius_transform([1, 2, 3, 4], subset=False)
[10, 6, 7, 4]
>>> inverse_mobius_transform(_, subset=False)
[1, 2, 3, 4]

工具书类

sympy.discrete.transforms.inverse_mobius_transform(seq, subset=True)[源代码]#

使用序列索引作为位掩码对子集格执行Mobius变换。

每个参数的索引被视为位串，对应于一个有限集的子集。

序列的右边会自动填充零，因为基于位掩码（索引）的子集/超集定义要求序列的大小是2的幂次。

参数:

seq ：i可读取

应用Mobius变换的序列。

子集 布尔

指定是否通过枚举给定集的子集或父集来应用Mobius变换。

实例

>>> from sympy import symbols
>>> from sympy import mobius_transform, inverse_mobius_transform
>>> x, y, z = symbols('x y z')

>>> mobius_transform([x, y, z])
[x, x + y, x + z, x + y + z]
>>> inverse_mobius_transform(_)
[x, y, z, 0]

>>> mobius_transform([x, y, z], subset=False)
[x + y + z, y, z, 0]
>>> inverse_mobius_transform(_, subset=False)
[x, y, z, 0]

>>> mobius_transform([1, 2, 3, 4])
[1, 3, 4, 10]
>>> inverse_mobius_transform(_)
[1, 2, 3, 4]
>>> mobius_transform([1, 2, 3, 4], subset=False)
[10, 6, 7, 4]
>>> inverse_mobius_transform(_, subset=False)
[1, 2, 3, 4]

工具书类

卷积#

本节列出了实现离散序列基本卷积的方法。

卷积#

这是计算离散序列卷积的一种通用方法，它在内部调用其中一种方法 convolution_fft ， convolution_ntt ， convolution_fwht 或 convolution_subset .

sympy.discrete.convolutions.convolution(a, b, cycle=0, dps=None, prime=None, dyadic=None, subset=None)[源代码]#

通过使用提示确定所需卷积的类型来执行卷积。

正是其中之一 dps ， prime ， dyadic ， subset 应显式指定参数以标识卷积的类型和参数 cycle 可以选择指定。

对于默认参数，使用 FFT .

参数:

a, b ：iterables公司

进行卷积的序列。

周期 ：整数

指定执行循环卷积的长度。

dps ：整数

指定执行精度的小数位数 FFT 按顺序。

首要的 ：整数

形式素模 \((m 2^k + 1)\) 用于表演 NTT 按顺序。

并矢 布尔

将卷积类型标识为并元( bitwise-XOR )卷积，使用 FWHT .

子集 布尔

将卷积类型标识为子集卷积。

实例

>>> from sympy import convolution, symbols, S, I
>>> u, v, w, x, y, z = symbols('u v w x y z')

>>> convolution([1 + 2*I, 4 + 3*I], [S(5)/4, 6], dps=3)
[1.25 + 2.5*I, 11.0 + 15.8*I, 24.0 + 18.0*I]
>>> convolution([1, 2, 3], [4, 5, 6], cycle=3)
[31, 31, 28]

>>> convolution([111, 777], [888, 444], prime=19*2**10 + 1)
[1283, 19351, 14219]
>>> convolution([111, 777], [888, 444], prime=19*2**10 + 1, cycle=2)
[15502, 19351]

>>> convolution([u, v], [x, y, z], dyadic=True)
[u*x + v*y, u*y + v*x, u*z, v*z]
>>> convolution([u, v], [x, y, z], dyadic=True, cycle=2)
[u*x + u*z + v*y, u*y + v*x + v*z]

>>> convolution([u, v, w], [x, y, z], subset=True)
[u*x, u*y + v*x, u*z + w*x, v*z + w*y]
>>> convolution([u, v, w], [x, y, z], subset=True, cycle=3)
[u*x + v*z + w*y, u*y + v*x, u*z + w*x]

快速傅里叶变换卷积#

sympy.discrete.convolutions.convolution_fft(a, b, dps=None)[源代码]#

使用快速傅立叶变换执行线性卷积。

参数:

a, b ：iterables公司

进行卷积的序列。

dps ：整数

指定精度的小数位数。

实例

>>> from sympy import S, I
>>> from sympy.discrete.convolutions import convolution_fft

>>> convolution_fft([2, 3], [4, 5])
[8, 22, 15]
>>> convolution_fft([2, 5], [6, 7, 3])
[12, 44, 41, 15]
>>> convolution_fft([1 + 2*I, 4 + 3*I], [S(5)/4, 6])
[5/4 + 5*I/2, 11 + 63*I/4, 24 + 18*I]

工具书类

数论变换卷积#

sympy.discrete.convolutions.convolution_ntt(a, b, prime)[源代码]#

使用数论变换执行线性卷积。

参数:

a, b ：iterables公司

进行卷积的序列。

首要的 ：整数

形式素模 \((m 2^k + 1)\) 用于表演 NTT 按顺序。

实例

>>> from sympy.discrete.convolutions import convolution_ntt
>>> convolution_ntt([2, 3], [4, 5], prime=19*2**10 + 1)
[8, 22, 15]
>>> convolution_ntt([2, 5], [6, 7, 3], prime=19*2**10 + 1)
[12, 44, 41, 15]
>>> convolution_ntt([333, 555], [222, 666], prime=19*2**10 + 1)
[15555, 14219, 19404]

工具书类

快速Walsh-Hadamard变换卷积#

sympy.discrete.convolutions.convolution_fwht(a, b)[源代码]#

执行并矢( bitwise-XOR )使用快速Walsh-Hadamard变换的卷积。

卷积会自动在右侧填充零，如 radix-2 FWHT 要求采样点的数量是2的幂次方。

参数:

a, b ：iterables公司

进行卷积的序列。

实例

>>> from sympy import symbols, S, I
>>> from sympy.discrete.convolutions import convolution_fwht

>>> u, v, x, y = symbols('u v x y')
>>> convolution_fwht([u, v], [x, y])
[u*x + v*y, u*y + v*x]

>>> convolution_fwht([2, 3], [4, 5])
[23, 22]
>>> convolution_fwht([2, 5 + 4*I, 7], [6*I, 7, 3 + 4*I])
[56 + 68*I, -10 + 30*I, 6 + 50*I, 48 + 32*I]

>>> convolution_fwht([S(33)/7, S(55)/6, S(7)/4], [S(2)/3, 5])
[2057/42, 1870/63, 7/6, 35/4]

工具书类

卷积子集#

sympy.discrete.convolutions.convolution_subset(a, b)[源代码]#

对给定序列执行子集卷积。

每个参数的索引被视为位串，对应于一个有限集的子集。

序列会自动用零填充到右边，因为基于位图（索引）的子集定义要求序列的大小为2的幂。

参数:

a, b ：iterables公司

进行卷积的序列。

实例

>>> from sympy import symbols, S
>>> from sympy.discrete.convolutions import convolution_subset
>>> u, v, x, y, z = symbols('u v x y z')

>>> convolution_subset([u, v], [x, y])
[u*x, u*y + v*x]
>>> convolution_subset([u, v, x], [y, z])
[u*y, u*z + v*y, x*y, x*z]

>>> convolution_subset([1, S(2)/3], [3, 4])
[3, 6]
>>> convolution_subset([1, 3, S(5)/7], [7])
[7, 21, 5, 0]

工具书类

覆盖产品#

sympy.discrete.convolutions.covering_product(a, b)[源代码]#

返回给定序列的覆盖积。

每个参数的索引被视为位串，对应于一个有限集的子集。

给定序列的覆盖积是一个序列，它包含由 bitwise-OR 相应的指数。

序列会自动用零填充到右边，因为基于位图（索引）的子集定义要求序列的大小为2的幂。

参数:

a, b ：iterables公司

得到覆盖积的序列。

实例

>>> from sympy import symbols, S, I, covering_product
>>> u, v, x, y, z = symbols('u v x y z')

>>> covering_product([u, v], [x, y])
[u*x, u*y + v*x + v*y]
>>> covering_product([u, v, x], [y, z])
[u*y, u*z + v*y + v*z, x*y, x*z]

>>> covering_product([1, S(2)/3], [3, 4 + 5*I])
[3, 26/3 + 25*I/3]
>>> covering_product([1, 3, S(5)/7], [7, 8])
[7, 53, 5, 40/7]

工具书类

交积#

sympy.discrete.convolutions.intersecting_product(a, b)[源代码]#

返回给定序列的相交积。

每个参数的索引被视为位串，对应于一个有限集的子集。

给定序列的交积是由给定序列的元素的乘积之和组成的序列 bitwise-AND 相应的指数。

序列会自动用零填充到右边，因为基于位图（索引）的子集定义要求序列的大小为2的幂。

参数:

a, b ：iterables公司

求交积的序列。

实例

>>> from sympy import symbols, S, I, intersecting_product
>>> u, v, x, y, z = symbols('u v x y z')

>>> intersecting_product([u, v], [x, y])
[u*x + u*y + v*x, v*y]
>>> intersecting_product([u, v, x], [y, z])
[u*y + u*z + v*y + x*y + x*z, v*z, 0, 0]

>>> intersecting_product([1, S(2)/3], [3, 4 + 5*I])
[9 + 5*I, 8/3 + 10*I/3]
>>> intersecting_product([1, 3, S(5)/7], [7, 8])
[327/7, 24, 0, 0]

工具书类