001/* 002 * $Id$ 003 */ 004 005package edu.jas.ufd; 006 007 008import edu.jas.arith.BigInteger; 009import edu.jas.arith.ModInteger; 010import edu.jas.poly.ExpVector; 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 * GCD Hensel algorithm tests with JUnit. 023 * @author Heinz Kredel 024 */ 025 026public class GCDHenselTest 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>GCDHenselTest</CODE> object. 039 * @param name String. 040 */ 041 public GCDHenselTest(String name) { 042 super(name); 043 } 044 045 046 /** 047 */ 048 public static Test suite() { 049 TestSuite suite = new TestSuite(GCDHenselTest.class); 050 return suite; 051 } 052 053 054 GreatestCommonDivisorAbstract<BigInteger> ufd; 055 056 057 GreatestCommonDivisorAbstract<BigInteger> ufd1; 058 059 060 TermOrder to = new TermOrder(TermOrder.INVLEX); 061 062 063 GenPolynomialRing<BigInteger> dfac; 064 065 066 BigInteger cofac; 067 068 069 //BigInteger ai, bi, ci, di, ei; 070 071 072 GenPolynomial<BigInteger> a; 073 074 075 GenPolynomial<BigInteger> b; 076 077 078 GenPolynomial<BigInteger> c; 079 080 081 GenPolynomial<BigInteger> d; 082 083 084 GenPolynomial<BigInteger> e; 085 086 087 GenPolynomial<BigInteger> ac; 088 089 090 GenPolynomial<BigInteger> bc; 091 092 093 GenPolynomial<GenPolynomial<BigInteger>> ar, br, cr, dr, er; 094 095 096 int rl = 3; 097 098 099 String[] vars = { "x", "y", "z" }; 100 101 102 int kl = 4; 103 104 105 int ll = 5; 106 107 108 int el = 4; //3; 109 110 111 float q = 0.3f; 112 113 114 @Override 115 protected void setUp() { 116 a = b = c = d = e = null; 117 //ai = bi = ci = di = ei = null; 118 //ar = br = cr = dr = er = null; 119 cofac = new BigInteger(); 120 ufd = new GreatestCommonDivisorHensel<ModInteger>(); 121 dfac = new GenPolynomialRing<BigInteger>(cofac, rl, to, vars); 122 } 123 124 125 @Override 126 protected void tearDown() { 127 a = b = c = d = e = null; 128 //ai = bi = ci = di = ei = null; 129 //ar = br = cr = dr = er = null; 130 ufd = null; 131 dfac = null; 132 } 133 134 135 /** 136 * Test Hensel algorithm gcd. 137 */ 138 public void testHenselGcd() { 139 //GenPolynomialRing<BigInteger> dfac = new GenPolynomialRing<BigInteger>(cofac, rl, to); 140 for (int i = 0; i < 1; i++) { 141 a = dfac.random(kl, ll + i, el + i, q); 142 b = dfac.random(kl, ll + i, el + i, q); 143 c = dfac.random(kl, ll + i, el + i, q); 144 c = c.multiply(dfac.univariate(0)); 145 //a = ufd.basePrimitivePart(a); 146 //b = ufd.basePrimitivePart(b); 147 ExpVector ev = c.leadingExpVector(); 148 if (ev != null) { 149 c.doPutToMap(ev, dfac.coFac.getONE()); 150 } 151 152 if (a.isZERO() || b.isZERO() || c.isZERO()) { 153 // skip for this turn 154 continue; 155 } 156 assertTrue("length( c" + i + " ) <> 0", c.length() > 0); 157 //System.out.println("a = " + a); 158 //System.out.println("b = " + b); 159 //System.out.println("c = " + c); 160 161 a = a.multiply(c); //.multiply(c); 162 b = b.multiply(c); 163 //System.out.println("a c = " + a); 164 //System.out.println("b c = " + b); 165 166 d = ufd.gcd(a, b); 167 //d = ufd.baseGcd(a,b); 168 169 c = ufd.basePrimitivePart(c).abs(); 170 e = PolyUtil.<BigInteger> baseSparsePseudoRemainder(d, c); 171 //System.out.println("c = " + c); 172 //System.out.println("d = " + d); 173 //System.out.println("e = " + e); 174 assertTrue("c | gcd(ac,bc): " + d + ", c = " + c, e.isZERO()); 175 176 e = PolyUtil.<BigInteger> baseSparsePseudoRemainder(a, d); 177 //System.out.println("e = " + e); 178 assertTrue("gcd(a,b) | a: " + e + ", d = " + d, e.isZERO()); 179 180 e = PolyUtil.<BigInteger> baseSparsePseudoRemainder(b, d); 181 //System.out.println("e = " + e); 182 assertTrue("gcd(a,b) | b: " + e + ", d = " + d, e.isZERO()); 183 } 184 } 185 186 187 /** 188 * Test linear Hensel algorithm gcd. 189 */ 190 public void ytestHenselLinearSubresGcd() { 191 ufd1 = new GreatestCommonDivisorHensel<ModInteger>(false); 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 ExpVector ev = c.leadingExpVector(); 202 if (ev != null) { 203 c.doPutToMap(ev, dfac.coFac.getONE()); 204 } 205 206 if (a.isZERO() || b.isZERO() || c.isZERO()) { 207 // skip for this turn 208 continue; 209 } 210 assertTrue("length( c" + i + " ) <> 0", c.length() > 0); 211 //System.out.println("a = " + a); 212 //System.out.println("b = " + b); 213 //System.out.println("c = " + c); 214 215 a = a.multiply(c); //.multiply(c); 216 b = b.multiply(c); 217 //System.out.println("a c = " + a); 218 //System.out.println("b c = " + b); 219 220 long t = System.currentTimeMillis(); 221 d = ufd1.gcd(a, b); 222 t = System.currentTimeMillis() - t; 223 //d = ufd.baseGcd(a,b); 224 225 long tq = System.currentTimeMillis(); 226 e = ufd.gcd(a, b); 227 tq = System.currentTimeMillis() - tq; 228 //System.out.println("Hensel quadratic, time = " + tq); 229 //System.out.println("Hensel linear, time = " + t); 230 231 c = ufd.basePrimitivePart(c).abs(); 232 e = PolyUtil.<BigInteger> baseSparsePseudoRemainder(d, c); 233 //System.out.println("c = " + c); 234 //System.out.println("d = " + d); 235 //System.out.println("e = " + e); 236 assertTrue("c | gcd(ac,bc): " + d + ", c = " + c, e.isZERO()); 237 238 e = PolyUtil.<BigInteger> baseSparsePseudoRemainder(a, d); 239 //System.out.println("e = " + e); 240 assertTrue("gcd(a,b) | a: " + e + ", d = " + d, e.isZERO()); 241 242 e = PolyUtil.<BigInteger> baseSparsePseudoRemainder(b, d); 243 //System.out.println("e = " + e); 244 assertTrue("gcd(a,b) | b: " + e + ", d = " + d, e.isZERO()); 245 } 246 } 247 248 249 /** 250 * Test Hensel gcd 3 variables. 251 */ 252 public void testHenselGCD3() { 253 BigInteger ifa = new BigInteger(1); 254 //dfac = new GenPolynomialRing<BigInteger>(ifa, 2, to , new String[] {"x", "y" }); 255 dfac = new GenPolynomialRing<BigInteger>(ifa, 3, to, new String[] { "x", "y", "z" }); 256 257 for (int i = 0; i < 1; i++) { 258 a = dfac.random(kl, ll, el + i, q); 259 b = dfac.random(kl, ll, el, q); 260 c = dfac.random(kl, ll, el, q); 261 // make monic and c with univariate head term 262 ExpVector ev = a.leadingExpVector(); 263 if (ev != null) { 264 a.doPutToMap(ev, ifa.getONE()); 265 } 266 ev = b.leadingExpVector(); 267 if (ev != null) { 268 b.doPutToMap(ev, ifa.getONE()); 269 } 270 ev = c.leadingExpVector(); 271 if (ev != null) { 272 //c.doPutToMap(ev,ifa.getONE()); 273 } 274 assertFalse("ev == null ", ev == null); 275 if (ev.dependencyOnVariables().length > 1) { 276 c = dfac.univariate(1); //getONE(); 277 } 278 //a = dfac.parse(" y^2 + 2 x y - 3 y + x^2 - 3 x - 4 "); 279 //b = dfac.parse(" y^2 + 2 x y + 5 y + x^2 + 5 x + 4 "); 280 //a = dfac.parse(" x + 2 y + z^2 + 5 "); 281 //b = dfac.parse(" x - y - 3 + y z "); 282 //c = dfac.parse(" x y + z^2 + y "); 283 //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) "); 284 //b = dfac.parse(" 7 y^4 + 39 y^3 + 32 y^2 "); 285 //c = dfac.parse(" 7 y + 32 "); 286 287 //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 ) "); 288 //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 ) ) "); 289 //c = dfac.parse(" 13 z^3 + y^3 - 8 "); 290 291 //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 "); 292 //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 "); 293 //c = dfac.parse("z^2 + ( 6 y^2 + 4 x^3 + 7 x^2 + 9 ) z"); 294 295 //a = a.abs(); 296 //b = b.abs(); 297 //c = c.abs(); 298 //System.out.println("a = " + a); 299 //System.out.println("b = " + b); 300 //System.out.println("c = " + c); 301 if (a.isZERO() || b.isZERO() || c.isZERO()) { 302 // skip for this turn 303 continue; 304 } 305 306 a = a.multiply(c); 307 b = b.multiply(c); 308 //System.out.println("a = " + a); 309 //System.out.println("b = " + b); 310 311 d = ufd.gcd(a, b); 312 e = PolyUtil.<BigInteger> baseSparsePseudoRemainder(d, c); 313 //System.out.println("e = " + e); 314 //System.out.println("d = " + d); 315 //System.out.println("c = " + c); 316 assertTrue("c | gcd(ac,bc) " + e + ", d = " + d, e.isZERO()); 317 } 318 } 319 320}