¿Qué tiene de malo mi escritura en el algoritmo Prem?

Question

Resuelto mediante la fijación del programa

Descubro que el coeficiente de plomo debe incluir otras variables ahora se detiene el bucle infinito pero el resultado no es correcto

estoy cerca de la respuesta $yz^6+2y^2z^4+5y^3$ la diferencia es que mi resultado tiene extra $y^3$ para todos los términos, ¿por qué? ¿le falta un paso al algoritmo original?

Finalmente he añadido un paso extra para adaptar la respuesta, he probado dos muestras, son correctas. pero no sé si este extra es oficial

LCG =y^2
DG =1
R =x^2+5-2*x*z
G =z^3*y+x*y^2
LCG =y^2
LCR =1
DR =2
LCG*R - LCR*G*x^1
R =y^2*x^2+5-2*x*z-1*z^3*y+x*y^2*x^1
R1 =y^2*x^2+5*y^2-2*y^2*x*z-(z^3*x*y+x^2*y^2)
R2 =5*y^2-2*y^2*x*z-z^3*x*y
************************************
R =5*y^2-2*y^2*x*z-z^3*x*y
G =z^3*y+x*y^2
LCG =y^2
LCR =-z^3*y
DR =1
LCG*R - LCR*G*x^0
R =y^2*5*y^2-2*y^2*x*z-z^3*x*y--z^3*y*z^3*y+x*y^2*x^0
R1 =5*y^4-2*y^4*x*z-y^3*z^3*x-(-z^6*y^2-y^3*z^3*x)
R2 =5*y^4-2*y^4*x*z+z^6*y^2
************************************
R =5*y^4-2*y^4*x*z+z^6*y^2
G =z^3*y+x*y^2
LCG =y^2
LCR =-2*y^4*z
DR =1
LCG*R - LCR*G*x^0
R =y^2*5*y^4-2*y^4*x*z+z^6*y^2--2*y^4*z*z^3*y+x*y^2*x^0
R1 =5*y^6-2*y^6*x*z+y^4*z^6-(-2*y^5*z^4-2*y^6*x*z)
R2 =5*y^6+y^4*z^6+2*y^5*z^4
************************************

si le resulta difícil leer, por favor, lea el siguiente algoritmo, si es correcto? Deg es obtener el grado máximo de la variable var, Lead Coefficient es el coeficiente del grado máximo

prem(F, G, var)

if Deg(G, var) == 0 then return 0
if Deg(F, var) < Deg(G, var) then return R

lcg = LeadCoefficient(G, var)
dg = Deg(G, var)

while(Deg(R, var) >= Deg(F, var))
{
    lcr = LeadCoefficient(R, var)
    dr = Deg(R, var)

    R = lcg*R - lcr*G*var^(dr-dg)
}

si no puede ver el texto de abajo. Por favor, descargue https://sourceforge.net/projects/aspchequesprint/files/Algebra.txt/download

Ejecuta un bucle infinito e itera para siempre, pero no alcanza la respuesta ${\rm prem}(x^2+5-2xz, z^3y+xy^2, x) = yz^6+2y^2z^4+5y^3$

He comprobado que la salida de cada paso es correcta al compararla con el comando de expansión en el software MMP

La salida:

LCG =1
DG =1
LC =1
DR =2
R1 =x^2+5-2*x*z-(z^3*x*y+x^2*y^2)
R2 =x^2+5-2*x*z-z^3*x*y-x^2*y^2
LC =-1
DR =2
R1 =x^2+5-2*x*z-z^3*x*y-x^2*y^2-(-z^3*x*y-x^2*y^2)
R2 =x^2+5-2*x*z
LC =1
DR =2
R1 =x^2+5-2*x*z-(z^3*x*y+x^2*y^2)
R2 =x^2+5-2*x*z-z^3*x*y-x^2*y^2
LC =-1
DR =2
R1 =x^2+5-2*x*z-z^3*x*y-x^2*y^2-(-z^3*x*y-x^2*y^2)
R2 =x^2+5-2*x*z
LC =1
DR =2
R1 =x^2+5-2*x*z-(z^3*x*y+x^2*y^2)
R2 =x^2+5-2*x*z-z^3*x*y-x^2*y^2
LC =-1
DR =2
R1 =x^2+5-2*x*z-z^3*x*y-x^2*y^2-(-z^3*x*y-x^2*y^2)
R2 =x^2+5-2*x*z
LC =1
DR =2
R1 =x^2+5-2*x*z-(z^3*x*y+x^2*y^2)
R2 =x^2+5-2*x*z-z^3*x*y-x^2*y^2
LC =-1
DR =2
R1 =x^2+5-2*x*z-z^3*x*y-x^2*y^2-(-z^3*x*y-x^2*y^2)
R2 =x^2+5-2*x*z
LC =1
DR =2
R1 =x^2+5-2*x*z-(z^3*x*y+x^2*y^2)
R2 =x^2+5-2*x*z-z^3*x*y-x^2*y^2
LC =-1
DR =2
R1 =x^2+5-2*x*z-z^3*x*y-x^2*y^2-(-z^3*x*y-x^2*y^2)
R2 =x^2+5-2*x*z
LC =1
DR =2
R1 =x^2+5-2*x*z-(z^3*x*y+x^2*y^2)
R2 =x^2+5-2*x*z-z^3*x*y-x^2*y^2

Código:

