001 /*
002 * $Id: GCDHenselTest.java 3538 2011-02-18 19:53:41Z kredel $
003 */
004
005 package edu.jas.ufd;
006
007
008 //import java.util.Map;
009
010 import org.apache.log4j.BasicConfigurator;
011
012 import junit.framework.Test;
013 import junit.framework.TestCase;
014 import junit.framework.TestSuite;
015
016 import edu.jas.arith.BigInteger;
017 import edu.jas.arith.ModInteger;
018 import edu.jas.poly.ExpVector;
019 import edu.jas.poly.GenPolynomial;
020 import edu.jas.poly.GenPolynomialRing;
021 import edu.jas.poly.PolyUtil;
022 import edu.jas.poly.TermOrder;
023
024
025 /**
026 * GCD Hensel algorithm tests with JUnit.
027 * @author Heinz Kredel.
028 */
029
030 public class GCDHenselTest extends TestCase {
031
032
033 /**
034 * main.
035 */
036 public static void main(String[] args) {
037 BasicConfigurator.configure();
038 junit.textui.TestRunner.run(suite());
039 }
040
041
042 /**
043 * Constructs a <CODE>GCDHenselTest</CODE> object.
044 * @param name String.
045 */
046 public GCDHenselTest(String name) {
047 super(name);
048 }
049
050
051 /**
052 */
053 public static Test suite() {
054 TestSuite suite = new TestSuite(GCDHenselTest.class);
055 return suite;
056 }
057
058
059 //private final static int bitlen = 100;
060
061 GreatestCommonDivisorAbstract<BigInteger> ufd;
062
063
064 GreatestCommonDivisorAbstract<BigInteger> ufd1;
065
066
067 TermOrder to = new TermOrder(TermOrder.INVLEX);
068
069
070 GenPolynomialRing<BigInteger> dfac;
071
072
073 GenPolynomialRing<BigInteger> cfac;
074
075
076 GenPolynomialRing<GenPolynomial<BigInteger>> rfac;
077
078
079 //PrimeList primes = new PrimeList();
080
081 BigInteger cofac;
082
083
084 BigInteger ai;
085
086
087 BigInteger bi;
088
089
090 BigInteger ci;
091
092
093 BigInteger di;
094
095
096 BigInteger ei;
097
098
099 GenPolynomial<BigInteger> a;
100
101
102 GenPolynomial<BigInteger> b;
103
104
105 GenPolynomial<BigInteger> c;
106
107
108 GenPolynomial<BigInteger> d;
109
110
111 GenPolynomial<BigInteger> e;
112
113
114 GenPolynomial<BigInteger> ac;
115
116
117 GenPolynomial<BigInteger> bc;
118
119
120 GenPolynomial<GenPolynomial<BigInteger>> ar;
121
122
123 GenPolynomial<GenPolynomial<BigInteger>> br;
124
125
126 GenPolynomial<GenPolynomial<BigInteger>> cr;
127
128
129 GenPolynomial<GenPolynomial<BigInteger>> dr;
130
131
132 GenPolynomial<GenPolynomial<BigInteger>> er;
133
134
135 GenPolynomial<GenPolynomial<BigInteger>> arc;
136
137
138 GenPolynomial<GenPolynomial<BigInteger>> brc;
139
140
141 int rl = 3;
142
143
144 int kl = 4;
145
146
147 int ll = 5;
148
149
150 int el = 4; //3;
151
152
153 float q = 0.3f;
154
155
156 @Override
157 protected void setUp() {
158 a = b = c = d = e = null;
159 ai = bi = ci = di = ei = null;
160 ar = br = cr = dr = er = null;
161 cofac = new BigInteger();
162 ufd = new GreatestCommonDivisorHensel<ModInteger>();
163 dfac = new GenPolynomialRing<BigInteger>(cofac, rl, to);
164 cfac = new GenPolynomialRing<BigInteger>(cofac, rl - 1, to);
165 rfac = new GenPolynomialRing<GenPolynomial<BigInteger>>(cfac, 1, to);
166 }
167
168
169 @Override
170 protected void tearDown() {
171 a = b = c = d = e = null;
172 ai = bi = ci = di = ei = null;
173 ar = br = cr = dr = er = null;
174 ufd = null;
175 dfac = null;
176 cfac = null;
177 rfac = null;
178 }
179
180
181 /**
182 * Test univariate Hensel algorithm gcd with subres PRS recursive algorithm.
183 */
184 public void testHenselSubresGcd() {
185
186 GenPolynomial<BigInteger> a;
187 GenPolynomial<BigInteger> b;
188 GenPolynomial<BigInteger> c;
189 GenPolynomial<BigInteger> d;
190 GenPolynomial<BigInteger> e;
191
192 GenPolynomialRing<BigInteger> dfac = new GenPolynomialRing<BigInteger>(cofac, rl, to);
193
194 for (int i = 0; i < 1; i++) {
195 a = dfac.random(kl, ll + i, el + i, q);
196 b = dfac.random(kl, ll + i, el + i, q);
197 c = dfac.random(kl, ll + i, el + i, q);
198 c = c.multiply(dfac.univariate(0));
199 //a = ufd.basePrimitivePart(a);
200 //b = ufd.basePrimitivePart(b);
201
202 if (a.isZERO() || b.isZERO() || c.isZERO()) {
203 // skip for this turn
204 continue;
205 }
206 assertTrue("length( c" + i + " ) <> 0", c.length() > 0);
207 //assertTrue(" not isZERO( c"+i+" )", !c.isZERO() );
208 //assertTrue(" not isONE( c"+i+" )", !c.isONE() );
209
210 //System.out.println("a = " + a);
211 //System.out.println("b = " + b);
212 //System.out.println("c = " + c);
213
214 a = a.multiply(c); //.multiply(c);
215 b = b.multiply(c);
216
217 //System.out.println("a c = " + a);
218 //System.out.println("b c = " + b);
219
220 d = ufd.gcd(a, b);
221 //d = ufd.baseGcd(a,b);
222
223 c = ufd.basePrimitivePart(c).abs();
224 e = PolyUtil.<BigInteger> basePseudoRemainder(d, c);
225 //System.out.println("c = " + c);
226 //System.out.println("d = " + d);
227 //System.out.println("e = " + e);
228
229 assertTrue("c | gcd(ac,bc): " + d + ", c = " + c, e.isZERO());
230
231 e = PolyUtil.<BigInteger> basePseudoRemainder(a, d);
232 //System.out.println("e = " + e);
233 assertTrue("gcd(a,b) | a: " + e, e.isZERO());
234
235 e = PolyUtil.<BigInteger> basePseudoRemainder(b, d);
236 //System.out.println("e = " + e);
237 assertTrue("gcd(a,b) | b: " + e, e.isZERO());
238 }
239 }
240
241
242 /**
243 * Test univariate linear Hensel algorithm gcd with subres PRS recursive
244 * algorithm.
245 */
246 public void testHenselLinearSubresGcd() {
247
248 ufd1 = new GreatestCommonDivisorHensel<ModInteger>(false);
249
250 GenPolynomial<BigInteger> a;
251 GenPolynomial<BigInteger> b;
252 GenPolynomial<BigInteger> c;
253 GenPolynomial<BigInteger> d;
254 GenPolynomial<BigInteger> e;
255
256 GenPolynomialRing<BigInteger> dfac = new GenPolynomialRing<BigInteger>(cofac, rl, to);
257
258 for (int i = 0; i < 1; i++) {
259 a = dfac.random(kl, ll + i, el + i, q);
260 b = dfac.random(kl, ll + i, el + i, q);
261 c = dfac.random(kl, ll + i, el + i, q);
262 c = c.multiply(dfac.univariate(0));
263 //a = ufd.basePrimitivePart(a);
264 //b = ufd.basePrimitivePart(b);
265
266 if (a.isZERO() || b.isZERO() || c.isZERO()) {
267 // skip for this turn
268 continue;
269 }
270 assertTrue("length( c" + i + " ) <> 0", c.length() > 0);
271 //assertTrue(" not isZERO( c"+i+" )", !c.isZERO() );
272 //assertTrue(" not isONE( c"+i+" )", !c.isONE() );
273
274 //System.out.println("a = " + a);
275 //System.out.println("b = " + b);
276 //System.out.println("c = " + c);
277
278 a = a.multiply(c); //.multiply(c);
279 b = b.multiply(c);
280
281 //System.out.println("a c = " + a);
282 //System.out.println("b c = " + b);
283
284 long t = System.currentTimeMillis();
285 d = ufd1.gcd(a, b);
286 t = System.currentTimeMillis() - t;
287 //d = ufd.baseGcd(a,b);
288
289 long tq = System.currentTimeMillis();
290 //e = ufd.gcd(a,b);
291 tq = System.currentTimeMillis() - tq;
292
293
294 //System.out.println("Hensel quadratic, time = " + tq);
295 //System.out.println("Hensel linear, time = " + t);
296
297 c = ufd.basePrimitivePart(c).abs();
298 e = PolyUtil.<BigInteger> basePseudoRemainder(d, c);
299 //System.out.println("c = " + c);
300 //System.out.println("d = " + d);
301 //System.out.println("e = " + e);
302
303 assertTrue("c | gcd(ac,bc): " + d + ", c = " + c, e.isZERO());
304
305 e = PolyUtil.<BigInteger> basePseudoRemainder(a, d);
306 //System.out.println("e = " + e);
307 assertTrue("gcd(a,b) | a: " + e, e.isZERO());
308
309 e = PolyUtil.<BigInteger> basePseudoRemainder(b, d);
310 //System.out.println("e = " + e);
311 assertTrue("gcd(a,b) | b: " + e, e.isZERO());
312 }
313 }
314
315
316 /**
317 * Test Hensel gcd 3 variables.
318 *
319 */
320 public void testHenselGCD3() {
321 BigInteger ifa = new BigInteger(1);
322 //dfac = new GenPolynomialRing<BigInteger>(ifa, 2, to , new String[] {"x", "y" });
323 dfac = new GenPolynomialRing<BigInteger>(ifa, 3, to , new String[] { "x" , "y", "z" });
324
325 for (int i = 0; i < 1; i++) {
326 a = dfac.random(kl, ll, el + i, q);
327 b = dfac.random(kl, ll, el, q);
328 c = dfac.random(kl, ll, el, q);
329 // make monic and c with univariate head term
330 ExpVector ev = a.leadingExpVector();
331 if ( ev != null ) {
332 a.doPutToMap(ev,ifa.getONE());
333 }
334 ev = b.leadingExpVector();
335 if ( ev != null ) {
336 b.doPutToMap(ev,ifa.getONE());
337 }
338 ev = c.leadingExpVector();
339 if ( ev != null ) {
340 c.doPutToMap(ev,ifa.getONE());
341 }
342 if ( ev.dependencyOnVariables().length > 1 ) {
343 c = dfac.univariate(1); //getONE();
344 }
345 //a = dfac.parse(" y^2 + 2 x y - 3 y + x^2 - 3 x - 4 ");
346 //b = dfac.parse(" y^2 + 2 x y + 5 y + x^2 + 5 x + 4 ");
347 //a = dfac.parse(" x + 2 y + z^2 + 5 ");
348 //b = dfac.parse(" x - y - 3 + y z ");
349 //c = dfac.parse(" x y + z^2 + y ");
350 //System.out.println("a = " + a);
351 //System.out.println("b = " + b);
352 //System.out.println("c = " + c);
353
354 if (a.isZERO() || b.isZERO() || c.isZERO()) {
355 // skip for this turn
356 continue;
357 }
358 //assertTrue(" not isZERO( c"+i+" )", !c.isZERO() );
359
360 a = a.multiply(c);
361 b = b.multiply(c);
362 //System.out.println("a = " + a);
363 //System.out.println("b = " + b);
364
365 d = ufd.gcd(a, b);
366 e = PolyUtil.<BigInteger> basePseudoRemainder(d, c);
367 //System.out.println("e = " + e);
368 //System.out.println("d = " + d);
369 //System.out.println("c = " + c);
370 assertTrue("c | gcd(ac,bc) " + e, e.isZERO());
371 }
372 }
373
374 }