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 F_list = get_list(F); List result_list = new List(); 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 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; }