Gaussian and Eisenstein integers can do Euclidean division. It would be handy to add floordiv and mod (and a divmod method that lets you choose the rounding function used, and maybe stuff that depends on divmod like gcd).
I'm not sure what should happen if you try a//b on arbitrary QuadraticInteger values (where d is not 1, -1, or -3). One option is to just raise ValueError('not a Euclidean domain'); another is to return a/b if b|a and raise an exception otherwise (which you can do just by return a/b); another is to just ignore the fact that it's not valid Euclidean division (so abs(a % b) <= abs(b) is not guaranteed) and do it anyway.
Anyway, I haven't looked at your code in detail yet, so I don't have a pull request. But here's some slapped-together code that works for sympy using a simple a+b*w representation for d==-3 (it's even simpler for -1 and 1, of course):
w = Symbol('w')
W = (-1 + sqrt(3)*I)/2 # or if you prefer exp(2*pi*I/3)
def rewrite_in_W(x):
x = x.subs(w, W)
a, b3 = re(x), im(x)/sqrt(3)
return a+b3, 2*b3
def divmod(x, y, *, round=floor):
qa, qb = rewrite_in_W(x/y)
qa, qb = round(qa), round(qb)
q = qa + qb*w
r = x - q*y
ra, rb = rewrite_in_W(x - q*y)
assert (ra, rb) == (round(ra), round(rb))
r = ra + rb*w
return q, r
assert divmod(-7+7*w, 1+6*w) == (2+w, -3)
assert divmod(-7+7*w, 1+6*w, round=ceil) == (3+2*w, 2-w)
And here's code that does the same with your type from outside:
Ei = QuadraticIntegerRing(-3)
w = (-1 + sqrt(3)*I)/2
def rewrite_in_w(x):
a, b3 = re(x), im(x)/sqrt(3)
return a+b3, 2*b3
def divmod(x, y, *, round=floor):
qa, qb = rewrite_in_w(x.value/y.value)
qa, qb = round(qa), round(qb)
q = qa + qb*w
r = x - q*y
return type(x)(q), type(x)(r)
ei77 = Ei(-7+7*w)
ei16 = Ei(1+6*w)
assert divmod(ei77, ei16) == (Ei(2+w), Ei(-3))
assert divmod(ei77, ei16, round=ceil) == (Ei(3+2*w), Ei(2-w))
Gaussian and Eisenstein integers can do Euclidean division. It would be handy to add floordiv and mod (and a
divmodmethod that lets you choose the rounding function used, and maybe stuff that depends ondivmodlikegcd).I'm not sure what should happen if you try
a//bon arbitraryQuadraticIntegervalues (wheredis not 1, -1, or -3). One option is to justraise ValueError('not a Euclidean domain'); another is to returna/bifb|aand raise an exception otherwise (which you can do just byreturn a/b); another is to just ignore the fact that it's not valid Euclidean division (soabs(a % b) <= abs(b)is not guaranteed) and do it anyway.Anyway, I haven't looked at your code in detail yet, so I don't have a pull request. But here's some slapped-together code that works for sympy using a simple
a+b*wrepresentation ford==-3(it's even simpler for -1 and 1, of course):And here's code that does the same with your type from outside: