Re: [sage-devel] Re: sage thoughts
On Wed, Feb 9, 2011 at 10:46 PM, daly wrote: > On Wed, 2011-02-09 at 22:18 -0800, rjf wrote: >> You say, >> > gcd(2/1,4) returns 1 "for simplicity" (!), because 2/1 is a rational. >> > This is shockingly silly. >> >> I don't know exactly how this came up, but if 2/1 is in a different >> domain (rational) >> from 2, (integer), then gcd should probably be 1, since any non- >> zero >> rational number divides any other, and one commonly uses the positive >> "unit" 1 for >> such a case. You could argue that since you can coerce 2/1, you >> should. >> >> That's sometimes OK, but not always. >> >> Really, the issue is much broader. for example, do you also want to >> treat the complex number >> 1+0*i the same as 1? do you want to treat the floating point number >> 1.0 the same as 1? >> >> What about 1X1 matrices? >> >> Is 1^0 the same as 1^0.0 or 1.0^0 or 1.0^0.0? Do you perhaps wish >> to consider/dismiss >> the existence of number systems with signed zeros (IEEE floating-point >> standard) on the >> grounds that -0 = +0, [true, for numerical comparison] and therefore >> there should be >> only a single zero? >> >> While I don't know the exact formulation of this GCD problem, the >> issue of >> implicit coercion is one of the troubling sore spots in a system >> design, and should not >> be decided by counting up casual +1 votes. >> >> I think the Axiom people might have thought more about it than others. >> > > It is a question of domains. In Axiom you can specify the domains. You can in Sage too. The question is whether 1 is the right answer for the domain of rational numbers. (That's what it currently does, just like Axiom, but it's not very useful.) > 2/1 is a Fraction(Integer) aka rational > 4 is an Integer > (2/1)::Integer => 2 where 2 is an Integer. > 4::Fraction(Integer) is a Fraction(Integer) > > So there are several cases: > gcd((2/1),4::Fraction(Integer)) => 1 of type Fraction(Integer) > gcd((2/1)::Integer,4)) => 2 of type PositiveInteger > gcd(2/1,4) => 1 of type Fraction(Integer) > gcd(2,4) => 2 of type PositiveInteger > gcd(2,4::Fraction(Integer)) => 1 of type Fraction(Integer) > > Tim Daly > > > > -- > 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 > -- 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
[sage-devel] Re: sage thoughts
Hi Nils, On 11 Feb., 20:25, Nils Bruin wrote: > I'd say: return 0 if a=b=0 and some random non-zero field element > otherwise. That will teach people to write programs that depend on > properly defined mathematical concepts rather than implementation > details. (this is not a serious proposal for this particular case but > the principle of not going out of your way to fix arbitrary choices > and to avoid depending on them being made in a particular way has > served me well). Yes and no. "Yes", because it is a bad idea to rely on choices that have no mathematical justification. "No", since it is a bad idea to *not* rely on canonical choices if one is in a situation that allows for a canonical choice. Here, we can argue: If a programmer writes code for principal ideal domains, then s/he is supposed to not rely on a particular choice of lcm/gcd -- because in a PID F, these notions are only defined up to a unit of F. However, if the programmer writes code for the fraction field, F, of PIDs, R, then one certainly is in a special situation. There is a mathematically sound way to define lcm/gcd uniquely up to a unit of R (not of F). So, the ambiguity is less, and it would be silly to not use the smaller ambiguity. I think this kind of argument holds in general, not only for gcd/lcm. Cheers, Simon -- 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
[sage-devel] Re: sage thoughts
On Feb 11, 9:56 am, Simon King wrote: > Why an exception? If the elements are in a field that is not the > fraction field of a PID, it is totally fine that gcd(a,b) returns 0 if > one of a,b is zero, and returns 1 otherwise. > > I hope the whole discussion is not "painting a bike shed"... I'd say: return 0 if a=b=0 and some random non-zero field element otherwise. That will teach people to write programs that depend on properly defined mathematical concepts rather than implementation details. (this is not a serious proposal for this particular case but the principle of not going out of your way to fix arbitrary choices and to avoid depending on them being made in a particular way has served me well). The "positive generator of the fractional ideal" choice makes a lot of sense to me in an interactive setting, but I'd expect that the dependence of a program on that behaviour would almost always be an error. -- 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
[sage-devel] Re: sage thoughts
Hi Andrey, On 11 Feb., 15:59, Andrey Novoseltsev wrote: > > sage: (1/4).content(1/6) > > 1/12 > > Which agrees with what I have suggested before - gcd "analog" for > fields should have some other name. After all, since any rational > number is divisible by any non-zero, how can we pick "the greatest" of > them all? For ZZ the notion of greatness agrees with the usual > understanding of greater... The term "greatest" may be in the background of the original definition for the gcd in ZZ, but it is quite common in math that the generalisation of a notion (like "gcd(a,b) in a PID is defined to be a generator of the principal ideal generated by a and b") has not much to do with the original formulation (like "gcd(a,b) in ZZ is the greatest integer that divides both a and b"). > How about such an approach: > 1) if gcd got elements of a fraction field, e.g. (2/1, 4), it tries to > convert them to the ring of intergers and compute the gcd there (and > lcm too) The suggestion is to define gcd in QQ (and, more general, in fraction fields of a PID) such that it is not needed to try and convert 2/1 to an integer. I gave a possible approach in a previous post. > 2) if it fails, raise an exception Why an exception? If the elements are in a field that is not the fraction field of a PID, it is totally fine that gcd(a,b) returns 0 if one of a,b is zero, and returns 1 otherwise. I hope the whole discussion is not "painting a bike shed"... Cheers, Simon -- 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
[sage-devel] Re: sage thoughts
On Feb 11, 4:25 am, koffie wrote: > By the way, notice that inhttp://trac.sagemath.org/sage_trac/ticket/3214 > they also added a function "content" which does the old gcd behaviour > (i.e. similar to what simon describes). > > sage: (1/4).content(1/6) > 1/12 > Which agrees with what I have suggested before - gcd "analog" for fields should have some other name. After all, since any rational number is divisible by any non-zero, how can we pick "the greatest" of them all? For ZZ the notion of greatness agrees with the usual understanding of greater... How about such an approach: 1) if gcd got elements of a fraction field, e.g. (2/1, 4), it tries to convert them to the ring of intergers and compute the gcd there (and lcm too) 2) if it fails, raise an exception This will take care of the original problem. Thank you, Andrey > On Feb 11, 12:15 pm, koffie wrote: > > > First of all, sorry Simon to have misread you :(. > > > To awnser your question. I guess your algorithm makes sense when you > > do it with fractions in the reduced form. I will do it only for prime > > powers since the general case will follow from this. > > Suppose we have two prime powers p^a and p^b with a,b possabilly > > negative. Then gcd(p^a,p^b)=p^(min(a,b)) (*) would be sensible and up > > to units not depending on any choise. It is easy to see that this > > operation is associative and and commutative simply because min(a,b) > > has those properties. > > Now consider the cases (1) a,b>0, (2) a>0,b<0 (3) a,b<0 (and of course > > the more trivial cases with a=0) > > In the case (1) we get with your algorithm gcd(p^a,p^b)/ > > lcm(1,1)=p^(min(a,b)) which agrees with the definition (*) > > In the case (2) a>0 b<0 we get gcd(p^a,1)/lcm(1,p^(-b))=1/(p^(-b))=p^b > > which agrees with (*) since b > In the case (3) we get gcd(1,1)/lcm(p^(-a),p^(-b))=p^(-max(-a,- > > b))=p^min(a,b) which also agrees with (*). > > > Kind regards, > > Maarten Derickx > > > On Feb 11, 11:12 am, Simon King wrote: > > > > Hi Tim, > > > > I just opened #10771 for that purpose. Algorithm is proposed below. > > > > On 11 Feb., 10:55, daly wrote: > > > > > On Fri, 2011-02-11 at 01:49 -0800, Simon King wrote: > > > > > Hi, > > > > > > On 11 Feb., 09:56, Simon King wrote: > > > > > Does anyone have a better idea? Would it be a correct definition if > > > > > one insisted on reduced fractions? > > > > > That's why I was asking for an algorithm for gcd and lcm > > > > in the subdomain. > > > > What do you mean by "subdomain"? Do you mean, an integral domain R as > > > a subdomain of Frac(R)? > > > > > The unit (1) is correct but not by your definition, and > > > > apparently not helpful for the original poster. > > > > Any unit is a correct answer from the point of view of a PID. That's > > > why it makes sense to use the freedom. > > > > Here is an algorithm: > > > > - > > > ASSUMPTIONS: > > > > R is an integral domain, F is its fraction field. > > > gcd and lcm are defined for R > > > > INPUT: > > > > x,y: Elements of F. > > > > Since there is gcd in R, we can assume that x.numerator() and > > > y.denominator() are relatively prime, i.e., x=a/b and y=c/d for > > > a,b,c,d in R, the two fractions being reduced. > > > > OUTPUT: > > > > gcd(x,y) returns gcd(x.numerator(),y.numerator())/ > > > lcm(x.denominator(),y.denominator()) > > > lcm(x,y) returns lcm(x.numerator(),y.numerator())/ > > > gcd(x.denominator(),y.denominator()) > > > - > > > > PROPERTIES: > > > > - Up to units in R, we have gcd(x,y)*lcm(x,y) = gcd(a,c)/ > > > lcm(b,d)*lcm(a,c)/gcd(b,d) = a*c/b*d = x*y > > > > - Moreover, again up to units in R, we have gcd(a/1,b/1) = gcd(a,b)/ > > > lcm(1,1) = gcd(a,b) and lcm(a/1,b/1) = lcm(a,b)/gcd(1,1) = lcm(a,b) > > > > My questions to people that get more sleep than I: > > > Does that algorithm makes sense, mathematically? > > > > At least it seems to me that the gcd-definition is exactly what is > > > used in Maxima: > > > > sage: P. = QQ[] > > > sage: a = (1+x^2)*(1+2*x)^2 > > > sage: b = 1-x^4 > > > sage: c = (1+3*x^2)*(1+2*x) > > > sage: d = 1-x^5 > > > sage: x = a/b > > > sage: y = c/d > > > sage: factor(gcd(maxima(x),maxima(y))) > > > (2*x+1)/((x-1)*(x+1)*(x^4+x^3+x^2+x+1)) > > > sage: factor(gcd(x.numerator(),y.numerator())/ > > > lcm(x.denominator(),y.denominator())) > > > (x - 1)^-1 * (x + 1)^-1 * (x + 1/2) * (x^4 + x^3 + x^2 + x + 1)^-1 > > > > Best regards, > > > Simon -- 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
[sage-devel] Re: sage thoughts
By the way, notice that in http://trac.sagemath.org/sage_trac/ticket/3214 they also added a function "content" which does the old gcd behaviour (i.e. similar to what simon describes). sage: (1/4).content(1/6) 1/12 On Feb 11, 12:15 pm, koffie wrote: > First of all, sorry Simon to have misread you :(. > > To awnser your question. I guess your algorithm makes sense when you > do it with fractions in the reduced form. I will do it only for prime > powers since the general case will follow from this. > Suppose we have two prime powers p^a and p^b with a,b possabilly > negative. Then gcd(p^a,p^b)=p^(min(a,b)) (*) would be sensible and up > to units not depending on any choise. It is easy to see that this > operation is associative and and commutative simply because min(a,b) > has those properties. > Now consider the cases (1) a,b>0, (2) a>0,b<0 (3) a,b<0 (and of course > the more trivial cases with a=0) > In the case (1) we get with your algorithm gcd(p^a,p^b)/ > lcm(1,1)=p^(min(a,b)) which agrees with the definition (*) > In the case (2) a>0 b<0 we get gcd(p^a,1)/lcm(1,p^(-b))=1/(p^(-b))=p^b > which agrees with (*) since b In the case (3) we get gcd(1,1)/lcm(p^(-a),p^(-b))=p^(-max(-a,- > b))=p^min(a,b) which also agrees with (*). > > Kind regards, > Maarten Derickx > > On Feb 11, 11:12 am, Simon King wrote: > > > > > > > > > Hi Tim, > > > I just opened #10771 for that purpose. Algorithm is proposed below. > > > On 11 Feb., 10:55, daly wrote: > > > > On Fri, 2011-02-11 at 01:49 -0800, Simon King wrote: > > > > Hi, > > > > > On 11 Feb., 09:56, Simon King wrote: > > > > Does anyone have a better idea? Would it be a correct definition if > > > > one insisted on reduced fractions? > > > > That's why I was asking for an algorithm for gcd and lcm > > > in the subdomain. > > > What do you mean by "subdomain"? Do you mean, an integral domain R as > > a subdomain of Frac(R)? > > > > The unit (1) is correct but not by your definition, and > > > apparently not helpful for the original poster. > > > Any unit is a correct answer from the point of view of a PID. That's > > why it makes sense to use the freedom. > > > Here is an algorithm: > > > - > > ASSUMPTIONS: > > > R is an integral domain, F is its fraction field. > > gcd and lcm are defined for R > > > INPUT: > > > x,y: Elements of F. > > > Since there is gcd in R, we can assume that x.numerator() and > > y.denominator() are relatively prime, i.e., x=a/b and y=c/d for > > a,b,c,d in R, the two fractions being reduced. > > > OUTPUT: > > > gcd(x,y) returns gcd(x.numerator(),y.numerator())/ > > lcm(x.denominator(),y.denominator()) > > lcm(x,y) returns lcm(x.numerator(),y.numerator())/ > > gcd(x.denominator(),y.denominator()) > > - > > > PROPERTIES: > > > - Up to units in R, we have gcd(x,y)*lcm(x,y) = gcd(a,c)/ > > lcm(b,d)*lcm(a,c)/gcd(b,d) = a*c/b*d = x*y > > > - Moreover, again up to units in R, we have gcd(a/1,b/1) = gcd(a,b)/ > > lcm(1,1) = gcd(a,b) and lcm(a/1,b/1) = lcm(a,b)/gcd(1,1) = lcm(a,b) > > > My questions to people that get more sleep than I: > > Does that algorithm makes sense, mathematically? > > > At least it seems to me that the gcd-definition is exactly what is > > used in Maxima: > > > sage: P. = QQ[] > > sage: a = (1+x^2)*(1+2*x)^2 > > sage: b = 1-x^4 > > sage: c = (1+3*x^2)*(1+2*x) > > sage: d = 1-x^5 > > sage: x = a/b > > sage: y = c/d > > sage: factor(gcd(maxima(x),maxima(y))) > > (2*x+1)/((x-1)*(x+1)*(x^4+x^3+x^2+x+1)) > > sage: factor(gcd(x.numerator(),y.numerator())/ > > lcm(x.denominator(),y.denominator())) > > (x - 1)^-1 * (x + 1)^-1 * (x + 1/2) * (x^4 + x^3 + x^2 + x + 1)^-1 > > > Best regards, > > Simon -- 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
[sage-devel] Re: sage thoughts
First of all, sorry Simon to have misread you :(. To awnser your question. I guess your algorithm makes sense when you do it with fractions in the reduced form. I will do it only for prime powers since the general case will follow from this. Suppose we have two prime powers p^a and p^b with a,b possabilly negative. Then gcd(p^a,p^b)=p^(min(a,b)) (*) would be sensible and up to units not depending on any choise. It is easy to see that this operation is associative and and commutative simply because min(a,b) has those properties. Now consider the cases (1) a,b>0, (2) a>0,b<0 (3) a,b<0 (and of course the more trivial cases with a=0) In the case (1) we get with your algorithm gcd(p^a,p^b)/ lcm(1,1)=p^(min(a,b)) which agrees with the definition (*) In the case (2) a>0 b<0 we get gcd(p^a,1)/lcm(1,p^(-b))=1/(p^(-b))=p^b which agrees with (*) since b wrote: > Hi Tim, > > I just opened #10771 for that purpose. Algorithm is proposed below. > > On 11 Feb., 10:55, daly wrote: > > > On Fri, 2011-02-11 at 01:49 -0800, Simon King wrote: > > > Hi, > > > > On 11 Feb., 09:56, Simon King wrote: > > > Does anyone have a better idea? Would it be a correct definition if > > > one insisted on reduced fractions? > > > That's why I was asking for an algorithm for gcd and lcm > > in the subdomain. > > What do you mean by "subdomain"? Do you mean, an integral domain R as > a subdomain of Frac(R)? > > > The unit (1) is correct but not by your definition, and > > apparently not helpful for the original poster. > > Any unit is a correct answer from the point of view of a PID. That's > why it makes sense to use the freedom. > > Here is an algorithm: > > - > ASSUMPTIONS: > > R is an integral domain, F is its fraction field. > gcd and lcm are defined for R > > INPUT: > > x,y: Elements of F. > > Since there is gcd in R, we can assume that x.numerator() and > y.denominator() are relatively prime, i.e., x=a/b and y=c/d for > a,b,c,d in R, the two fractions being reduced. > > OUTPUT: > > gcd(x,y) returns gcd(x.numerator(),y.numerator())/ > lcm(x.denominator(),y.denominator()) > lcm(x,y) returns lcm(x.numerator(),y.numerator())/ > gcd(x.denominator(),y.denominator()) > - > > PROPERTIES: > > - Up to units in R, we have gcd(x,y)*lcm(x,y) = gcd(a,c)/ > lcm(b,d)*lcm(a,c)/gcd(b,d) = a*c/b*d = x*y > > - Moreover, again up to units in R, we have gcd(a/1,b/1) = gcd(a,b)/ > lcm(1,1) = gcd(a,b) and lcm(a/1,b/1) = lcm(a,b)/gcd(1,1) = lcm(a,b) > > My questions to people that get more sleep than I: > Does that algorithm makes sense, mathematically? > > At least it seems to me that the gcd-definition is exactly what is > used in Maxima: > > sage: P. = QQ[] > sage: a = (1+x^2)*(1+2*x)^2 > sage: b = 1-x^4 > sage: c = (1+3*x^2)*(1+2*x) > sage: d = 1-x^5 > sage: x = a/b > sage: y = c/d > sage: factor(gcd(maxima(x),maxima(y))) > (2*x+1)/((x-1)*(x+1)*(x^4+x^3+x^2+x+1)) > sage: factor(gcd(x.numerator(),y.numerator())/ > lcm(x.denominator(),y.denominator())) > (x - 1)^-1 * (x + 1)^-1 * (x + 1/2) * (x^4 + x^3 + x^2 + x + 1)^-1 > > Best regards, > Simon -- 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
[sage-devel] Re: sage thoughts
On Feb 11, 10:49 am, Simon King wrote: > Hi, > > On 11 Feb., 09:56, Simon King wrote: > > > Well, I had the impression that a couple of people are in favour of > > the following: > > gcd(a/b,c/d) := gcd(a,c)/lcm(b,d) > > lcm(a/b,c/d) := lcm(a,c)/gcd(b,d) > > It just occurs to me that I am incredibly stupid. > > The definition above wouldn't work at all, it isn't even well-defined. > Just replace gcd(1/4,1/6) by gcd(3/12,9/54). You obtain gcd(1,1)/ > lcm(4,6) = 1/12, but gcd(3,9)/lcm(12,54) = 1/36. > > Does anyone have a better idea? Would it be a correct definition if > one insisted on reduced fractions? Mathematically, if K is the fraction field of a PID R, then you should first reduce both fractions to a common denominator r1/d and r2/d. Then: gcd(r1/d, r2/d) = gcd(r1,r2)/d lcm(r1/d, r2/d) = lcm(r1, r2)/d This approach will be independent on the representation of the fractions (up to units in R). Although a direct translation of this idea seems inefficient. -- 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
[sage-devel] Re: sage thoughts
Hi Tim, I just opened #10771 for that purpose. Algorithm is proposed below. On 11 Feb., 10:55, daly wrote: > On Fri, 2011-02-11 at 01:49 -0800, Simon King wrote: > > Hi, > > > On 11 Feb., 09:56, Simon King wrote: > > Does anyone have a better idea? Would it be a correct definition if > > one insisted on reduced fractions? > > > That's why I was asking for an algorithm for gcd and lcm > in the subdomain. What do you mean by "subdomain"? Do you mean, an integral domain R as a subdomain of Frac(R)? > The unit (1) is correct but not by your definition, and > apparently not helpful for the original poster. Any unit is a correct answer from the point of view of a PID. That's why it makes sense to use the freedom. Here is an algorithm: - ASSUMPTIONS: R is an integral domain, F is its fraction field. gcd and lcm are defined for R INPUT: x,y: Elements of F. Since there is gcd in R, we can assume that x.numerator() and y.denominator() are relatively prime, i.e., x=a/b and y=c/d for a,b,c,d in R, the two fractions being reduced. OUTPUT: gcd(x,y) returns gcd(x.numerator(),y.numerator())/ lcm(x.denominator(),y.denominator()) lcm(x,y) returns lcm(x.numerator(),y.numerator())/ gcd(x.denominator(),y.denominator()) - PROPERTIES: - Up to units in R, we have gcd(x,y)*lcm(x,y) = gcd(a,c)/ lcm(b,d)*lcm(a,c)/gcd(b,d) = a*c/b*d = x*y - Moreover, again up to units in R, we have gcd(a/1,b/1) = gcd(a,b)/ lcm(1,1) = gcd(a,b) and lcm(a/1,b/1) = lcm(a,b)/gcd(1,1) = lcm(a,b) My questions to people that get more sleep than I: Does that algorithm makes sense, mathematically? At least it seems to me that the gcd-definition is exactly what is used in Maxima: sage: P. = QQ[] sage: a = (1+x^2)*(1+2*x)^2 sage: b = 1-x^4 sage: c = (1+3*x^2)*(1+2*x) sage: d = 1-x^5 sage: x = a/b sage: y = c/d sage: factor(gcd(maxima(x),maxima(y))) (2*x+1)/((x-1)*(x+1)*(x^4+x^3+x^2+x+1)) sage: factor(gcd(x.numerator(),y.numerator())/ lcm(x.denominator(),y.denominator())) (x - 1)^-1 * (x + 1)^-1 * (x + 1/2) * (x^4 + x^3 + x^2 + x + 1)^-1 Best regards, Simon -- 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
Re: [sage-devel] Re: sage thoughts
On Fri, 2011-02-11 at 01:49 -0800, Simon King wrote: > Hi, > > On 11 Feb., 09:56, Simon King wrote: > > Well, I had the impression that a couple of people are in favour of > > the following: > > gcd(a/b,c/d) := gcd(a,c)/lcm(b,d) > > lcm(a/b,c/d) := lcm(a,c)/gcd(b,d) > > It just occurs to me that I am incredibly stupid. > > The definition above wouldn't work at all, it isn't even well-defined. > Just replace gcd(1/4,1/6) by gcd(3/12,9/54). You obtain gcd(1,1)/ > lcm(4,6) = 1/12, but gcd(3,9)/lcm(12,54) = 1/36. > > Does anyone have a better idea? Would it be a correct definition if > one insisted on reduced fractions? > > Cheers, > Simon > That's why I was asking for an algorithm for gcd and lcm in the subdomain. I'm not sure what answer is expected. The unit (1) is correct but not by your definition, and apparently not helpful for the original poster. Tim Daly -- 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
[sage-devel] Re: sage thoughts
Hi, On 11 Feb., 09:56, Simon King wrote: > Well, I had the impression that a couple of people are in favour of > the following: > gcd(a/b,c/d) := gcd(a,c)/lcm(b,d) > lcm(a/b,c/d) := lcm(a,c)/gcd(b,d) It just occurs to me that I am incredibly stupid. The definition above wouldn't work at all, it isn't even well-defined. Just replace gcd(1/4,1/6) by gcd(3/12,9/54). You obtain gcd(1,1)/ lcm(4,6) = 1/12, but gcd(3,9)/lcm(12,54) = 1/36. Does anyone have a better idea? Would it be a correct definition if one insisted on reduced fractions? Cheers, Simon -- 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
[sage-devel] Re: sage thoughts
PS: On 11 Feb., 09:56, Simon King wrote: > Hi Tim, > > On 11 Feb., 08:06, daly wrote: > > > ... > > Can you suggest an algorithm to implement this? > > Is there an agreed-upon answer (i.e., not 42?) > > Well, I had the impression that a couple of people are in favour of > the following: Or was your question: *How* to implement it? I supposed that the functions gcd(a,b) and lcd(a,b) should first coerce a and b into a common parent, P. So, suppose by now that a and b both belong to P. Currently, gcd(a,b,c...) (a,b,c,... not in ZZ or long or int) uses sage.arith.__GCD_sequence, which then relies on the gcd-methods of the elements. Fraction fields can be easily detected: They belong to the category QuotientFields(). Hence, it would be reasonable to implement gcd- and lcm-methods for fraction field elements as ElementMethods of QuotientFields(). Of course, the custom gcd/lcm-methods that we currently have for the rationals (and maybe for some other fraction fields) should be removed. If one implements gcd/lcm as ElementMethods of QuotientFields(), then gcd/lcm for elements of Frac(QQ[x]) would work out of the box. Best regards, Simon -- 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
[sage-devel] Re: sage thoughts
Hi Tim, On 11 Feb., 08:06, daly wrote: > ... > Can you suggest an algorithm to implement this? > Is there an agreed-upon answer (i.e., not 42?) Well, I had the impression that a couple of people are in favour of the following: gcd(a/b,c/d) := gcd(a,c)/lcm(b,d) lcm(a/b,c/d) := lcm(a,c)/gcd(b,d) It seems that this definition is already used in Maxima: sage: a=maxima(3/4) sage: b=maxima(5/6) sage: gcd(a,b) 1/12 Moreover, as one can easily see, the property gcd(x,y)*lcm(x,y)=x*y is preserved by that definition. In addition, if F is the fraction field of R and a,b are elements of R, then gcd(F(a),F(b))==gcd(a,b) and lcm(F(a),F(b))==lcm(a,b). So, that's the rationale. Best regards, Simon -- 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
Re: [sage-devel] Re: sage thoughts
On Thu, 2011-02-10 at 22:57 -0800, Simon King wrote: > Hi Bruno! > > On 11 Feb., 01:37, Bruno Le Floch wrote: > > > You could have both consistencies. That depends on how you define gcd > > > and lcm: > > > > > - Quotient fields as described by Bruno. > > > - Fields: zero if both elements are zero. A non-zero element > > > otherwise (most fields would choose 1 here). > > > - PID: a generator of the corresponding ideal. > > > > I don't see how this brings in both consistencies. Algebraic > > consistency requires gcd and lcm on QQ to have different outputs > > depending on whether QQ is seen a Field, a PID, a Quotient Field... Is > > there a clear way for the user to indicate "which QQ" he wants? > > I am sorry for the FUD that I spread in my earlier posts. > > Meanwhile people convinced me that it is indeed possible to have both > consistencies. The point is: In a PID, "the" lcm of a and b is only > defined up to a unit - it is only required that lcm(a,b) generates the > intersection of the ideals generated by a and b. My mistake was: 1 is > certainly "the" canonical choice of a generator of the ideal \cap > (a,b non-zero); but that does not mean that it is the best return > value of lcm(a,b)! > > So, if lcm(a,b) for a,b non-zero returns *any* non-zero element, then > "consistency from the category point of view" is granted - > lcm(1/2,1/4) = 42 is not wrong in QQ. > > But that freedom means: We can *in addition* achieve consistency with > respect to sub-structures, namely by seeing QQ as a quotient field. > > Cheers, > Simon > Can you suggest an algorithm to implement this? Is there an agreed-upon answer (i.e., not 42?) Tim Daly -- 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
[sage-devel] Re: sage thoughts
Hi Bruno! On 11 Feb., 01:37, Bruno Le Floch wrote: > > You could have both consistencies. That depends on how you define gcd > > and lcm: > > > - Quotient fields as described by Bruno. > > - Fields: zero if both elements are zero. A non-zero element > > otherwise (most fields would choose 1 here). > > - PID: a generator of the corresponding ideal. > > I don't see how this brings in both consistencies. Algebraic > consistency requires gcd and lcm on QQ to have different outputs > depending on whether QQ is seen a Field, a PID, a Quotient Field... Is > there a clear way for the user to indicate "which QQ" he wants? I am sorry for the FUD that I spread in my earlier posts. Meanwhile people convinced me that it is indeed possible to have both consistencies. The point is: In a PID, "the" lcm of a and b is only defined up to a unit - it is only required that lcm(a,b) generates the intersection of the ideals generated by a and b. My mistake was: 1 is certainly "the" canonical choice of a generator of the ideal \cap (a,b non-zero); but that does not mean that it is the best return value of lcm(a,b)! So, if lcm(a,b) for a,b non-zero returns *any* non-zero element, then "consistency from the category point of view" is granted - lcm(1/2,1/4) = 42 is not wrong in QQ. But that freedom means: We can *in addition* achieve consistency with respect to sub-structures, namely by seeing QQ as a quotient field. Cheers, Simon -- 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
Re: [sage-devel] Re: sage thoughts
>> Let me phrase it like this: There are different interpretations of the >> term "consistent". @Simon: You are right to distinguish the two kinds of consistencies. And I can understand that sometimes it is preferable to have the algebraic consistency. I tend to care about elements of the objects more than the objects of the category (i.e. individual rational numbers rather than the field/PID/quotient field QQ), and thus I tend towards subring consistency. > You could have both consistencies. That depends on how you define gcd > and lcm: > > - Quotient fields as described by Bruno. > - Fields: zero if both elements are zero. A non-zero element > otherwise (most fields would choose 1 here). > - PID: a generator of the corresponding ideal. I don't see how this brings in both consistencies. Algebraic consistency requires gcd and lcm on QQ to have different outputs depending on whether QQ is seen a Field, a PID, a Quotient Field... Is there a clear way for the user to indicate "which QQ" he wants? Or we could have (I don't really know how this is done ;-) ) lcm(10/21, 14/15, type="PID") = 1 lcm(10/21, 14/15, type="Field") = 1 lcm(10/21, 15/14, type="quotient-of-ZZ") = 30/7 I doubt that the "field" version is useful at all: the lcm is basically always 1 (except when one of the arguments is zero). lcm and gcd should only be defined for PIDs, where they are interesting (or for factorization rings? I can't remember my undergrad). > http://groups.google.com/group/sage-devel/browse_thread/thread/12524b18d2325633/7b8af907c3c45c8b?lnk=gst&q=gcd+and+lcm+for+field+elements#7b8af907c3c45c8b Interesting read, thanks. -- 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
Re: [sage-devel] Re: sage thoughts
> Well, I used to use gcd for obtaining the primitive integral vector > with a specified rational direction. My concern on Trac 3214 was that > gcd(a1, ..., ak) depended on the order of arguments and I wanted it to > be fixed. The eventual solution was to agree that gcd as the "greatest > common divisor" does not really make much sense for fields, but > instead of raising an exception it can just return 1. This meant that > I cannot use it for my original purpose (not a big deal - it is easy > to do more directly), but I think that it was quite a sensible > decision: > 1) I don't recall seeing gcd of rational numbers in any book or paper > 2) there is clearly no natural extension of this notion from ZZ to QQ > 3) the name itself indeed is very strange applied to fields. > > So I personally think that any kind of gcd/lcm combinations of > numerators/denominators of rational numbers should have some other > more appropriate names, since making up some conventions for gcd is > potentially dangerous and may make code using it harder to understand > if a reader thinks of gcd differently than the original author... > I agree that it's a little bit awkward, but I think that we should go with the maxima/pari/mathematica convention. * The issue the OP brought up, where gcd silently gave nonsensical issues when one of the "integers" accidentally got divided by 1 (or you used / instead of // in a case where you know one is divisible by the other) is compelling. * The gcd should be a generator of the fractional ideal generated by the inputs; the lcm of the intersection as long as that fractional ideal is principal (if we're in a non-PID or fraction field of a non-PID I think we should raise an error). There's an ambiguity about units; we should make a consistent choice between the PID and its fraction field. In the case of integers and rationals, this means we choose the results to be positive and have the relation gcd(x,y)*lcm(x,y) = abs(x,y) as John pointed out. David -- 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
[sage-devel] Re: sage thoughts
On Feb 10, 11:01 am, William Stein wrote: > On Thu, Feb 10, 2011 at 9:55 AM, William Stein wrote: > > [... gcd stuff ...] > > It seems like nobody explained how the current gcd definition got > included. It's from a patch to rational.pyx from Alex Ghitza (who I > cc'd) that did this: > > - d = self.denom()*other.denom() > - self_d = self.numer()*other.denom() > - other_d = other.numer()*self.denom() > - return self_d.gcd(other_d) / d > + if self == 0 and other == 0: > + return Rational(0) > + else: > + return Rational(1) > > This was from trac 3214 "uniformise the behaviour of gcd for rational > numbers": > > http://trac.sagemath.org/sage_trac/ticket/3214 > > which was reported by Andrey Novoseltsev. > > So if Andrey or Alex cared so much, they may want to pipe up. > > This thread is at least: > > http://groups.google.com/group/sage-devel/browse_thread/thread/cd0558... > > William Well, I used to use gcd for obtaining the primitive integral vector with a specified rational direction. My concern on Trac 3214 was that gcd(a1, ..., ak) depended on the order of arguments and I wanted it to be fixed. The eventual solution was to agree that gcd as the "greatest common divisor" does not really make much sense for fields, but instead of raising an exception it can just return 1. This meant that I cannot use it for my original purpose (not a big deal - it is easy to do more directly), but I think that it was quite a sensible decision: 1) I don't recall seeing gcd of rational numbers in any book or paper 2) there is clearly no natural extension of this notion from ZZ to QQ 3) the name itself indeed is very strange applied to fields. So I personally think that any kind of gcd/lcm combinations of numerators/denominators of rational numbers should have some other more appropriate names, since making up some conventions for gcd is potentially dangerous and may make code using it harder to understand if a reader thinks of gcd differently than the original author... Thank you, Andrey -- 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
Re: [sage-devel] Re: sage thoughts
I have not taken the time to read this whole thread, but here goes anyway: The distinction is between ideals of Q (which are of course only (0) and (1)) and sub-Z-modules of Q, a.k.a. fractional ideals (since in the generalization to number fields K we (ab)use the terminology "ideal of K" to mean "fractional ideal of K" which is the same as "OK_submodule of K (of maximal rank)". Every f.g. Z-submodule of Q is cyclic, and instead of the current behaviour of gcd(x,y) for rationals (which is to give the generator of the Q-ideal generated by x and y) the old -- and perhaps desired -- behaviour is to give the generator of the Z-module generated by x and y. The latter is, of course, unique up to sign. It's the same as Simon's generator of the sum of the Z-submodules generated by x and by y. And then lcm(x,y) is the genrator of their intersection. This way, both gcd(x,y) and lcm(x,y) are positive rationals (or 0 but not when x and y are nonzero). And we have gcd(x,y)*lcm(x,y) = abs(x*y) which I think is a better convention for when x and/or y are negative than deciding to make one of the gcd and the lcm negative. John On Thu, Feb 10, 2011 at 10:01 AM, William Stein wrote: > On Thu, Feb 10, 2011 at 9:55 AM, William Stein wrote: >> [... gcd stuff ...] > > It seems like nobody explained how the current gcd definition got > included. It's from a patch to rational.pyx from Alex Ghitza (who I > cc'd) that did this: > > - d = self.denom()*other.denom() > - self_d = self.numer()*other.denom() > - other_d = other.numer()*self.denom() > - return self_d.gcd(other_d) / d > + if self == 0 and other == 0: > + return Rational(0) > + else: > + return Rational(1) > > > This was from trac 3214 "uniformise the behaviour of gcd for rational > numbers": > > http://trac.sagemath.org/sage_trac/ticket/3214 > > which was reported by Andrey Novoseltsev. > > So if Andrey or Alex cared so much, they may want to pipe up. > > This thread is at least: > > > http://groups.google.com/group/sage-devel/browse_thread/thread/cd05585cf395b3a0/160c549d6bdc8867#160c549d6bdc8867 > > William > > -- > 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 > -- 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
Re: [sage-devel] Re: sage thoughts
On Thu, Feb 10, 2011 at 9:55 AM, William Stein wrote: > [... gcd stuff ...] It seems like nobody explained how the current gcd definition got included. It's from a patch to rational.pyx from Alex Ghitza (who I cc'd) that did this: -d = self.denom()*other.denom() -self_d = self.numer()*other.denom() -other_d = other.numer()*self.denom() -return self_d.gcd(other_d) / d +if self == 0 and other == 0: +return Rational(0) +else: +return Rational(1) This was from trac 3214 "uniformise the behaviour of gcd for rational numbers": http://trac.sagemath.org/sage_trac/ticket/3214 which was reported by Andrey Novoseltsev. So if Andrey or Alex cared so much, they may want to pipe up. This thread is at least: http://groups.google.com/group/sage-devel/browse_thread/thread/cd05585cf395b3a0/160c549d6bdc8867#160c549d6bdc8867 William -- 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
Re: [sage-devel] Re: sage thoughts
On Thu, Feb 10, 2011 at 9:49 AM, Simon King wrote:
> Hi Luis,
>
> On 10 Feb., 17:48, luisfe wrote:
>> ...
>> You could have both consistencies. That depends on how you define gcd
>> and lcm:
>>
>> - Quotient fields as described by Bruno.
>> - Fields: zero if both elements are zero. A non-zero element
>> otherwise (most fields would choose 1 here).
>> - PID: a generator of the corresponding ideal.
>>
>> This is not trivial. For instance Fields do not have a default gcd/lcm
>> method. I asked in sage-devel about some time ago about sensible
>> approaches
>> here.http://groups.google.com/group/sage-devel/browse_thread/thread/12524b...
>
> Yes, on my way home, I thought that perhaps "lcm(4/1,2)=1" is not so
> obvious as I first found. lcm(a,b) has to be a generator of the
> intersection of the ideals generated by a and b. Of course, 1 is a
> quite canonical generator for the only non-zero ideal in a field --
> simply because any field has a 1.
>
> But any other non-zero element is fine as well, in a field. So, after
> all, defining lcm(a/b,c/d)=lcm(a,c)/gcd(b,d) for fraction fields of
> principal ideal domains makes more sense than I originally thought.
> And with gcd(a/b,c/d)=gcd(a,c)/lcm(b,d), we would indeed have
> gcd(x,y)*lcm(x,y)=x*y.
>
> According to Richard Fateman, that definition seems to be be used in
> Maxima ("in maxima, gcd(1/4,1/6) is 1/12, lcm is 1/2"). But
> according to Tim Daly, Axiom returns 1 as lcm of any two rationals.
> So, should Sage stay on the side of Axiom or switch to the side of
> Maxima?
It should switch to the side of Maxima/Pari/Mathematica/etc. in this.
-- William
--
William Stein
Professor of Mathematics
University of Washington
http://wstein.org
--
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
[sage-devel] Re: sage thoughts
Hi Luis,
On 10 Feb., 17:48, luisfe wrote:
> ...
> You could have both consistencies. That depends on how you define gcd
> and lcm:
>
> - Quotient fields as described by Bruno.
> - Fields: zero if both elements are zero. A non-zero element
> otherwise (most fields would choose 1 here).
> - PID: a generator of the corresponding ideal.
>
> This is not trivial. For instance Fields do not have a default gcd/lcm
> method. I asked in sage-devel about some time ago about sensible
> approaches
> here.http://groups.google.com/group/sage-devel/browse_thread/thread/12524b...
Yes, on my way home, I thought that perhaps "lcm(4/1,2)=1" is not so
obvious as I first found. lcm(a,b) has to be a generator of the
intersection of the ideals generated by a and b. Of course, 1 is a
quite canonical generator for the only non-zero ideal in a field --
simply because any field has a 1.
But any other non-zero element is fine as well, in a field. So, after
all, defining lcm(a/b,c/d)=lcm(a,c)/gcd(b,d) for fraction fields of
principal ideal domains makes more sense than I originally thought.
And with gcd(a/b,c/d)=gcd(a,c)/lcm(b,d), we would indeed have
gcd(x,y)*lcm(x,y)=x*y.
According to Richard Fateman, that definition seems to be be used in
Maxima ("in maxima, gcd(1/4,1/6) is 1/12, lcm is 1/2"). But
according to Tim Daly, Axiom returns 1 as lcm of any two rationals.
So, should Sage stay on the side of Axiom or switch to the side of
Maxima?
Cheers,
Simon
--
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
[sage-devel] Re: sage thoughts
On Feb 10, 2:10 pm, Simon King wrote: > Hi Bruno > > Let me phrase it like this: There are different interpretations of the > term "consistent". > > On the one hand, one could mean "consistency with respect to sub- > structures": Let S be a sub-ring of a ring R; gcd_R is consistent with > gcd_S <=> gcd_R(x,y)==gcd_S(x,y) for all x,y in S. As you have > pointed out, there is a way to define the gcd of a quotient field > consistent with the gcd of the underlying ring. > > On the other hand, one could mean "consistent as algebraic notion" (or > perhaps "consistent with respect to categories"). Let me elaborate: > One could argue that there is a partial map "gcd_*" that assigns to > any object R of Rings() a function gcd_R that accepts two arguments > (namely elements of R) returning elements of R. > Now, it is possible to consider the same object R as object of > different categories. For example, we have > sage: QQ in QuotientFields() > True > sage: QQ in Fields() > True > sage: QQ in PrincipalIdealDomains() > True > > So, it makes sense to call gcd_* "consistent as algebraic notion", if > gcd_R for R object of some category C is the same as gcd_R for the > same R considered as an object of a different category C'. > > What you propose would be "consistent with respect to > subrings" ( gcd(QQ(m),QQ(n))==gcd(m,n) for m,n in ZZ), but it would be > "inconsistent as algebraic notion", as gcd(a/b,c/d) would depend on > whether we consider QQ as a quotient field or as a principal ideal > domain. > > I strongly prefer to work with things that are consistent as algebraic > notions. You could have both consistencies. That depends on how you define gcd and lcm: - Quotient fields as described by Bruno. - Fields: zero if both elements are zero. A non-zero element otherwise (most fields would choose 1 here). - PID: a generator of the corresponding ideal. This is not trivial. For instance Fields do not have a default gcd/lcm method. I asked in sage-devel about some time ago about sensible approaches here. http://groups.google.com/group/sage-devel/browse_thread/thread/12524b18d2325633/7b8af907c3c45c8b?lnk=gst&q=gcd+and+lcm+for+field+elements#7b8af907c3c45c8b -- 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
[sage-devel] Re: sage thoughts
Hi Bruno On 10 Feb., 12:26, Bruno Le Floch wrote: > True. But in the case of Q (and more generally in the case of the > quotient field of a (principal?) ring), we can be consistent with the > ring of integers, without any guess-work. Sure. This could be one of the definitions I mentioned: lcm(a/b,c/d) = lcm(a,c)/gcd(b,d). But: Would it be a wise idea to have a totally different definition for fields and for quotient fields? Let me phrase it like this: There are different interpretations of the term "consistent". On the one hand, one could mean "consistency with respect to sub- structures": Let S be a sub-ring of a ring R; gcd_R is consistent with gcd_S <=> gcd_R(x,y)==gcd_S(x,y) for all x,y in S. As you have pointed out, there is a way to define the gcd of a quotient field consistent with the gcd of the underlying ring. On the other hand, one could mean "consistent as algebraic notion" (or perhaps "consistent with respect to categories"). Let me elaborate: One could argue that there is a partial map "gcd_*" that assigns to any object R of Rings() a function gcd_R that accepts two arguments (namely elements of R) returning elements of R. Now, it is possible to consider the same object R as object of different categories. For example, we have sage: QQ in QuotientFields() True sage: QQ in Fields() True sage: QQ in PrincipalIdealDomains() True So, it makes sense to call gcd_* "consistent as algebraic notion", if gcd_R for R object of some category C is the same as gcd_R for the same R considered as an object of a different category C'. What you propose would be "consistent with respect to subrings" ( gcd(QQ(m),QQ(n))==gcd(m,n) for m,n in ZZ), but it would be "inconsistent as algebraic notion", as gcd(a/b,c/d) would depend on whether we consider QQ as a quotient field or as a principal ideal domain. I strongly prefer to work with things that are consistent as algebraic notions. Best regards, Simon -- 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
Re: [sage-devel] Re: sage thoughts
Hi all, > So, a coercion from QQ to ZZ would presumably be a morphism from QQ to > ZZ in the category of unital rings - which doesn't exist. Agreed. > So, I think it is by far better to have a consistent notion than to > have to *guess* whether a user really means the integer 2 if s/he > write 4/2 (which in the first place is a rational, not an integer). > Bugs that are result of guesswork are the most ugly, IMHO. True. But in the case of Q (and more generally in the case of the quotient field of a (principal?) ring), we can be consistent with the ring of integers, without any guess-work. (*) This is a white lie (see below). Every rational number has a unique(*) form Product(p^(a_p), p prime) for some integer powers a_p. The rational is an integer iff all a_p are non-negative. In that case, gcd(Product(p^(a_p)), Product(p^(b_p))) = Product(p^(min(a_p,b_p))) and lcm is defined with max(a_p,b_p). But actually this definition does not rely at all on the fact that the a_p and b_p are positive. So we have a definition of the gcd and lcm for free on the quotient field of any (principal?) ring. Then, gcd(x,y).lcm(x,y)=x.y; the notion reduces to the one for integers, etc. This definition amounts to the definition of lcm(x,y) as the smallest integer multiple of x which is also an integer multiple of y. (*) In fact, there is the issue of the sign, or more generally units (elements that are invertible in the ring (here, ZZ) ). For this, there has to be some arbitrariness on the sign of gcd and lcm of negative numbers. Note that for RDF and its colleagues, this does not apply (since they are not the quotient field of any sensible ring), and we should stick with the definition gcd(x,y)=1, however much x and y look like integers. Regards, Bruno -- 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
[sage-devel] Re: sage thoughts
Hi Doug! On 10 Feb., 09:40, "D. S. McNeil" wrote: > @Simon King: as you note, there are multiple ways to extend the > concept of gcds and lcms to the rationals. In such a situation, it > would seem that two minimal things you would like would be (1) to > reduce to the integer case for integer values, and (2) to maintain > some nice properties so that the names "gcd" and "lcm" still fit. > Given some definition satisfying (1), coercing down to integers from > rationals isn't much of a problem, ... There is no "coercing down to integers from rationals". One important property of a coercion map is that it is a map, in contrast to a partial map. Actually, it even is a morphism. So, a coercion from QQ to ZZ would presumably be a morphism from QQ to ZZ in the category of unital rings - which doesn't exist. When I wrote "lcm(2/1,4) should not raise an error but use coercion", I meant of course that the integer 4 should be coerced into the common parent of 2/1 and 4, which is the rational field. > Choosing any definition > which doesn't reduce to the integer one, as is currently done, seems > problematic to me as a design decision, given that it's far more > likely to be used that way in error than it is that someone decided to > obfuscate "1" by writing it as gcd(some rational, some integer). No, I think you are mistaken. If you work with a,b rational or, worse, real numbers, then it is very highly unlikely that a and b *are* integers if they happen to seem like integers. Just think of rounding errors. This is another reason why "coercing down to the integers" won't make sense: It is highly unlikely that 1.0 really is the integer number 1. So, I think it is by far better to have a consistent notion than to have to *guess* whether a user really means the integer 2 if s/he write 4/2 (which in the first place is a rational, not an integer). Bugs that are result of guesswork are the most ugly, IMHO. Cheers, Simon -- 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
Re: [sage-devel] Re: sage thoughts
@rjf: > I don't know exactly how this came up, but if 2/1 is in a different domain > (rational) from 2, (integer), then gcd should probably be 1, since any > non-zero rational number divides any other, and one commonly uses the > positive "unit" 1 for such a case. One also commonly uses the content, as it provides information and is likely to be useful, whereas setting the "gcd" to 1 doesn't, really: I could simply use 1 directly instead. In practice: Mma and Pari both have my preferred behaviour, gcd(2/1, 4) = 2, gcd(2/3, 4/3) = 2/3, lcm(2/1, 4) = 4, lcm(2/3, 4/3) = 4/3. Maple gives instead gcd(2/1, 4) = 2, gcd(2/3, 4/3) = 1, lcm(2/1, 4) = 4, lcm(2/3, 4/3) = 8/9, which I'd also be okay with. Let a thousand flowers bloom! I don't know if Maxima has an lcm function, but at least gcd(2/1,4) = 2 and gcd(2/3, 4/3) = 2/3. Magma barfs at rational input, which is defensible. (Maybe there's another gcd which doesn't, not sure.) This would frustrate me, but at least avoids errors such as the one that got me started on this subject in the first place. Sage, by comparison, gives 1, 1, error (or 4 if you use 4/1), 4/3, which doesn't seem nearly as useful as either the Mma/Pari or Maple behaviour. They choose different conventions, but both make sense to me, and convince me that I'm not crazy. :^) It's worth emphasizing that Sage __already gives the Pari answers__ for the cases of (rational, rational) and (integer, rational) argument to lcm (and has a Rational.content implementation); I'd be interested in understanding why gcd should be different. > Really, the issue is much broader. for example, do you also want to treat the > complex number > 1+0*i the same as 1? do you want to treat the floating point number 1.0 the > same as 1? As the use cases seem far less common, I have no issues requiring explicit coercions for symbolic complex numbers. I certainly don't have problems requiring explicit coercions for finite-precision types, and have no opinions about any of the thousand other possibilities. @Simon King: as you note, there are multiple ways to extend the concept of gcds and lcms to the rationals. In such a situation, it would seem that two minimal things you would like would be (1) to reduce to the integer case for integer values, and (2) to maintain some nice properties so that the names "gcd" and "lcm" still fit. Given some definition satisfying (1), coercing down to integers from rationals isn't much of a problem, because the values will be the same. Pari, Mma, and Maple all do this in a way which makes sense, and Sage already halfway does it (with lcm). Choosing any definition which doesn't reduce to the integer one, as is currently done, seems problematic to me as a design decision, given that it's far more likely to be used that way in error than it is that someone decided to obfuscate "1" by writing it as gcd(some rational, some integer). > So, is QQ reasonably covered by "Wherever possible"?? I doubt. > Note that currently we have > sage: gcd(-2,1) > 1 > sage: lcm(-2,1) > 2 > So, gcd(x,y)*lcm(x,y) == x*y doesn't even hold in ZZ. Why should it hold in > QQ? I'd return different signatures, myself, but even if you don't agree, the property can easily hold as-is for Z+ and Q+. Why is "for positive integers and rationals" not an acceptable content for "wherever possible"? (I'm a physicist, not a mathematician, so I'm sometimes physics-sloppy when writing: what should I have written instead of "wherever possible" as shorthand for something like "on the largest region containing the regime of interest while preserving the relationships under discussion"?) Doug -- Department of Earth Sciences University of Hong Kong -- 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
[sage-devel] Re: sage thoughts
PPS: On 10 Feb., 08:34, Simon King wrote: > ... > But I think the problem here is not coercion but the "right" (or at > least reasonable) choice of a definition. What would textbooks say? I should add: I do believe that the choice is already made and the choice is fine (see Tim's and William's posts above). Only, lcm(2/1,4) should not raise an error but use coercion (similar to what gcd(2/1,4) does). Best regards, Simon -- 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
[sage-devel] Re: sage thoughts
PS: On 9 Feb., 15:57, luisfe wrote: > There is also something wrong with lcm for rationals > > sage: a = 2/3 # rational > sage: b = 1 # integer > sage: gcd(a,b) > 1 > sage: lcm(a,b) > ... > TypeError I would agree that this is a bug. I think it would be just consequent to first coerce a and b before computing their gcd or lcm. > Also, I am little surprised about the definition of lcm here. I would > expect, maybe naively, that the lcm of 1/3 and 1/2 is 1/6. That is: > lcm(numerators) / lcm(denominators) > Although the current behavior is well documented. Thinking a little > bit the lcm seems to be defined as the smallest 'integer' multiple of > 1/3 and 1/2. The generator of the intersection of the ZZ-modules > ZZ[1/3] and ZZ[1/2]. So it makes sense... Ah, yet another definition with yet another answer for the rationals. So, now we have at least six different ways to extend the common notion of lcm from ZZ to QQ: lcm(1/4,1/6) = 0 (infimum over positive multiples) lcm(1/4,1/6) = 1/4 (infimum over positive multiples with factor at least one) lcm(1/4,1/6) = 1/12 (lcm(numerators) / lcm(denominators)) lcm(1/4,1/6) = 1/2 (infimum over positive multiples with integer factor) lcm(1/4,1/6) = 1 (minimal positive multiple that is an integer) lcm(1/4,1/6) = 1/2 (lcm(numerators)/gcd(denominators)) ... [add further definitions here] Tough choice! At least, the last one has the property gcd(x,y)*lcm(x,y)==x*y, assuming that we also define gcd(a/b,c/d) = gcd(a,c)/lcm(b,d). I agree with Richard Fateman that in this case one shouldn't simply decide by counting "+1" (isn't there a board for that purpose?). But I think the problem here is not coercion but the "right" (or at least reasonable) choice of a definition. What would textbooks say? Cheers, Simon -- 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
[sage-devel] Re: sage thoughts
Hi all!
On 9 Feb., 15:57, luisfe wrote:
> On Feb 9, 9:46 am, "D. S. McNeil" wrote:
>
> > >> (1) gcd is broken. http://trac.sagemath.org/sage_trac/ticket/10459
> > [..]
> > > I'm personally OK either way with this.
>
> > IMO a*b = gcd(a,b)*lcm(a,b) should be maintained wherever possible.
What does "Wherever possible" mean in an ordered ring, R? In
particular, is it possible for R=QQ? Or even for R=ZZ?
If I am not mistaken, lcm(x,y) could be defined as
inf {x*m | m in R, x*m>0, there is n in R with x*m==y*n}(1)
At least, that definition matches the situation in ZZ (note that
lcm(-2,-2) = 2).
Or is there any reason to have a minimum rather than an infimum?
On the other hand, what is the notion of a "multiple" of x? Is it
simply x*m for any m in R? Or is it rather x*m for any abs(m)>=1 in R?
In that case, definition (1) above became
inf {x*m | m in R, abs(m)>=1, x*m>0, there is n in R with abs(n)>=1
and x*m==y*n} (2)
Again, it's one definition that matches the situation in ZZ.
Now, consider R=QQ.
According to definition (1), the least common multiple of 1/1 and 1/1
is: Zero! 'Cause any positive rational is a multiple of 1/1, and the
infimum is zero.
But according to definition (2), the least common multiple of 1/1 and
1/1 is: 1/1.
Perhaps there are other possible ways to extend the notion of lcm from
ZZ to any ordered ring. I could imagine that different textbooks use
slightly different ways of defining lcm and gcd in ZZ, extending to QQ
differently.
So, is QQ reasonably covered by "Wherever possible"?? I doubt.
Note that currently we have
sage: gcd(-2,1)
1
sage: lcm(-2,1)
2
So, gcd(x,y)*lcm(x,y) == x*y doesn't even hold in ZZ. Why should it
hold in QQ?
Cheers,
Simon
--
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
Re: [sage-devel] Re: sage thoughts
On Wed, Feb 9, 2011 at 10:46 PM, daly wrote: > On Wed, 2011-02-09 at 22:18 -0800, rjf wrote: >> You say, >> > gcd(2/1,4) returns 1 "for simplicity" (!), because 2/1 is a rational. >> > This is shockingly silly. >> >> I don't know exactly how this came up, but if 2/1 is in a different >> domain (rational) >> from 2, (integer), then gcd should probably be 1, since any non- >> zero >> rational number divides any other, and one commonly uses the positive >> "unit" 1 for >> such a case. You could argue that since you can coerce 2/1, you >> should. >> >> That's sometimes OK, but not always. >> >> Really, the issue is much broader. for example, do you also want to >> treat the complex number >> 1+0*i the same as 1? do you want to treat the floating point number >> 1.0 the same as 1? >> >> What about 1X1 matrices? >> >> Is 1^0 the same as 1^0.0 or 1.0^0 or 1.0^0.0? Do you perhaps wish >> to consider/dismiss >> the existence of number systems with signed zeros (IEEE floating-point >> standard) on the >> grounds that -0 = +0, [true, for numerical comparison] and therefore >> there should be >> only a single zero? >> >> While I don't know the exact formulation of this GCD problem, the >> issue of >> implicit coercion is one of the troubling sore spots in a system >> design, and should not >> be decided by counting up casual +1 votes. >> >> I think the Axiom people might have thought more about it than others. >> > > It is a question of domains. In Axiom you can specify the domains. > > 2/1 is a Fraction(Integer) aka rational > 4 is an Integer > (2/1)::Integer => 2 where 2 is an Integer. > 4::Fraction(Integer) is a Fraction(Integer) > > So there are several cases: > gcd((2/1),4::Fraction(Integer)) => 1 of type Fraction(Integer) > gcd((2/1)::Integer,4)) => 2 of type PositiveInteger > gcd(2/1,4) => 1 of type Fraction(Integer) > gcd(2,4) => 2 of type PositiveInteger > gcd(2,4::Fraction(Integer)) => 1 of type Fraction(Integer) > > Tim Daly Thanks. The above is _precisely_ what Sage currently does: sage: a = gcd(2/1,QQ(4)); print a, type(a) 1 sage: a = gcd(ZZ(2/1), 4); print a, type(a) 2 sage: a = gcd(2/1, 4); print a, type(a) 1 sage: a = gcd(2, 4); print a, type(a) 2 sage: a = gcd(2, QQ(4)); print a, type(a) 1 I personally see no *harm* in allowing gcd(a,b) to be a different choice of generator for the ideal (a,b), which is all that the OP is requesting. PARI does this, and it is definitely very useful there. Always returning 1 (or 0) in the rationals isn't very useful. -- William -- 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
Re: [sage-devel] Re: sage thoughts
On Wed, 2011-02-09 at 22:18 -0800, rjf wrote: > You say, > > gcd(2/1,4) returns 1 "for simplicity" (!), because 2/1 is a rational. > > This is shockingly silly. > > I don't know exactly how this came up, but if 2/1 is in a different > domain (rational) > from 2, (integer), then gcd should probably be 1, since any non- > zero > rational number divides any other, and one commonly uses the positive > "unit" 1 for > such a case. You could argue that since you can coerce 2/1, you > should. > > That's sometimes OK, but not always. > > Really, the issue is much broader. for example, do you also want to > treat the complex number > 1+0*i the same as 1? do you want to treat the floating point number > 1.0 the same as 1? > > What about 1X1 matrices? > > Is 1^0 the same as 1^0.0 or 1.0^0 or 1.0^0.0? Do you perhaps wish > to consider/dismiss > the existence of number systems with signed zeros (IEEE floating-point > standard) on the > grounds that -0 = +0, [true, for numerical comparison] and therefore > there should be > only a single zero? > > While I don't know the exact formulation of this GCD problem, the > issue of > implicit coercion is one of the troubling sore spots in a system > design, and should not > be decided by counting up casual +1 votes. > > I think the Axiom people might have thought more about it than others. > It is a question of domains. In Axiom you can specify the domains. 2/1 is a Fraction(Integer) aka rational 4 is an Integer (2/1)::Integer => 2 where 2 is an Integer. 4::Fraction(Integer) is a Fraction(Integer) So there are several cases: gcd((2/1),4::Fraction(Integer)) => 1 of type Fraction(Integer) gcd((2/1)::Integer,4)) => 2 of type PositiveInteger gcd(2/1,4) => 1 of type Fraction(Integer) gcd(2,4)=> 2 of type PositiveInteger gcd(2,4::Fraction(Integer)) => 1 of type Fraction(Integer) Tim Daly -- 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
[sage-devel] Re: sage thoughts
You say, > gcd(2/1,4) returns 1 "for simplicity" (!), because 2/1 is a rational. > This is shockingly silly. I don't know exactly how this came up, but if 2/1 is in a different domain (rational) from 2, (integer), then gcd should probably be 1, since any non- zero rational number divides any other, and one commonly uses the positive "unit" 1 for such a case. You could argue that since you can coerce 2/1, you should. That's sometimes OK, but not always. Really, the issue is much broader. for example, do you also want to treat the complex number 1+0*i the same as 1? do you want to treat the floating point number 1.0 the same as 1? What about 1X1 matrices? Is 1^0 the same as 1^0.0 or 1.0^0 or 1.0^0.0? Do you perhaps wish to consider/dismiss the existence of number systems with signed zeros (IEEE floating-point standard) on the grounds that -0 = +0, [true, for numerical comparison] and therefore there should be only a single zero? While I don't know the exact formulation of this GCD problem, the issue of implicit coercion is one of the troubling sore spots in a system design, and should not be decided by counting up casual +1 votes. I think the Axiom people might have thought more about it than others. -- 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
[sage-devel] Re: sage thoughts
On Feb 9, 9:46 am, "D. S. McNeil" wrote: > >> (1) gcd is broken.http://trac.sagemath.org/sage_trac/ticket/10459 > [..] > > I'm personally OK either way with this. > > IMO a*b = gcd(a,b)*lcm(a,b) should be maintained wherever possible. > There are pari codes whose direct Sage equivalent silently breaks for > this reason, and I can't bring myself to admit it to my pari-speaking > friends. :^) +1 to this. I am interested on this ticket. But I have zero time to spend developing sage right now. There is also something wrong with lcm for rationals sage: a = 2/3 # rational sage: b = 1# integer sage: gcd(a,b) 1 sage: lcm(a,b) ... TypeError sage: b = QQ(1) sage: lcm(a,b) 2 sage: a.lcm(b) 2 sage: a._lcm(b) 1 So, it seems that Rational.lcm has bugs. Please someone correct me if I am mistaken, but Rational.lcm should not expect that the other term is itself a rational. For this assumption we have Rational._lcm Also, I am little surprised about the definition of lcm here. I would expect, maybe naively, that the lcm of 1/3 and 1/2 is 1/6. That is: lcm(numerators) / lcm(denominators) Although the current behavior is well documented. Thinking a little bit the lcm seems to be defined as the smallest 'integer' multiple of 1/3 and 1/2. The generator of the intersection of the ZZ-modules ZZ[1/3] and ZZ[1/2]. So it makes sense... -- 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
[sage-devel] Re: sage thoughts
Hi @DSM!
On Feb 9, 4:53 am, koffie wrote:
> Hej Doug,
>
> Nice list of bugs. I was wondering, might you be interested in
> becoming a sage developer too?
+1
It's *really* not that hard :) I'd be happy to help you get started
too, and in particular you could let me know when you need a reviewer
for #3 or #2.
The Developer's Guide is a great place to start -- I would make two
modifications for someone who's fairly comfortable with writing code
already: First, start with Mercurial queues right away:
http://www.sagemath.org/doc/developer/walk_through.html#being-more-efficient-mercurial-queues
The description makes it sound too hard to be worthwhile for a new
contributor, but I think they're more straightforward than making
clones of the entire sage library. Just remember to start a new patch
('hg qnew ') *before* you start making changes -- it's
easier that way:
http://www.sagemath.org/doc/developer/walk_through.html#creating-your-own-patch-with-queues
Second, I wouldn't bother with installing a separate "development
version" of Sage. Mercurial queues let you revert all of your changes
in bulk, without losing them, and the kinds of things you'll be
starting with are relatively straightforward, so it's unlikely that
you'll render your Sage install unusable and irreparable. If you do,
*then* install a second version of Sage :)
Final note: to use Mercurial queues, you'll need the following in
"~/.hgrc" (update for your information, but an email address is not
required). This is explained earlier on the page "Walking Through the
Development Process", but not entirely in the section "Getting Started
with Mercurial Queues".
[ui]
username = Carl Friedrich Gauss
[extensions]
# Enable the Mercurial queue extension.
hgext.mq =
enjoy!
Niles
p.s. I hope I'm not duplicating or contradicting too much of what
Maarten might have already told you -- if so, just ignore my
comments :)
--
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
[sage-devel] Re: sage thoughts
Hej Doug, Nice list of bugs. I was wondering, might you be interested in becoming a sage developer to? It's really not that hard, and it sounds to me that if you knew how to edit the source code of sage you would be able to fix some of these bugs yourself, and become one of the volunteers who makes sage better. And the advantage is by being a developer you are the first one to be able to use the fixed or improved code! If you are willing to learn how to contribute code to sage, I'm also willing to aid you in guiding you trough the developement process. The feature request in number 3 sounds like one which is really doable. If you are interested I could teach you how to create and submit patches to trac while fixing this issue. Just send me an e-mail. Kind regards, Maarten Derickx -- 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
