Bug #154
GCD normalization (e.g. monic)
Description
If the field is a FractionField then there's a fairly natural choice of normalized factor.
If it is not then the preferred choice of normalization is unclear. There are three options:
- no normalization, the costant factor is whatever it turns out to be
- make the factor monic (this is surely canonical)
- some other normalization (but what???)
Note that making the factor monic can be "unnatural". Suppose the result is 7*x+8
in ZZ/(32003)[x]
; making this monic produces the less comprehensible x+4573
.
Related issues
History
#1 Updated by Anna Maria Bigatti over 10 years ago
- Subject changed from GCD normalization to GCD normalization (e.g. monic)
- Category set to Tidying
- Target version set to CoCoALib-0.99534 Seoul14
- % Done changed from 0 to 10
I agree that it would be convenient having a guarantee on the result, but the operation might be uselessly costly (for example if I'm interested in knowing only the degree of the GCD).
It might be a good idea having two functions:
- gcd
, GcdMonic
(or whatever)
or
- GcdNonMonic
, - gcd
#2 Updated by John Abbott over 10 years ago
I think we should guarantee that if the gcd is trivial then the result is 1, so users can write clear code such as if (gcd(f,g) == 1) ...
The function called gcd
should give this guarantee.
I prefer that the fn called gcd
give a normalized result, and that the possibly faster function which may give unnormalized results have a "strange" name.
#3 Updated by Anna Maria Bigatti over 10 years ago
John Abbott wrote:
I think we should guarantee that if the gcd is trivial then the result is 1, so users can write clear code such as
if (gcd(f,g) == 1) ...
The function calledgcd
should give this guarantee.
There is a trivial solution for this case: when the final result of gcd
is invertible we just return one(R)
.
That is cheap (just depends on IsInvertible
which is usually fast) performs no other operation, and has no ambiguity in the definition!
#4 Updated by John Abbott almost 10 years ago
- Target version changed from CoCoALib-0.99534 Seoul14 to CoCoALib-1.0
#5 Updated by John Abbott over 7 years ago
- Status changed from New to In Progress
- % Done changed from 10 to 20
I stumbled across this problem/issue again when trying to implement GCDFreeBasis
(see #259).
In reference to my comment 2 (above), the code would actually be clearer if I wrote if (IsCoprime(f,g))
which ought to be marginally cheaper than if (gcd(f,g)==1)
since the latter requires converting 1
to an element of the relevant ring.
We could try to implement two fns, "normalized" GCD and "unnormalized" GCD, and then do some tests to compare them. My expectation is that they are equally fast/slow in almost all cases.
Note that we can normalize a single element just by computing gcd(elem,0)
- in
ZZ
the result is non-negative. - in
ZZ[...]
the result has positive leading coeff. - in
QQ[...]
the result isZZ
-primitive with positive leading coeff (special case:gcd(0,0) = 0
). - in
FrF[...]
whereFrF
is a field of fractions, the result is primitive in "base ring" ofk
and coeff of LPP is normalized. - in
k[...]
withk
a field, the result is monic. - in
R[a,b][x,y]
the result is the same as inR[a,b,x,y]
.
I am not actually sure that the above rules are exhaustive, but I think they are a reasonable starting point.
These rules do imply that we get the "hard to comprehend" result x+4573
instead of 7*x+8
in the example given in the initial description.
There are some other possibly "surprising" results: e.g. in QQ[x]
we get gcd(x+1/2, x^2-1/4) = 2*x+1
Maybe there could be an extra rule that in k[...]
if all args are monic then the result is monic?
Comments? Ideas? Criticisms?
#6 Updated by John Abbott over 7 years ago
- Related to Feature #259: Squarefree(?) GCD-free basis added