7#include "factory/factory.h"
30#define modp_number int
39 return (
modp_number)(((
unsigned long)
x)*((
unsigned long)
y)%((
unsigned long)
myp));
150void WriteMonoList (mon_list_entry *list)
164 row_list_entry *curptr;
168 cout << endl <<
"quotient basis: ";
170 cout << endl <<
"leading terms: ";
172 cout << endl <<
"to be checked: ";
175 cout << endl <<
"Matrix:" << endl;
185 row=curptr->row_matrix;
186 solve=curptr->row_solve;
189 cout << *row <<
" , ";
195 cout << *
solve <<
" , ";
200 cout <<
"Special row: Solve row:" << endl;
204 cout << *row <<
" , ";
211 cout << *row <<
" , ";
217 cout << endl << endl;
223 long u,
v, u0, u1, u2, q, r;
238 if ((u1<0)||((u1*a)%
p!=1))
244 if ((a*
i)%
p==1)
return i;
273 if (m1[
i]!=m2[
i])
return false;;
300 mon_list_entry *curptr=list;
301 mon_list_entry *prevptr=
NULL;
302 mon_list_entry *temp;
306 if (
EqualMon (mon,(*curptr).mon))
return list;
307 if (
Greater ((*curptr).mon,mon))
break;
311 temp=(mon_list_entry*)
omAlloc0(
sizeof(mon_list_entry));
315 if (prevptr==
NULL)
return temp;
325 mon_list_entry *cur=list;
327 for (
i=0;
i<n;
i++) cur=cur->next;
416 for (pos_gen=2;pos_gen<
myp;pos_gen++)
421 gen_table[
i]=
modp_mul(gen_table[
i-1],pos_gen);
438 mon_list_entry *pptr;
505 row_list_entry *pptr;
568 mpz_set_si(mon_conv,mn[
k]);
569 mpz_mul(ev,ev,mon_conv);
632 mpz_set_si(big_myp,
myp);
699 row_list_entry *row_ptr;
708#ifdef integerstrategy
713 while (row_ptr!=
NULL)
715 cur_row_ptr=row_ptr->row_matrix;
716 solve_row_ptr=row_ptr->row_solve;
719 first_col=row_ptr->first_col;
720 cur_row_ptr=cur_row_ptr+first_col;
721 my_row_ptr=my_row_ptr+first_col;
725#ifdef integerstrategy
726 prep_val=*cur_row_ptr;
732 if (*m_row_ptr!=0) *m_row_ptr=
modp_mul(*m_row_ptr,prep_val);
738 if (*m_row_ptr!=0) *m_row_ptr=
modp_mul(*m_row_ptr,prep_val);
747 mul_val=
modp_mul(*cur_row_ptr,red_val);
748 *my_row_ptr=
modp_sub(*my_row_ptr,mul_val);
755 if (*solve_row_ptr!=0)
757 mul_val=
modp_mul(*solve_row_ptr,red_val);
758 *my_solve_row_ptr=
modp_sub(*my_solve_row_ptr,mul_val);
764 row_ptr=row_ptr->next;
766 PrintS(
"reduction by row ");
780 if (*row!=0) {zero=0;
break;}
790 if (m1[
i]>m2[
i])
return false;;
796 mon_list_entry *c_ptr;
797 mon_list_entry *p_ptr;
798 mon_list_entry *n_ptr;
808 p_ptr->next=c_ptr->next;
824 mon_list_entry *n_check_list;
860 row_list_entry *pptr;
861 row_list_entry *temp;
866#ifndef unsortedmatrix
867 if ( first_col <= ptr->first_col )
break;
872 temp=(row_list_entry*)
omAlloc0(
sizeof(row_list_entry));
877 (*temp).first_col=first_col;
891#ifdef integerstrategy
923 if (*row!=0) *row=
modp_mul(*row,red_val);
929 if (*row!=0) *row=
modp_mul(*row,red_val);
939 modp_result_entry *temp;
940 temp=(modp_result_entry*)
omAlloc0(
sizeof(modp_result_entry));
961 generator_entry *cur_gen;
962 generator_entry *next_gen;
963 cur_gen=e->generator;
964 while (cur_gen!=
NULL)
966 next_gen=cur_gen->next;
978 generator_entry *cur_ptr;
979 generator_entry *prev_ptr;
980 generator_entry *temp;
983 while (cur_ptr!=
NULL)
986 cur_ptr=cur_ptr->next;
988 temp=(generator_entry*)
omAlloc0(
sizeof(generator_entry));
990 else prev_ptr->next=temp;
1002#ifndef integerstrategy
1004 generator_entry *cur_ptr;
1006 while (cur_ptr!=
NULL)
1011 cur_ptr=cur_ptr->next;
1016void PresentGenerator (
int i)
1019 modp_result_entry *cur_ptr;
1020 generator_entry *cur_gen;
1022 while (cur_ptr!=
NULL)
1024 cur_gen=cur_ptr->generator;
1025 for (
j=0;
j<
i;
j++) cur_gen=cur_gen->next;
1028 Print(
"%d;", cur_gen->coef[
j]);
1031 WriteMono (cur_gen->lt);
1032 Print(
" ( %d ) prime = %d\n", cur_gen->ltcoef, cur_ptr->p);
1033 cur_ptr=cur_ptr->next;
1047 modp_result_entry *cur_ptr;
1054 while (cur_ptr!=
NULL)
1056 *congr_ptr=cur_ptr->p;
1057 cur_ptr=cur_ptr->next;
1080 bool first_gcd=
true;
1106 str=(
char*)
omAlloc0(
sizeof(
char)*1000);
1107 modp_result_entry *cur_ptr;
1108 generator_entry *cur_gen;
1122 while (cur_ptr!=
NULL)
1124 cur_gen=cur_ptr->generator;
1125 for (
j=0;
j<ngen;
j++) cur_gen=cur_gen->next;
1127 cur_ptr=cur_ptr->next;
1136 if (temp<0) temp=temp+
congr[
k];
1139 mpz_set_si(sol,
v[n-1]);
1140 for (
k=n-2;
k>=0;
k--)
1142 mpz_mul_ui(sol,sol,
congr[
k]);
1143 mpz_add_ui(sol,sol,
v[
k]);
1146 int s=mpz_cmpabs(sol,nsol);
1147 if (
s>0) mpz_set(sol,nsol);
1154 size=mpz_sizeinbase(sol,10);
1155 if (
size>maximal_size) maximal_size=
size;
1168 modp_result_entry *temp;
1187 PrintS(
"-discarding ALL.\n");
1190 modp_result_entry *ntfree;
1191 generator_entry *cur_gen;
1210 cur_gen=cur_gen->next;
1228 PrintS(
"wrong number of generators occurred");
1238 PrintS(
"denom of coef divisible by p");
1245 generator_entry *cur_gen;
1246 mon_list_entry *cur_mon;
1251 if (!
EqualMon(cur_mon->mon,cur_gen->lt))
1254 PrintS(
"wrong leading term occurred");
1261 cur_gen=cur_gen->next;
1262 cur_mon=cur_mon->next;
1269 PrintS(
"wrong seq of cols occurred");
1280void WriteGenerator ()
1311 mpz_add(sum,sum,val);
1313 if (mpz_sgn(sum)!=0)
1327 gen_list_entry *temp;
1346 gen_list_entry *temp,*prev;
1365 temp=(gen_list_entry*)
omAlloc0(
sizeof(gen_list_entry));
1372 mpz_init(temp->polycoef[
i]);
1382 gen_list_entry *temp;
1392 str=mpz_get_str(str,10,temp->polycoef[
i]);
1395 WriteMono(temp->polyexp[
i]);
1421 cout <<
"row produced for monomial ";
1422 WriteMono (cur_mon);
1434 cout <<
"row is zero - linear dependence found (should be seen in my_solve_row)" << endl;
1435 cout <<
"monomial added to leading terms list" << endl;
1436 cout <<
"check list updated" << endl;
1446 cout <<
"row is non-zero" << endl;
1447 cout <<
"monomial added to quotient basis list" << endl;
1448 cout <<
"new monomials added to check list" << endl;
1449 cout <<
"check list reduced by monomials from leading term list" << endl;
1454 cout <<
"row prepared and put into matrix" << endl;
1467 mpq_set_si(c,m_val,1);
1473 mpz_set(mpq_numref(c),
m->z);
1474 mpz_set(mpq_denref(c),
m->n);
1475 mpq_canonicalize(c);
1493 WerrorS(
"coefficient field should be Zp or Q!");
1498 WerrorS(
"quotient ring not supported!");
1503 WerrorS(
"ordering must be global!");
1509 WerrorS(
"list and intvec must have the same length!");
1528 PrintS(
"multiplicities: ");
1540 for(
i=0;
i<L.size();
i++)
1555 Print(
"coordinate %d for point %d initialized twice!\n",pcvar+1,
i+1);
1580 PrintS(
"not a variable? ");
1599 Print(
"coordinate %d for point %d not known!\n",
j+1,
i+1);
1608 WerrorS(
"data structure is invalid");
1623 bool correct_gen=
false;
1630 Print(
"trying %d cycles mod p...\n",modp_cycles);
1666 PrintS(
"wrong generator!\n");
1679 Print(
"maximal size of output: %d, precision bound: %d.\n",maximalsize,mpz_sizeinbase(
bigcongr,10));
1682 modp_cycles=modp_cycles+10;
1692 PrintS(
"computations finished.\n");
1701 WerrorS(
"internal error - coefficient too big!");
1732 cur_gen=cur_gen->next;
1746 if (mpz_sgn(temp->polycoef[a])!=0)
1752 mpz_init_set(n->z,temp->polycoef[a]);
bool solve(int **extmat, int nrows, int ncols)
int cf_getNumSmallPrimes()
int cf_getSmallPrime(int i)
static FORCE_INLINE void n_Normalize(number &n, const coeffs r)
inplace-normalization of n; produces some canonical representation of n;
const CanonicalForm int s
const CanonicalForm int const CFList const Variable & y
const Variable & v
< [in] a sqrfree bivariate poly
for(j=0;j< factors.length();j++)
void WerrorS(const char *s)
if(!FE_OPT_NO_SHELL_FLAG)(void) system(sys)
static void NewGenerator(mono_type mon)
static void TakeNextMonomial(mono_type mon)
static modp_number TakePrime(modp_number)
STATIC_VAR int * multiplicity
static void ClearGenList()
STATIC_VAR modp_number * my_row
static modp_number modp_sub(modp_number x, modp_number y)
static mon_list_entry * FreeMonList(mon_list_entry *list)
static void ReduceCheckListByMon(mono_type m)
STATIC_VAR int last_solve_column
static void modp_Evaluate(modp_number *ev, mono_type mon, condition_type con)
static mono_type ZeroMonomial()
static void UpdateGenList()
static mono_type MonListElement(mon_list_entry *list, int n)
static void FreeProcData()
STATIC_VAR mpz_t bigcongr
static void ResolveCoeff(mpq_t c, number m)
STATIC_VAR mon_list_entry * check_list
static modp_number modp_mul(modp_number x, modp_number y)
STATIC_VAR mon_list_entry * generic_lt
ideal interpolation(const std::vector< ideal > &L, intvec *v)
static void IntegerPoints()
static bool EqualMon(mono_type m1, mono_type m2)
STATIC_VAR coordinates * points
struct modp_result_struct * prev
static void MakeConditions()
static void CloseChinese()
static void int_Evaluate(mpz_t ev, mono_type mon, condition_type con)
struct modp_result_struct * next
coordinate_products * coordinates
static void NewResultEntry()
static void PrepareChinese(int n)
STATIC_VAR modp_number myp
static void ReduceCheckListByLTs()
STATIC_VAR q_coordinates * q_points
static modp_number OneInverse(modp_number a, modp_number p)
static void ReconstructGenerator(int ngen, int n)
STATIC_VAR modp_result_entry * modp_result
STATIC_VAR int bad_primes
static void modp_PrepareProducts()
static void PrepareRow(mono_type mon)
STATIC_VAR modp_coordinates * modp_points
STATIC_VAR bool only_modp
static bool CheckGenerator()
STATIC_VAR modp_number * my_solve_row
static mon_list_entry * MonListAdd(mon_list_entry *list, mono_type mon)
STATIC_VAR mono_type * polyexp
STATIC_VAR condition_type * condition_list
STATIC_VAR poly comparizon_p1
static exponent MonDegree(mono_type mon)
static void InitProcData()
STATIC_VAR modp_number * congr
STATIC_VAR modp_number modp_denom
STATIC_VAR mpz_t common_denom
struct mon_list_entry_struct * next
STATIC_VAR modp_number * in_gamma
STATIC_VAR int good_primes
STATIC_VAR mon_list_entry * base_list
STATIC_VAR mon_list_entry * lt_list
static void ProduceRow(mono_type mon)
struct row_list_entry_struct * next
STATIC_VAR int final_base_dim
static void MultGenerators()
STATIC_VAR mono_type * generic_column_name
STATIC_VAR modp_number * modp_Reverse
struct generator_struct * next
static void UpdateCheckList(mono_type m)
static void GeneralInit()
STATIC_VAR mpz_t * polycoef
modp_number * modp_coordinates
STATIC_VAR mono_type * column_name
STATIC_VAR bool denom_divisible
STATIC_VAR int_coordinates * int_points
STATIC_VAR gen_list_entry * gen_list
static void FreeResultEntry(modp_result_entry *e)
static void int_PrepareProducts()
struct gen_list_struct * next
static void GeneralDone()
static void CheckColumnSequence()
static bool DivisibleMon(mono_type m1, mono_type m2)
generator_entry * generator
STATIC_VAR int generic_n_generators
static void RowListAdd(int first_col, mono_type mon)
STATIC_VAR row_list_entry * row_list
modp_number * coordinate_products
STATIC_VAR coord_exist_table * coord_exist
static void modp_SetColumnNames()
STATIC_VAR poly comparizon_p2
STATIC_VAR modp_result_entry * cur_result
static bool Greater(mono_type m1, mono_type m2)
static number & pGetCoeff(poly p)
return an alias to the leading coefficient of p assumes that p != NULL NOTE: not copy
VAR ring currRing
Widely used global variable which specifies the current polynomial ring for Singular interpreter and ...
Compatibility layer for legacy polynomial operations (over currRing)
#define pHead(p)
returns newly allocated copy of Lm(p), coef is copied, next=NULL, p might be NULL
#define pLmCmp(p, q)
returns 0|1|-1 if p=q|p>q|p<q w.r.t monomial ordering
void PrintS(const char *s)
static BOOLEAN rField_is_Zp(const ring r)
static BOOLEAN rField_is_Q(const ring r)
ideal idInit(int idsize, int rank)
initialise an ideal / module