# What's wrong with my writing in Prem algorithm?

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

dg = Deg(G, var)

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

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


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();
max_degree = Convert.ToInt32(atom.degree);
//min_coeff = term.coeff;
}
}
}
}
return result_list[0].coeff;
}
static double max_deg(string head, string var)
{
double max_deg = 0;
{
foreach (Atom atom in term.atom)
{
if (atom.degree > max_deg && atom.name == var)
{
max_deg = atom.degree;
}
}
}
return max_deg;
}

-
Unreadable. If it weren't so long, I'd edit it into TeX for you. What's a prem? – Gerry Myerson Aug 4 '11 at 2:01
@Gerry Myerson: My guess is it's a Maple function that stands for "pseudo-remainder". – hardmath Aug 4 '11 at 2:21
I am not familiar with this blog, how to make text display clearly – Walker Aug 4 '11 at 4:05
i press tab and $, it do not show code block – Walker Aug 4 '11 at 4:08 it is pseudo-remainder – Walker Aug 4 '11 at 5:11 ## 1 Answer 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. - i am near the answer y*z^6+2*y^2*z^4+5*y^3 the difference is my result have extra y^3 for all terms, why ? is the original algorithm missing a step ? – Walker Aug 4 '11 at 10:12 @user353573: Your algorithm probably should end one step earlier, because the variable$x$has already disappeared after the penultimate iteration. That leaves you with an extra factor of$y$only. That is the result of not cancelling that common factor$y\$ (that I did in the last step). Depending on what you do with the result, I don't know whether it is worth your while to work on that. Do what the customer wants! It may well be that there is some variation as to how to present the result. – Jyrki Lahtonen Aug 4 '11 at 10:22
even stop one step earlier, there is still a exta y, this y is accumulated in each iteration – Walker Aug 5 '11 at 1:16
@user353573: Yes, I said so. Your test result and the algorithm given to you don't match. Either you need to divide both LCG and LCR with their common factor before you use them or you are stuck with this result. – Jyrki Lahtonen Aug 5 '11 at 7:09
you are right however, common factor of LCG y^2 and LCR -2*y^4*z is y^2, i divide y^2 is wrong, should be y^3, would you mind tell the correct algorithm of prem? – Walker Aug 5 '11 at 9:26