我正在尝试在 GF(2) 字段中划分多项式。 http://en.wikipedia.org/wiki/Finite_field_arithmetic http://en.wikipedia.org/wiki/GF(2)
似乎我的整个划分序列进展顺利,我非常坚持的问题是它一直保持顺利超过它应该停止的点。XOR 用于减法,如果您检查变量 b 应该在某个时候保持正确的余数,但它会继续运行。
class binary1polynomials:
#binary arithemtic on polynomials
def __init__(self,expr):
self.expr = expr
def degree(self):
return len(self.expr)
def id(self):
return [self.expr[i]%2 for i in range(len(self.expr))]
def listToInt(self):
#return int(reduce(lambda x,y: x+str(y), self.expr, ''))
result = binary1polynomials.id(self)
return int(''.join(map(str,result)))
def divide(a,b): #a,b are lists like (1,0,1,0,0,1,....)
a = binary1polynomials.listToInt(a); b = binary1polynomials.listToInt(b)
print "a,b,type(a) ",a,b,type(a)
bina = int(str(a),2); binb = int(str(b),2)
a = min(bina,binb); b = max(bina,binb);
print "a,b ",a,b
g = []; bitsa = "{0:b}".format(a); bitsb = "{0:b}".format(b)
difflen = len(str(bitsb)) - len(str(bitsa))
print "difflen,bitsa,bitsb,type(bitsa) ",difflen,bitsa,bitsb,type(bitsa)
print "a,b ",a,b
c = a<<difflen
print "a,b,c ",a,b,c
#for bit in range(difflen):
#for i,bit in enumerate(bitsa): #'bitsa' must be an integer base 2 before passing in
while difflen > 0 or b != 0:
print "A. b,c ",bin(b),bin(c)
b = b^c #,a*int(bitsa[bit])
lendif = abs(len(str(bin(b))) - len(str(bin(c))))
c = c>>lendif
difflen = difflen - 1
print "B. b,c,lendif ",bin(b),bin(c),lendif#,int(bitsa[bit])
z = "{0:b}".format(b)
return z
j = (1,1,1,1);h = (1,1,0,1);k = (1,0,1,1,0);t1 = (1,1,1); t2 = (1,0,1)
t3 = (1,1); t4 = (1, 0, 1, 1, 1, 1, 1)
a = binary1polynomials(j);b = binary1polynomials(h);c = binary1polynomials(k)
f1 = binary1polynomials(t1); f2 = binary1polynomials(t2)
f3 = binary1polynomials(t3); f4 = binary1polynomials(t4)
print "divide: ",binary1polynomials.divide(f1,b)
print "divide: ",binary1polynomials.divide(f4,a)
print "divide: ",binary1polynomials.divide(f4,f2)
print "divide: ",binary1polynomials.divide(f2,a)
从这个 OUTPUT 来看,它似乎在某个时候(每次)都得到了正确的答案,但随后就直接过去了。
*** Remote Interpreter Reinitialized ***
>>>
divide: a,b,type(a) 111 1101 <type 'int'>
a,b 7 13
difflen,bitsa,bitsb,type(bitsa) 1 111 1101 <type 'str'>
a,b 7 13
a,b,c 7 13 14
A. b,c 0b1101 0b1110
B. b,c,lendif 0b11 0b11 2
A. b,c 0b11 0b11
B. b,c,lendif 0b0 0b1 1
g []
0
divide: a,b,type(a) 1011111 1111 <type 'int'>
a,b 15 95
difflen,bitsa,bitsb,type(bitsa) 3 1111 1011111 <type 'str'>
a,b 15 95
a,b,c 15 95 120
A. b,c 0b1011111 0b1111000
B. b,c,lendif 0b100111 0b111100 1
A. b,c 0b100111 0b111100
B. b,c,lendif 0b11011 0b11110 1
A. b,c 0b11011 0b11110
B. b,c,lendif 0b101 0b111 2
A. b,c 0b101 0b111
B. b,c,lendif 0b10 0b11 1
A. b,c 0b10 0b11
B. b,c,lendif 0b1 0b1 1
A. b,c 0b1 0b1
B. b,c,lendif 0b0 0b1 0
g []
0
divide: a,b,type(a) 1011111 101 <type 'int'>
a,b 5 95
difflen,bitsa,bitsb,type(bitsa) 4 101 1011111 <type 'str'>
a,b 5 95
a,b,c 5 95 80
A. b,c 0b1011111 0b1010000
B. b,c,lendif 0b1111 0b1010 3
A. b,c 0b1111 0b1010
B. b,c,lendif 0b101 0b101 1
A. b,c 0b101 0b101
B. b,c,lendif 0b0 0b1 2
A. b,c 0b0 0b1
B. b,c,lendif 0b1 0b1 0
A. b,c 0b1 0b1
B. b,c,lendif 0b0 0b1 0
g []
0
divide: a,b,type(a) 101 1111 <type 'int'>
a,b 5 15
difflen,bitsa,bitsb,type(bitsa) 1 101 1111 <type 'str'>
a,b 5 15
a,b,c 5 15 10
A. b,c 0b1111 0b1010
B. b,c,lendif 0b101 0b101 1
A. b,c 0b101 0b101
B. b,c,lendif 0b0 0b1 2
g []
0
这可能是我在自学 Python 时犯的一些简单错误。