Changeset 7b5cb2 in git
 Timestamp:
 Aug 8, 2012, 1:31:30 PM (10 years ago)
 Branches:
 (u'jengelhdatetime', 'ceac47cbc86fe4a15902392bdbb9bd2ae0ea02c6')(u'spielwiese', '96ce329119711a2b80858c8365abd29f8460bbfa')
 Children:
 8267b8f9ab43170a4026e7e570df48db4601a748
 Parents:
 97686ecde8614d72ee9d26e96dc9344df8a7da32
 gitauthor:
 Martin Lee <martinlee84@web.de>20120808 13:31:30+02:00
 gitcommitter:
 Martin Lee <martinlee84@web.de>20120904 18:01:07+02:00
 Location:
 factory
 Files:

 2 edited
Legend:
 Unmodified
 Added
 Removed

factory/facSparseHensel.cc
r97686e r7b5cb2 21 21 #include "facFqFactorize.h" 22 22 23 bool 23 int 24 24 LucksWangSparseHeuristic (const CanonicalForm& F, const CFList& factors, 25 25 int level, const CFList& leadingCoeffs, CFList& result) … … 66 66 delete [] monomsLead; 67 67 68 CFArray termsF= getTerms (F); 69 sort (termsF); 68 CFArray termsF= getBiTerms (F); 69 if (termsF.size() > 450) 70 { 71 delete [] monoms; 72 return 0; 73 } 74 sort (termsF, level); 70 75 71 76 CFList tmp; … … 80 85 CanonicalForm H= prod (tmp); 81 86 CFArray monomsH= getMonoms (H); 82 sort (monomsH); 83 84 groupTogether (termsF, level); 87 sort (monomsH,F.level()); 88 85 89 groupTogether (monomsH, F.level()); 86 90 … … 88 92 { 89 93 delete [] stripped2; 90 return false;94 return 0; 91 95 } 92 96 … … 99 103 { 100 104 delete [] stripped2; 101 return false;105 return 0; 102 106 } 103 107 104 108 CFArray A= getEquations (monomsH, termsF); 109 CFArray startingSolution= solution; 105 110 CFArray newSolution= CFArray (solution.size()); 106 111 do … … 110 115 break; 111 116 if (!simplify (A, newSolution, F.level() + 1)) 112 { 113 delete [] stripped2; 114 return false; 115 } 117 break; 116 118 if (isZero (newSolution)) 117 { 118 delete [] stripped2; 119 return false; 120 } 119 break; 121 120 if (!merge (solution, newSolution)) 122 { 123 delete [] stripped2; 124 return false; 125 } 121 break; 126 122 } while (1); 127 123 128 124 129 125 result= CFList(); 126 if (isEqual (startingSolution, solution)) 127 { 128 delete [] stripped2; 129 return 0; 130 } 130 131 CanonicalForm factor; 131 132 num= 0; … … 135 136 factor= 0; 136 137 for (j= 0; j < k; j++, num++) 138 { 139 if (solution [num].isZero()) 140 continue; 137 141 factor += solution [num]*stripped2[i][j]; 142 } 138 143 result.append (factor); 139 144 } 140 145 141 146 delete [] stripped2; 142 return true; 147 if (result.length() > 0) 148 return 1; 149 return 0; 143 150 } 144 151 
factory/facSparseHensel.h
r97686e r7b5cb2 18 18 #include "cf_iter.h" 19 19 #include "templates/ftmpl_functions.h" 20 #include "cf_algorithm.h" 21 #include "cf_map.h" 20 22 21 23 /// compare polynomials … … 81 83 /// quick sort helper function 82 84 inline 83 void quickSort (int lo, int hi, CFArray& A )85 void quickSort (int lo, int hi, CFArray& A, int l) 84 86 { 85 87 int i= lo, j= hi; … … 87 89 while (i <= j) 88 90 { 89 while (comp (A [i], tmp) < 0 && i < hi) i++; 90 while (comp (tmp, A[j]) < 0 && j > lo) j; 91 if (l > 0) 92 { 93 while (comp (A [i], tmp, l) < 0 && i < hi) i++; 94 while (comp (tmp, A[j], l) < 0 && j > lo) j; 95 } 96 else 97 { 98 while (comp (A [i], tmp) < 0 && i < hi) i++; 99 while (comp (tmp, A[j]) < 0 && j > lo) j; 100 } 91 101 if (i <= j) 92 102 { … … 96 106 } 97 107 } 98 if (lo < j) quickSort (lo, j, A );99 if (i < hi) quickSort (i, hi, A );108 if (lo < j) quickSort (lo, j, A, l); 109 if (i < hi) quickSort (i, hi, A, l); 100 110 } 101 111 102 112 /// quick sort @a A 103 113 inline 104 void sort (CFArray& A) 105 { 106 quickSort (0, A.size()  1, A); 107 } 114 void sort (CFArray& A, int l= 0) 115 { 116 quickSort (0, A.size()  1, A, l); 117 } 118 108 119 109 120 /// find normalizing factors for @a biFactors and build monic univariate factors … … 187 198 } 188 199 200 /// helper function for getBiTerms 201 inline CFArray 202 getBiTerms_helper (const CanonicalForm& F, const CFMap& M) 203 { 204 CFArray buf= CFArray (size (F)); 205 int k= 0, level= F.level()  1; 206 Variable x= F.mvar(); 207 Variable y= Variable (F.level()  1); 208 Variable one= Variable (1); 209 Variable two= Variable (2); 210 CFIterator j; 211 for (CFIterator i= F; i.hasTerms(); i++) 212 { 213 if (i.coeff().level() < level) 214 { 215 buf[k]= M (i.coeff())*power (one,i.exp()); 216 k++; 217 continue; 218 } 219 j= i.coeff(); 220 for (;j.hasTerms(); j++, k++) 221 buf[k]= power (one,i.exp())*power (two,j.exp())*M (j.coeff()); 222 } 223 CFArray result= CFArray (k); 224 for (int i= 0; i < k; i++) 225 result[i]= buf[i]; 226 return result; 227 } 228 229 /// get terms of @a F where F is considered a bivariate poly in Variable(1), 230 /// Variable (2) 231 inline CFArray 232 getBiTerms (const CanonicalForm& F) 233 { 234 if (F.inCoeffDomain()) 235 { 236 CFArray result= CFArray (1); 237 result [0]= F; 238 return result; 239 } 240 if (F.isUnivariate()) 241 { 242 CFArray result= CFArray (size(F)); 243 int j= 0; 244 for (CFIterator i= F; i.hasTerms(); i++, j++) 245 result[j]= i.coeff()*power (F.mvar(), i.exp()); 246 return result; 247 } 248 249 CanonicalForm G= F; 250 251 CFMap M; 252 M.newpair (Variable (1), F.mvar()); 253 M.newpair (Variable (2), Variable (F.level()  1)); 254 G= swapvar (F, Variable (1), F.mvar()); 255 G= swapvar (G, Variable (2), Variable (F.level()  1)); 256 257 CFArray result= getBiTerms_helper (G, M); 258 return result; 259 } 260 189 261 /// build a poly from entries in @a A 190 262 inline CanonicalForm … … 197 269 } 198 270 199 /// group together elements in @a A, where entries in @a A are put puttogether271 /// group together elements in @a A, where entries in @a A are put together 200 272 /// if they coincide up to level @a level 201 273 inline void … … 213 285 } 214 286 } 287 if (A[n].isZero()) 288 k; 215 289 CFArray B= CFArray (k); 216 290 n++; … … 509 583 /// 510 584 /// @return @a LucksWangSparseHeuristic returns true if it was successful 511 bool 585 int 512 586 LucksWangSparseHeuristic (const CanonicalForm& F, ///<[in] polynomial to be 513 587 ///< factored
Note: See TracChangeset
for help on using the changeset viewer.