ASKSAGE: Sage Q&A Forum - RSS feedhttps://ask.sagemath.org/questions/Q&A Forum for SageenCopyright Sage, 2010. Some rights reserved under creative commons license.Wed, 17 Nov 2021 23:00:07 +0100How can you define a function that finds the Greatest Common Divisor (Gcd) two polynomials for every field?https://ask.sagemath.org/question/59777/how-can-you-define-a-function-that-finds-the-greatest-common-divisor-gcd-two-polynomials-for-every-field/
Hi, as the title says I`m trying to define a function that finds the gcd of two polynomial without using the pre-established function gcd. I've tried everything I thought it would work:
First, I tried to use the Euclidan Algorithm, for that you need to divide the polynomials. Knowing so, I tried to find the degrees of the different polynomials to divide in consequence of the degrees (which gave me error). Then I tried it without the degree part and it didn't work at all since % couldn't be used as a divisor of polynomials.
def GCD(field, f, g):
R.<x> = PolynomialRing(field, 'x')
x.parent()
a = f.degree()
b = g.degree()
if a>b:
while g != 0:
r = g
g = f%g
else:
while f != 0:
r = g
f = g%f
return r
Shortly after I tried to factor both of the polynomial and make the función return the part that repeated. But I rapidly saw my hopes decay when I realized I have not a single clue in how to do so (even though I've done some research I couldn't find the answer).
def mcd(field, f, g):
R.<x> = PolynomialRing(field)
a = f.factor()
b = g.factor()
And this was the last code I wrote before asking for some enlightening:
def MCD(Field,PolynomialA, PolinomialB):
R.<x> = PolynomialRing(Field, 'x')
a = PolynomialA
b = PolynomialB
c = 1
while c != 0:
c = a%b
a = b
b = c
return aWed, 17 Nov 2021 00:58:06 +0100https://ask.sagemath.org/question/59777/how-can-you-define-a-function-that-finds-the-greatest-common-divisor-gcd-two-polynomials-for-every-field/Answer by rburing for <p>Hi, as the title says I`m trying to define a function that finds the gcd of two polynomial without using the pre-established function gcd. I've tried everything I thought it would work: </p>
<p>First, I tried to use the Euclidan Algorithm, for that you need to divide the polynomials. Knowing so, I tried to find the degrees of the different polynomials to divide in consequence of the degrees (which gave me error). Then I tried it without the degree part and it didn't work at all since % couldn't be used as a divisor of polynomials. </p>
<pre><code>def GCD(field, f, g):
R.<x> = PolynomialRing(field, 'x')
x.parent()
a = f.degree()
b = g.degree()
if a>b:
while g != 0:
r = g
g = f%g
else:
while f != 0:
r = g
f = g%f
return r
</code></pre>
<p>Shortly after I tried to factor both of the polynomial and make the función return the part that repeated. But I rapidly saw my hopes decay when I realized I have not a single clue in how to do so (even though I've done some research I couldn't find the answer).</p>
<pre><code>def mcd(field, f, g):
R.<x> = PolynomialRing(field)
a = f.factor()
b = g.factor()
</code></pre>
<p>And this was the last code I wrote before asking for some enlightening:</p>
<pre><code>def MCD(Field,PolynomialA, PolinomialB):
R.<x> = PolynomialRing(Field, 'x')
a = PolynomialA
b = PolynomialB
c = 1
while c != 0:
c = a%b
a = b
b = c
return a
</code></pre>
https://ask.sagemath.org/question/59777/how-can-you-define-a-function-that-finds-the-greatest-common-divisor-gcd-two-polynomials-for-every-field/?answer=59798#post-id-59798It seems that you try to use the following idea: $\gcd(f,g) = f$ if $g=0$ and otherwise it equals $\gcd(g, f \mbox{ mod } g)$. So while $g \neq 0$ you should set $(f, g) := (g, f \mbox{ mod } g)$, and at the end return $f$. To express this without assignment of a tuple (even though that is possible in SageMath/Python) you can use a temporary variable, say $r$: first put $r:=g$ and then $g:=f \mbox{ mod } g$ and then $f:=r$. In code it becomes:
def mygcd(f,g):
while g != 0:
r = g
g = f % g
f = r
return f/f.lc()
You almost had this, just somehow not using the temporary variable correctly. I also changed the last line to return a monic polynomial (this is a convention, e.g. followed by SageMath's own `gcd`).
The function works when passed elements of a polynomial ring such as `R.<x> = PolynomialRing(QQ)`.Wed, 17 Nov 2021 17:21:08 +0100https://ask.sagemath.org/question/59777/how-can-you-define-a-function-that-finds-the-greatest-common-divisor-gcd-two-polynomials-for-every-field/?answer=59798#post-id-59798Comment by Escolopendra for <p>It seems that you try to use the following idea: $\gcd(f,g) = f$ if $g=0$ and otherwise it equals $\gcd(g, f \mbox{ mod } g)$. So while $g \neq 0$ you should set $(f, g) := (g, f \mbox{ mod } g)$, and at the end return $f$. To express this without assignment of a tuple (even though that is possible in SageMath/Python) you can use a temporary variable, say $r$: first put $r:=g$ and then $g:=f \mbox{ mod } g$ and then $f:=r$. In code it becomes:</p>
<pre><code>def mygcd(f,g):
while g != 0:
r = g
g = f % g
f = r
return f/f.lc()
</code></pre>
<p>You almost had this, just somehow not using the temporary variable correctly. I also changed the last line to return a monic polynomial (this is a convention, e.g. followed by SageMath's own <code>gcd</code>).</p>
<p>The function works when passed elements of a polynomial ring such as <code>R.<x> = PolynomialRing(QQ)</code>.</p>
https://ask.sagemath.org/question/59777/how-can-you-define-a-function-that-finds-the-greatest-common-divisor-gcd-two-polynomials-for-every-field/?comment=59806#post-id-59806Thank you very much it works perfectly.Wed, 17 Nov 2021 23:00:07 +0100https://ask.sagemath.org/question/59777/how-can-you-define-a-function-that-finds-the-greatest-common-divisor-gcd-two-polynomials-for-every-field/?comment=59806#post-id-59806