Dear all,
The implementation of QQ[] using FLINT is making lots of progress and
it seems as if everything should be *much* faster than it is now.
At the moment, I've got two questions. First one is about the design
of the gcd method, and possibly affects other rings too. The second
method is pretty implementation specific; I'd be grateful if someone
with a good knowledge of FLINT and GMP could please have a look at it,
because otherwise it might lead to some difficult bugs later.
1.
Given rational polynomials a and b, what should gcd(a,b) return? The
problem arises since the gcd is only defined up to rational units. I
think the two sound options are either the monic normalisation, or a
primitive integer polynomial with positive leading coefficient.
Personally, I would be in favour of the second choice, because in the
new implementation using FLINT, the polynomial is represented as an
integer polynomial with a positive integer denominator coprime to the
content of the numerator. If in a higher level block of code calls
are made to gcd on a frequent basis, this would be faster than if gcd
always had to return the monic version.
Here are two other examples from SAGE (ignoring the case gcd(0,0) ==
0):
- Integers: Positive values.
- Rationals: 1.
- Integer polynomials: Polynomial with positive leading
coefficient.
- Polynomials over Z/nZ via FLINT: Not quite sure, except that gcd
(a,0) == a and gcd(0,b) == b. By the way, working in (Z/27Z)[t], gcd
(3*t+2, (3*t+2)*(t^3 + t - 1)) returns 1, which looks like a bug. In
any case, enforcing gcd(a,0) == a leads to an inconsistent
normalisation, so it might also be a good idea to think about what gcd
should return working in (Z/nZ)[t].
I'd appreciate your input on how to normalise the gcd output.
2.
One of the input methods for rational polynomials needs to take a SAGE
Rational. In particular, it needs to initialise an integer of type
fmpz_t and set it to the value of an integer of type mpz_t. The
following block of code illustrates the problem (although it doesn't
exactly like this appear in my code):
# Assume that x a rational is of type mpq_t, properly initialised
to some value.
# Want to set den to the denominator of x.
cdef fmpz_t den
cdef unsigned long limbs
limbs = mpz_size(mpq_denref(x)) # TODO: Check that fmpz and mpz
limbs are compatible!
den = fmpz_init(limbs)
mpz_to_fmpz(den, mpq_denref(x))
I am afraid that this way, the call "fmpz_init(limbs)" might not
allocate enough room for the value I want to store. I have worked
with GMP (using C code) before, but this is the first time that I am
working with FLINT and hence fmpz_t's. Can someone please confirm
that the above code does the right thing, or let me know how to do
this?
Many thanks!
Sebastian
--~--~---------~--~----~------------~-------~--~----~
To post to this group, send an email to sage-devel@googlegroups.com
To unsubscribe from this group, send an email to
sage-devel-unsubscr...@googlegroups.com
For more options, visit this group at http://groups.google.com/group/sage-devel
URL: http://www.sagemath.org
-~----------~----~----~----~------~----~------~--~---
