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