Changeset 52a933f in git


Ignore:
Timestamp:
Jun 20, 2014, 2:45:30 PM (10 years ago)
Author:
Martin Lee <martinlee84@…>
Branches:
(u'fieker-DuVal', '117eb8c30fc9e991c4decca4832b1d19036c4c65')(u'spielwiese', '38077648e7239f98078663eb941c3c979511150a')
Children:
2080e22c0e94d72b5402e5d6ec49d7a581b21f3f
Parents:
a4d2fae92c6a452e379d088cfdef55fab20197de
git-author:
Martin Lee <martinlee84@web.de>2014-06-20 14:45:30+02:00
git-committer:
Martin Lee <martinlee84@web.de>2014-06-24 12:06:05+02:00
Message:
chg: renamed modular GCD variants in cf_gcd_smallp to modGCDFp, modGCDFq, modGCDGF, modGCDZ
Location:
factory
Files:
4 edited

Legend:

Unmodified
Added
Removed

  • factory/cfEzgcd.cc

    ra4d2fa r52a933f  
    956956  {
    957957    if (hasFirstAlgVar (FF, a) || hasFirstAlgVar (GG, a))
    958       return GCD_Fp_extension (FF, GG, a);
     958      return modGCDFq (FF, GG, a);
    959959    else if (CFFactory::gettype() == GaloisFieldDomain)
    960       return GCD_GF (FF, GG);
     960      return modGCDGF (FF, GG);
    961961    else
    962       return GCD_small_p (FF, GG);
     962      return modGCDFp (FF, GG);
    963963  }
    964964
    … …  
    10211021  {
    10221022    if (hasFirstAlgVar (F, a) || hasFirstAlgVar (G, a))
    1023       return N (d*GCD_Fp_extension (F, G, a));
     1023      return N (d*modGCDFq (F, G, a));
    10241024    else if (CFFactory::gettype() == GaloisFieldDomain)
    1025       return N (d*GCD_GF (F, G));
     1025      return N (d*modGCDGF (F, G));
    10261026    else
    1027       return N (d*GCD_small_p (F, G));
     1027      return N (d*modGCDFp (F, G));
    10281028  }
    10291029
    … …  
    13931393        if (algExtension)
    13941394        {
    1395           result= GCD_Fp_extension (F, G, a);
     1395          result= modGCDFq (F, G, a);
    13961396          if (extOfExt)
    13971397            result= mapDown (result, primElem, imPrimElem, oldA, dest, source);
    … …  
    14001400        if (CFFactory::gettype() == GaloisFieldDomain)
    14011401        {
    1402           result= GCD_GF (F, G);
     1402          result= modGCDGF (F, G);
    14031403          if (passToGF)
    14041404          {
    … …  
    14161416        }
    14171417        else
    1418           return N (d*GCD_small_p (F,G));
     1418          return N (d*modGCDFp (F,G));
    14191419      }
    14201420
    … …  
    14271427        if (algExtension)
    14281428        {
    1429           result= GCD_Fp_extension (F, G, a);
     1429          result= modGCDFq (F, G, a);
    14301430          if (extOfExt)
    14311431            result= mapDown (result, primElem, imPrimElem, oldA, dest, source);
    … …  
    14341434        if (CFFactory::gettype() == GaloisFieldDomain)
    14351435        {
    1436           result= GCD_GF (F, G);
     1436          result= modGCDGF (F, G);
    14371437          if (passToGF)
    14381438          {
    … …  
    14541454            return N (d*sparseGCDFp (F,G));
    14551455          else
    1456             return N (d*GCD_small_p (F,G));
     1456            return N (d*modGCDFp (F,G));
    14571457        }
    14581458      }

  • factory/cf_gcd.cc

    ra4d2fa r52a933f  
    111111      Variable a;
    112112      if (hasFirstAlgVar (fc, a) || hasFirstAlgVar (gc, a))
    113         fc=GCD_Fp_extension (fc, gc, a);
     113        fc=modGCDFq (fc, gc, a);
    114114      else if (CFFactory::gettype() == GaloisFieldDomain)
    115         fc=GCD_GF (fc, gc);
     115        fc=modGCDGF (fc, gc);
    116116      else
    117         fc=GCD_small_p (fc, gc);
     117        fc=modGCDFp (fc, gc);
    118118    }
    119119    else
    … …  
    126126      fc= ezgcd (fc, gc);
    127127    else if (isOn(SW_USE_CHINREM_GCD))
    128       fc = chinrem_gcd( fc, gc);
     128      fc = modGCDZ( fc, gc);
    129129    else
    130130    {

  • factory/cf_gcd_smallp.cc

    ra4d2fa r52a933f  
    44 *
    55 * This file implements the GCD of two polynomials over \f$ F_{p} \f$ ,
    6  * \f$ F_{p}(\alpha ) \f$ or GF based on Alg. 7.2. as described in "Algorithms
    7  * for Computer Algebra" by Geddes, Czapor, Labahn
     6 * \f$ F_{p}(\alpha ) \f$, GF or Z based on Alg. 7.1. and 7.2. as described in
     7 * "Algorithms for Computer Algebra" by Geddes, Czapor, Labahn via modular
     8 * computations. And sparse modular variants as described in Zippel
     9 * "Effective Polynomial Computation", deKleine, Monagan, Wittkopf
     10 * "Algorithms for the non-monic case of the sparse modular GCD algorithm" and
     11 * Javadi "A new solution to the normalization problem"
    812 *
    913 * @author Martin Lee
    … …  
    441445
    442446CanonicalForm
    443 GCD_Fp_extension (const CanonicalForm& F, const CanonicalForm& G,
     447modGCDFq (const CanonicalForm& F, const CanonicalForm& G,
    444448                  CanonicalForm& coF, CanonicalForm& coG,
    445449                  Variable & alpha, CFList& l, bool& topLevel);
    446450
    447451CanonicalForm
    448 GCD_Fp_extension (const CanonicalForm& F, const CanonicalForm& G,
     452modGCDFq (const CanonicalForm& F, const CanonicalForm& G,
    449453                  Variable & alpha, CFList& l, bool& topLevel)
    450454{
    451455  CanonicalForm dummy1, dummy2;
    452   CanonicalForm result= GCD_Fp_extension (F, G, dummy1, dummy2, alpha, l,
     456  CanonicalForm result= modGCDFq (F, G, dummy1, dummy2, alpha, l,
    453457                                          topLevel);
    454458  return result;
    … …  
    460464/// Computer Algebra" by Geddes, Czapor, Labahn
    461465CanonicalForm
    462 GCD_Fp_extension (const CanonicalForm& F, const CanonicalForm& G,
     466modGCDFq (const CanonicalForm& F, const CanonicalForm& G,
    463467                  CanonicalForm& coF, CanonicalForm& coG,
    464468                  Variable & alpha, CFList& l, bool& topLevel)
    … …  
    648652      TIMING_START (gcd_recursion);
    649653      G_random_element=
    650       GCD_Fp_extension (ppA (random_element, x), ppB (random_element, x),
     654      modGCDFq (ppA (random_element, x), ppB (random_element, x),
    651655                        coF_random_element, coG_random_element, V_buf,
    652656                        list, topLevel);
    … …  
    660664      TIMING_START (gcd_recursion);
    661665      G_random_element=
    662       GCD_Fp_extension (ppA(random_element, x), ppB(random_element, x),
     666      modGCDFq (ppA(random_element, x), ppB(random_element, x),
    663667                        coF_random_element, coG_random_element, V_buf,
    664668                        list, topLevel);
    … …  
    823827
    824828CanonicalForm
    825 GCD_GF (const CanonicalForm& F, const CanonicalForm& G,
     829modGCDGF (const CanonicalForm& F, const CanonicalForm& G,
    826830        CanonicalForm& coF, CanonicalForm& coG,
    827831        CFList& l, bool& topLevel);
    828832
    829833CanonicalForm
    830 GCD_GF (const CanonicalForm& F, const CanonicalForm& G, CFList& l,
     834modGCDGF (const CanonicalForm& F, const CanonicalForm& G, CFList& l,
    831835        bool& topLevel)
    832836{
    833837  CanonicalForm dummy1, dummy2;
    834   CanonicalForm result= GCD_GF (F, G, dummy1, dummy2, l, topLevel);
     838  CanonicalForm result= modGCDGF (F, G, dummy1, dummy2, l, topLevel);
    835839  return result;
    836840}
    … …  
    838842/// GCD of F and G over GF, based on Alg. 7.2. as described in "Algorithms for
    839843/// Computer Algebra" by Geddes, Czapor, Labahn
    840 /// Usually this algorithm will be faster than GCD_Fp_extension since GF has
     844/// Usually this algorithm will be faster than modGCDFq since GF has
    841845/// faster field arithmetics, however it might fail if the input is large since
    842846/// the size of the base field is bounded by 2^16, output is monic
    843847CanonicalForm
    844 GCD_GF (const CanonicalForm& F, const CanonicalForm& G,
     848modGCDGF (const CanonicalForm& F, const CanonicalForm& G,
    845849        CanonicalForm& coF, CanonicalForm& coG,
    846850        CFList& l, bool& topLevel)
    … …  
    979983      {
    980984        expon= (int) floor((log ((double)((1<<16) - 1)))/(log((double)p)*kk));
    981         ASSERT (expon >= 2, "not enough points in GCD_GF");
     985        ASSERT (expon >= 2, "not enough points in modGCDGF");
    982986        setCharacteristic (p, (int)(kk*expon), 'b');
    983987      }
    … …  
    10001004      CFList list;
    10011005      TIMING_START (gcd_recursion);
    1002       G_random_element= GCD_GF (ppA(random_element, x), ppB(random_element, x),
     1006      G_random_element= modGCDGF (ppA(random_element, x), ppB(random_element, x),
    10031007                                coF_random_element, coG_random_element,
    10041008                                list, topLevel);
    … …  
    10111015      CFList list;
    10121016      TIMING_START (gcd_recursion);
    1013       G_random_element= GCD_GF (ppA(random_element, x), ppB(random_element, x),
     1017      G_random_element= modGCDGF (ppA(random_element, x), ppB(random_element, x),
    10141018                                coF_random_element, coG_random_element,
    10151019                                list, topLevel);
    … …  
    11921196
    11931197CanonicalForm
    1194 GCD_small_p (const CanonicalForm& F, const CanonicalForm&  G,
     1198modGCDFp (const CanonicalForm& F, const CanonicalForm&  G,
    11951199             CanonicalForm& coF, CanonicalForm& coG,
    11961200             bool& topLevel, CFList& l);
    11971201
    11981202CanonicalForm
    1199 GCD_small_p (const CanonicalForm& F, const CanonicalForm& G,
     1203modGCDFp (const CanonicalForm& F, const CanonicalForm& G,
    12001204             bool& topLevel, CFList& l)
    12011205{
    12021206  CanonicalForm dummy1, dummy2;
    1203   CanonicalForm result= GCD_small_p (F, G, dummy1, dummy2, topLevel, l);
     1207  CanonicalForm result= modGCDFp (F, G, dummy1, dummy2, topLevel, l);
    12041208  return result;
    12051209}
    12061210
    12071211CanonicalForm
    1208 GCD_small_p (const CanonicalForm& F, const CanonicalForm&  G,
     1212modGCDFp (const CanonicalForm& F, const CanonicalForm&  G,
    12091213             CanonicalForm& coF, CanonicalForm& coG,
    12101214             bool& topLevel, CFList& l)
    … …  
    13421346      TIMING_START (gcd_recursion);
    13431347      G_random_element=
    1344       GCD_small_p (ppA (random_element,x), ppB (random_element,x),
     1348      modGCDFp (ppA (random_element,x), ppB (random_element,x),
    13451349                   coF_random_element, coG_random_element, topLevel,
    13461350                   list);
    … …  
    13541358      TIMING_START (gcd_recursion);
    13551359      G_random_element=
    1356       GCD_Fp_extension (ppA (random_element, x), ppB (random_element, x),
     1360      modGCDFq (ppA (random_element, x), ppB (random_element, x),
    13571361                        coF_random_element, coG_random_element, V_buf,
    13581362                        list, topLevel);
    … …  
    13801384      TIMING_START (gcd_recursion);
    13811385      G_random_element=
    1382       GCD_Fp_extension (ppA (random_element, x), ppB (random_element, x),
     1386      modGCDFq (ppA (random_element, x), ppB (random_element, x),
    13831387                        coF_random_element, coG_random_element, alpha,
    13841388                        list, topLevel);
    … …  
    14481452      TIMING_START (gcd_recursion);
    14491453      G_random_element=
    1450       GCD_Fp_extension (ppA (random_element, x), ppB (random_element, x),
     1454      modGCDFq (ppA (random_element, x), ppB (random_element, x),
    14511455                        coF_random_element, coG_random_element, V_buf,
    14521456                        list, topLevel);
    … …  
    38533857    }
    38543858    else
    3855       return N(gcdcAcB*GCD_small_p (ppA, ppB));
     3859      return N(gcdcAcB*modGCDFp (ppA, ppB));
    38563860  } while (1); //end of first do
    38573861}
    38583862
    3859 TIMING_DEFINE_PRINT(chinrem_termination)
    3860 TIMING_DEFINE_PRINT(chinrem_recursion)
     3863TIMING_DEFINE_PRINT(modZ_termination)
     3864TIMING_DEFINE_PRINT(modZ_recursion)
    38613865
    38623866/// modular gcd algorithm, see Keith, Czapor, Geddes "Algorithms for Computer
    38633867/// Algebra", Algorithm 7.1
    3864 CanonicalForm chinrem_gcd ( const CanonicalForm & FF, const CanonicalForm & GG )
     3868CanonicalForm modGCDZ ( const CanonicalForm & FF, const CanonicalForm & GG )
    38653869{
    38663870  CanonicalForm f, g, cl, q(0), Dp, newD, D, newq, newqh;
    … …  
    39323936    fp= mapinto (f);
    39333937    gp= mapinto (g);
    3934     TIMING_START (chinrem_recursion)
     3938    TIMING_START (modZ_recursion)
    39353939#ifdef HAVE_NTL
    39363940    if (size (fp)/maxNumVars > 500 && size (gp)/maxNumVars > 500)
    3937       Dp = GCD_small_p (fp, gp, cofp, cogp);
     3941      Dp = modGCDFp (fp, gp, cofp, cogp);
    39383942    else
    39393943    {
    … …  
    39473951    cogp= gp/Dp;
    39483952#endif
    3949     TIMING_END_AND_PRINT (chinrem_recursion,
     3953    TIMING_END_AND_PRINT (modZ_recursion,
    39503954                          "time for gcd mod p in modular gcd: ");
    39513955    Dp /=Dp.lc();
    … …  
    40224026      cogn /= cl/cDn;
    40234027      //cogn /= icontent (cogn);
    4024       TIMING_START (chinrem_termination);
     4028      TIMING_START (modZ_termination);
    40254029      if ((terminationTest (f,g, cofn, cogn, Dn)) ||
    40264030          ((equal || q > b) && fdivides (Dn, f) && fdivides (Dn, g)))
    40274031      {
    4028         TIMING_END_AND_PRINT (chinrem_termination,
     4032        TIMING_END_AND_PRINT (modZ_termination,
    40294033                            "time for successful termination in modular gcd: ");
    40304034        //printf(" -> success\n");
    40314035        return Dn*gcdcfcg;
    40324036      }
    4033       TIMING_END_AND_PRINT (chinrem_termination,
     4037      TIMING_END_AND_PRINT (modZ_termination,
    40344038                          "time for unsuccessful termination in modular gcd: ");
    40354039      equal= false;

  • factory/cf_gcd_smallp.h

    ra4d2fa r52a933f  
    55/** @file cf_gcd_smallp.h
    66 *
    7  * This file defines the functions GCD_Fp_extension which computes the GCD of
    8  * two polynomials over \f$ F_{p}(\alpha ) \f$ , GCD_small_p which computes the
    9  * GCD of two polynomials over  \f$ F_{p} \f$ , and GCD_GF which computes the
    10  * GCD of two polynomials over GF. Algorithms are based on "On the Genericity of
    11  * the Modular Polynomial GCD Algorithm" by E. Kaltofen & M. Monagan
     7 * modular and sparse modular GCD algorithms over finite fields and Z.
    128 *
    139 * @author Martin Lee
    … …  
    2521#include "cf_factory.h"
    2622
    27 CanonicalForm GCD_Fp_extension (const CanonicalForm& F, const CanonicalForm& G,
     23CanonicalForm modGCDFq (const CanonicalForm& F, const CanonicalForm& G,
    2824                  Variable & alpha, CFList& l, bool& top_level);
    2925
    3026/// GCD of A and B over \f$ F_{p}(\alpha ) \f$
    31 static inline CanonicalForm GCD_Fp_extension (const CanonicalForm& A, const CanonicalForm& B,
     27static inline CanonicalForm modGCDFq (const CanonicalForm& A, const CanonicalForm& B,
    3228                                Variable & alpha)
    3329{
    3430  CFList list;
    3531  bool top_level= true;
    36   return GCD_Fp_extension (A, B, alpha, list, top_level);
     32  return modGCDFq (A, B, alpha, list, top_level);
    3733}
    3834
    3935
    40 CanonicalForm GCD_small_p (const CanonicalForm& F, const CanonicalForm&  G,
     36CanonicalForm modGCDFp (const CanonicalForm& F, const CanonicalForm&  G,
    4137                           bool& top_level, CFList& l);
    4238
    43 CanonicalForm GCD_small_p (const CanonicalForm& F, const CanonicalForm&  G, CanonicalForm& coF, CanonicalForm& coG,
     39CanonicalForm modGCDFp (const CanonicalForm& F, const CanonicalForm&  G, CanonicalForm& coF, CanonicalForm& coG,
    4440                           bool& topLevel, CFList& l);
    4541
    4642///GCD of A and B over \f$ F_{p} \f$
    47 static inline CanonicalForm GCD_small_p (const CanonicalForm& A, const CanonicalForm& B)
     43static inline CanonicalForm modGCDFp (const CanonicalForm& A, const CanonicalForm& B)
    4844{
    4945  CFList list;
    5046  bool top_level= true;
    51   return GCD_small_p (A, B, top_level, list);
     47  return modGCDFp (A, B, top_level, list);
    5248}
    5349
    54 static inline CanonicalForm GCD_small_p (const CanonicalForm& A, const CanonicalForm& B, CanonicalForm& coA, CanonicalForm& coB)
     50static inline CanonicalForm modGCDFp (const CanonicalForm& A, const CanonicalForm& B, CanonicalForm& coA, CanonicalForm& coB)
    5551{
    5652  CFList list;
    5753  bool top_level= true;
    58   return GCD_small_p (A, B, coA, coB, top_level, list);
     54  return modGCDFp (A, B, coA, coB, top_level, list);
    5955}
    6056
    61 CanonicalForm GCD_GF (const CanonicalForm& F, const CanonicalForm& G, CFList& l,
     57CanonicalForm modGCDGF (const CanonicalForm& F, const CanonicalForm& G, CFList& l,
    6258        bool& top_level);
    6359
    6460/// GCD of A and B over GF
    65 static inline CanonicalForm GCD_GF (const CanonicalForm& A, const CanonicalForm& B)
     61static inline CanonicalForm modGCDGF (const CanonicalForm& A, const CanonicalForm& B)
    6662{
    6763  ASSERT (CFFactory::gettype() == GaloisFieldDomain,
    … …  
    6965  CFList list;
    7066  bool top_level= true;
    71   return GCD_GF (A, B, list, top_level);
     67  return modGCDGF (A, B, list, top_level);
    7268}
    7369
    … …  
    111107                 const CanonicalForm& cand);
    112108
    113 CanonicalForm chinrem_gcd ( const CanonicalForm & FF, const CanonicalForm & GG );
     109CanonicalForm modGCDZ ( const CanonicalForm & FF, const CanonicalForm & GG );
    114110#endif
Note: See TracChangeset for help on using the changeset viewer.