Design #377
IsDivisible -- exact semantics?
Description
While dealing with issue #248 I realised that the exact semantics of IsDivisible
are not clear.
The problem is when the ring contains zero-divisors.
Guideline: IsDivisible(a,b)
gives true iff a/b
will succeed
Let zd
be a (non-zero) zero-divisor; let nzd
be a non-zero-divisor:
- it is clear that IsDivisible(0,nzd)
should produce true
- what should IsDivisible(0,zero(R))
produce?
- what should IsDivisible(0,zd)
produce?
- what should IsDivisible(2*zd,zd)
produce?
For concreteness, you can take the ring R = NewZZmod(6)
and zd = 2
and nzd = 5
Comments?
Related issues
History
#1 Updated by John Abbott almost 11 years ago
- Status changed from New to In Progress
- Assignee set to John Abbott
The problem with dividing 4/2
in ZZ/6
is that the true answer is 2
in ZZ/3
-- a different ring! The answer could be either 2
or 5
in ZZ/6
.
(A) So we could say that 4
is divisible by 2
, but when we perform the division we must choose one answer among many.
(B) Or we could say that 4
is not divisible by 2
because the answer is not unique in that ring.
Consequences:
(C) If we adopt approach (A) then presumably we must also say that 0
is divisible by 0
; but that implies that one can compute 0/0
and expect to get an answer...
(D) If we adopt approach (B) then IsDivisible(0,zd)
should always give false
(because the answer is not unique: it could be 0
or any cofactor of zd
).
At the moment I favour approach (B).
#2 Updated by John Abbott almost 11 years ago
- % Done changed from 0 to 10
JAA continues to believe that attempting to compute 0/0
in any ring should give an error. Giving an answer is almost surely going to lead to a nasty surprise sooner or later.
This reinforces my preference for design decision (B).
#3 Updated by Anna Maria Bigatti over 10 years ago
- Target version changed from CoCoALib-0.99534 Seoul14 to CoCoALib-0.99532
#4 Updated by Anna Maria Bigatti almost 10 years ago
- Target version changed from CoCoALib-0.99532 to CoCoALib-0.99533 Easter14
#5 Updated by John Abbott almost 10 years ago
- % Done changed from 10 to 30
Summarising:IsDivisible(a,b)
gives true
iff there is a unique c
in the ring satisfying a = b*c
(assuming ring is commutative). This implies that a/b
is well-defined (and so ought to be computable).
As Anna said: this fits in well with CoCoA's "pragmatic philosphy".
Nevertheless the documentation should point out the pecularities of IsDivisible
in CoCoA.
Note that IsDivisible
throws ERR::DivByZero
if b=0
; we chose this behaviour because we think that testing for divisibility by 0 is more likely a consequence of a programming error than an intended test.
Note that IsDivisible
apparently always gives false
if the 2nd arg is a non-zero zero-divisor (agreeing with condition that the quotient be unique).
Action: check & correct documentation, check & correct implementations!
#6 Updated by John Abbott almost 10 years ago
- % Done changed from 30 to 50
Aldo says that "a
is divisible by b
" means that there exists at least one c
such that a = b*c
. He accepted happily that this means that 0 is divisible by 0; this is, of course, quite unacceptable for CoCoA (because 0/0
will cause an error; it'd be too "dangerous" to give a result).
- if
b
is a zero-divisor then give error (ERR::DivByZero
) - otherwise return
true
orfalse
appropriately
I observe that in comment-5 we had proposed error for b=0
but not for other zero-divisors; this is somewhat inconsistent! The proposal in this comment is more consistent.
#7 Updated by John Abbott almost 10 years ago
- Status changed from In Progress to Feedback
- % Done changed from 50 to 90
Implemented the proposal in comment-6; changed several IsZero
checks into IsZeroDivisor
.
Changed state to feedback
#8 Updated by John Abbott almost 10 years ago
- Status changed from Feedback to Closed
- % Done changed from 90 to 100
#9 Updated by Anna Maria Bigatti almost 10 years ago
- Estimated time set to 3.00 h
#10 Updated by John Abbott over 3 years ago
- Related to Design #1500: IsDivisible in a field? added