Loading...
Searching...
No Matches
fac_sqrfree.cc
Go to the documentation of this file.
/* emacs edit mode for this file is -*- C++ -*- */
#include "config.h"
#include "cf_assert.h"
#include "cf_defs.h"
#include "canonicalform.h"
#include "cf_map.h"
#include "cf_algorithm.h"
#ifdef HAVE_FLINT
#include "FLINTconvert.h" // for __FLINT_RELEASE
#endif
static int
compareFactors( const CFFactor & f, const CFFactor & g )
{
return f.exp() > g.exp();
}
CFFList
sortCFFList( CFFList & F )
{
F.sort( compareFactors );
int exp;
CanonicalForm f;
CFFListIterator I = F;
CFFList result;
// join elements with the same degree
while ( I.hasItem() ) {
f = I.getItem().factor();
exp = I.getItem().exp();
I++;
while ( I.hasItem() && I.getItem().exp() == exp ) {
f *= I.getItem().factor();
I++;
}
result.append( CFFactor( f, exp ) );
}
return result;
}
CFFList sqrFreeZ ( const CanonicalForm & a )
{
if ( a.inCoeffDomain() )
return CFFactor( a, 1 );
CanonicalForm aa, LcA;
if (isOn (SW_RATIONAL))
{
LcA= bCommonDen (a);
aa= a*LcA;
}
else
{
LcA= icontent (a);
if (lc (a).sign() < 0)
LcA= -LcA;
aa= a/LcA;
}
CanonicalForm cont = content( aa );
aa /= cont;
CanonicalForm b = aa.deriv(), c = gcd( aa, b );
CanonicalForm y, z, w = aa / c;
int i = 1;
CFFList F;
Variable v = aa.mvar();
CanonicalForm lcinv;
while ( c.degree(v) != 0 )
{
y = gcd( w, c ); z = w / y;
if ( degree( z, v ) > 0 )
{
if (isOn (SW_RATIONAL))
{
lcinv= 1/Lc (z);
z *= lcinv;
z *= bCommonDen (z);
}
if (lc (z).sign() < 0)
z= -z;
F.append( CFFactor( z, i ) );
}
i++;
w = y; c = c / y;
}
if ( degree( w,v ) > 0 )
{
if (isOn (SW_RATIONAL))
{
lcinv= 1/Lc (w);
w *= lcinv;
w *= bCommonDen (w);
}
if (lc (w).sign() < 0)
w= -w;
F.append( CFFactor( w, i ) );
}
if ( ! cont.isOne() )
{
CFFList buf= sqrFreeZ (cont);
buf.removeFirst();
F = Union( F, buf );
}
F.insert (CFFactor (LcA, 1));
return F;
}
CanonicalForm
sqrfPart (const CanonicalForm& F)
{
if (F.inCoeffDomain())
return F;
CFMap M;
CanonicalForm A= compress (F, M);
CanonicalForm w, v, b;
CanonicalForm result;
int i= 1;
for (; i <= A.level(); i++)
{
if (!deriv (A, Variable (i)).isZero())
break;
}
w= gcd (A, deriv (A, Variable (i)));
b= A/w;
result= b;
if (degree (w) < 1)
return M (result);
i++;
for (; i <= A.level(); i++)
{
if (!deriv (w, Variable (i)).isZero())
{
b= w;
w= gcd (w, deriv (w, Variable (i)));
b /= w;
if (degree (b) < 1)
break;
CanonicalForm g= gcd (b, result);
if (degree (g) > 0)
result *= b/g;
if (degree (g) <= 0)
result *= b;
}
}
result= M (result);
return result;
}
#if !defined(HAVE_NTL)
static int divexp = 1;
static void divexpfunc ( CanonicalForm &, int & e )
{
e /= divexp;
}
CFFList sqrFreeFp ( const CanonicalForm & f )
{
CanonicalForm t0 = f, t, v, w, h;
CanonicalForm leadcf = t0.lc();
Variable x = f.mvar();
CFFList F;
int p = getCharacteristic();
int k, e = 1;
if ( ! leadcf.isOne() )
t0 /= leadcf;
divexp = p;
while ( t0.degree(x) > 0 )
{
t = gcd( t0, t0.deriv() );
v = t0 / t;
k = 0;
while ( v.degree(x) > 0 )
{
k = k+1;
if ( k % p == 0 )
{
t /= v;
k = k+1;
}
w = gcd( t, v );
h = v / w;
v = w;
t /= v;
if ( h.degree(x) > 0 )
F.append( CFFactor( h/h.lc(), e*k ) );
}
t0 = apply( t, divexpfunc );
e = p * e;
}
if ( ! leadcf.isOne() )
{
if ( !F.isEmpty() && (F.getFirst().exp() == 1) )
{
leadcf = F.getFirst().factor() * leadcf;
F.removeFirst();
}
F.insert( CFFactor( leadcf, 1 ) );
}
return F;
}
#endif
FLINTconvert.h
This file defines functions for conversion to FLINT (www.flintlib.org) and back.
isOn
bool isOn(int sw)
switches
Definition canonicalform.cc:1971
canonicalform.h
Header for factory's main class CanonicalForm.
content
CanonicalForm FACTORY_PUBLIC content(const CanonicalForm &)
CanonicalForm content ( const CanonicalForm & f ).
Definition cf_gcd.cc:603
lc
CanonicalForm lc(const CanonicalForm &f)
Definition canonicalform.h:304
icontent
CanonicalForm FACTORY_PUBLIC icontent(const CanonicalForm &f)
CanonicalForm icontent ( const CanonicalForm & f ).
Definition cf_gcd.cc:74
degree
int degree(const CanonicalForm &f)
Definition canonicalform.h:316
deriv
CanonicalForm deriv(const CanonicalForm &f, const Variable &x)
Definition canonicalform.h:346
CFFListIterator
ListIterator< CFFactor > CFFListIterator
Definition canonicalform.h:394
CFFList
List< CFFactor > CFFList
Definition canonicalform.h:393
Lc
CanonicalForm Lc(const CanonicalForm &f)
Definition canonicalform.h:307
CFFactor
Factor< CanonicalForm > CFFactor
Definition canonicalform.h:392
apply
CanonicalForm apply(const CanonicalForm &f, void(*mf)(CanonicalForm &, int &))
CanonicalForm apply ( const CanonicalForm & f, void (*mf)( CanonicalForm &, int & ) ).
Definition cf_ops.cc:402
getCharacteristic
int FACTORY_PUBLIC getCharacteristic()
Definition cf_char.cc:70
i
int i
Definition cfEzgcd.cc:132
k
int k
Definition cfEzgcd.cc:99
x
Variable x
Definition cfModGcd.cc:4090
p
int p
Definition cfModGcd.cc:4086
g
g
Definition cfModGcd.cc:4098
b
CanonicalForm b
Definition cfModGcd.cc:4111
bCommonDen
CanonicalForm bCommonDen(const CanonicalForm &f)
void psqr ( const CanonicalForm & f, const CanonicalForm & g, CanonicalForm & q, CanonicalForm & r,...
Definition cf_algorithm.cc:293
cf_algorithm.h
declarations of higher level algorithms.
cf_assert.h
assertions for Factory
cf_defs.h
factory switches.
SW_RATIONAL
static const int SW_RATIONAL
set to 1 for computations over Q
Definition cf_defs.h:31
compress
CanonicalForm compress(const CanonicalForm &f, CFMap &m)
CanonicalForm compress ( const CanonicalForm & f, CFMap & m ).
Definition cf_map.cc:210
cf_map.h
map polynomials
f
FILE * f
Definition checklibs.c:9
CFMap
class CFMap
Definition cf_map.h:85
CanonicalForm
factory's main class
Definition canonicalform.h:86
CanonicalForm::degree
int degree() const
Returns -1 for the zero polynomial and 0 if CO is in a base domain.
Definition canonicalform.cc:414
CanonicalForm::mvar
Variable mvar() const
mvar() returns the main variable of CO or Variable() if CO is in a base domain.
Definition canonicalform.cc:593
CanonicalForm::isOne
CF_NO_INLINE bool isOne() const
CanonicalForm::deriv
CanonicalForm deriv() const
deriv() - return the formal derivation of CO.
Definition canonicalform.cc:1300
CanonicalForm::inCoeffDomain
bool inCoeffDomain() const
Definition canonicalform.cc:122
CanonicalForm::lc
CanonicalForm lc() const
CanonicalForm CanonicalForm::lc (), Lc (), LC (), LC ( v ) const.
Definition canonicalform.cc:337
Factor::exp
int exp() const
Definition ftmpl_factor.h:31
Factor::factor
T factor() const
Definition ftmpl_factor.h:30
ListIterator::hasItem
int hasItem()
Definition ftmpl_list.cc:439
ListIterator::getItem
T & getItem() const
Definition ftmpl_list.cc:431
List::getFirst
T getFirst() const
Definition ftmpl_list.cc:279
List::removeFirst
void removeFirst()
Definition ftmpl_list.cc:287
List::sort
void sort(int(*)(const T &, const T &))
Definition ftmpl_list.cc:339
List::append
void append(const T &)
Definition ftmpl_list.cc:256
List::insert
void insert(const T &)
Definition ftmpl_list.cc:193
List::isEmpty
int isEmpty() const
Definition ftmpl_list.cc:267
Variable
factory's class for variables
Definition factory.h:127
result
return result
Definition facAbsBiFact.cc:76
y
const CanonicalForm int const CFList const Variable & y
Definition facAbsFact.cc:53
w
const CanonicalForm & w
Definition facAbsFact.cc:51
v
const Variable & v
< [in] a sqrfree bivariate poly
Definition facBivar.h:39
isZero
bool isZero(const CFArray &A)
checks if entries of A are zero
Definition facSparseHensel.h:468
sqrfPart
CanonicalForm sqrfPart(const CanonicalForm &F)
squarefree part of a poly
Definition fac_sqrfree.cc:115
sqrFreeZ
CFFList sqrFreeZ(const CanonicalForm &a)
Definition fac_sqrfree.cc:49
compareFactors
static int compareFactors(const CFFactor &f, const CFFactor &g)
Definition fac_sqrfree.cc:19
sortCFFList
CFFList sortCFFList(CFFList &F)
Definition fac_sqrfree.cc:25
sqrFreeFp
CFFList sqrFreeFp(const CanonicalForm &f)
Union
template List< Variable > Union(const List< Variable > &, const List< Variable > &)
h
STATIC_VAR Poly * h
Definition janet.cc:971
exp
gmp_float exp(const gmp_float &a)
Definition mpr_complex.cc:349
sign
static int sign(int x)
Definition ring.cc:3504
buf
int status int void * buf
Definition si_signals.h:69
A
#define A
Definition sirandom.c:24
M
#define M
Definition sirandom.c:25
gcd
int gcd(int a, int b)
Definition walkSupport.cc:836