Changeset 04dd0c in git
 Timestamp:
 Jun 17, 2010, 2:49:49 PM (13 years ago)
 Branches:
 (u'jengelhdatetime', 'ceac47cbc86fe4a15902392bdbb9bd2ae0ea02c6')(u'spielwiese', 'f875bbaccd0831e36aaed09ff6adeb3eb45aeb94')
 Children:
 fecc08cb1fbac7aebf01c221287ec9360849a8b4
 Parents:
 547f6439fcbe82be0ab53e3707bf2e0d4fbc7872
 File:

 1 edited
Legend:
 Unmodified
 Added
 Removed

factory/cf_gcd_smallp.cc
r547f64 r04dd0c 31 31 #include "cf_random.h" 32 32 33 // i nline helper functions:33 // iinline helper functions: 34 34 #include "cf_map_ext.h" 35 35 36 36 #ifdef HAVE_NTL 37 37 #include <NTL/ZZ_pEX.h> 38 #include <NTLconvert.h> 38 39 #endif 39 40 … … 45 46 /// compressing two polynomials F and G, M is used for compressing, 46 47 /// N to reverse the compression 48 static inline 47 49 int myCompress (const CanonicalForm& F, const CanonicalForm& G, CFMap & M, 48 50 CFMap & N, bool& top_level) … … 335 337 /// based on Alg. 7.2. as described in "Algorithms for 336 338 /// Computer Algebra" by Geddes, Czapor, Labahn 337 CanonicalForm339 static inline CanonicalForm 338 340 GCD_Fp_extension (const CanonicalForm& F, const CanonicalForm& G, 339 341 Variable & alpha, CFList& l, bool& top_level) … … 436 438 437 439 DEBOUTLN (cerr, "getMipo (alpha)= " << getMipo (alpha)); 438 DEBOUTLN (cerr, "getMipo ( alpha)= " << getMipo (V_buf2));440 DEBOUTLN (cerr, "getMipo (V_buf2)= " << getMipo (V_buf2)); 439 441 inextension= true; 440 442 for (CFListIterator i= l; i.hasItem(); i++) … … 535 537 /// univariate polynomial, returns fail if there are no field elements left 536 538 /// which have not been used before 539 static inline 537 540 CanonicalForm 538 541 GFRandomElement (const CanonicalForm& F, CFList& list, bool& fail) … … 574 577 /// faster field arithmetics, however it might fail if the input is large since 575 578 /// the size of the base field is bounded by 2^16, output is monic 579 inline 576 580 CanonicalForm 577 581 GCD_GF (const CanonicalForm& F, const CanonicalForm& G, CFList& l, … … 663 667 num_vars; 664 668 p= getCharacteristic(); 665 expon= floor ((log ((double) ipower (d + 1, num_vars))/log ((double) p)));669 expon= (int) floor ((log ((double) ipower (d + 1, num_vars))/log ((double) p))); 666 670 if (expon < 2) 667 671 expon= 2; … … 671 675 else 672 676 { 673 expon= floor((log ((double)((1<<16)  1)))/(log((double)p)*kk));677 expon= (int) floor((log ((double)((1<<16)  1)))/(log((double)p)*kk)); 674 678 ASSERT (expon >= 2, "not enough points in GCD_GF"); 675 679 setCharacteristic (p, (int)(kk*expon), 'b'); … … 777 781 /// computes a random monic irreducible univariate polynomial of random 778 782 /// degree < i in x which does not divide F 783 static inline 779 784 CanonicalForm 780 randomIrredpoly (int i, const Variable & x, 781 CFList & list) 785 randomIrredpoly (int i, const Variable & x) 782 786 { 783 int random;784 787 int p= getCharacteristic(); 785 788 ZZ NTLp= to_ZZ (p); … … 787 790 ZZ_pX NTLirredpoly; 788 791 CanonicalForm CFirredpoly; 789 int buf= ceil((log((double) i) / log((double) p))); 790 buf= buf + 1; 791 int bound= 0; 792 //lower bound on the number of monic irreducibles of degree less than buf 793 for (int j= 2; j < buf; j++) 794 bound += ((ipower (p, j)  2*ipower(p, j/2)) / j); 795 if (list.length() > bound) 796 { 797 if (buf > 1) 798 buf; 799 buf *= 2; 800 buf++; 801 } 802 for (int j= ((buf  1)/2) + 1; j < buf; j++) 803 bound += ((ipower (p, j)  2*ipower(p, j/2)) / j); 804 do 805 { 806 if (list.length() <= bound) 807 { 808 random= factoryrandom ((int) buf); 809 if (random <= 1) 810 random= 2; 811 } 812 else 813 { 814 if (buf > 1) 815 buf; 816 buf *= 2; 817 buf++; 818 for (int j= ((int) (buf  1)/2) + 1; j < buf; j++) 819 bound += ((ipower (p, j)  2*ipower(p, j/2)) / j); 820 random= factoryrandom ((int) buf); 821 if (random <= 1) 822 random= 2; 823 } 824 BuildIrred (NTLirredpoly, random); 825 CFirredpoly= convertNTLZZpX2CF (NTLirredpoly, x); 826 } while (find (list, CFirredpoly)); 792 BuildIrred (NTLirredpoly, i + 1); 793 CFirredpoly= convertNTLZZpX2CF (NTLirredpoly, x); 827 794 return CFirredpoly; 828 795 } 829 796 797 static inline 830 798 CanonicalForm 831 799 FpRandomElement (const CanonicalForm& F, CFList& list, bool& fail) … … 861 829 } 862 830 831 static inline 863 832 CanonicalForm GCD_small_p (const CanonicalForm& F, const CanonicalForm& G, 864 833 bool& top_level, CFList& l) … … 977 946 int deg= 3; 978 947 do { 979 mipo= randomIrredpoly (deg, x , list);948 mipo= randomIrredpoly (deg, x); 980 949 alpha= rootOf (mipo); 981 950 inextension= true; … … 1069 1038 d= d0; 1070 1039 } 1071 1040 1072 1041 TIMING_START (newton_interpolation); 1073 1042 H= newtonInterp (random_element, G_random_element, newtonPoly, G_m, x);
Note: See TracChangeset
for help on using the changeset viewer.