What's wrong with my writing in Prem algorithm?

Question

Solved by fixing program

I discover lead coefficient should include other variables now it stop infinite loop but result not correct

i am near the answer $yz^6+2y^2z^4+5y^3$ the difference is my result have extra $y^3$ for all terms, why? is the original algorithm missing a step?

Finally i add a extra step to adapt the answer, i have test two samples, they are correct. but i do not know this extra whether is official one

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
************************************

if you feel difficult to read, please read below algorithm, whether it is correct? Deg is get the maximum degree of variable var, Lead Coefficient is the coefficient of maximum degree

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)
}

if can not see the text below. Please download https://sourceforge.net/projects/aspchequesprint/files/Algebra.txt/download

It run a infinite loop and iterate forever, but do not reach answer ${\rm prem}(x^2+5-2xz, z^3y+xy^2, x) = yz^6+2y^2z^4+5y^3$

I checked output of each step is correct when comparing with expand command in software MMP

Output:

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

Code:

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

I don't know for sure, but I think that the algorithm is supposed to do the following. It seeks to compute the remainder of the first polynomial $a$ when divided by the latter $b$. Both are actually viewed as polynomials in $x$ alone, so we treat the other variables are coefficients. IOW we want to find a 'remainder' $r$ such that $ua+vb=r$ where the degree of $r$ as a polynomial of $x$ is as small as it can be. Here $u$ can be a polynomial in $y$ and $z$ only, but $v$ can be a polynomial in all three variables (is this right?)

Here the polynomial $b$ is linear in $x$ and the leading coefficient is $y^2$. In order to reduce the $x$-degree of polynomial $a$ by subtracting a multiple of $b$ we need to make its leading coefficient divisible by $y^2$. The first polynomial $a$ has a leading coefficient equal to 1, so we need to multiply it by $y^2$ and use $y^2a=y^2x^2-2zy^2x+5y^2$ instead of $a$. Now we can kill the $x^2$ term by subtracting a multiple of $b$. This leaves us the following first remainder $$ 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. $$ Note that I group the terms according to the power of $x$ that divides them.

This remainder is of degree 1 in $x$. Unfortunately its leading coefficient isn't divisible by $y^2$ either. It is divisible by $y$ though, so we only need to multiply it by $y$ to make further reductions:

$$ 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. $$

This remainder is of lower degree (=0 in this case) than the polynomial $b$ in the unknown $x$, so no further reduction is possible. This also seems to be the desired output.

I most certainly don't want to implement this myself :-). The part that I would find scary is finding the common factor of the two leading coefficients (needed to minimize the degree of the polynomial we multiply the preceding remainder with). I don't know what your variables stand for, so cannot comment your code and the test output. I suspect that somehow you have forgotten to do the necessary multiplications. Hopefully this sample run (or my best guess of what this sample run should look like) will help you figure out the bug. My $r_1$ and $r_2$ probably mean something else than yours. I'm not fluent in C, and studying your data structures would take too much time, so I can't do more. Sorry.