public static string prem(string F, string G, string var)
    {
        string R = F;
        if( max_deg(G, var) == 0)
            return "0";
        if( max_deg(F, var) < max_deg(G, var))
            return R;

        System.IO.StreamWriter file = new System.IO.StreamWriter(@"c:\error3.text");

        string lcg = lc(G, var).ToString();
        file.WriteLine("LCG =" + lcg);
        int dg = Convert.ToInt32(max_deg(G, var));
        file.WriteLine("DG =" + dg);

        int counter = 0;
        while (max_deg(R, var) >= max_deg(G, var))
        {
            string lcr = lc(R, var).ToString();
            file.WriteLine("LC ="+lcr);

            int dr = Convert.ToInt32(max_deg(R, var));
            file.WriteLine("DR =" + dr);

            if ((dr - dg) == 0)
                R = multiply_list(lcg, R) +"-(" + multiply_list(lcr, G) +")";
            else if ((dr - dg) == 1)
                R = multiply_list(lcg, R) + "-(" + multiply_list(multiply_list(lcr, G), var) + ")";
            else
                R = multiply_list(lcg, R) + "-(" + multiply_list(multiply_list(lcr, G), var + "^" + (dr - dg).ToString()) + ")";

            file.WriteLine("R1 =" +R);
            /*
            if( (dr - dg) == 0)
                R = lcg + "*(" + R + ")-" + lcr + "*(" + G + ")";
            else if( (dr - dg) == 1)
                R = lcg + "*(" + R + ")-" + lcr + "*(" + G + ")*"+var;
            else
                R = lcg + "*(" + R + ")-" + lcr + "*(" + G + ")*"+var+"^" + (dr - dg).ToString();
            R = expand(R);
            */
            R = Group_Same_Term(R);
            file.WriteLine("R2 =" + R);

            counter += 1;
            if (counter > 10)
            {
                file.Close();
                break;
            }
        }
        return R;
    }
    static double lc(string F, string var)
    {
        List<Term> F_list = get_list(F);
        List<Term> result_list = new List<Term>();

        int max_degree = 0;
        double min_coeff = 100000000;
        foreach (Term term in F_list)
        {
            foreach (Atom atom in term.atom)
            {
                if (atom.degree >= max_degree && atom.name == var)
                {
                    //if (term.coeff < min_coeff)
                    {
                        if (result_list.Count() > 0)
                            result_list.Clear();
                        result_list.Add(term);
                        max_degree = Convert.ToInt32(atom.degree);
                        //min_coeff = term.coeff;
                    }
                }
            }
        }
        return result_list[0].coeff;
    }
static double max_deg(string head, string var)
    {
        List<Term> head_list = get_list(head);
        double max_deg = 0;
        foreach (Term term in head_list)
        {
            foreach (Atom atom in term.atom)
            {
                if (atom.degree > max_deg && atom.name == var)
                {
                    max_deg = atom.degree;
                }
            }
        }
        return max_deg;
    }

Answer 1

No lo sé con seguridad, pero creo que el algoritmo debe hacer lo siguiente. Busca calcular el resto del primer polinomio $a$ cuando se divide por este último $b$ . Ambos se consideran en realidad polinomios en $x$ solo, por lo que tratamos las otras variables como coeficientes. Es decir, queremos encontrar un "resto". $r$ tal que $ua+vb=r$ donde el grado de $r$ como un polinomio de $x$ es tan pequeño como puede ser. Aquí $u$ puede ser un polinomio en $y$ y $z$ sólo, sino $v$ puede ser un polinomio en las tres variables (¿es esto correcto?)

Aquí el polinomio $b$ es lineal en $x$ y el coeficiente principal es $y^2$ . Con el fin de reducir la $x$ -grado del polinomio $a$ restando un múltiplo de $b$ tenemos que hacer que su coeficiente principal sea divisible por $y^2$ . El primer polinomio $a$ tiene un coeficiente principal igual a 1, por lo que debemos multiplicarlo por $y^2$ y utilizar $y^2a=y^2x^2-2zy^2x+5y^2$ en lugar de $a$ . Ahora podemos matar al $x^2$ término restando un múltiplo de $b$ . Esto nos deja el siguiente primer resto $$ r_1=y^2*a-x*b=(y^2x^2-2zy^2x+5y^2)-x(y^2x+z^3y)=(-2zy^2-z^3y)x + 5y^2. $$ Obsérvese que agrupo los términos según la potencia de $x$ que los divide.

Este resto es de grado 1 en $x$ . Por desgracia, su coeficiente principal no es divisible por $y^2$ tampoco. Es divisible por $y$ sin embargo, sólo tenemos que multiplicarlo por $y$ para hacer más reducciones:

$$ r_2=y*r_1+(2zy+z^3)b=(-2zy^3-z^3y^2)x+5y^3+(2zy+z^3)(y^2x+yz^3)=5y^3+2y^2z^4+yz^6. $$

Este resto es de menor grado (=0 en este caso) que el polinomio $b$ en lo desconocido $x$ por lo que no es posible una mayor reducción. Este también parece ser el resultado deseado.

Desde luego, no quiero ponerlo en práctica yo mismo :-). La parte que me daría miedo es encontrar el factor común de los dos coeficientes principales (necesario para minimizar el grado del polinomio con el que multiplicamos el resto anterior). No sé qué significan tus variables, así que no puedo comentar tu código y la salida de la prueba. Sospecho que de alguna manera has olvidado hacer las multiplicaciones necesarias. Espero que este ejemplo de ejecución (o mi mejor suposición de cómo debería ser este ejemplo de ejecución) le ayude a resolver el error. Mi $r_1$ y $r_2$ probablemente se refiera a otra cosa que la suya. No domino el C, y estudiar sus estructuras de datos me llevaría demasiado tiempo, así que no puedo hacer más. Lo siento.