Re: [sage-support] cant explain this behavior - simple aritmethics / extended euclidean algorithm
Ok, from this point of view see the point. But I dont know if it's documented this way somewhere. greatz Am 28.12.2010 23:00, schrieb Iwao Kimura: > Hi Johannes, > > I'm not sure but if we think gcd(2, 0) is the generator of the ideal > generated by 2 and 0 in the rationals, we see gcd(2,0) is 1 because > the ideal is not zero (and QQ is a field :) > > Best regards. > > On Wed, Dec 29, 2010 at 6:33 AM, Johannes wrote: >> I got it solved. It's a type error: >> the matrix sing is a matrix over QQ. >> If its a matrix over ZZ it works fine. >> >> but why is gcd(2,0) = 1 for 2,0 as Rationals? >> in my eyes its not well defined or should be the maximum of those values. >> >> greatz >> >> Am 28.12.2010 22:08, schrieb Johannes: >>> Hi list, >>> I've a very confusing problem with some simple algorithm: >>> >>> following setting: a matrix sing: >>> sage: sing >>> [ 3 0 1] >>> [-2 -1 -2] >>> [ 0 1 0] >>> sage: l = sings.column(2);l >>> (1, -2, 0) >>> #my algorithem, code see below: >>> sage: extgcd(l) >>> #some printoutput for debugging: >>> l: (1, -2, 0) >>> tlist: (-2, 0) >>> #this should not be, d = gcd(tlist) >>> d: 1 >>> l: [1, 1] >>> [u, v]: [0, 1] >>> l: (-2, 0) >>> [u, v]: [1, 0] >>> res: [0, 1, 0] >>> #the result: >>> [0, 1, 0] >>> #now the same but i construct the vector on my own: >>> sage: l = vector([1,-2,0]);l >>> (1, -2, 0) >>> sage: extgcd(l) >>> l: (1, -2, 0) >>> tlist: (-2, 0) >>> #here it works fine >>> d: 2 >>> l: [1, 2] >>> [u, v]: [1, 0] >>> l: (-2, 0) >>> [u, v]: [1, 0] >>> res: [1, 0, 0] >>> #getting the expected result: >>> [1, 0, 0] >>> >>> the code of my algorithm: >>> >>> def extgcd(l): >>> print "l: " + str(l) >>> assert len(l) > 1 >>> >>> if len(l) == 2: >>> #calculated ext euclidean for two values >>> a = l[0] >>> b = l[1] >>> >>> u=t=1 >>> v=s=0 >>> while b>0: >>> q=a//b >>> a, b = b, a-q*b >>> u, s = s, u-q*s >>> v, t = t, v-q*t >>> print "[u, v]: " + str([u, v]) >>> return [u, v] >>> else: >>> >>> #this is the part where it does not work! >>> tlist = l[1:] >>> print "tlist: " + str(tlist) >>> d = gcd(tlist) >>> print "d: " + str(gcd(tlist)) >>> >>> #calculate part decomp >>> u, v = extgcd([l[0],d]) >>> #calculate rest >>> ttlist = extgcd(tlist) >>> res = [u] >>> #combine results >>> res.extend([v * item for item in ttlist]) >>> print "res: " + str(res) >>> return res >>> >>> I hope somebody can help me. >>> greatz Johannes >>> >> >> -- >> To post to this group, send email to sage-support@googlegroups.com >> To unsubscribe from this group, send email to >> sage-support+unsubscr...@googlegroups.com >> For more options, visit this group at >> http://groups.google.com/group/sage-support >> URL: http://www.sagemath.org >> > > > -- To post to this group, send email to sage-support@googlegroups.com To unsubscribe from this group, send email to sage-support+unsubscr...@googlegroups.com For more options, visit this group at http://groups.google.com/group/sage-support URL: http://www.sagemath.org
Re: [sage-support] cant explain this behavior - simple aritmethics / extended euclidean algorithm
Hi Johannes, I'm not sure but if we think gcd(2, 0) is the generator of the ideal generated by 2 and 0 in the rationals, we see gcd(2,0) is 1 because the ideal is not zero (and QQ is a field :) Best regards. On Wed, Dec 29, 2010 at 6:33 AM, Johannes wrote: > I got it solved. It's a type error: > the matrix sing is a matrix over QQ. > If its a matrix over ZZ it works fine. > > but why is gcd(2,0) = 1 for 2,0 as Rationals? > in my eyes its not well defined or should be the maximum of those values. > > greatz > > Am 28.12.2010 22:08, schrieb Johannes: >> Hi list, >> I've a very confusing problem with some simple algorithm: >> >> following setting: a matrix sing: >> sage: sing >> [ 3 0 1] >> [-2 -1 -2] >> [ 0 1 0] >> sage: l = sings.column(2);l >> (1, -2, 0) >> #my algorithem, code see below: >> sage: extgcd(l) >> #some printoutput for debugging: >> l: (1, -2, 0) >> tlist: (-2, 0) >> #this should not be, d = gcd(tlist) >> d: 1 >> l: [1, 1] >> [u, v]: [0, 1] >> l: (-2, 0) >> [u, v]: [1, 0] >> res: [0, 1, 0] >> #the result: >> [0, 1, 0] >> #now the same but i construct the vector on my own: >> sage: l = vector([1,-2,0]);l >> (1, -2, 0) >> sage: extgcd(l) >> l: (1, -2, 0) >> tlist: (-2, 0) >> #here it works fine >> d: 2 >> l: [1, 2] >> [u, v]: [1, 0] >> l: (-2, 0) >> [u, v]: [1, 0] >> res: [1, 0, 0] >> #getting the expected result: >> [1, 0, 0] >> >> the code of my algorithm: >> >> def extgcd(l): >> print "l: " + str(l) >> assert len(l) > 1 >> >> if len(l) == 2: >> #calculated ext euclidean for two values >> a = l[0] >> b = l[1] >> >> u=t=1 >> v=s=0 >> while b>0: >> q=a//b >> a, b = b, a-q*b >> u, s = s, u-q*s >> v, t = t, v-q*t >> print "[u, v]: " + str([u, v]) >> return [u, v] >> else: >> >> #this is the part where it does not work! >> tlist = l[1:] >> print "tlist: " + str(tlist) >> d = gcd(tlist) >> print "d: " + str(gcd(tlist)) >> >> #calculate part decomp >> u, v = extgcd([l[0],d]) >> #calculate rest >> ttlist = extgcd(tlist) >> res = [u] >> #combine results >> res.extend([v * item for item in ttlist]) >> print "res: " + str(res) >> return res >> >> I hope somebody can help me. >> greatz Johannes >> > > -- > To post to this group, send email to sage-support@googlegroups.com > To unsubscribe from this group, send email to > sage-support+unsubscr...@googlegroups.com > For more options, visit this group at > http://groups.google.com/group/sage-support > URL: http://www.sagemath.org > -- --- Iwao KIMURA Dept. Math., University of Toyama, Japan. -- To post to this group, send email to sage-support@googlegroups.com To unsubscribe from this group, send email to sage-support+unsubscr...@googlegroups.com For more options, visit this group at http://groups.google.com/group/sage-support URL: http://www.sagemath.org
Re: [sage-support] cant explain this behavior - simple aritmethics / extended euclidean algorithm
I got it solved. It's a type error: the matrix sing is a matrix over QQ. If its a matrix over ZZ it works fine. but why is gcd(2,0) = 1 for 2,0 as Rationals? in my eyes its not well defined or should be the maximum of those values. greatz Am 28.12.2010 22:08, schrieb Johannes: > Hi list, > I've a very confusing problem with some simple algorithm: > > following setting: a matrix sing: > sage: sing > [ 3 0 1] > [-2 -1 -2] > [ 0 1 0] > sage: l = sings.column(2);l > (1, -2, 0) > #my algorithem, code see below: > sage: extgcd(l) > #some printoutput for debugging: > l: (1, -2, 0) > tlist: (-2, 0) > #this should not be, d = gcd(tlist) > d: 1 > l: [1, 1] > [u, v]: [0, 1] > l: (-2, 0) > [u, v]: [1, 0] > res: [0, 1, 0] > #the result: > [0, 1, 0] > #now the same but i construct the vector on my own: > sage: l = vector([1,-2,0]);l > (1, -2, 0) > sage: extgcd(l) > l: (1, -2, 0) > tlist: (-2, 0) > #here it works fine > d: 2 > l: [1, 2] > [u, v]: [1, 0] > l: (-2, 0) > [u, v]: [1, 0] > res: [1, 0, 0] > #getting the expected result: > [1, 0, 0] > > the code of my algorithm: > > def extgcd(l): > print "l: " + str(l) > assert len(l) > 1 > > if len(l) == 2: > #calculated ext euclidean for two values > a = l[0] > b = l[1] > > u=t=1 > v=s=0 > while b>0: > q=a//b > a, b = b, a-q*b > u, s = s, u-q*s > v, t = t, v-q*t > print "[u, v]: " + str([u, v]) > return [u, v] > else: > > #this is the part where it does not work! > tlist = l[1:] > print "tlist: " + str(tlist) > d = gcd(tlist) > print "d: " + str(gcd(tlist)) > > #calculate part decomp > u, v = extgcd([l[0],d]) > #calculate rest > ttlist = extgcd(tlist) > res = [u] > #combine results > res.extend([v * item for item in ttlist]) > print "res: " + str(res) > return res > > I hope somebody can help me. > greatz Johannes > -- To post to this group, send email to sage-support@googlegroups.com To unsubscribe from this group, send email to sage-support+unsubscr...@googlegroups.com For more options, visit this group at http://groups.google.com/group/sage-support URL: http://www.sagemath.org
[sage-support] cant explain this behavior - simple aritmethics / extended euclidean algorithm
Hi list, I've a very confusing problem with some simple algorithm: following setting: a matrix sing: sage: sing [ 3 0 1] [-2 -1 -2] [ 0 1 0] sage: l = sings.column(2);l (1, -2, 0) #my algorithem, code see below: sage: extgcd(l) #some printoutput for debugging: l: (1, -2, 0) tlist: (-2, 0) #this should not be, d = gcd(tlist) d: 1 l: [1, 1] [u, v]: [0, 1] l: (-2, 0) [u, v]: [1, 0] res: [0, 1, 0] #the result: [0, 1, 0] #now the same but i construct the vector on my own: sage: l = vector([1,-2,0]);l (1, -2, 0) sage: extgcd(l) l: (1, -2, 0) tlist: (-2, 0) #here it works fine d: 2 l: [1, 2] [u, v]: [1, 0] l: (-2, 0) [u, v]: [1, 0] res: [1, 0, 0] #getting the expected result: [1, 0, 0] the code of my algorithm: def extgcd(l): print "l: " + str(l) assert len(l) > 1 if len(l) == 2: #calculated ext euclidean for two values a = l[0] b = l[1] u=t=1 v=s=0 while b>0: q=a//b a, b = b, a-q*b u, s = s, u-q*s v, t = t, v-q*t print "[u, v]: " + str([u, v]) return [u, v] else: #this is the part where it does not work! tlist = l[1:] print "tlist: " + str(tlist) d = gcd(tlist) print "d: " + str(gcd(tlist)) #calculate part decomp u, v = extgcd([l[0],d]) #calculate rest ttlist = extgcd(tlist) res = [u] #combine results res.extend([v * item for item in ttlist]) print "res: " + str(res) return res I hope somebody can help me. greatz Johannes -- To post to this group, send email to sage-support@googlegroups.com To unsubscribe from this group, send email to sage-support+unsubscr...@googlegroups.com For more options, visit this group at http://groups.google.com/group/sage-support URL: http://www.sagemath.org
