Loading...
Searching...
No Matches
facFqBivarUtil.cc
Go to the documentation of this file.
/*****************************************************************************\
* Computer Algebra System SINGULAR
\*****************************************************************************/
/** @file facFqBivarUtil.cc
*
* This file provides utility functions for bivariate factorization
*
* @author Martin Lee
*
**/
/*****************************************************************************/
#include "config.h"
#include "timing.h"
#include "cf_map.h"
#include "cf_map_ext.h"
#include "templates/ftmpl_functions.h"
#include "ExtensionInfo.h"
#include "cf_algorithm.h"
#include "cf_factory.h"
#include "cf_util.h"
#include "imm.h"
#include "cf_iter.h"
#include "facFqBivarUtil.h"
#include "cfNewtonPolygon.h"
#include "facHensel.h"
#include "facMul.h"
#ifdef HAVE_FLINT
#include "FLINTconvert.h"
#endif
TIMING_DEFINE_PRINT(fac_log_deriv_div)
TIMING_DEFINE_PRINT(fac_log_deriv_mul)
TIMING_DEFINE_PRINT(fac_log_deriv_pre)
void append (CFList& factors1, const CFList& factors2)
{
for (CFListIterator i= factors2; i.hasItem(); i++)
{
if (!i.getItem().inCoeffDomain())
factors1.append (i.getItem());
}
return;
}
void decompress (CFList& factors, const CFMap& N)
{
for (CFListIterator i= factors; i.hasItem(); i++)
i.getItem()= N (i.getItem());
}
void decompress (CFFList& factors, const CFMap& N)
{
for (CFFListIterator i= factors; i.hasItem(); i++)
i.getItem()= CFFactor (N (i.getItem().factor()), i.getItem().exp());
}
void decompress (CFAFList& factors, const CFMap& N)
{
for (CFAFListIterator i= factors; i.hasItem(); i++)
i.getItem()= CFAFactor (N (i.getItem().factor()), i.getItem().minpoly(),
i.getItem().exp());
}
void appendSwapDecompress (CFList& factors1, const CFList& factors2,
const CFList& factors3, const bool swap1,
const bool swap2, const CFMap& N)
{
Variable x= Variable (1);
Variable y= Variable (2);
for (CFListIterator i= factors1; i.hasItem(); i++)
{
if (swap1)
{
if (!swap2)
i.getItem()= swapvar (i.getItem(), x, y);
}
else
{
if (swap2)
i.getItem()= swapvar (i.getItem(), y, x);
}
i.getItem()= N (i.getItem());
}
for (CFListIterator i= factors2; i.hasItem(); i++)
factors1.append (N (i.getItem()));
for (CFListIterator i= factors3; i.hasItem(); i++)
factors1.append (N (i.getItem()));
return;
}
void swapDecompress (CFList& factors, const bool swap, const CFMap& N)
{
Variable x= Variable (1);
Variable y= Variable (2);
for (CFListIterator i= factors; i.hasItem(); i++)
{
if (swap)
i.getItem()= swapvar (i.getItem(), x, y);
i.getItem()= N (i.getItem());
}
return;
}
static inline
bool GFInExtensionHelper (const CanonicalForm& F, const int number)
{
if (F.isOne()) return false;
InternalCF* buf;
int exp;
bool result= false;
if (F.inBaseDomain())
{
buf= F.getval();
exp= imm2int (buf);
if (exp%number != 0)
return true;
else
return result;
}
else
{
for (CFIterator i= F; i.hasTerms(); i++)
{
result= GFInExtensionHelper (i.coeff(), number);
if (result == true)
return result;
}
}
return result;
}
static inline
bool FqInExtensionHelper (const CanonicalForm& F, const CanonicalForm& gamma,
const CanonicalForm& delta, CFList& source,
CFList& dest)
{
bool result= false;
if (F.inBaseDomain())
return result;
else if (F.inCoeffDomain())
{
if (!fdivides (gamma, F))
return true;
else
{
int pos= findItem (source, F);
if (pos > 0)
return false;
Variable a;
hasFirstAlgVar (F, a);
int bound= ipower (getCharacteristic(), degree (getMipo (a)));
CanonicalForm buf= 1;
for (int i= 1; i < bound; i++)
{
buf *= gamma;
if (buf == F)
{
source.append (buf);
dest.append (power (delta, i));
return false;
}
}
return true;
}
}
else
{
for (CFIterator i= F; i.hasTerms(); i++)
{
result= FqInExtensionHelper (i.coeff(), gamma, delta, source, dest);
if (result == true)
return result;
}
}
return result;
}
bool isInExtension (const CanonicalForm& F, const CanonicalForm& gamma,
const int k, const CanonicalForm& delta,
CFList& source, CFList& dest)
{
bool result;
if (CFFactory::gettype() == GaloisFieldDomain)
{
int p= getCharacteristic();
int orderFieldExtension= ipower (p, getGFDegree()) - 1;
int order= ipower (p, k) - 1;
int number= orderFieldExtension/order;
result= GFInExtensionHelper (F, number);
return result;
}
else
{
result= FqInExtensionHelper (F, gamma, delta, source, dest);
return result;
}
}
CanonicalForm
mapDown (const CanonicalForm& F, const ExtensionInfo& info, CFList& source,
CFList& dest)
{
int k= info.getGFDegree();
Variable beta= info.getAlpha();
CanonicalForm primElem= info.getGamma();
CanonicalForm imPrimElem= info.getDelta();
if (k > 1)
return GFMapDown (F, k);
else if (k == 1)
return F;
if (/*k==0 &&*/ beta == Variable (1))
return F;
else /*if (k==0 && beta != Variable (1))*/
return mapDown (F, imPrimElem, primElem, beta, source, dest);
}
void appendTestMapDown (CFList& factors, const CanonicalForm& f,
const ExtensionInfo& info, CFList& source, CFList& dest)
{
int k= info.getGFDegree();
Variable beta= info.getBeta();
Variable alpha= info.getAlpha();
CanonicalForm delta= info.getDelta();
CanonicalForm gamma= info.getGamma();
CanonicalForm g= f;
int degMipoBeta=0;
if (!k && beta.level() == 1)
degMipoBeta= 1;
else if (!k && beta.level() != 1)
degMipoBeta= degree (getMipo (beta));
if (k > 1)
{
if (!isInExtension (g, gamma, k, delta, source, dest))
{
g= GFMapDown (g, k);
factors.append (g);
}
}
else if (k == 1)
{
if (!isInExtension (g, gamma, k, delta, source, dest))
factors.append (g);
}
else if (!k && beta == Variable (1))
{
if (degree (g, alpha) < degMipoBeta)
factors.append (g);
}
else if (!k && beta != Variable (1))
{
if (!isInExtension (g, gamma, k, delta, source, dest))
{
g= mapDown (g, delta, gamma, alpha, source, dest);
factors.append (g);
}
}
return;
}
void
appendMapDown (CFList& factors, const CanonicalForm& g,
const ExtensionInfo& info, CFList& source, CFList& dest)
{
int k= info.getGFDegree();
Variable beta= info.getBeta();
Variable alpha= info.getAlpha();
CanonicalForm gamma= info.getGamma();
CanonicalForm delta= info.getDelta();
if (k > 1)
factors.append (GFMapDown (g, k));
else if (k == 1)
factors.append (g);
else if (!k && beta == Variable (1))
factors.append (g);
else if (!k && beta != Variable (1))
factors.append (mapDown (g, delta, gamma, alpha, source, dest));
return;
}
void normalize (CFList& factors)
{
CanonicalForm lcinv;
for (CFListIterator i= factors; i.hasItem(); i++)
{
lcinv= 1/Lc (i.getItem());
i.getItem() *= lcinv;
}
return;
}
void normalize (CFFList& factors)
{
CanonicalForm lcinv;
for (CFFListIterator i= factors; i.hasItem(); i++)
{
lcinv= 1/ Lc (i.getItem().factor());
i.getItem()= CFFactor (i.getItem().factor()*lcinv,
i.getItem().exp());
}
return;
}
CFList subset (int index [], const int& s, const CFArray& elements,
bool& noSubset)
{
int r= elements.size();
int i= 0;
CFList result;
noSubset= false;
if (index[s - 1] == 0)
{
while (i < s)
{
index[i]= i + 1;
result.append (elements[i]);
i++;
}
return result;
}
int buf;
int k;
bool found= false;
if (index[s - 1] == r)
{
if (index[0] == r - s + 1)
{
noSubset= true;
return result;
}
else {
while (found == false)
{
if (index[s - 2 - i] < r - i - 1)
found= true;
i++;
}
buf= index[s - i - 1];
k= 0;
while (s - i - 1 + k < s)
{
index[s - i - 1 + k]= buf + k + 1;
k++;
}
}
for (int j= 0; j < s; j++)
result.append (elements[index[j] - 1]);
return result;
}
else
{
index[s - 1] += 1;
for (int j= 0; j < s; j++)
result.append (elements[index[j] - 1]);
return result;
}
}
CFArray copy (const CFList& list)
{
CFArray array= CFArray (list.length());
int j= 0;
for (CFListIterator i= list; i.hasItem(); i++, j++)
array[j]= i.getItem();
return array;
}
void indexUpdate (int index [], const int& subsetSize, const int& setSize,
bool& noSubset)
{
noSubset= false;
if (subsetSize > setSize)
{
noSubset= true;
return;
}
int * v= new int [setSize];
for (int i= 0; i < setSize; i++)
v[i]= index[i];
if (subsetSize == 1)
{
v[0]= v[0] - 1;
if (v[0] >= setSize)
{
noSubset= true;
delete [] v;
return;
}
}
else
{
if (v[subsetSize - 1] - v[0] + 1 == subsetSize && v[0] > 1)
{
if (v[0] + subsetSize - 1 > setSize)
{
noSubset= true;
delete [] v;
return;
}
v[0]= v[0] - 1;
for (int i= 1; i < subsetSize - 1; i++)
v[i]= v[i - 1] + 1;
v[subsetSize - 1]= v[subsetSize - 2];
}
else
{
if (v[0] + subsetSize - 1 > setSize)
{
noSubset= true;
delete [] v;
return;
}
for (int i= 1; i < subsetSize - 1; i++)
v[i]= v[i - 1] + 1;
v[subsetSize - 1]= v[subsetSize - 2];
}
}
for (int i= 0; i < setSize; i++)
index[i]= v[i];
delete [] v;
}
int subsetDegree (const CFList& S)
{
int result= 0;
for (CFListIterator i= S; i.hasItem(); i++)
result += degree (i.getItem(), Variable (1));
return result;
}
CFFList multiplicity (CanonicalForm& F, const CFList& factors)
{
if (F.inCoeffDomain())
return CFFList (CFFactor (F, 1));
CFFList result;
int multi= 0;
CanonicalForm quot;
for (CFListIterator i= factors; i.hasItem(); i++)
{
while (fdivides (i.getItem(), F, quot))
{
multi++;
F= quot;
}
if (multi > 0)
result.append (CFFactor (i.getItem(), multi));
multi= 0;
}
return result;
}
#ifdef HAVE_NTL
CFArray
logarithmicDerivative (const CanonicalForm& F, const CanonicalForm& G, int l,
CanonicalForm& Q
)
{
Variable x= Variable (2);
Variable y= Variable (1);
CanonicalForm xToL= power (x, l);
CanonicalForm q,r;
CanonicalForm logDeriv;
TIMING_START (fac_log_deriv_div);
q= newtonDiv (F, G, xToL);
TIMING_END_AND_PRINT (fac_log_deriv_div, "time for division in logderiv1: ");
TIMING_START (fac_log_deriv_mul);
logDeriv= mulMod2 (q, deriv (G, y), xToL);
TIMING_END_AND_PRINT (fac_log_deriv_mul, "time to multiply in logderiv1: ");
if (degree (logDeriv, x) == 0)
{
Q= q;
return CFArray();
}
int j= degree (logDeriv, y) + 1;
CFArray result= CFArray (j);
CFIterator ii;
for (CFIterator i= logDeriv; i.hasTerms() && !logDeriv.isZero(); i++)
{
if (i.coeff().inCoeffDomain())
result[0] += i.coeff()*power (x,i.exp());
else
{
for (ii= i.coeff(); ii.hasTerms(); ii++)
result[ii.exp()] += ii.coeff()*power (x,i.exp());
}
}
Q= q;
return result;
}
CFArray
logarithmicDerivative (const CanonicalForm& F, const CanonicalForm& G, int l,
int oldL, const CanonicalForm& oldQ, CanonicalForm& Q
)
{
Variable x= Variable (2);
Variable y= Variable (1);
CanonicalForm xToL= power (x, l);
CanonicalForm xToOldL= power (x, oldL);
CanonicalForm xToLOldL= power (x, l-oldL);
CanonicalForm q,r;
CanonicalForm logDeriv;
CanonicalForm bufF;
TIMING_START (fac_log_deriv_pre);
if ((oldL > 100 && l - oldL < 50) || (oldL < 100 && l - oldL < 30))
{
bufF= F;
CanonicalForm oldF= mulMod2 (G, oldQ, xToL);
bufF -= oldF;
bufF= div (bufF, xToOldL);
}
else
{
//middle product style computation of [G*oldQ]^{l}_{oldL}
CanonicalForm G3= div (G, xToOldL);
CanonicalForm Up= mulMod2 (G3, oldQ, xToLOldL);
CanonicalForm xToOldL2= power (x, (oldL+1)/2);
CanonicalForm G2= mod (G, xToOldL);
CanonicalForm G1= div (G2, xToOldL2);
CanonicalForm G0= mod (G2, xToOldL2);
CanonicalForm oldQ1= div (oldQ, xToOldL2);
CanonicalForm oldQ0= mod (oldQ, xToOldL2);
CanonicalForm Mid;
if (oldL % 2 == 1)
Mid= mulMod2 (G1, oldQ1*x, xToLOldL);
else
Mid= mulMod2 (G1, oldQ1, xToLOldL);
//computation of Low might be faster using a real middle product?
CanonicalForm Low= mulMod2 (G0, oldQ1, xToOldL)+mulMod2 (G1, oldQ0, xToOldL);
Low= div (Low, power (x, oldL/2));
Low= mod (Low, xToLOldL);
Up += Mid + Low;
bufF= div (F, xToOldL);
bufF -= Up;
}
TIMING_END_AND_PRINT (fac_log_deriv_pre, "time to preprocess: ");
TIMING_START (fac_log_deriv_div);
if (l-oldL > 0)
q= newtonDiv (bufF, G, xToLOldL);
else
q= 0;
q *= xToOldL;
q += oldQ;
TIMING_END_AND_PRINT (fac_log_deriv_div, "time for div in logderiv2: ");
TIMING_START (fac_log_deriv_mul);
logDeriv= mulMod2 (q, deriv (G, y), xToL);
TIMING_END_AND_PRINT (fac_log_deriv_mul, "time for mul in logderiv2: ");
if (degree (logDeriv, x) == 0)
{
Q= q;
return CFArray();
}
int j= degree (logDeriv,y) + 1;
CFArray result= CFArray (j);
CFIterator ii;
for (CFIterator i= logDeriv; i.hasTerms() && !logDeriv.isZero(); i++)
{
if (i.coeff().inCoeffDomain())
result[0] += i.coeff()*power (x,i.exp());
else
{
for (ii= i.coeff(); ii.hasTerms(); ii++)
result[ii.exp()] += ii.coeff()*power (x,i.exp());
}
}
Q= q;
return result;
}
#endif
void
writeInMatrix (CFMatrix& M, const CFArray& A, const int column,
const int startIndex
)
{
ASSERT (A.size () - startIndex >= 0, "wrong starting index");
ASSERT (A.size () - startIndex <= M.rows(), "wrong starting index");
ASSERT (column > 0 && column <= M.columns(), "wrong column");
if (A.size() - startIndex <= 0) return;
int j= 1;
for (int i= startIndex; i < A.size(); i++, j++)
M (j, column)= A [i];
}
CFArray getCoeffs (const CanonicalForm& F, const int k)
{
ASSERT (F.isUnivariate() || F.inCoeffDomain(), "univariate input expected");
if (degree (F, 2) < k)
return CFArray();
CFArray result= CFArray (degree (F) - k + 1);
CFIterator j= F;
for (int i= degree (F); i >= k; i--)
{
if (j.exp() == i)
{
result [i - k]= j.coeff();
j++;
if (!j.hasTerms())
return result;
}
else
result[i - k]= 0;
}
return result;
}
CFArray getCoeffs (const CanonicalForm& F, const int k, const Variable& alpha)
{
ASSERT (F.isUnivariate() || F.inCoeffDomain(), "univariate input expected");
if (degree (F, 2) < k)
return CFArray ();
int d= degree (getMipo (alpha));
CFArray result= CFArray ((degree (F) - k + 1)*d);
CFIterator j= F;
CanonicalForm buf;
CFIterator iter;
for (int i= degree (F); i >= k; i--)
{
if (j.exp() == i)
{
iter= j.coeff();
for (int l= degree (j.coeff(), alpha); l >= 0; l--)
{
if (iter.exp() == l)
{
result [(i - k)*d + l]= iter.coeff();
iter++;
if (!iter.hasTerms())
break;
}
}
j++;
if (!j.hasTerms())
return result;
}
else
{
for (int l= 0; l < d; l++)
result[(i - k)*d + l]= 0;
}
}
return result;
}
#ifdef HAVE_NTL
CFArray
getCoeffs (const CanonicalForm& G, const int k, const int l, const int degMipo,
const Variable& alpha, const CanonicalForm& evaluation,
const mat_zz_p& M)
{
ASSERT (G.isUnivariate() || G.inCoeffDomain(), "univariate input expected");
CanonicalForm F= G (G.mvar() - evaluation, G.mvar());
if (F.isZero())
return CFArray ();
Variable y= Variable (2);
F= F (power (y, degMipo), y);
F= F (y, alpha);
zz_pX NTLF= convertFacCF2NTLzzpX (F);
NTLF.rep.SetLength (l*degMipo);
NTLF.rep= M*NTLF.rep;
NTLF.normalize();
F= convertNTLzzpX2CF (NTLF, y);
if (degree (F, 2) < k)
return CFArray();
CFArray result= CFArray (degree (F) - k + 1);
CFIterator j= F;
for (int i= degree (F); i >= k; i--)
{
if (j.exp() == i)
{
result [i - k]= j.coeff();
j++;
if (!j.hasTerms())
return result;
}
else
result[i - k]= 0;
}
return result;
}
#endif
#ifdef HAVE_FLINT
CFArray
getCoeffs (const CanonicalForm& G, const int k, const int l, const int degMipo,
const Variable& alpha, const CanonicalForm& evaluation,
const nmod_mat_t M)
{
ASSERT (G.isUnivariate() || G.inCoeffDomain(), "univariate input expected");
CanonicalForm F= G (G.mvar() - evaluation, G.mvar());
if (F.isZero())
return CFArray ();
Variable y= Variable (2);
F= F (power (y, degMipo), y);
F= F (y, alpha);
nmod_poly_t FLINTF;
nmod_mat_t MFLINTF, mulResult;
nmod_mat_init (MFLINTF, l*degMipo, 1, getCharacteristic());
nmod_mat_init (mulResult, l*degMipo, 1, getCharacteristic());
convertFacCF2nmod_poly_t (FLINTF, F);
#ifndef slong
#define slong long
#endif
slong i;
for (i= 0; i < FLINTF->length; i++)
nmod_mat_entry (MFLINTF, i, 0)= FLINTF->coeffs[i];
for (; i < MFLINTF->r; i++)
nmod_mat_entry (MFLINTF, i, 0)= 0;
nmod_mat_mul (mulResult, M, MFLINTF);
F= 0;
for (i= 0; i < mulResult->r; i++)
F += CanonicalForm ((long) nmod_mat_entry (mulResult, i, 0))*power (y, i);
nmod_mat_clear (MFLINTF);
nmod_mat_clear (mulResult);
nmod_poly_clear(FLINTF);
if (degree (F, 2) < k)
return CFArray();
CFArray result= CFArray (degree (F) - k + 1);
CFIterator j= F;
for (int i= degree (F); i >= k; i--)
{
if (j.exp() == i)
{
result [i - k]= j.coeff();
j++;
if (!j.hasTerms())
return result;
}
else
result[i - k]= 0;
}
return result;
}
#endif
int * computeBounds (const CanonicalForm& F, int& n, bool& isIrreducible)
{
n= degree (F, 1);
int* result= new int [n];
int sizeOfNewtonPolygon;
int** newtonPolyg= newtonPolygon (F, sizeOfNewtonPolygon);
isIrreducible= false;
if (sizeOfNewtonPolygon == 3)
{
bool check1=
(newtonPolyg[0][0]==0 || newtonPolyg[1][0]==0 || newtonPolyg[2][0]==0);
if (check1)
{
bool check2=
(newtonPolyg[0][1]==0 || newtonPolyg[1][1]==0 || newtonPolyg[2][0]==0);
if (check2)
{
int p=getCharacteristic();
int d=1;
char bufGFName='Z';
bool GF= (CFFactory::gettype()==GaloisFieldDomain);
if (GF)
{
d= getGFDegree();
bufGFName=gf_name;
}
setCharacteristic(0);
CanonicalForm tmp= gcd (newtonPolyg[0][0],newtonPolyg[0][1]); // maybe it's better to use plain intgcd
tmp= gcd (tmp, newtonPolyg[1][0]);
tmp= gcd (tmp, newtonPolyg[1][1]);
tmp= gcd (tmp, newtonPolyg[2][0]);
tmp= gcd (tmp, newtonPolyg[2][1]);
isIrreducible= (tmp==1);
if (GF)
setCharacteristic (p, d, bufGFName);
else
setCharacteristic(p);
}
}
}
int minX, minY, maxX, maxY;
minX= newtonPolyg [0] [0];
minY= newtonPolyg [0] [1];
maxX= minX;
maxY= minY;
int indZero= 0;
for (int i= 1; i < sizeOfNewtonPolygon; i++)
{
if (newtonPolyg[i][1] == 0)
{
if (newtonPolyg[indZero][1] == 0)
{
if (newtonPolyg[indZero][0] < newtonPolyg[i][0])
indZero= i;
}
else
indZero= i;
}
if (minX > newtonPolyg [i] [0])
minX= newtonPolyg [i] [0];
if (maxX < newtonPolyg [i] [0])
maxX= newtonPolyg [i] [0];
if (minY > newtonPolyg [i] [1])
minY= newtonPolyg [i] [1];
if (maxY < newtonPolyg [i] [1])
maxY= newtonPolyg [i] [1];
}
int slopeNum, slopeDen, constTerm;
bool negativeSlope=false;
if (indZero != sizeOfNewtonPolygon - 1)
{
slopeNum= newtonPolyg[indZero+1][0]-newtonPolyg[indZero][0];
slopeDen= newtonPolyg[indZero+1][1];
constTerm= newtonPolyg[indZero][0];
}
else
{
slopeNum= newtonPolyg[0][0]-newtonPolyg[indZero][0];
slopeDen= newtonPolyg[0][1];
constTerm= newtonPolyg[indZero][0];
}
if (slopeNum < 0)
{
slopeNum= -slopeNum;
negativeSlope= true;
}
int k= 0;
int* point= new int [2];
for (int i= 0; i < n; i++)
{
if (((indZero+1) < sizeOfNewtonPolygon && (i+1) > newtonPolyg[indZero+1][1])
|| ((indZero+1) >= sizeOfNewtonPolygon && (i+1) > newtonPolyg[0][1]))
{
if (indZero + 1 != sizeOfNewtonPolygon)
indZero++;
else
indZero= 0;
if (indZero != sizeOfNewtonPolygon - 1)
{
slopeNum= newtonPolyg[indZero+1][0]-newtonPolyg[indZero][0];
slopeDen= newtonPolyg[indZero+1][1]-newtonPolyg[indZero][1];
constTerm= newtonPolyg[indZero][0];
}
else
{
slopeNum= newtonPolyg[0][0]-newtonPolyg[indZero][0];
slopeDen= newtonPolyg[0][1]-newtonPolyg[indZero][1];
constTerm= newtonPolyg[indZero][0];
}
if (slopeNum < 0)
{
negativeSlope= true;
slopeNum= - slopeNum;
k= (int) -(((long) slopeNum*((i+1)-newtonPolyg[indZero][1])+slopeDen-1)/
slopeDen) + constTerm;
}
else
k= (int) (((long) slopeNum*((i+1)-newtonPolyg[indZero][1])) / slopeDen)
+ constTerm;
}
else
{
if (negativeSlope)
k= (int) -(((long) slopeNum*((i+1)-newtonPolyg[indZero][1])+slopeDen-1)/
slopeDen) + constTerm;
else
k= (int) ((long) slopeNum*((i+1)-newtonPolyg[indZero][1])) / slopeDen
+ constTerm;
}
if (i + 1 > maxY || i + 1 < minY)
{
result [i]= 0;
continue;
}
point [0]= k;
point [1]= i + 1;
if (!isInPolygon (newtonPolyg, sizeOfNewtonPolygon, point) && k > 0)
k= 0;
result [i]= k;
}
delete [] point;
for (int i= 0; i < sizeOfNewtonPolygon; i++)
delete [] newtonPolyg[i];
delete [] newtonPolyg;
return result;
}
int *
computeBoundsWrtDiffMainvar (const CanonicalForm& F, int& n,
bool& isIrreducible)
{
n= degree (F, 2);
int* result= new int [n];
int sizeOfNewtonPolygon;
int** newtonPolyg= newtonPolygon (F, sizeOfNewtonPolygon);
isIrreducible= false;
if (sizeOfNewtonPolygon == 3)
{
bool check1=
(newtonPolyg[0][0]==0 || newtonPolyg[1][0]==0 || newtonPolyg[2][0]==0);
if (check1)
{
bool check2=
(newtonPolyg[0][1]==0 || newtonPolyg[1][1]==0 || newtonPolyg[2][0]==0);
if (check2)
{
int p=getCharacteristic();
int d=1;
char bufGFName='Z';
bool GF= (CFFactory::gettype()==GaloisFieldDomain);
if (GF)
{
d= getGFDegree();
bufGFName=gf_name;
}
setCharacteristic(0);
CanonicalForm tmp= gcd (newtonPolyg[0][0],newtonPolyg[0][1]);
tmp= gcd (tmp, newtonPolyg[1][0]);
tmp= gcd (tmp, newtonPolyg[1][1]);
tmp= gcd (tmp, newtonPolyg[2][0]);
tmp= gcd (tmp, newtonPolyg[2][1]);
isIrreducible= (tmp==1);
if (GF)
setCharacteristic (p, d, bufGFName);
else
setCharacteristic(p);
}
}
}
int swap;
for (int i= 0; i < sizeOfNewtonPolygon; i++)
{
swap= newtonPolyg[i][1];
newtonPolyg[i][1]=newtonPolyg[i][0];
newtonPolyg[i][0]= swap;
}
sizeOfNewtonPolygon= polygon(newtonPolyg, sizeOfNewtonPolygon);
int minX, minY, maxX, maxY;
minX= newtonPolyg [0] [0];
minY= newtonPolyg [0] [1];
maxX= minX;
maxY= minY;
int indZero= 0;
for (int i= 1; i < sizeOfNewtonPolygon; i++)
{
if (newtonPolyg[i][1] == 0)
{
if (newtonPolyg[indZero][1] == 0)
{
if (newtonPolyg[indZero][0] < newtonPolyg[i][0])
indZero= i;
}
else
indZero= i;
}
if (minX > newtonPolyg [i] [0])
minX= newtonPolyg [i] [0];
if (maxX < newtonPolyg [i] [0])
maxX= newtonPolyg [i] [0];
if (minY > newtonPolyg [i] [1])
minY= newtonPolyg [i] [1];
if (maxY < newtonPolyg [i] [1])
maxY= newtonPolyg [i] [1];
}
int slopeNum, slopeDen, constTerm;
bool negativeSlope=false;
if (indZero != sizeOfNewtonPolygon - 1)
{
slopeNum= newtonPolyg[indZero+1][0]-newtonPolyg[indZero][0];
slopeDen= newtonPolyg[indZero+1][1];
constTerm= newtonPolyg[indZero][0];
}
else
{
slopeNum= newtonPolyg[0][0]-newtonPolyg[indZero][0];
slopeDen= newtonPolyg[0][1];
constTerm= newtonPolyg[indZero][0];
}
if (slopeNum < 0)
{
slopeNum= -slopeNum;
negativeSlope= true;
}
int k= 0;
int* point= new int [2];
for (int i= 0; i < n; i++)
{
if (((indZero+1) < sizeOfNewtonPolygon && (i+1) > newtonPolyg[indZero+1][1])
|| ((indZero+1) >= sizeOfNewtonPolygon && (i+1) > newtonPolyg[0][1]))
{
if (indZero + 1 != sizeOfNewtonPolygon)
indZero++;
else
indZero= 0;
if (indZero != sizeOfNewtonPolygon - 1)
{
slopeNum= newtonPolyg[indZero+1][0]-newtonPolyg[indZero][0];
slopeDen= newtonPolyg[indZero+1][1]-newtonPolyg[indZero][1];
constTerm= newtonPolyg[indZero][0];
}
else
{
slopeNum= newtonPolyg[0][0]-newtonPolyg[indZero][0];
slopeDen= newtonPolyg[0][1]-newtonPolyg[indZero][1];
constTerm= newtonPolyg[indZero][0];
}
if (slopeNum < 0)
{
negativeSlope= true;
slopeNum= - slopeNum;
k= (int) -(((long) slopeNum*((i+1)-newtonPolyg[indZero][1])+slopeDen-1)/
slopeDen) + constTerm;
}
else
k= (int) (((long) slopeNum*((i+1)-newtonPolyg[indZero][1])) / slopeDen)
+ constTerm;
}
else
{
if (negativeSlope)
k= (int) -(((long) slopeNum*((i+1)-newtonPolyg[indZero][1])+slopeDen-1)/
slopeDen) + constTerm;
else
k= (int) ((long) slopeNum*((i+1)-newtonPolyg[indZero][1])) / slopeDen
+ constTerm;
}
if (i + 1 > maxY || i + 1 < minY)
{
result [i]= 0;
continue;
}
point [0]= k;
point [1]= i + 1;
if (!isInPolygon (newtonPolyg, sizeOfNewtonPolygon, point) && k > 0)
k= 0;
result [i]= k;
}
delete [] point;
for (int i= 0; i < sizeOfNewtonPolygon; i++)
delete [] newtonPolyg[i];
delete [] newtonPolyg;
return result;
}
int
substituteCheck (const CanonicalForm& F, const Variable& x)
{
if (F.inCoeffDomain())
return 0;
if (degree (F, x) < 0)
return 0;
CanonicalForm f= swapvar (F, F.mvar(), x);
int sizef= 0;
for (CFIterator i= f; i.hasTerms(); i++, sizef++)
{
if (i.exp() == 1)
return 0;
}
int * expf= new int [sizef];
int j= 0;
for (CFIterator i= f; i.hasTerms(); i++, j++)
expf [j]= i.exp();
int indf= sizef - 1;
if (expf[indf] == 0)
indf--;
int result= expf[indf];
for (int i= indf - 1; i >= 0; i--)
{
if (expf [i]%result != 0)
{
delete [] expf;
return 0;
}
}
delete [] expf;
return result;
}
static int
substituteCheck (const CanonicalForm& F, const CanonicalForm& G)
{
if (F.inCoeffDomain() || G.inCoeffDomain())
return 0;
Variable x= Variable (1);
if (degree (F, x) <= 1 || degree (G, x) <= 1)
return 0;
CanonicalForm f= swapvar (F, F.mvar(), x);
CanonicalForm g= swapvar (G, G.mvar(), x);
int sizef= 0;
int sizeg= 0;
for (CFIterator i= f; i.hasTerms(); i++, sizef++)
{
if (i.exp() == 1)
return 0;
}
for (CFIterator i= g; i.hasTerms(); i++, sizeg++)
{
if (i.exp() == 1)
return 0;
}
int * expf= new int [sizef];
int * expg= new int [sizeg];
int j= 0;
for (CFIterator i= f; i.hasTerms(); i++, j++)
{
expf [j]= i.exp();
}
j= 0;
for (CFIterator i= g; i.hasTerms(); i++, j++)
{
expg [j]= i.exp();
}
int indf= sizef - 1;
int indg= sizeg - 1;
if (expf[indf] == 0)
indf--;
if (expg[indg] == 0)
indg--;
if ((expg[indg]%expf [indf] != 0 && expf[indf]%expg[indg] != 0) ||
(expg[indg] == 1 && expf[indf] == 1))
{
delete [] expg;
delete [] expf;
return 0;
}
int result;
if (expg [indg]%expf [indf] == 0)
result= expf[indf];
else
result= expg[indg];
for (int i= indf - 1; i >= 0; i--)
{
if (expf [i]%result != 0)
{
delete [] expf;
delete [] expg;
return 0;
}
}
for (int i= indg - 1; i >= 0; i--)
{
if (expg [i]%result != 0)
{
delete [] expf;
delete [] expg;
return 0;
}
}
delete [] expg;
delete [] expf;
return result;
}
int recSubstituteCheck (const CanonicalForm& F, const int d)
{
if (F.inCoeffDomain())
return 0;
Variable x= Variable (1);
if (degree (F, x) <= 1)
return 0;
CanonicalForm f= swapvar (F, F.mvar(), x);
int sizef= 0;
for (CFIterator i= f; i.hasTerms(); i++, sizef++)
{
if (i.exp() == 1)
return 0;
}
int * expf= new int [sizef];
int j= 0;
for (CFIterator i= f; i.hasTerms(); i++, j++)
{
expf [j]= i.exp();
}
int indf= sizef - 1;
if (expf[indf] == 0)
indf--;
if ((d%expf [indf] != 0 && expf[indf]%d != 0) || (expf[indf] == 1))
{
delete [] expf;
return 0;
}
int result;
if (d%expf [indf] == 0)
result= expf[indf];
else
result= d;
for (int i= indf - 1; i >= 0; i--)
{
if (expf [i]%result != 0)
{
delete [] expf;
return 0;
}
}
delete [] expf;
return result;
}
int substituteCheck (const CFList& L)
{
ASSERT (L.length() > 1, "expected a list of at least two elements");
if (L.length() < 2)
return 0;
CFListIterator i= L;
i++;
int result= substituteCheck (L.getFirst(), i.getItem());
if (result <= 1)
return result;
i++;
for (;i.hasItem(); i++)
{
result= recSubstituteCheck (i.getItem(), result);
if (result <= 1)
return result;
}
return result;
}
void
subst (const CanonicalForm& F, CanonicalForm& A, const int d, const Variable& x)
{
if (d <= 1)
{
A= F;
return;
}
if (degree (F, x) <= 0)
{
A= F;
return;
}
CanonicalForm C= 0;
CanonicalForm f= swapvar (F, x, F.mvar());
for (CFIterator i= f; i.hasTerms(); i++)
C += i.coeff()*power (f.mvar(), i.exp()/ d);
A= swapvar (C, x, F.mvar());
}
CanonicalForm
reverseSubst (const CanonicalForm& F, const int d, const Variable& x)
{
if (d <= 1)
return F;
if (degree (F, x) <= 0)
return F;
CanonicalForm f= swapvar (F, x, F.mvar());
CanonicalForm result= 0;
for (CFIterator i= f; i.hasTerms(); i++)
result += i.coeff()*power (f.mvar(), d*i.exp());
return swapvar (result, x, F.mvar());
}
void
reverseSubst (CFList& L, const int d, const Variable& x)
{
for (CFListIterator i= L; i.hasItem(); i++)
i.getItem()= reverseSubst (i.getItem(), d, x);
}
ExtensionInfo.h
This file provides a class to store information about finite fields and extensions thereof.
FLINTconvert.h
This file defines functions for conversion to FLINT (www.flintlib.org) and back.
convertNTLzzpX2CF
CanonicalForm convertNTLzzpX2CF(const zz_pX &poly, const Variable &x)
Definition NTLconvert.cc:255
convertFacCF2NTLzzpX
zz_pX convertFacCF2NTLzzpX(const CanonicalForm &f)
Definition NTLconvert.cc:105
swap
#define swap(_i, _j)
power
CanonicalForm power(const CanonicalForm &f, int n)
exponentiation
Definition canonicalform.cc:1896
CFAFactor
AFactor< CanonicalForm > CFAFactor
Definition canonicalform.h:389
div
CF_NO_INLINE FACTORY_PUBLIC CanonicalForm div(const CanonicalForm &, const CanonicalForm &)
mod
CF_NO_INLINE FACTORY_PUBLIC CanonicalForm mod(const CanonicalForm &, const CanonicalForm &)
CFAFListIterator
ListIterator< CFAFactor > CFAFListIterator
Definition canonicalform.h:391
degree
int degree(const CanonicalForm &f)
Definition canonicalform.h:316
deriv
CanonicalForm deriv(const CanonicalForm &f, const Variable &x)
Definition canonicalform.h:346
getGFDegree
int getGFDegree()
Definition cf_char.cc:75
CFArray
Array< CanonicalForm > CFArray
Definition canonicalform.h:397
setCharacteristic
void FACTORY_PUBLIC setCharacteristic(int c)
Definition cf_char.cc:28
hasFirstAlgVar
bool hasFirstAlgVar(const CanonicalForm &f, Variable &a)
check if poly f contains an algebraic variable a
Definition cf_ops.cc:679
CFFListIterator
ListIterator< CFFactor > CFFListIterator
Definition canonicalform.h:394
CFMatrix
Matrix< CanonicalForm > CFMatrix
Definition canonicalform.h:398
swapvar
CanonicalForm FACTORY_PUBLIC swapvar(const CanonicalForm &, const Variable &, const Variable &)
swapvar() - swap variables x1 and x2 in f.
Definition cf_ops.cc:168
CFListIterator
ListIterator< CanonicalForm > CFListIterator
Definition canonicalform.h:396
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
CFList
List< CanonicalForm > CFList
Definition canonicalform.h:395
CFAFList
List< CFAFactor > CFAFList
Definition canonicalform.h:390
getCharacteristic
int FACTORY_PUBLIC getCharacteristic()
Definition cf_char.cc:70
N
const CanonicalForm CFMap CFMap & N
Definition cfEzgcd.cc:56
l
int l
Definition cfEzgcd.cc:100
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
isInPolygon
bool isInPolygon(int **points, int sizePoints, int *point)
check if point is inside a polygon described by points
Definition cfNewtonPolygon.cc:383
newtonPolygon
int ** newtonPolygon(const CanonicalForm &F, int &sizeOfNewtonPoly)
compute the Newton polygon of a bivariate polynomial
Definition cfNewtonPolygon.cc:282
polygon
int polygon(int **points, int sizePoints)
compute a polygon
Definition cfNewtonPolygon.cc:172
cfNewtonPolygon.h
This file provides functions to compute the Newton polygon of a bivariate polynomial.
cf_algorithm.h
declarations of higher level algorithms.
fdivides
bool fdivides(const CanonicalForm &f, const CanonicalForm &g)
ASSERT
#define ASSERT(expression, message)
Definition cf_assert.h:99
GaloisFieldDomain
#define GaloisFieldDomain
Definition cf_defs.h:18
cf_factory.h
Interface to generate InternalCF's over various domains from intrinsic types or mpz_t's.
cf_iter.h
Iterators for CanonicalForm's.
bound
static CanonicalForm bound(const CFMatrix &M)
Definition cf_linsys.cc:460
cf_map.h
map polynomials
findItem
int findItem(const CFList &list, const CanonicalForm &item)
helper function
Definition cf_map_ext.cc:42
GFMapDown
CanonicalForm GFMapDown(const CanonicalForm &F, int k)
maps a polynomial over to a polynomial over , d needs to be a multiple of k
Definition cf_map_ext.cc:277
mapDown
static CanonicalForm mapDown(const CanonicalForm &F, const Variable &alpha, const CanonicalForm &G, CFList &source, CFList &dest)
the CanonicalForm G is the output of map_up, returns F considered as an element over ,...
Definition cf_map_ext.cc:124
cf_map_ext.h
This file implements functions to map between extensions of finite fields.
ipower
int ipower(int b, int m)
int ipower ( int b, int m )
Definition cf_util.cc:27
cf_util.h
f
FILE * f
Definition checklibs.c:9
Array::size
int size() const
Definition ftmpl_array.cc:92
CFFactory::gettype
static int gettype()
Definition cf_factory.h:28
CFIterator
class to iterate through CanonicalForm's
Definition cf_iter.h:44
CFIterator::exp
CF_NO_INLINE int exp() const
get the current exponent
CFIterator::coeff
CF_NO_INLINE CanonicalForm coeff() const
get the current coefficient
CFIterator::hasTerms
CF_NO_INLINE int hasTerms() const
check if iterator has reached the end of CanonicalForm
CFMap
class CFMap
Definition cf_map.h:85
CanonicalForm
factory's main class
Definition canonicalform.h:86
CanonicalForm::isZero
CF_NO_INLINE bool isZero() const
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::getval
InternalCF * getval() const
Definition canonicalform.cc:34
CanonicalForm::isOne
CF_NO_INLINE bool isOne() const
CanonicalForm::inCoeffDomain
bool inCoeffDomain() const
Definition canonicalform.cc:122
CanonicalForm::inBaseDomain
bool inBaseDomain() const
Definition canonicalform.cc:104
CanonicalForm::isUnivariate
bool isUnivariate() const
Definition canonicalform.cc:155
ExtensionInfo
ExtensionInfo contains information about extension.
Definition ExtensionInfo.h:51
InternalCF
virtual class for internal CanonicalForm's
Definition int_cf.h:47
List::getFirst
T getFirst() const
Definition ftmpl_list.cc:279
List::length
int length() const
Definition ftmpl_list.cc:273
List::append
void append(const T &)
Definition ftmpl_list.cc:256
Variable
factory's class for variables
Definition factory.h:127
iter
CFFListIterator iter
Definition facAbsBiFact.cc:54
alpha
Variable alpha
Definition facAbsBiFact.cc:52
result
return result
Definition facAbsBiFact.cc:76
slong
#define slong
evaluation
const CanonicalForm int const CFList & evaluation
Definition facAbsFact.cc:52
s
const CanonicalForm int s
Definition facAbsFact.cc:51
y
const CanonicalForm int const CFList const Variable & y
Definition facAbsFact.cc:53
beta
Variable beta
Definition facAbsFact.cc:95
append
CFFList append(const CFFList &Inputlist, const CFFactor &TheFactor)
Definition facAlgFuncUtil.cc:32
v
const Variable & v
< [in] a sqrfree bivariate poly
Definition facBivar.h:39
found
bool found
Definition facFactorize.cc:55
GFInExtensionHelper
static bool GFInExtensionHelper(const CanonicalForm &F, const int number)
Definition facFqBivarUtil.cc:111
subsetDegree
int subsetDegree(const CFList &S)
compute the sum of degrees in Variable(1) of elements in S
Definition facFqBivarUtil.cc:428
logarithmicDerivative
CFArray logarithmicDerivative(const CanonicalForm &F, const CanonicalForm &G, int l, CanonicalForm &Q)
compute the coefficients of the logarithmic derivative of G mod Variable (2)^l over Fq
Definition facFqBivarUtil.cc:459
computeBounds
int * computeBounds(const CanonicalForm &F, int &n, bool &isIrreducible)
compute bounds for logarithmic derivative as described in K. Belabas, M. van Hoeij,...
Definition facFqBivarUtil.cc:768
appendTestMapDown
void appendTestMapDown(CFList &factors, const CanonicalForm &f, const ExtensionInfo &info, CFList &source, CFList &dest)
test if g is in a subfield of the current field, if so map it down and append it to factors
Definition facFqBivarUtil.cc:223
factors2
const CFList & factors2
Definition facFqBivarUtil.cc:42
appendSwapDecompress
void appendSwapDecompress(CFList &factors1, const CFList &factors2, const CFList &factors3, const bool swap1, const bool swap2, const CFMap &N)
first swap Variables in factors1 if necessary, then append factors2 and factors3 on factors1 and fina...
Definition facFqBivarUtil.cc:70
mapDown
CanonicalForm mapDown(const CanonicalForm &F, const ExtensionInfo &info, CFList &source, CFList &dest)
map a poly into a subfield of the current field, no testing is performed!
Definition facFqBivarUtil.cc:206
normalize
void normalize(CFList &factors)
normalize factors, i.e. make factors monic
Definition facFqBivarUtil.cc:286
indexUpdate
void indexUpdate(int index[], const int &subsetSize, const int &setSize, bool &noSubset)
update index
Definition facFqBivarUtil.cc:373
appendMapDown
void appendMapDown(CFList &factors, const CanonicalForm &g, const ExtensionInfo &info, CFList &source, CFList &dest)
map g down into a subfield of the current field and append it to factors
Definition facFqBivarUtil.cc:267
reverseSubst
CanonicalForm reverseSubst(const CanonicalForm &F, const int d, const Variable &x)
reverse a substitution x^d->x
Definition facFqBivarUtil.cc:1295
subst
void subst(const CanonicalForm &F, CanonicalForm &A, const int d, const Variable &x)
substitute x^d by x in F
Definition facFqBivarUtil.cc:1275
getCoeffs
CFArray getCoeffs(const CanonicalForm &F, const int k)
extract coefficients of for where is a variable of level 1
Definition facFqBivarUtil.cc:599
copy
CFArray copy(const CFList &list)
write elements of list into an array
Definition facFqBivarUtil.cc:364
recSubstituteCheck
int recSubstituteCheck(const CanonicalForm &F, const int d)
Definition facFqBivarUtil.cc:1205
swapDecompress
void swapDecompress(CFList &factors, const bool swap, const CFMap &N)
swap Variables in factors, then decompress factors
Definition facFqBivarUtil.cc:97
subset
CFList subset(int index[], const int &s, const CFArray &elements, bool &noSubset)
extract a subset given by index of size s from elements, if there is no subset we have not yet consid...
Definition facFqBivarUtil.cc:309
isInExtension
bool isInExtension(const CanonicalForm &F, const CanonicalForm &gamma, const int k, const CanonicalForm &delta, CFList &source, CFList &dest)
tests if F is not contained in a subfield defined by gamma (Fq case) or k (GF case)
Definition facFqBivarUtil.cc:184
FqInExtensionHelper
static bool FqInExtensionHelper(const CanonicalForm &F, const CanonicalForm &gamma, const CanonicalForm &delta, CFList &source, CFList &dest)
Definition facFqBivarUtil.cc:139
writeInMatrix
void writeInMatrix(CFMatrix &M, const CFArray &A, const int column, const int startIndex)
write A into M starting at row startIndex
Definition facFqBivarUtil.cc:586
substituteCheck
int substituteCheck(const CanonicalForm &F, const Variable &x)
check if a substitution x^n->x is possible
Definition facFqBivarUtil.cc:1089
computeBoundsWrtDiffMainvar
int * computeBoundsWrtDiffMainvar(const CanonicalForm &F, int &n, bool &isIrreducible)
as above just wrt to the other variable
Definition facFqBivarUtil.cc:922
decompress
void decompress(CFList &factors, const CFMap &N)
decompress a list of polys factors using the map N
Definition facFqBivarUtil.cc:51
facFqBivarUtil.h
This file provides utility functions for bivariate factorization.
j
int j
Definition facHensel.cc:110
convertFacCF2nmod_poly_t
convertFacCF2nmod_poly_t(FLINTmipo, M)
nmod_poly_clear
nmod_poly_clear(FLINTmipo)
facHensel.h
This file defines functions for Hensel lifting.
mulMod2
CanonicalForm mulMod2(const CanonicalForm &A, const CanonicalForm &B, const CanonicalForm &M)
Karatsuba style modular multiplication for bivariate polynomials.
Definition facMul.cc:2992
newtonDiv
void newtonDiv(const CanonicalForm &F, const CanonicalForm &G, CanonicalForm &Q)
Definition facMul.cc:386
facMul.h
This file defines functions for fast multiplication and division with remainder.
getMipo
CanonicalForm getMipo(const Variable &alpha, const Variable &x)
Definition variable.cc:207
const
#define const
Definition fegetopt.c:39
ftmpl_functions.h
some useful template functions.
isIrreducible
bool isIrreducible(const CanonicalForm &f)
bool isIrreducible ( const CanonicalForm & f )
Definition gengftables-conway.cc:77
gf_name
VAR char gf_name
Definition gfops.cc:52
imm.h
operations on immediates, that is elements of F_p, GF, Z, Q that fit into intrinsic int,...
imm2int
static long imm2int(const InternalCF *const imm)
Definition imm.h:70
multiplicity
STATIC_VAR int * multiplicity
Definition interpolation.cc:86
G
STATIC_VAR TreeM * G
Definition janet.cc:31
info
#define info
Definition libparse.cc:1256
exp
gmp_float exp(const gmp_float &a)
Definition mpr_complex.cc:349
index
static int index(p_Length length, p_Ord ord)
Definition p_Procs_Impl.h:592
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
Q
#define Q
Definition sirandom.c:26
timing.h
TIMING_DEFINE_PRINT
#define TIMING_DEFINE_PRINT(t)
Definition timing.h:95
TIMING_START
#define TIMING_START(t)
Definition timing.h:92
TIMING_END_AND_PRINT
#define TIMING_END_AND_PRINT(t, msg)
Definition timing.h:94
gcd
int gcd(int a, int b)
Definition walkSupport.cc:836