On Sep 14, 2009, at 3:47 PM, Sebastian Pancratz wrote: > 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.
I would expect monic polynomials. > 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? Bill Hart would be the one who knows this. - Robert --~--~---------~--~----~------------~-------~--~----~ 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 -~----------~----~----~----~------~----~------~--~---
