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