Changeset 53e6c3 in git
 Timestamp:
 Aug 26, 2014, 11:21:22 AM (9 years ago)
 Branches:
 (u'spielwiese', '8e0ad00ce244dfd0756200662572aef8402f13d5')
 Children:
 98abec57dad14f757407f31931b9555ceee6c4ad
 Parents:
 30e27f8a94644c552a6548c8b0d0b2026ceb2068
 gitauthor:
 Martin Lee <martinlee84@web.de>20140826 11:21:22+02:00
 gitcommitter:
 Martin Lee <martinlee84@web.de>20140826 12:29:12+02:00
 File:

 1 edited
Legend:
 Unmodified
 Added
 Removed

factory/cfEzgcd.cc
r30e27f r53e6c3 307 307 for (int i= A.min(); i <= A.max(); i++) 308 308 { 309 if (!A[i].isZero()) 309 if (!A[i].isZero() && 310 ((getCharacteristic() > degree (U,i))  getCharacteristic() == 0)) 310 311 { 311 312 termEstimate *= degree (U,i)*2; … … 433 434 } 434 435 436 /// real implementation of EZGCD over Z 435 437 static CanonicalForm 436 438 ezgcd ( const CanonicalForm & FF, const CanonicalForm & GG, REvaluation & b, … … 776 778 #endif 777 779 780 /// Extended Zassenhaus GCD over Z. 781 /// In case things become too dense we switch to a modular algorithm. 778 782 CanonicalForm 779 783 ezgcd ( const CanonicalForm & FF, const CanonicalForm & GG ) … … 790 794 791 795 #ifdef HAVE_NTL 792 static inline793 int Hensel_P (const CanonicalForm & UU, CFArray & G, const Evaluation & AA,794 const CFArray& LeadCoeffs )795 {796 CFList factors;797 factors.append (G[1]);798 factors.append (G[2]);799 800 CFMap NN, MM;801 Evaluation A= optimize4Lift (UU, MM, NN, AA);802 803 CanonicalForm U= MM (UU);804 CFArray LCs= CFArray (1,2);805 LCs [1]= MM (LeadCoeffs [1]);806 LCs [2]= MM (LeadCoeffs [2]);807 808 CFList evaluation;809 long termEstimate= size (U);810 for (int i= A.min(); i <= A.max(); i++)811 {812 if (!A[i].isZero() && (getCharacteristic() > degree (U,i))) //TODO find a good estimate for getCharacteristic() <= degree (U,i)813 {814 termEstimate *= degree (U,i)*2;815 termEstimate /= 3;816 }817 evaluation.append (A [i]);818 }819 if (termEstimate/getNumVars(U) > 500)820 return 1;821 CFList UEval;822 CanonicalForm shiftedU= myShift2Zero (U, UEval, evaluation);823 824 if (size (shiftedU)/getNumVars (U) > 500)825 return 1;826 827 CFArray shiftedLCs= CFArray (2);828 CFList shiftedLCsEval1, shiftedLCsEval2;829 shiftedLCs[0]= myShift2Zero (LCs[1], shiftedLCsEval1, evaluation);830 shiftedLCs[1]= myShift2Zero (LCs[2], shiftedLCsEval2, evaluation);831 factors.insert (1);832 int liftBound= degree (UEval.getLast(), 2) + 1;833 CFArray Pi;834 CFMatrix M= CFMatrix (liftBound, factors.length()  1);835 CFList diophant;836 CFArray lcs= CFArray (2);837 lcs [0]= shiftedLCsEval1.getFirst();838 lcs [1]= shiftedLCsEval2.getFirst();839 nonMonicHenselLift12 (UEval.getFirst(), factors, liftBound, Pi, diophant, M,840 lcs, false);841 842 for (CFListIterator i= factors; i.hasItem(); i++)843 {844 if (!fdivides (i.getItem(), UEval.getFirst()))845 return 0;846 }847 848 int * liftBounds;849 bool noOneToOne= false;850 if (U.level() > 2)851 {852 liftBounds= new int [U.level()  1]; /* index: 0.. U.level()2 */853 liftBounds[0]= liftBound;854 for (int i= 1; i < U.level()  1; i++)855 liftBounds[i]= degree (shiftedU, Variable (i + 2)) + 1;856 factors= nonMonicHenselLift2 (UEval, factors, liftBounds, U.level()  1,857 false, shiftedLCsEval1, shiftedLCsEval2, Pi,858 diophant, noOneToOne);859 delete [] liftBounds;860 if (noOneToOne)861 return 0;862 }863 G[1]= factors.getFirst();864 G[2]= factors.getLast();865 G[1]= myReverseShift (G[1], evaluation);866 G[2]= myReverseShift (G[2], evaluation);867 G[1]= NN (G[1]);868 G[2]= NN (G[2]);869 return 1;870 }871 872 static inline873 bool findeval_P (const CanonicalForm & F, const CanonicalForm & G,874 CanonicalForm & Fb, CanonicalForm & Gb, CanonicalForm & Db,875 REvaluation & b, int delta, int degF, int degG, int maxeval,876 int & count, int& k, int bound, int& l)877 {878 if( count == 0 && delta != 0)879 {880 if( count++ > maxeval )881 return false;882 }883 if (count > 0)884 {885 b.nextpoint(k);886 if (k == 0)887 k++;888 l++;889 if (l > bound)890 {891 l= 1;892 k++;893 if (k > tmax (F.level(), G.level())  1)894 return false;895 b.nextpoint (k);896 }897 if (count++ > maxeval)898 return false;899 }900 while( true )901 {902 Fb = b( F );903 if( degree( Fb, 1 ) == degF )904 {905 Gb = b( G );906 if( degree( Gb, 1 ) == degG )907 {908 Db = gcd( Fb, Gb );909 if( delta > 0 )910 {911 if( degree( Db, 1 ) <= delta )912 return true;913 }914 else915 return true;916 }917 }918 if (k == 0)919 k++;920 b.nextpoint(k);921 l++;922 if (l > bound)923 {924 l= 1;925 k++;926 if (k > tmax (F.level(), G.level())  1)927 return false;928 b.nextpoint (k);929 }930 if( count++ > maxeval )931 return false;932 }933 }934 935 796 // parameters for heuristic 936 797 static int maxNumEval= 200; … … 938 799 939 800 /// Extended Zassenhaus GCD for finite fields. 940 /// In case things become too dense we switch to a modular algorithm 801 /// In case things become too dense we switch to a modular algorithm. 941 802 CanonicalForm EZGCD_P( const CanonicalForm & FF, const CanonicalForm & GG ) 942 803 { … … 1154 1015 { 1155 1016 TIMING_START (ez_p_eval); 1156 if( !findeval _P( F, G, Fb, Gb, Db, b, delta, degF, degG, maxeval, count, o,1017 if( !findeval( F, G, Fb, Gb, Db, b, delta, degF, degG, maxeval, count, o, 1157 1018 maxeval/maxNumVars, t )) 1158 1019 { // too many eval. used > try another method … … 1248 1109 bt = b; 1249 1110 TIMING_START (ez_p_eval); 1250 if( !findeval _P(F,G,Fbt,Gbt,Dbt, bt, delta, degF, degG, maxeval, count, o,1111 if( !findeval(F,G,Fbt,Gbt,Dbt, bt, delta, degF, degG, maxeval, count, o, 1251 1112 maxeval/maxNumVars, t )) 1252 1113 { // too many eval. used > try another method … … 1453 1314 1454 1315 TIMING_START (ez_p_hensel_lift); 1455 gcdfound= Hensel _P(B*lcD, DD, b, lcDD);1316 gcdfound= Hensel (B*lcD, DD, b, lcDD); 1456 1317 TIMING_END_AND_PRINT (ez_p_hensel_lift, "time for Hensel lift in EZ_P: "); 1457 1318
Note: See TracChangeset
for help on using the changeset viewer.