Advanced Search

Question: Getting Wrong sub-reslutant terms when Implementing Subresultant p.r.s. algorithm for calculating GCD,

Question:Getting Wrong sub-reslutant terms when Implementing Subresultant p.r.s. algorithm for calculating GCD,

ddwuz 15 Maple
programming gcd
November 10 2016
1

I am trying to implement Subresultant p.r.s. algorithm for calculating greatest common divisor. The algorithm decribed in the book:

My code return the correct GCD, however the sub-resultant terms are different from the result of the built-in function. The last term a[i-1] is huge and involves fractions. I think my implementation is same as the algorithm described in the textbook.

I have attached the file. Could anybody spot anything wrong in the code? Why do fractions still appear? In my code, "lsr" is last subresultant term returned from the built-in function, the second one is my result.

with(RegularChains);

[Chain, ChangeOfOrder, Construct, Cut, DahanSchostTransform, Dimension, Empty, EqualSaturatedIdeals, EquiprojectableDecomposition, Extend, ExtendedNormalizedGcd, IsAlgebraic, IsEmptyChain, IsInRadical, IsInSaturate, IsIncluded, IsPrimitive, IsStronglyNormalized, IsZeroDimensional, IteratedResultant, LastSubresultant, Lift, ListConstruct, NormalizeRegularChain, NumberOfSolutions, Polynomial, Regularize, RemoveRedundantComponents, SeparateSolutions, Squarefree, SquarefreeFactorization, SubresultantChain, SubresultantOfIndex, Under, Upper]

 (1)

A42vlastsub := proc (f, g) local i, a, dt, bt, om; i := 1; if degree(f) < degree(g) then a[0] := primpart(g, x); a[1] := primpart(f, x) else a[0] := primpart(f, x); a[1] := primpart(g, x) end if; dt[0] := degree(a[0])-degree(a[1]); bt[2] := (-1)^(dt[0]+1); om[2] := -1; while a[i] <> 0 do a[i+1] := normal(prem(a[i-1], a[i], x)/bt[i+1]); dt[i] := degree(a[i])-degree(a[i+1]); i := i+1; om[i+1] := (-lcoeff(a[i-1]))^dt[i-2]*om[i]^(1-dt[i-2]); bt[i+1] := -lcoeff(a[i-1])*om[i+1]^dt[i-1] end do; return a[i-1] end proc;

 

 (2)

f := (y^2-1)*((y+1)*x^4+(y^2-1)*x^3+(y^3-1)*x^2+(y^4-1)*x+y^5-1);

(y-1)*x^5+(y^2-1)*x^4+(y^3-1)*x^3+(y^4-1)*x^2+(y^5-1)*x+y^6-1

 (3)

R := RegularChains:-PolynomialRing([y, x]);

subresultant_chain

 (4)

lsr := LastSubresultant(src, R);

y^25+y^24+2*y^23+4*y^22+8*y^21+16*y^20+46*y^19+160*y^18+402*y^17+808*y^16+1384*y^15+2080*y^14+2932*y^13+3762*y^12+4406*y^11+4740*y^10+4720*y^9+4400*y^8+3810*y^7+2968*y^6+2102*y^5+1360*y^4+800*y^3+400*y^2+139*y+21

 (5)

``

mylastsr := A42vlastsub(primpart(f, x), primpart(g, x));

-(35867/3794275180128377091639574036764685364535950857523710002444946112771297432041422848)*y^9-(10309/7588550360256754183279148073529370729071901715047420004889892225542594864082845696)*y^8-(2889061/60708402882054033466233184588234965832575213720379360039119137804340758912662765568)*y^10-(94304133/60708402882054033466233184588234965832575213720379360039119137804340758912662765568)*y^13-(35600337/60708402882054033466233184588234965832575213720379360039119137804340758912662765568)*y^12-(11265153/60708402882054033466233184588234965832575213720379360039119137804340758912662765568)*y^11-(4325932673/60708402882054033466233184588234965832575213720379360039119137804340758912662765568)*y^21-(3534515779/60708402882054033466233184588234965832575213720379360039119137804340758912662765568)*y^20-(2703789263/60708402882054033466233184588234965832575213720379360039119137804340758912662765568)*y^19-(1929251163/60708402882054033466233184588234965832575213720379360039119137804340758912662765568)*y^18-(1277273509/60708402882054033466233184588234965832575213720379360039119137804340758912662765568)*y^17-(778538921/60708402882054033466233184588234965832575213720379360039119137804340758912662765568)*y^16-(432069123/60708402882054033466233184588234965832575213720379360039119137804340758912662765568)*y^15-(215109057/60708402882054033466233184588234965832575213720379360039119137804340758912662765568)*y^14-(5255652033/60708402882054033466233184588234965832575213720379360039119137804340758912662765568)*y^25-(5374732281/60708402882054033466233184588234965832575213720379360039119137804340758912662765568)*y^23-(5474736805/60708402882054033466233184588234965832575213720379360039119137804340758912662765568)*y^24-(4971065401/60708402882054033466233184588234965832575213720379360039119137804340758912662765568)*y^22-(475/3794275180128377091639574036764685364535950857523710002444946112771297432041422848)*y^7-(21/3794275180128377091639574036764685364535950857523710002444946112771297432041422848)*y^6-(332387607/30354201441027016733116592294117482916287606860189680019559568902170379456331382784)*y^32-(1/60708402882054033466233184588234965832575213720379360039119137804340758912662765568)*y^49-(23/60708402882054033466233184588234965832575213720379360039119137804340758912662765568)*y^48-(251/60708402882054033466233184588234965832575213720379360039119137804340758912662765568)*y^47-(1735/60708402882054033466233184588234965832575213720379360039119137804340758912662765568)*y^46-(8571/60708402882054033466233184588234965832575213720379360039119137804340758912662765568)*y^45-(32463/60708402882054033466233184588234965832575213720379360039119137804340758912662765568)*y^44-(99205/60708402882054033466233184588234965832575213720379360039119137804340758912662765568)*y^43-(255999/60708402882054033466233184588234965832575213720379360039119137804340758912662765568)*y^42-(586005/60708402882054033466233184588234965832575213720379360039119137804340758912662765568)*y^41-(1263605/60708402882054033466233184588234965832575213720379360039119137804340758912662765568)*y^40-(2747253/60708402882054033466233184588234965832575213720379360039119137804340758912662765568)*y^39-(6322305/60708402882054033466233184588234965832575213720379360039119137804340758912662765568)*y^38-(15325169/60708402882054033466233184588234965832575213720379360039119137804340758912662765568)*y^37-(37286331/60708402882054033466233184588234965832575213720379360039119137804340758912662765568)*y^36-(86630947/60708402882054033466233184588234965832575213720379360039119137804340758912662765568)*y^35-(186556683/60708402882054033466233184588234965832575213720379360039119137804340758912662765568)*y^34-(92016457/15177100720513508366558296147058741458143803430094840009779784451085189728165691392)*y^33-(275974877/15177100720513508366558296147058741458143803430094840009779784451085189728165691392)*y^31-(847698927/30354201441027016733116592294117482916287606860189680019559568902170379456331382784)*y^30-(1210953247/30354201441027016733116592294117482916287606860189680019559568902170379456331382784)*y^29-(1616246617/30354201441027016733116592294117482916287606860189680019559568902170379456331382784)*y^28-(505494959/7588550360256754183279148073529370729071901715047420004889892225542594864082845696)*y^27-(2376326883/30354201441027016733116592294117482916287606860189680019559568902170379456331382784)*y^26

 (6)

``


 

Download subresultant.mw
Please Wait...