001/* 002 * $Id: PolyUfdUtilTest.java 4020 2012-07-22 19:19:51Z 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.BigRational; 014 015import edu.jas.kern.ComputerThreads; 016 017import edu.jas.poly.GenPolynomial; 018import edu.jas.poly.GenPolynomialRing; 019import edu.jas.poly.TermOrder; 020import edu.jas.poly.PolyUtil; 021 022 023/** 024 * PolyUfdUtil tests with JUnit. 025 * @author Heinz Kredel. 026 */ 027 028public class PolyUfdUtilTest extends TestCase { 029 030 031 /** 032 * main. 033 */ 034 public static void main(String[] args) { 035 //BasicConfigurator.configure(); 036 junit.textui.TestRunner.run(suite()); 037 ComputerThreads.terminate(); 038 } 039 040 041 /** 042 * Constructs a <CODE>PolyUtilTest</CODE> object. 043 * @param name String. 044 */ 045 public PolyUfdUtilTest(String name) { 046 super(name); 047 } 048 049 050 /** 051 */ 052 public static Test suite() { 053 TestSuite suite = new TestSuite(PolyUfdUtilTest.class); 054 return suite; 055 } 056 057 058 //private final static int bitlen = 100; 059 060 TermOrder to = new TermOrder(TermOrder.INVLEX); 061 062 063 GenPolynomialRing<BigInteger> dfac; 064 065 066 GenPolynomialRing<BigInteger> cfac; 067 068 069 GenPolynomialRing<GenPolynomial<BigInteger>> rfac; 070 071 072 BigInteger ai; 073 074 075 BigInteger bi; 076 077 078 BigInteger ci; 079 080 081 BigInteger di; 082 083 084 BigInteger ei; 085 086 087 GenPolynomial<BigInteger> a; 088 089 090 GenPolynomial<BigInteger> b; 091 092 093 GenPolynomial<BigInteger> c; 094 095 096 GenPolynomial<BigInteger> d; 097 098 099 GenPolynomial<BigInteger> e; 100 101 102 GenPolynomial<GenPolynomial<BigInteger>> ar; 103 104 105 GenPolynomial<GenPolynomial<BigInteger>> br; 106 107 108 GenPolynomial<GenPolynomial<BigInteger>> cr; 109 110 111 GenPolynomial<GenPolynomial<BigInteger>> dr; 112 113 114 GenPolynomial<GenPolynomial<BigInteger>> er; 115 116 117 int rl = 5; 118 119 120 int kl = 5; 121 122 123 int ll = 5; 124 125 126 int el = 3; 127 128 129 float q = 0.3f; 130 131 132 @Override 133 protected void setUp() { 134 a = b = c = d = e = null; 135 ai = bi = ci = di = ei = null; 136 dfac = new GenPolynomialRing<BigInteger>(new BigInteger(1), rl, to); 137 cfac = new GenPolynomialRing<BigInteger>(new BigInteger(1), rl - 1, to); 138 rfac = new GenPolynomialRing<GenPolynomial<BigInteger>>(cfac, 1, to); 139 } 140 141 142 @Override 143 protected void tearDown() { 144 a = b = c = d = e = null; 145 ai = bi = ci = di = ei = null; 146 dfac = null; 147 cfac = null; 148 rfac = null; 149 ComputerThreads.terminate(); 150 } 151 152 153 protected static java.math.BigInteger getPrime1() { 154 long prime = 2; //2^60-93; // 2^30-35; //19; knuth (2,390) 155 for (int i = 1; i < 60; i++) { 156 prime *= 2; 157 } 158 prime -= 93; 159 //prime = 37; 160 //System.out.println("p1 = " + prime); 161 return new java.math.BigInteger("" + prime); 162 } 163 164 165 protected static java.math.BigInteger getPrime2() { 166 long prime = 2; //2^60-93; // 2^30-35; //19; knuth (2,390) 167 for (int i = 1; i < 30; i++) { 168 prime *= 2; 169 } 170 prime -= 35; 171 //prime = 19; 172 //System.out.println("p1 = " + prime); 173 return new java.math.BigInteger("" + prime); 174 } 175 176 177 /** 178 * Test Kronecker substitution. 179 */ 180 public void testKroneckerSubstitution() { 181 182 for (int i = 0; i < 10; i++) { 183 a = dfac.random(kl, ll * 2, el * 5, q); 184 long d = a.degree() + 1L; 185 //System.out.println("\na = " + a); 186 //System.out.println("deg(a)+1 = " + d); 187 188 b = PolyUfdUtil.<BigInteger> substituteKronecker(a, d); 189 //System.out.println("b = " + b); 190 191 c = PolyUfdUtil.<BigInteger> backSubstituteKronecker(dfac, b, d); 192 //System.out.println("c = " + c); 193 e = a.subtract(c); 194 //System.out.println("e = " + e); 195 assertTrue("back(subst(a)) = a", e.isZERO()); 196 } 197 } 198 199 200 /** 201 * Test recursive dense pseudo division. 202 */ 203 public void testRecursivePseudoDivisionDense() { 204 String[] cnames = new String[] { "x" }; 205 String[] mnames = new String[] { "t" }; 206 dfac = new GenPolynomialRing<BigInteger>(new BigInteger(1),to,cnames); 207 //GenPolynomialRing<BigRational> rdfac = new GenPolynomialRing<BigRational>(new BigRational(1),dfac); 208 rfac = new GenPolynomialRing<GenPolynomial<BigInteger>>(dfac, to, mnames); 209 QuotientRing<BigInteger> qfac = new QuotientRing<BigInteger>(dfac); 210 GenPolynomialRing<Quotient<BigInteger>> rqfac = new GenPolynomialRing<Quotient<BigInteger>>(qfac,rfac); 211 //System.out.println("\ndfac = " + dfac); 212 //System.out.println("rdfac = " + rdfac); 213 //System.out.println("rfac = " + rfac); 214 //System.out.println("qfac = " + qfac); 215 //System.out.println("rqfac = " + rqfac); 216 217 ar = rfac.random(kl, 2*ll, el+4, q); 218 //ar = rfac.parse(" ( -2 x^4 + 8 x^3 - 5 x^2 - x + 6 ) t^3 + ( 2 x - 8 ) t^2 - ( 13 x^4 - 13 x^3 + x^2 + 2 x - 13 ) "); 219 br = rfac.random(kl, 2*ll, el+2, q); 220 //ar = ar.multiply(br); 221 //br = rfac.parse(" ( 13 ) t^3 + ( 3 x^2 - 6 ) t - ( 13 x^4 - 8 x^3 + 10 x^2 + 22 x + 21 ) "); 222 //System.out.println("ar = " + ar); 223 //System.out.println("br = " + br); 224 225 dr = PolyUtil.<BigInteger> recursivePseudoDivide(ar, br); 226 //System.out.println("qr = " + dr); 227 cr = PolyUtil.<BigInteger> recursiveDensePseudoRemainder(ar, br); 228 //System.out.println("rr = " + cr); 229 230 //boolean t = PolyUtil.<BigInteger> isRecursivePseudoQuotientRemainder(ar, br, dr, cr); 231 //System.out.println("assertTrue lc^n a = q b + r: " + t); 232 //assertTrue("lc^n a = q b + r: " + cr, t); // ?? not always true 233 234 GenPolynomial<Quotient<BigInteger>> ap = PolyUfdUtil.<BigInteger> quotientFromIntegralCoefficients(rqfac,ar); 235 GenPolynomial<Quotient<BigInteger>> bp = PolyUfdUtil.<BigInteger> quotientFromIntegralCoefficients(rqfac,br); 236 GenPolynomial<Quotient<BigInteger>> cp = PolyUfdUtil.<BigInteger> quotientFromIntegralCoefficients(rqfac,cr); 237 GenPolynomial<Quotient<BigInteger>> dp = PolyUfdUtil.<BigInteger> quotientFromIntegralCoefficients(rqfac,dr); 238 //System.out.println("ap = " + ap); 239 //System.out.println("bp = " + bp); 240 //System.out.println("cp = " + cp); 241 ////System.out.println("dp = " + dp); 242 //System.out.println("dp = " + dp.monic()); 243 244 GenPolynomial<Quotient<BigInteger>> qp = ap.divide(bp); 245 GenPolynomial<Quotient<BigInteger>> rp = ap.remainder(bp); 246 ////System.out.println("qp = " + qp); 247 //System.out.println("qp = " + qp.monic()); 248 //System.out.println("rp = " + rp); 249 GenPolynomial<Quotient<BigInteger>> rhs = qp.multiply(bp).sum(rp); 250 //System.out.println("qp bp + rp = " + rhs); 251 252 assertEquals("ap = qp bp + rp: ", ap, rhs); 253 254 assertEquals("cp = rp: ", rp.monic(), cp.monic() ); 255 //System.out.println("dp = qp: " + qp.monic().equals(dp.monic()) ); 256 assertEquals("dp = qp: ", qp.monic(), dp.monic() ); // ?? 257 } 258 259 260 /** 261 * Test recursive sparse pseudo division. 262 */ 263 public void testRecursivePseudoDivisionSparse() { 264 String[] cnames = new String[] { "x" }; 265 String[] mnames = new String[] { "t" }; 266 dfac = new GenPolynomialRing<BigInteger>(new BigInteger(1),to,cnames); 267 //GenPolynomialRing<BigRational> rdfac = new GenPolynomialRing<BigRational>(new BigRational(1),dfac); 268 rfac = new GenPolynomialRing<GenPolynomial<BigInteger>>(dfac, to, mnames); 269 QuotientRing<BigInteger> qfac = new QuotientRing<BigInteger>(dfac); 270 GenPolynomialRing<Quotient<BigInteger>> rqfac = new GenPolynomialRing<Quotient<BigInteger>>(qfac,rfac); 271 //System.out.println("\ndfac = " + dfac); 272 //System.out.println("rdfac = " + rdfac); 273 //System.out.println("rfac = " + rfac); 274 //System.out.println("qfac = " + qfac); 275 //System.out.println("rqfac = " + rqfac); 276 277 ar = rfac.random(kl, 2*ll, el+4, q); 278 //ar = rfac.parse(" ( -2 x^4 + 8 x^3 - 5 x^2 - x + 6 ) t^3 + ( 2 x - 8 ) t^2 - ( 13 x^4 - 13 x^3 + x^2 + 2 x - 13 ) "); 279 br = rfac.random(kl, 2*ll, el+2, q); 280 //ar = ar.multiply(br); 281 //br = rfac.parse(" ( 13 ) t^3 + ( 3 x^2 - 6 ) t - ( 13 x^4 - 8 x^3 + 10 x^2 + 22 x + 21 ) "); 282 //System.out.println("ar = " + ar); 283 //System.out.println("br = " + br); 284 285 dr = PolyUtil.<BigInteger> recursivePseudoDivide(ar, br); 286 //System.out.println("qr = " + dr); 287 cr = PolyUtil.<BigInteger> recursiveSparsePseudoRemainder(ar, br); 288 //System.out.println("rr = " + cr); 289 290 //boolean t = PolyUtil.<BigInteger> isRecursivePseudoQuotientRemainder(ar, br, dr, cr); 291 //System.out.println("assertTrue lc^n a = q b + r: " + t); 292 //assertTrue("lc^n a = q b + r: " + cr, t); // ?? not always true 293 294 GenPolynomial<Quotient<BigInteger>> ap = PolyUfdUtil.<BigInteger> quotientFromIntegralCoefficients(rqfac,ar); 295 GenPolynomial<Quotient<BigInteger>> bp = PolyUfdUtil.<BigInteger> quotientFromIntegralCoefficients(rqfac,br); 296 GenPolynomial<Quotient<BigInteger>> cp = PolyUfdUtil.<BigInteger> quotientFromIntegralCoefficients(rqfac,cr); 297 GenPolynomial<Quotient<BigInteger>> dp = PolyUfdUtil.<BigInteger> quotientFromIntegralCoefficients(rqfac,dr); 298 //System.out.println("ap = " + ap); 299 //System.out.println("bp = " + bp); 300 //System.out.println("cp = " + cp); 301 ////System.out.println("dp = " + dp); 302 //System.out.println("dp = " + dp.monic()); 303 304 GenPolynomial<Quotient<BigInteger>> qp = ap.divide(bp); 305 GenPolynomial<Quotient<BigInteger>> rp = ap.remainder(bp); 306 ////System.out.println("qp = " + qp); 307 //System.out.println("qp = " + qp.monic()); 308 //System.out.println("rp = " + rp); 309 GenPolynomial<Quotient<BigInteger>> rhs = qp.multiply(bp).sum(rp); 310 //System.out.println("qp bp + rp = " + rhs); 311 312 assertEquals("ap = qp bp + rp: ", ap, rhs); 313 314 assertEquals("cp = rp: ", rp.monic(), cp.monic() ); 315 //System.out.println("dp = qp: " + qp.monic().equals(dp.monic()) ); 316 assertEquals("dp = qp: ", qp.monic(), dp.monic() ); // ?? 317 } 318 319}