Changeset 7d1c995 in git


Ignore:
Timestamp:
May 31, 2011, 3:48:35 PM (13 years ago)
Author:
Martin Lee <martinlee84@…>
Branches:
(u'fieker-DuVal', '117eb8c30fc9e991c4decca4832b1d19036c4c65')(u'spielwiese', '3a4bc649f1d0185cc9f8b122bd75f21f75ac9c9a')
Children:
a8e8b95ce901a8a52041639c48329ebc09efae2b
Parents:
5b274570b3977c8b95131bdda194e0b179f17b8b
Message:
added test to prevent multiple inclusion of headers
moved function declarations from fieldGCD.h to algext.h
deleted broken routine univarQGCD 


git-svn-id: file:///usr/local/Singular/svn/trunk@14253 2c84dea3-7e68-4137-9b89-c4e89433aadc
Location:
factory
Files:
6 edited

Legend:

Unmodified
Added
Removed
  • factory/GNUmakefile.in

    r5b2745 r7d1c995  
    128128# factory source files
    129129basefactorysrc := \
     130                algext.cc \
    130131                canonicalform.cc \
    131132                cf_algorithm.cc \
  • factory/algext.cc

    r5b2745 r7d1c995  
    145145  return false;
    146146}
    147 
    148 CanonicalForm univarQGCD( const CanonicalForm & F, const CanonicalForm & G )
    149 { // F,G in Q(a)[x]
    150   CanonicalForm f, g, tmp, M, q, D, Dp, cl, newD, newq;
    151   int p, dp_deg, bound, i;
    152   bool fail;
    153   On(SW_RATIONAL);
    154   f = F * bCommonDen(F);
    155   g = G * bCommonDen(G);
    156   Variable a,b;
    157   if( !hasFirstAlgVar( f, a ) && !hasFirstAlgVar( g, b ))
    158   {
    159     // F and G are in Q[x], call...
    160 #ifdef HAVE_NTL
    161     if ( isOn( SW_USE_NTL_GCD_0 ))
    162       return gcd_univar_ntl0( f, g );
    163 #endif
    164     return gcd_poly_univar0( f, g, false );
    165   }
    166   if( b.level() > a.level() )
    167     a = b;
    168   // here: a is the biggest alg. var in f and g
    169   tmp = getMipo(a);
    170   M = tmp * bCommonDen(tmp);
    171   Off(SW_RATIONAL);
    172   // calculate upper bound for degree of gcd
    173   bound = degree(f);
    174   i = degree(g);
    175   if( i < bound )
    176     bound = i;
    177 
    178   cl = lc(M) * lc(f) * lc(g);
    179   q = 1;
    180   D = 0;
    181   for(i=cf_getNumBigPrimes()-1; i>-1; i--)
    182   {
    183     p = cf_getBigPrime(i);
    184     if( mod( cl, p ).isZero() ) // skip lc-bad primes
    185       continue;
    186 
    187     fail = false;
    188     setCharacteristic(p);
    189     tryEuclid( mapinto(f), mapinto(g), mapinto(M), Dp, fail );
    190     setCharacteristic(0);
    191     if( fail ) // M splits in char p
    192       continue;
    193 
    194     dp_deg = degree(Dp);
    195 
    196     if( dp_deg == 0 ) // early termination
    197     {
    198       CanonicalForm inv;
    199       tryInvert(Dp, M, inv, fail);
    200       if(fail)
    201         continue;
    202       return CanonicalForm(1);
    203     }
    204 
    205     if( dp_deg > bound ) // current prime unlucky
    206       continue;
    207 
    208     if( dp_deg < bound ) // all previous primes unlucky
    209     {
    210       q = p;
    211       D = mapinto(Dp); // shortcut CRA
    212       bound = dp_deg; // tighten bound
    213       continue;
    214     }
    215     chineseRemainder( D, q, mapinto(Dp), p, newD, newq );
    216     // newD = Dp mod p
    217     // newD = D mod q
    218     // newq = p*q
    219     q = newq;
    220     if( D != newD )
    221     {
    222       D = newD;
    223       continue;
    224     }
    225     On( SW_RATIONAL );
    226     tmp = Farey( D, q );
    227     if( fdivides( tmp, f ) && fdivides( tmp, g )) // trial division
    228     {
    229       Off( SW_RATIONAL );
    230       return tmp;
    231     }
    232     Off( SW_RATIONAL );
    233   }
    234   // hopefully, we never reach this point
    235   Off( SW_USE_QGCD );
    236   D = gcd( f, g );
    237   On( SW_USE_QGCD );
    238   return D;
    239 }
    240 
    241 
    242147
    243148CanonicalForm QGCD( const CanonicalForm & F, const CanonicalForm & G );
  • factory/algext.h

    r5b2745 r7d1c995  
     1#ifndef ALGEXT_H
     2#define ALGEXT_H
     3
    14#include <config.h>
    25
     
    58
    69CanonicalForm QGCD( const CanonicalForm &, const CanonicalForm & );
    7 CanonicalForm univarQGCD( const CanonicalForm & F, const CanonicalForm & G );
    8 //void tryEuclid( const CanonicalForm &, const CanonicalForm &, const CanonicalForm, CanonicalForm &, bool & );
     10void tryEuclid( const CanonicalForm &, const CanonicalForm &, const CanonicalForm &, CanonicalForm &, bool & );
    911void tryInvert( const CanonicalForm &, const CanonicalForm &, CanonicalForm &, bool & );
    1012bool hasFirstAlgVar( const CanonicalForm &, Variable & );
     
    1214void tryCRA( const CanonicalForm & x1, const CanonicalForm & q1, const CanonicalForm & x2, const CanonicalForm & q2, CanonicalForm & xnew, CanonicalForm & qnew, bool & fail );
    1315void tryExtgcd( const CanonicalForm & F, const CanonicalForm & G, CanonicalForm & result, CanonicalForm & s, CanonicalForm & t, bool & fail );
     16int * leadDeg(const CanonicalForm & f, int *degs);
     17bool isLess(int *a, int *b, int lower, int upper);
     18bool isEqual(int *a, int *b, int lower, int upper);
     19CanonicalForm firstLC(const CanonicalForm & f);
    1420
     21#endif
    1522
    16 
  • factory/cf_gcd.cc

    r5b2745 r7d1c995  
    834834          (getCharacteristic() == 0) &&
    835835          (hasFirstAlgVar(f,m) || hasFirstAlgVar(g,m))
    836           //&& f.isUnivariate()
    837           //&& g.isUnivariate()
    838836          )
    839837          {
    840             //if ((f.level()==g.level()) && f.isUnivariate() && g.isUnivariate())
    841             //  return univarQGCD(f,g);
    842             //else
    843               //return QGCD(f,g);
    844838            bool on_rational = isOn(SW_RATIONAL);
    845839            CanonicalForm r=QGCD(f,g);
     
    12381232}
    12391233
    1240 #include "algext.cc"
    1241 
  • factory/facAlgExt.h

    r5b2745 r7d1c995  
    1717**/
    1818//*****************************************************************************
     19
     20#ifndef FAC_ALG_EXT_H
     21#define FAC_ALG_EXT_H
    1922
    2023#include "assert.h"
     
    3841                 const Variable& alpha   ///<[in] an algebraic variable
    3942                );
     43
     44#endif
     45
  • factory/fieldGCD.h

    r5b2745 r7d1c995  
     1#ifndef FIELD_GCD_H
     2#define FIELD_GCD_H
     3
    14CanonicalForm fieldGCD( const CanonicalForm & F, const CanonicalForm & G );
    25void CRA(const CanonicalForm & x1, const CanonicalForm & q1, const CanonicalForm & x2, const CanonicalForm & q2, CanonicalForm & xnew, CanonicalForm & qnew);
    3 int * leadDeg(const CanonicalForm & f, int *degs);
    4 bool isLess(int *a, int *b, int lower, int upper);
    5 bool isEqual(int *a, int *b, int lower, int upper);
    6 CanonicalForm firstLC(const CanonicalForm & f);
    76
     7#endif
     8
Note: See TracChangeset for help on using the changeset viewer.