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

3

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.

  • 0
    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 ?2011-08-04
  • 0
    @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.2011-08-04
  • 0
    even stop one step earlier, there is still a exta y, this y is accumulated in each iteration2011-08-05
  • 0
    @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.2011-08-05
  • 0
    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?2011-08-05
  • 0
    In the previous round they have a common factor $y$, too. I don't know what the correct algorithm would be. For some purposes the extra factor may not matter. For example, if you treat these as polynomials in $x$ with coefficients from the *field* $\mathbf{C}(y,z)$, then $y$ becomes a unit and won't matter as an extra factor. In another application it may be necessary to get rid of these extra factors. But they may be there to begin with, and in those cases you shouldn't. I have not seen a **definition** of prem, so I cannot tell what you should do.2011-08-05
  • 0
    i find the bugs existing in my program Lead Coefficient and multiply_list, after comparing with maple program, it is correct now. the algorithm is correct. It is my fault. Thanks2011-08-06