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を独学しているので、単純な間違いを犯している可能性があります。