Попытка написать алгоритм деления на Sympy, который, по-видимому, имеет свою собственную истину (логические переменные)

Question

Итак, я пытался написать код для выполнения алгоритма полиномиального деления с одной переменной, используя SymPy с открытым исходным кодом. В нем уже есть функция ведущего члена, поэтому я подумал, что это будет легко. Книга Кокса, Литтла и О'Ши Идеалы, разновидности и алгоритмы дает псевдокод:

Input: g, f
Output: q, r
q := 0; r := f
WHILE r <> 0 AND LT (g) divides LT (r ) DO
    q := q + LT (r )/ LT (g)
    r := r − ( LT (r )/ LT (g))g

Итак, мой python код:

from sympy import *

x = symbols('x')

f= x**4-5*x**2-2*x+7
g = 3*x**2 + 4*x - 2

q = 0 
r = f
while (r != 0 & degree(g) < LT(r ) ):
    q = q + LT (r )/ LT (g)
    r = r - ( LT (r )/ LT (g))*g

print(q,r)

Но это дает сообщение об ошибке: TypeError: неподдерживаемые типы операндов для &: 'int' и 'Integer' . Итак, в консоли я запрашиваю type(r != 0), и он дает bool , но для type(degree(g) < degree(r)) он дает sympy.logi c .boolalg.BooleanTrue . Я попытался найти документацию для sympy.logi c .boolalg.BooleanTrue , но не смог найти, как сделать его объектом, чтобы можно было комбинировать его с bool с помощью логического &.

Почему у sympy есть свои собственные логические переменные и как мне заставить его хорошо работать с обычными логическими переменными?

Answer 1

SymPy имеет свой собственный класс Boolean, потому что он должен использоваться в конструкции выражения Basic и должен поддерживать такие методы, как subs et c, которые будут использоваться последовательно в архитектуре SymPy.

Тип Boolean может использоваться с bool, например:

In [7]: S.true & True                                                                                                             
Out[7]: True

In [8]: S.true and True                                                                                                           
Out[8]: True

Проблема в вашем примере на самом деле связана с предпочтениями оператора:

In [9]: r != 0 & degree(g) < LT(r )                                                                                               
---------------------------------------------------------------------------
TypeError                                 Traceback (most recent call last)
<ipython-input-9-f2737cccd83e> in <module>
----> 1 r != 0 & degree(g) < LT(r )

TypeError: unsupported operand type(s) for &: 'int' and 'Integer'

In [10]: (r != 0) & (degree(g) < LT(r))                                                                                           
Out[10]: 
     4
2 < x 


In [11]: r != (0 & degree(g)) < LT(r)                                                                                             
---------------------------------------------------------------------------
TypeError                                 Traceback (most recent call last)
<ipython-input-11-c7a6030e1401> in <module>
----> 1 r != (0 & degree(g)) < LT(r)

TypeError: unsupported operand type(s) for &: 'int' and 'Integer'

Это 0 & degree(g) который оценивается первым, а тип SymPy Integer не может использоваться с &, который используется для символов c "и" в SymPy:

In [14]: (x<1) & (x>-1)                                                                                                           
Out[14]: x > -1 ∧ x < 1

Вероятно, вы хотели использовать Python Оператор and, имеющий более низкий приоритет, чем &:

In [15]: r != 0 and degree(g) < LT(r)                                                                                             
Out[15]: 
     4
2 < x 

На самом деле он не будет работать, хотя в while l oop, потому что выражение Boolean является неопределенным:

---> 10 while (r != 0 and degree(g) < LT(r ) ):
     11     q = q + LT (r )/ LT (g)
     12     r = r - ( LT (r )/ LT (g))*g

~/current/sympy/sympy/sympy/core/relational.py in __nonzero__(self)
    382 
    383     def __nonzero__(self):
--> 384         raise TypeError("cannot determine truth value of Relational")
    385 
    386     __bool__ = __nonzero__

TypeError: cannot determine truth value of Relational

Это потому, что истинность условия неизвестна:

In [18]: degree(g) < LT(r)                                                                                                        
Out[18]: 
     4
2 < x 

Я думаю, что вы хотели проверить, есть rem(LT(g), LT(r)) == 0.

from sympy import *

x = symbols('x')

f= x**4-5*x**2-2*x+7
g = 3*x**2 + 4*x - 2

q = 0
r = f
while (r != 0 and rem(LT(g), LT(r)) == 0):
    q = q + LT (r )/ LT (g)
    r = r - ( LT (r )/ LT (g))*g

print(q,r)

Выход:

0 x**4 - 5*x**2 - 2*x + 7

Answer 2

Большое спасибо, Оскар (хотя я до сих пор не понимаю, что sympy boolean должно быть другим). Ваш ответ позволил мне найти другие проблемы, и следующий код работает (в функциональной форме):

from sympy import *

x = symbols('x')

# the division algorithm, returns the quotient and remainder

def DivAlg(f,g):   
    q = 0   # quotient
    r = f   # remainder

    while (r != 0) & (degree(g) <= degree(r)):
        q = q + LT(r)/LT(g) 
        r = r - expand(( LT(r)/LT(g)) * g) # the expand command is necessary!

    return [q,r]

Можно попробовать DivAlg(x**4-x**3-4*x**2-5*x-3, x**2+3*x-5).

Я также использовал это, чтобы написать функцию, которая использует алгоритм Евклида для нахождения GCD двух полиномов с одной переменной:

def GCD(f,g):
    h = f
    s = g
    while (s!= 0):
        r = DivAlg(h,s)[1]
        h = s
        s = r
    return h/LC(h)  # LC(h) is the coefficient of highest order term. 

Вы можете попробовать это с print(GCD(x**3-x**2-x-2,x**4-x**3-4*x**2-5*x-3)).

Это код, необходимый для решения задачи 1.5.8 (стр. 46) забавной книги Идеалы, разновидности и алгоритмы Кокса, Литтла и О'Ши. Я должен отметить, что у sympy - конечно же - уже есть реализация этого с помощью следующей команды: gcd(x**3-x**2-x-2,x**4-x**3-4*x**2-5*x-3,domain=QQ)