001/* 002 * $Id: GCDHenselTest.java 4377 2013-04-26 15:21:21Z kredel $ 003 */ 004 005package edu.jas.ufd; 006 007 008//import java.util.Map; 009 010import org.apache.log4j.BasicConfigurator; 011 012import junit.framework.Test; 013import junit.framework.TestCase; 014import junit.framework.TestSuite; 015 016import edu.jas.arith.BigInteger; 017import edu.jas.arith.ModInteger; 018import edu.jas.poly.ExpVector; 019import edu.jas.poly.GenPolynomial; 020import edu.jas.poly.GenPolynomialRing; 021import edu.jas.poly.PolyUtil; 022import edu.jas.poly.TermOrder; 023 024 025/** 026 * GCD Hensel algorithm tests with JUnit. 027 * @author Heinz Kredel. 028 */ 029 030public 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 GreatestCommonDivisorAbstract<BigInteger> ufd; 060 061 062 GreatestCommonDivisorAbstract<BigInteger> ufd1; 063 064 065 TermOrder to = new TermOrder(TermOrder.INVLEX); 066 067 068 GenPolynomialRing<BigInteger> dfac; 069 070 071 BigInteger cofac; 072 073 074 BigInteger ai; 075 076 077 BigInteger bi; 078 079 080 BigInteger ci; 081 082 083 BigInteger di; 084 085 086 BigInteger ei; 087 088 089 GenPolynomial<BigInteger> a; 090 091 092 GenPolynomial<BigInteger> b; 093 094 095 GenPolynomial<BigInteger> c; 096 097 098 GenPolynomial<BigInteger> d; 099 100 101 GenPolynomial<BigInteger> e; 102 103 104 GenPolynomial<BigInteger> ac; 105 106 107 GenPolynomial<BigInteger> bc; 108 109 110 GenPolynomial<GenPolynomial<BigInteger>> ar; 111 112 113 GenPolynomial<GenPolynomial<BigInteger>> br; 114 115 116 GenPolynomial<GenPolynomial<BigInteger>> cr; 117 118 119 GenPolynomial<GenPolynomial<BigInteger>> dr; 120 121 122 GenPolynomial<GenPolynomial<BigInteger>> er; 123 124 125 GenPolynomial<GenPolynomial<BigInteger>> arc; 126 127 128 GenPolynomial<GenPolynomial<BigInteger>> brc; 129 130 131 int rl = 3; 132 String [] vars = { "x", "y", "z" }; 133 134 135 int kl = 4; 136 137 138 int ll = 5; 139 140 141 int el = 4; //3; 142 143 144 float q = 0.3f; 145 146 147 @Override 148 protected void setUp() { 149 a = b = c = d = e = null; 150 ai = bi = ci = di = ei = null; 151 ar = br = cr = dr = er = null; 152 cofac = new BigInteger(); 153 ufd = new GreatestCommonDivisorHensel<ModInteger>(); 154 dfac = new GenPolynomialRing<BigInteger>(cofac, rl, to, vars); 155 } 156 157 158 @Override 159 protected void tearDown() { 160 a = b = c = d = e = null; 161 ai = bi = ci = di = ei = null; 162 ar = br = cr = dr = er = null; 163 ufd = null; 164 dfac = null; 165 } 166 167 168 /** 169 * Test Hensel algorithm gcd. 170 */ 171 public void testHenselGcd() { 172 //GenPolynomialRing<BigInteger> dfac = new GenPolynomialRing<BigInteger>(cofac, rl, to); 173 for (int i = 0; i < 1; i++) { 174 a = dfac.random(kl, ll + i, el + i, q); 175 b = dfac.random(kl, ll + i, el + i, q); 176 c = dfac.random(kl, ll + i, el + i, q); 177 c = c.multiply(dfac.univariate(0)); 178 //a = ufd.basePrimitivePart(a); 179 //b = ufd.basePrimitivePart(b); 180 ExpVector ev = c.leadingExpVector(); 181 if ( ev != null ) { 182 c.doPutToMap(ev,dfac.coFac.getONE()); 183 } 184 185 if (a.isZERO() || b.isZERO() || c.isZERO()) { 186 // skip for this turn 187 continue; 188 } 189 assertTrue("length( c" + i + " ) <> 0", c.length() > 0); 190 //System.out.println("a = " + a); 191 //System.out.println("b = " + b); 192 //System.out.println("c = " + c); 193 194 a = a.multiply(c); //.multiply(c); 195 b = b.multiply(c); 196 //System.out.println("a c = " + a); 197 //System.out.println("b c = " + b); 198 199 d = ufd.gcd(a, b); 200 //d = ufd.baseGcd(a,b); 201 202 c = ufd.basePrimitivePart(c).abs(); 203 e = PolyUtil.<BigInteger> basePseudoRemainder(d, c); 204 //System.out.println("c = " + c); 205 //System.out.println("d = " + d); 206 //System.out.println("e = " + e); 207 assertTrue("c | gcd(ac,bc): " + d + ", c = " + c, e.isZERO()); 208 209 e = PolyUtil.<BigInteger> basePseudoRemainder(a, d); 210 //System.out.println("e = " + e); 211 assertTrue("gcd(a,b) | a: " + e + ", d = " + d, e.isZERO()); 212 213 e = PolyUtil.<BigInteger> basePseudoRemainder(b, d); 214 //System.out.println("e = " + e); 215 assertTrue("gcd(a,b) | b: " + e + ", d = " + d, e.isZERO()); 216 } 217 } 218 219 220 /** 221 * Test linear Hensel algorithm gcd. 222 */ 223 public void ytestHenselLinearSubresGcd() { 224 ufd1 = new GreatestCommonDivisorHensel<ModInteger>(false); 225 //GenPolynomialRing<BigInteger> dfac = new GenPolynomialRing<BigInteger>(cofac, rl, to); 226 227 for (int i = 0; i < 1; i++) { 228 a = dfac.random(kl, ll + i, el + i, q); 229 b = dfac.random(kl, ll + i, el + i, q); 230 c = dfac.random(kl, ll + i, el + i, q); 231 c = c.multiply(dfac.univariate(0)); 232 //a = ufd.basePrimitivePart(a); 233 //b = ufd.basePrimitivePart(b); 234 ExpVector ev = c.leadingExpVector(); 235 if ( ev != null ) { 236 c.doPutToMap(ev,dfac.coFac.getONE()); 237 } 238 239 if (a.isZERO() || b.isZERO() || c.isZERO()) { 240 // skip for this turn 241 continue; 242 } 243 assertTrue("length( c" + i + " ) <> 0", c.length() > 0); 244 //System.out.println("a = " + a); 245 //System.out.println("b = " + b); 246 //System.out.println("c = " + c); 247 248 a = a.multiply(c); //.multiply(c); 249 b = b.multiply(c); 250 //System.out.println("a c = " + a); 251 //System.out.println("b c = " + b); 252 253 long t = System.currentTimeMillis(); 254 d = ufd1.gcd(a, b); 255 t = System.currentTimeMillis() - t; 256 //d = ufd.baseGcd(a,b); 257 258 long tq = System.currentTimeMillis(); 259 e = ufd.gcd(a,b); 260 tq = System.currentTimeMillis() - tq; 261 //System.out.println("Hensel quadratic, time = " + tq); 262 //System.out.println("Hensel linear, time = " + t); 263 264 c = ufd.basePrimitivePart(c).abs(); 265 e = PolyUtil.<BigInteger> basePseudoRemainder(d, c); 266 //System.out.println("c = " + c); 267 //System.out.println("d = " + d); 268 //System.out.println("e = " + e); 269 assertTrue("c | gcd(ac,bc): " + d + ", c = " + c, e.isZERO()); 270 271 e = PolyUtil.<BigInteger> basePseudoRemainder(a, d); 272 //System.out.println("e = " + e); 273 assertTrue("gcd(a,b) | a: " + e + ", d = " + d, e.isZERO()); 274 275 e = PolyUtil.<BigInteger> basePseudoRemainder(b, d); 276 //System.out.println("e = " + e); 277 assertTrue("gcd(a,b) | b: " + e + ", d = " + d, e.isZERO()); 278 } 279 } 280 281 282 /** 283 * Test Hensel gcd 3 variables. 284 */ 285 public void testHenselGCD3() { 286 BigInteger ifa = new BigInteger(1); 287 //dfac = new GenPolynomialRing<BigInteger>(ifa, 2, to , new String[] {"x", "y" }); 288 dfac = new GenPolynomialRing<BigInteger>(ifa, 3, to , new String[] { "x" , "y", "z" }); 289 290 for (int i = 0; i < 1; i++) { 291 a = dfac.random(kl, ll, el + i, q); 292 b = dfac.random(kl, ll, el, q); 293 c = dfac.random(kl, ll, el, q); 294 // make monic and c with univariate head term 295 ExpVector ev = a.leadingExpVector(); 296 if ( ev != null ) { 297 a.doPutToMap(ev,ifa.getONE()); 298 } 299 ev = b.leadingExpVector(); 300 if ( ev != null ) { 301 b.doPutToMap(ev,ifa.getONE()); 302 } 303 ev = c.leadingExpVector(); 304 if ( ev != null ) { 305 //c.doPutToMap(ev,ifa.getONE()); 306 } 307 assertFalse("ev == null ", ev == null); 308 if ( ev.dependencyOnVariables().length > 1 ) { 309 c = dfac.univariate(1); //getONE(); 310 } 311 //a = dfac.parse(" y^2 + 2 x y - 3 y + x^2 - 3 x - 4 "); 312 //b = dfac.parse(" y^2 + 2 x y + 5 y + x^2 + 5 x + 4 "); 313 //a = dfac.parse(" x + 2 y + z^2 + 5 "); 314 //b = dfac.parse(" x - y - 3 + y z "); 315 //c = dfac.parse(" x y + z^2 + y "); 316 //a = dfac.parse("7 y^4 - (35 x^3 - 32) y^3 - 160 x^3 y^2 + (105 x^2 - 119) y + (480 x^2 - 544) "); 317 //b = dfac.parse(" 7 y^4 + 39 y^3 + 32 y^2 "); 318 //c = dfac.parse(" 7 y + 32 "); 319 320 //a = dfac.parse(" ( -13 x^2 ) z^5 + ( 182 x^2 - 143 ) z^3 - ( x^2 * y^3 - 8 x^2 ) z^2 + ( 14 x^2 * y^3 - 11 y^3 - 112 x^2 + 88 ) "); 321 //b = dfac.parse(" ( -13 x^3 * y^3 ) z^6 + ( 65 y ) z^4 - ( x^3 * y^6 - 8 x^3 * y^3 - 52 y^3 - 195 y + 156 ) z^3 + ( 5 y^4 - 40 y ) z + ( 4 y^6 + 15 y^4 - 44 y^3 - 120 y + 96 ) ) "); 322 //c = dfac.parse(" 13 z^3 + y^3 - 8 "); 323 324 //a = dfac.parse(" 3 z^3 + ( 4 y^2 + 25 x^3 + 16 x^2 + 25 ) z^2 - ( 84 y^4 - 22 x^3 * y^2 + 128 x^2 * y^2 + 138 y^2 - 52 x^6 - 71 x^5 + 35 x^4 - 109 x^3 + 59 x^2 + 18 ) z "); 325 //b = dfac.parse(" 10 z^5 + ( 60 y^2 + 40 x^3 + 70 x^2 + 90 ) z^4 + ( 14 x + 3 ) z^2 + ( 84 x * y^2 + 18 y^2 + 56 x^4 + 110 x^3 + 21 x^2 + 126 x + 27 ) z "); 326 //c = dfac.parse("z^2 + ( 6 y^2 + 4 x^3 + 7 x^2 + 9 ) z"); 327 328 //a = a.abs(); 329 //b = b.abs(); 330 //c = c.abs(); 331 //System.out.println("a = " + a); 332 //System.out.println("b = " + b); 333 //System.out.println("c = " + c); 334 if (a.isZERO() || b.isZERO() || c.isZERO()) { 335 // skip for this turn 336 continue; 337 } 338 339 a = a.multiply(c); 340 b = b.multiply(c); 341 //System.out.println("a = " + a); 342 //System.out.println("b = " + b); 343 344 d = ufd.gcd(a, b); 345 e = PolyUtil.<BigInteger> basePseudoRemainder(d, c); 346 //System.out.println("e = " + e); 347 //System.out.println("d = " + d); 348 //System.out.println("c = " + c); 349 assertTrue("c | gcd(ac,bc) " + e + ", d = " + d, e.isZERO()); 350 } 351 } 352 353}