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