2
$\begingroup$

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;     } 
  • 2
    Unreadable. If it weren't so long, I'd edit it into TeX for you. What's a prem?2011-08-04
  • 1
    @Gerry Myerson: My guess is [it's a Maple function](http://www.maplesoft.com/support/help/Maple/view.aspx?path=Prem) that stands for "pseudo-remainder".2011-08-04
  • 0
    @hardmath, thanks, but now I have to ask, what's a pseudo-remainder?2011-08-04
  • 2
    I am not familiar with this blog, how to make text display clearly2011-08-04
  • 1
    i press tab and $, it do not show code block2011-08-04
  • 1
    it is pseudo-remainder2011-08-04
  • 0
    I've edited the very first bit of math into TeX, maybe that will help you see how to do the rest. So, what's a pseudo-remainder?2011-08-04
  • 1
    I've fixed the formatting for you. You have to describe your problem, and also the algorithm you're using. If there's something in the algorithm you don't understand, someone may be able to clarify. But if your actual question is just "please debug my code", then this is not the right website.2011-08-04
  • 0
    Or another way: where exactly did you obtain your "algorithm" for [pseudodivision](http://dx.doi.org/10.1093/comjnl/20.2.178)?2011-08-04
  • 0
    If LC stands for *leading coefficient*, then I think that it should be a polynomial in $y$ and $z$, because only $x$ is treated as a variable. Provided that my pseudoanswer to pseudodivision is even in the ballpark.2011-08-04
  • 0
    Again: if you wrote those pieces of code, where, oh where, did you copy the algorithm from?2011-08-04
  • 0
    @Jyrki: Likely true; in what I've seen, polynomials are rendered monic before pseudodividing, and then the appropriate multiplier is multiplied back in after the algorithm halts.2011-08-04
  • 0
    Ok, I tried to peruse your code. A polynomial is a *string*????! Anyway, the LC-subroutine (at least) looks suspicious. It should return a string as the leading coefficient is a polynomial in the other variables. It is not of type `double'. It should return a list of terms.2011-08-04
  • 0
    Good. You notice that your answer can be obtained from the target one by multiplying it with $y^3$. So the remaining problem comes from the cancellation of the common factors of the leading coefficients. It is probably something like the difference between prem and sprem behind the Maple link from Hardmath's comment.2011-08-04

1 Answers 1