对最少数量的加法和乘法运算进行符号化简
Symbolic simplification to least number of plus and multiply operations
最近我不得不使用带有很多长符号表达式的算法,比如这个
upperside = ( e * e * n * p * tn * tn +
2 * e * e * n * p * tn * tp +
e * e * n * p * tp * tp +
2 * e * n * n * p * te * tn +
2 * e * n * n * p * te * tp +
N * e * n * n * tp * tp +
2 * e * n * p * p * te * tn +
2 * e * n * p * p * te * tp -
2 * N * e * n * p * tn * tp +
N * e * p * p * tn * tn +
n * n * n * p * te * te +
2 * n * n * p * p * te * te +
n * p * p * p * te * te)
重新格式化
upperside = ( e * e * n * p * tn * tn +
2 * e * e * n * p * tn * tp +
e * e * n * p * tp * tp +
2 * e * n * n * p * te * tn +
2 * e * n * n * p * te * tp +
N * e * n * n * tp * tp +
2 * e * n * p * p * te * tn +
2 * e * n * p * p * te * tp -
2 * N * e * n * p * tn * tp +
N * e * p * p * tn * tn +
n * n * n * p * te * te +
2 * n * n * p * p * te * te +
n * p * p * p * te * te)
这些表达式是简化后的MATLAB符号例程。很明显,在这种情况下,不可能通过例如合并因子来简化代数表达式。但是,似乎很有可能简化这个表达式,从而大大减少实际操作次数。不幸的是,我无法在 MATLAB 或 Python.
中找到此类选项
感谢任何帮助。
编辑
目标是最小化 CPU 需要为此类表达式执行的操作。由于操作只涉及加法和乘法,我希望得到类似 (e+tn)*(te+tp)+n+... 的东西。我试图分解表达式,但不幸的是表达式不可分解。
如果有任何 python 软件包可以提供帮助,它可能是 Sympy :
from sympy import init_printing, symbols, simplify, collect, factor
e,n,p,tn,te,tp,N = symbols("e,n,p,tn,te,tp,N")
upperside = (e * e * n * p * tn * tn +
2 * e * e * n * p * tn * tp +
e * e * n * p * tp * tp +
2 * e * n * n * p * te * tn +
2 * e * n * n * p * te * tp +
N * e * n * n * tp * tp +
2 * e * n * p * p * te * tn +
2 * e * n * p * p * te * tp -
2 * N * e * n * p * tn * tp +
N * e * p * p * tn * tn +
n * n * n * p * te * te +
2 * n * n * p * p * te * te +
n * p * p * p * te * te)
print collect(upperside, e*n)
它输出:
N*e*p**2*tn**2 +
e**2*n*(p*tn**2 + 2*p*tn*tp + p*tp**2) +
e*n**2*(N*tp**2 + 2*p*te*tn + 2*p*te*tp) +
e*n*(-2*N*p*tn*tp + 2*p**2*te*tn + 2*p**2*te*tp) +
n**3*p*te**2 +
2*n**2*p**2*te**2 +
n*p**3*te**2
在此 page 中描述的所有方法中,collect
看起来最有希望。
这里有一种快速而肮脏的方法来遍历所有符号组合并显示找到的最短表达式:
from sympy import init_printing, symbols, collect, pprint
import itertools
init_printing()
e,n,p,tn,te,tp,big_n = symbols("e,n,p,tn,te,tp,big_n")
upperside = (e * e * n * p * tn * tn + 2 * e * e * n * p * tn * tp +
e * e * n * p * tp * tp + 2 * e * n * n * p * te * tn + 2 * e * n * n * p * te * tp +
big_n * e * n * n * tp * tp + 2 * e * n * p * p * te * tn +
2 * e * n * p * p * te * tp - 2 * big_n * e * n * p * tn * tp + big_n * e * p * p * tn * tn +
n * n * n * p * te * te + 2 * n * n * p * p * te * te + n * p * p * p * te * te)
my_symbols = [e, n, p, tn, te, tp, big_n]
min_length = float('inf')
for i in range(len(my_symbols)):
for symbol_subsets in itertools.combinations(my_symbols, i+1):
collect_by = '*'.join(str(symbol) for symbol in symbol_subsets)
expression = collect(upperside, collect_by)
length = len(str(expression))
if length < min_length:
min_length = length
print "With '%s' :" % collect_by
pprint(expression)
print
它输出:
With 'e' :
e**2*(n*p*tn**2 + 2*n*p*tn*tp + n*p*tp**2) + e*(big_n*n**2*tp**2 - 2*big_n*n*p*tn*tp + big_n*p**2*tn**2 + 2*n**2*p*te*tn + 2*n**2*p*te*tp + 2*n*p**2*te*tn + 2*n*p**2*te*tp) + n**3*p*te**2 + 2*n**2*p**2*te**2 + n*p**3*te**2
With 'n' :
big_n*e*p**2*tn**2 + n**3*p*te**2 + n**2*(big_n*e*tp**2 + 2*e*p*te*tn + 2*e*p*te*tp + 2*p**2*te**2) + n*(-2*big_n*e*p*tn*tp + e**2*p*tn**2 + 2*e**2*p*tn*tp + e**2*p*tp**2 + 2*e*p**2*te*tn + 2*e*p**2*te*tp + p**3*te**2)
With 'e*n' :
big_n*e*p**2*tn**2 + e**2*n*(p*tn**2 + 2*p*tn*tp + p*tp**2) + e*n**2*(big_n*tp**2 + 2*p*te*tn + 2*p*te*tp) + e*n*(-2*big_n*p*tn*tp + 2*p**2*te*tn + 2*p**2*te*tp) + n**3*p*te**2 + 2*n**2*p**2*te**2 + n*p**3*te**2
With 'e*n*p' :
big_n*e*n**2*tp**2 - 2*big_n*e*n*p*tn*tp + big_n*e*p**2*tn**2 + e**2*n*p*(tn**2 + 2*tn*tp + tp**2) + e*n**2*p*(2*te*tn + 2*te*tp) + e*n*p**2*(2*te*tn + 2*te*tp) + n**3*p*te**2 + 2*n**2*p**2*te**2 + n*p**3*te**2
公共子表达式消除(或 sympy cse)计算产品,如:ee 和 ep 以及加法。这有助于找到一个真正优化好的表达式。我见过一个巨大的表达式,有 3 种不同的数学方法,计算时间也大不相同。使用 cse 后,3 个公式的计算时间几乎相同。还有一些大因素比最快的非优化算法更快。
最近我不得不使用带有很多长符号表达式的算法,比如这个
upperside = ( e * e * n * p * tn * tn +
2 * e * e * n * p * tn * tp +
e * e * n * p * tp * tp +
2 * e * n * n * p * te * tn +
2 * e * n * n * p * te * tp +
N * e * n * n * tp * tp +
2 * e * n * p * p * te * tn +
2 * e * n * p * p * te * tp -
2 * N * e * n * p * tn * tp +
N * e * p * p * tn * tn +
n * n * n * p * te * te +
2 * n * n * p * p * te * te +
n * p * p * p * te * te)
重新格式化
upperside = ( e * e * n * p * tn * tn +
2 * e * e * n * p * tn * tp +
e * e * n * p * tp * tp +
2 * e * n * n * p * te * tn +
2 * e * n * n * p * te * tp +
N * e * n * n * tp * tp +
2 * e * n * p * p * te * tn +
2 * e * n * p * p * te * tp -
2 * N * e * n * p * tn * tp +
N * e * p * p * tn * tn +
n * n * n * p * te * te +
2 * n * n * p * p * te * te +
n * p * p * p * te * te)
这些表达式是简化后的MATLAB符号例程。很明显,在这种情况下,不可能通过例如合并因子来简化代数表达式。但是,似乎很有可能简化这个表达式,从而大大减少实际操作次数。不幸的是,我无法在 MATLAB 或 Python.
中找到此类选项感谢任何帮助。
编辑 目标是最小化 CPU 需要为此类表达式执行的操作。由于操作只涉及加法和乘法,我希望得到类似 (e+tn)*(te+tp)+n+... 的东西。我试图分解表达式,但不幸的是表达式不可分解。
如果有任何 python 软件包可以提供帮助,它可能是 Sympy :
from sympy import init_printing, symbols, simplify, collect, factor
e,n,p,tn,te,tp,N = symbols("e,n,p,tn,te,tp,N")
upperside = (e * e * n * p * tn * tn +
2 * e * e * n * p * tn * tp +
e * e * n * p * tp * tp +
2 * e * n * n * p * te * tn +
2 * e * n * n * p * te * tp +
N * e * n * n * tp * tp +
2 * e * n * p * p * te * tn +
2 * e * n * p * p * te * tp -
2 * N * e * n * p * tn * tp +
N * e * p * p * tn * tn +
n * n * n * p * te * te +
2 * n * n * p * p * te * te +
n * p * p * p * te * te)
print collect(upperside, e*n)
它输出:
N*e*p**2*tn**2 +
e**2*n*(p*tn**2 + 2*p*tn*tp + p*tp**2) +
e*n**2*(N*tp**2 + 2*p*te*tn + 2*p*te*tp) +
e*n*(-2*N*p*tn*tp + 2*p**2*te*tn + 2*p**2*te*tp) +
n**3*p*te**2 +
2*n**2*p**2*te**2 +
n*p**3*te**2
在此 page 中描述的所有方法中,collect
看起来最有希望。
这里有一种快速而肮脏的方法来遍历所有符号组合并显示找到的最短表达式:
from sympy import init_printing, symbols, collect, pprint
import itertools
init_printing()
e,n,p,tn,te,tp,big_n = symbols("e,n,p,tn,te,tp,big_n")
upperside = (e * e * n * p * tn * tn + 2 * e * e * n * p * tn * tp +
e * e * n * p * tp * tp + 2 * e * n * n * p * te * tn + 2 * e * n * n * p * te * tp +
big_n * e * n * n * tp * tp + 2 * e * n * p * p * te * tn +
2 * e * n * p * p * te * tp - 2 * big_n * e * n * p * tn * tp + big_n * e * p * p * tn * tn +
n * n * n * p * te * te + 2 * n * n * p * p * te * te + n * p * p * p * te * te)
my_symbols = [e, n, p, tn, te, tp, big_n]
min_length = float('inf')
for i in range(len(my_symbols)):
for symbol_subsets in itertools.combinations(my_symbols, i+1):
collect_by = '*'.join(str(symbol) for symbol in symbol_subsets)
expression = collect(upperside, collect_by)
length = len(str(expression))
if length < min_length:
min_length = length
print "With '%s' :" % collect_by
pprint(expression)
print
它输出:
With 'e' :
e**2*(n*p*tn**2 + 2*n*p*tn*tp + n*p*tp**2) + e*(big_n*n**2*tp**2 - 2*big_n*n*p*tn*tp + big_n*p**2*tn**2 + 2*n**2*p*te*tn + 2*n**2*p*te*tp + 2*n*p**2*te*tn + 2*n*p**2*te*tp) + n**3*p*te**2 + 2*n**2*p**2*te**2 + n*p**3*te**2
With 'n' :
big_n*e*p**2*tn**2 + n**3*p*te**2 + n**2*(big_n*e*tp**2 + 2*e*p*te*tn + 2*e*p*te*tp + 2*p**2*te**2) + n*(-2*big_n*e*p*tn*tp + e**2*p*tn**2 + 2*e**2*p*tn*tp + e**2*p*tp**2 + 2*e*p**2*te*tn + 2*e*p**2*te*tp + p**3*te**2)
With 'e*n' :
big_n*e*p**2*tn**2 + e**2*n*(p*tn**2 + 2*p*tn*tp + p*tp**2) + e*n**2*(big_n*tp**2 + 2*p*te*tn + 2*p*te*tp) + e*n*(-2*big_n*p*tn*tp + 2*p**2*te*tn + 2*p**2*te*tp) + n**3*p*te**2 + 2*n**2*p**2*te**2 + n*p**3*te**2
With 'e*n*p' :
big_n*e*n**2*tp**2 - 2*big_n*e*n*p*tn*tp + big_n*e*p**2*tn**2 + e**2*n*p*(tn**2 + 2*tn*tp + tp**2) + e*n**2*p*(2*te*tn + 2*te*tp) + e*n*p**2*(2*te*tn + 2*te*tp) + n**3*p*te**2 + 2*n**2*p**2*te**2 + n*p**3*te**2
公共子表达式消除(或 sympy cse)计算产品,如:ee 和 ep 以及加法。这有助于找到一个真正优化好的表达式。我见过一个巨大的表达式,有 3 种不同的数学方法,计算时间也大不相同。使用 cse 后,3 个公式的计算时间几乎相同。还有一些大因素比最快的非优化算法更快。