In this notebook, we will demonstrate some of the differences between SymPy's logic module, and PyEDA's logic expressions.
In [ ]:
import sympy
In [ ]:
import pyeda.boolalg.expr
import pyeda.boolalg.bfarray
The xs array is a tuple of SymPy symbolic variables,
and the ys array is a PyEDA function array.
In [ ]:
xs = sympy.symbols(",".join("x%d" % i for i in range(64)))
In [ ]:
ys = pyeda.boolalg.bfarray.exprvars('y', 64)
Create a SymPy XOR function:
In [ ]:
f = sympy.Xor(*xs[:4])
Create a PyEDA XOR function:
In [ ]:
g = pyeda.boolalg.expr.Xor(*ys[:4])
SymPy atoms method is similar to PyEDA's support property:
In [ ]:
f.atoms()
In [ ]:
g.support
SymPy's subs method is similar to PyEDA's restrict method:
In [ ]:
f.subs({xs[0]: 0, xs[1]: 1})
In [ ]:
g.restrict({ys[0]: 0, ys[1]: 1})
Conversion to negation normal form is also similar. One difference is that SymPy inverts the variables by applying a Not operator, but PyEDA converts inverted variables to complements (a negative literal).
In [ ]:
sympy.to_nnf(f)
In [ ]:
type(sympy.Not(xs[0]))
In [ ]:
g.to_nnf()
In [ ]:
type(~ys[0])
Conversion to disjunctive normal form, on the other hand, has some differences. With only four input variables, SymPy takes a couple seconds to do the calculation. The output is large, with unsimplified values and redundant clauses.
In [ ]:
sympy.to_dnf(f)
PyEDA's DNF conversion is minimal:
In [ ]:
g.to_dnf()
It's a little hard to do an apples-to-apples comparison, because 1) SymPy is pure Python and 2) the algorithms are probably different.
The simplify_logic function actually looks better for comparison:
In [ ]:
from sympy.logic import simplify_logic
In [ ]:
simplify_logic(f)
In [ ]:
simplify_logic(f)
Running this experiment from N=2 to N=6 shows that PyEDA's runtime grows significantly slower.
In [ ]:
import numpy as np
import matplotlib.pyplot as plt
In [ ]:
%matplotlib inline
In [ ]:
N = 5
sympy_times = (.000485, .000957, .00202, .00426, .0103)
pyeda_times = (.0000609, .000104, .000147, .00027, .000451)
ind = np.arange(N) # the x locations for the groups
width = 0.35 # the width of the bars
fig, ax = plt.subplots()
rects1 = ax.bar(ind, sympy_times, width, color='r')
rects2 = ax.bar(ind + width, pyeda_times, width, color='y')
# add some text for labels, title and axes ticks
ax.set_ylabel('Time (s)')
ax.set_title('SymPy vs. PyEDA: Xor(x[0], x[1], ..., x[n-1]) to DNF')
ax.set_xticks(ind + width)
ax.set_xticklabels(('N=2', 'N=3', 'N=4', 'N=5', 'N=6'))
ax.legend((rects1[0], rects2[0]), ('SymPy', 'PyEDA'))
plt.show()
Going a bit further, things get worse.
These numbers are from my laptop:
| N | sympy | pyeda | ratio |
|---|---|---|---|
| 2 | .000485 | .0000609 | 7.96 |
| 3 | .000957 | .000104 | 9.20 |
| 4 | .00202 | .000147 | 13.74 |
| 5 | .00426 | .00027 | 15.78 |
| 6 | .0103 | .000451 | 22.84 |
| 7 | .0231 | .000761 | 30.35 |
| 8 | .0623 | .00144 | 43.26 |
| 9 | .162 | .00389 | 41.65 |
| 10 | .565 | .00477 | 118.45 |
| 11 | 1.78 | .012 | 148.33 |
| 12 | 6.46 | .0309 | 209.06 |
SymPy supports some obvious simplifications, but PyEDA supports more. Here are a few examples.
In [ ]:
sympy.Equivalent(xs[0], xs[1], 0)
In [ ]:
pyeda.boolalg.expr.Equal(ys[0], ys[1], 0)
In [ ]:
sympy.ITE(xs[0], 0, xs[1])
In [ ]:
pyeda.boolalg.expr.ITE(ys[0], 0, ys[1])
In [ ]:
sympy.Or(xs[0], sympy.Or(xs[1], xs[2]))
In [ ]:
pyeda.boolalg.expr.Or(ys[0], pyeda.boolalg.expr.Or(ys[1], ys[2]))
In [ ]:
sympy.Xor(xs[0], sympy.Not(sympy.Xor(xs[1], xs[2])))
In [ ]:
pyeda.boolalg.expr.Xor(ys[0], pyeda.boolalg.expr.Xnor(ys[1], ys[2]))