Changeset 458174a in git


Ignore:
Timestamp:
May 2, 2018, 10:45:42 AM (5 years ago)
Author:
Karim Abou Zeid <karim23697@…>
Branches:
(u'spielwiese', '8e0ad00ce244dfd0756200662572aef8402f13d5')
Children:
0f987ab443ee33e628ea90f02a2fddfb9d8fa497
Parents:
75def9c8a4972706cb710a11c07681ad43676aed2ba25ee7ea3c483c73847576db73cb6464bc67ba
Message:
Merge branch 'spielwiese' into stable
Files:
8 edited

Legend:

Unmodified
Added
Removed

  • Singular/LIB/fpaprops.lib

    r2ba25e r458174a  
    1818
    1919PROCEDURES:
    20   lpNoetherian(<GB>);     check whether A/<GB> is (left/right) noetherian
     20  lpNoetherian(<GB>);     check whether A/<LM(GB)> is (left/right) Noetherian
    2121  lpIsSemiPrime(<GB>);    check whether A/<LM(GB)> is semi prime
    2222  lpIsPrime(<GB>);        check whether A/<LM(GB)> is prime
    … …  
    3333"USAGE: lpNoetherian(G); G an ideal in a Letterplace ring
    3434RETURN: int
    35 @*      0 not noetherian
    36 @*      1 left noetherian
    37 @*      2 right noetherian
    38 @*      3 noetherian
    39 PURPOSE: Check whether A/<G> is (left/right) noetherian
     35@*      0 not Noetherian
     36@*      1 left Noetherian
     37@*      2 right Noetherian
     38@*      3 Noetherian
     39@*      4 weak Noetherian
     40PURPOSE: Check whether the monomial algebra A/<LM(G)> is (left/right) noetherian
    4041ASSUME: - basering is a Letterplace ring
    4142@*      - G is a Groebner basis
     43THEORY: lpNoetherian works with the monomial algebra A/<LM(G)>.
     44If it gives an affirmative answer for one of the properties, then it
     45holds for both A/<LM(G)> and A/<G>. However, a negative answer applies
     46only to A/<LM(G)> and not necessarily to A/<G>.
     47NOTE: Weak Noetherian means that two-sided ideals in A/<LM(G)> satisfy
     48the acc (ascending chain condition).
    4249"
    4350{
    … …  
    9198  intvec visited;
    9299  visited[ncols(UG)] = 0;
    93   int inFlag, outFlag;
     100  int inFlag, outFlag, inOutFlag;
    94101  for (int v = 1; v <= ncols(UG) && (inFlag + outFlag) != 3; v++) {
    95     int inOutFlags = inOrOutCommingEdgeInCycle(UG, v, visited, 0);
     102    int inOutFlags = inOutCommingEdgesInCycles(UG, v, visited, 0);
    96103    if (inOutFlags == 1) {
    97104      inFlag = 1;
    98105    }
    99106    if (inOutFlags == 2) {
    100       outFlag = 2;
     107      outFlag = 1;
    101108    }
    102109    if (inOutFlags == 3) {
    103110      inFlag = 1;
    104       outFlag = 2;
     111      outFlag = 1;
     112    }
     113    if (inOutFlags == 4) {
     114      inOutFlag = 1;
     115    }
     116    if (inOutFlags == 5) {
     117      inFlag = 1;
     118      inOutFlag = 1;
     119    }
     120    if (inOutFlags == 6) {
     121      outFlag = 1;
     122      inOutFlag = 1;
     123    }
     124    if (inOutFlags == 7) {
     125      inFlag = 1;
     126      outFlag = 1;
     127      inOutFlag = 1;
    105128    }
    106129    kill inOutFlags;
    107130  } kill v;
    108   return (3 - inFlag - outFlag);
     131  int noetherian = 3 - 1*inFlag - 2*outFlag;
     132  if (noetherian == 0) {
     133    return (4 - 4*inOutFlag); // weak noetherian
     134  }
     135  return (noetherian);
    109136}
    110137example
    … …  
    118145}
    119146
    120 static proc inOrOutCommingEdgeInCycle(intmat G, int v, intvec visited, intvec path) {
     147static proc inOutCommingEdgesInCycles(intmat G, int v, intvec visited, intvec path) {
    121148  // Mark the current vertex as visited
    122149  visited[v] = 1;
    … …  
    129156  }
    130157
    131   int inFlag, outFlag;
     158  int inFlag, outFlag, inOutFlag;
    132159
    133160  for (int w = 1; w <= ncols(G) && (inFlag + outFlag) != 3; w++) {
    134161    if (G[v,w] == 1) {
    135       if (visited[w] == 1) {
    136         // new cycle
    137         if (v == w) {
     162      if (visited[w] == 1) { // new cycle
     163        int tmpInFlag;
     164        int tmpOutFlag;
     165        if (v == w) { // cycle is a loop
    138166          for (int u = 1; u <= ncols(G); u++) {
    139167            if (G[v,u] && u != v) {
    140               outFlag = 2;
     168              outFlag = 1;
     169              tmpOutFlag = 1;
    141170            }
    142171            if (G[u,v] && u != v) {
    143172              inFlag = 1;
     173              tmpInFlag = 1;
    144174            }
    145175          } kill u;
    … …  
    151181                if (path[i] != v) {
    152182                  if (u != path[i+1]) { // and u is not the next element in the cycle
    153                     outFlag = 2;
     183                    outFlag = 1;
     184                    tmpOutFlag = 1;
    154185                  }
    155186                } else {
    156187                  if (u != w) {
    157                     outFlag = 2;
     188                    outFlag = 1;
     189                    tmpOutFlag = 1;
    158190                  }
    159191                }
    … …  
    163195                  if (u != path[i-1]) { // and u is not the previous element in the cylce
    164196                    inFlag = 1;
     197                    tmpInFlag = 1;
    165198                  }
    166199                } else {
    167200                  if (u != v) {
    168201                    inFlag = 1;
     202                    tmpInFlag = 1;
    169203                  }
    170204                }
    … …  
    176210          } kill i;
    177211        }
     212        if (tmpInFlag > 0 && tmpOutFlag > 0) {
     213          // there are both in and outcomming edges in this cycle
     214          inOutFlag = 1;
     215        }
     216        kill tmpInFlag;
     217        kill tmpOutFlag;
    178218      } else {
    179         int inOutFlags = inOrOutCommingEdgeInCycle(G, w, visited, path);
     219        int inOutFlags = inOutCommingEdgesInCycles(G, w, visited, path);
    180220        if (inOutFlags == 1) {
    181221          inFlag = 1;
    182222        }
    183223        if (inOutFlags == 2) {
    184           outFlag = 2;
     224          outFlag = 1;
    185225        }
    186226        if (inOutFlags == 3) {
    187227          inFlag = 1;
    188           outFlag = 2;
     228          outFlag = 1;
     229        }
     230        if (inOutFlags == 4) {
     231          inOutFlag = 1;
     232        }
     233        if (inOutFlags == 5) {
     234          inFlag = 1;
     235          inOutFlag = 1;
     236        }
     237        if (inOutFlags == 6) {
     238          outFlag = 1;
     239          inOutFlag = 1;
     240        }
     241        if (inOutFlags == 7) {
     242          inFlag = 1;
     243          outFlag = 1;
     244          inOutFlag = 1;
    189245        }
    190246        kill inOutFlags;
    … …  
    193249  } kill w;
    194250
    195   return (inFlag + outFlag);
     251  return (1*inFlag + 2*outFlag + 4*inOutFlag);
    196252}
    197253
    … …  
    202258ASSUME: - basering is a Letterplace ring
    203259      - G is a Groebner basis
     260THEORY: lpIsSemiPrime works with the monomial algebra A/<LM(G)>.
     261A positive answer holds for both A/<LM(G)> and A/<G>, while
     262a negative answer applies only to A/<LM(G)> and not necessarily to
     263A/<G>.
    204264"
    205265{
    … …  
    303363ASSUME: - basering is a Letterplace ring
    304364      - G is a Groebner basis
     365THEORY: lpIsPrime works with the monomial algebra A/<LM(G)>.
     366A positive answer holds for both A/<LM(G)> and A/<G>, while
     367a negative answer applies only to A/<LM(G)> and not necessarily to A/<G>.
    305368"
    306369{

  • Singular/misc_ip.cc

    r75def9 r458174a  
    895895              StringAppendS("AvoidBranching,");
    896896#endif
    897 #ifdef HAVE_MULT_MOD
     897#ifdef HAVE_GENERIC_MULT
    898898              StringAppendS("GenericMult,");
    899899#else
    900900              StringAppendS("TableMult,");
     901#endif
     902#ifdef HAVE_INVTABLE
     903              StringAppendS("invTable,");
     904#else
     905              StringAppendS("no invTable,");
    901906#endif
    902907              StringAppendS("\n\t");

  • factory/ffops.h

    r75def9 r458174a  
    5353    long n = a % ff_prime;
    5454#if defined(i386) || defined(__x86_64__) || defined(NTL_AVOID_BRANCHING)
     55    #if SIZEOF_LONG==8
     56    n += (n >> 63) & ff_prime;
     57    #else
    5558    n += (n >> 31) & ff_prime;
     59    #endif
    5660    return n;
    5761#else

  • kernel/GBEngine/tgb_internal.h

    r75def9 r458174a  
    7171
    7272#define npInit n_Init
    73 #define npNeg n_InpNeg
    74 #define npInvers n_Invers
    75 #define npMult n_Mult
    76 #define npIsOne n_IsOne
    77 #define npIsZero n_IsZero
     73#define npNeg npNegM
     74#define npInvers npInversM
     75#define npMult npMultM
     76//#define npIsOne n_IsOne
     77#define npIsZero npIsZeroM
    7878
    7979#else

  • kernel/mod2.h

    r75def9 r458174a  
    8585#endif
    8686
    87 #define SINGULAR_PATCHLEVEL 0
     87#define SINGULAR_PATCHLEVEL 2
    8888#define SINGULAR_VERSION ((SINGULAR_MAJOR_VERSION*1000 + SINGULAR_MINOR_VERSION*100 + SINGULAR_SUB_VERSION*10)+SINGULAR_PATCHLEVEL)
    8989

  • libpolys/coeffs/modulop.cc

    r75def9 r458174a  
    141141}
    142142
    143 BOOLEAN npIsOne (number a, const coeffs r)
    144 {
    145   n_Test(a, r);
    146 
    147   return 1 == (long)a;
    148 }
    149 
    150143BOOLEAN npIsMOne (number a, const coeffs r)
    151144{
    … …  
    155148}
    156149
    157 #ifdef HAVE_DIV_MOD
    158 
    159 #ifdef USE_NTL_XGCD
    160 
    161 //ifdef HAVE_NTL // in ntl.a
    162 //extern void XGCD(long& d, long& s, long& t, long a, long b);
    163 #include <NTL/ZZ.h>
    164 #ifdef NTL_CLIENT
    165 NTL_CLIENT
    166 #endif
    167 
    168 #endif
    169 
    170 static inline long InvMod(long a, const coeffs R)
    171 {
    172    long d, s, t;
    173 
    174 #ifdef USE_NTL_XGCD
    175    XGCD(d, s, t, a, R->ch);
    176    assume (d == 1);
    177 #else
    178    long  u, v, u0, v0, u1, v1, u2, v2, q, r;
    179 
    180    assume(a>0);
    181    u1=1; u2=0;
    182    u = a; v = R->ch;
    183 
    184    while (v != 0)
    185    {
    186       q = u / v;
    187       r = u % v;
    188       u = v;
    189       v = r;
    190       u0 = u2;
    191       u2 = u1 - q*u2;
    192       u1 = u0;
    193    }
    194 
    195    assume(u==1);
    196    s = u1;
    197 #endif
    198    if (s < 0)
    199       return s + R->ch;
    200    else
    201       return s;
    202 }
    203 #endif
    204 
    205 static inline number npInversM (number c, const coeffs r)
    206 {
    207   n_Test(c, r);
    208 #ifndef HAVE_DIV_MOD
    209   number d = (number)(long)r->npExpTable[r->npPminus1M - r->npLogTable[(long)c]];
    210 #else
    211   long inv=(long)r->npInvTable[(long)c];
    212   if (inv==0)
    213   {
    214     inv=InvMod((long)c,r);
    215     r->npInvTable[(long)c]=inv;
    216   }
    217   number d = (number)inv;
    218 #endif
    219   n_Test(d, r);
    220   return d;
    221 
    222 }
    223 
    224150number npDiv (number a,number b, const coeffs r)
    225151{
    … …  
    227153  n_Test(b, r);
    228154
    229 //#ifdef NV_OPS
    230 //  if (r->ch>NV_MAX_PRIME)
    231 //    return nvDiv(a,b);
    232 //#endif
    233   if ((long)a==0L)
    234     return (number)0L;
    235   number d;
    236 
    237 #ifndef HAVE_DIV_MOD
    238155  if ((long)b==0L)
    239156  {
    … …  
    241158    return (number)0L;
    242159  }
    243 
     160  if ((long)a==0) return (number)0L;
     161
     162  number d;
     163#ifndef HAVE_GENERIC_MULT
    244164  int s = r->npLogTable[(long)a] - r->npLogTable[(long)b];
     165  #ifdef HAVE_GENERIC_ADD
    245166  if (s < 0)
    246167    s += r->npPminus1M;
     168  #else
     169    #if SIZEOF_LONG == 8
     170    s += ((long)s >> 63) & r->npPminus1M;
     171    #else
     172    s += ((long)s >> 31) & r->npPminus1M;
     173    #endif
     174  #endif
    247175  d = (number)(long)r->npExpTable[s];
    248176#else
    … …  
    391319void npKillChar(coeffs r)
    392320{
    393   #ifdef HAVE_DIV_MOD
     321  #ifdef HAVE_INVTABLE
    394322  if (r->npInvTable!=NULL)
    395   omFreeSize( (void *)r->npInvTable, r->ch*sizeof(unsigned short) );
    396   r->npInvTable=NULL;
    397   #else
     323  {
     324    omFreeSize( (void *)r->npInvTable, r->ch*sizeof(unsigned short) );
     325    r->npInvTable=NULL;
     326  }
     327  #endif
     328  #ifndef HAVE_GENERIC_MULT
    398329  if (r->npExpTable!=NULL)
    399330  {
    … …  
    544475#endif
    545476  {
    546 #ifdef HAVE_DIV_MOD
     477#ifdef HAVE_INVTABLE
    547478    r->npInvTable=(unsigned short*)omAlloc0( r->ch*sizeof(unsigned short) );
    548 #elif (!defined(HAVE_MULT_MOD)||(!HAVE_DIV_MOD))
     479#endif
     480#ifndef HAVE_GENERIC_MULT
    549481    r->npExpTable=(unsigned short *)omAlloc0( r->ch*sizeof(unsigned short) );
    550482    r->npLogTable=(unsigned short *)omAlloc0( r->ch*sizeof(unsigned short) );
    … …  
    797729}
    798730
    799 static inline long nvInvMod(long a, const coeffs R)
    800 {
    801 #ifdef HAVE_DIV_MOD
    802   return InvMod(a, R);
    803 #else
    804 /// TODO: use "long InvMod(long a, const coeffs R)"?!
    805 
    806    long  s;
    807 
    808    long  u, u0, u1, u2, q, r; // v0, v1, v2,
    809 
    810    u1=1; // v1=0;
    811    u2=0; // v2=1;
    812    u = a;
    813 
    814    long v = R->ch;
    815 
    816    while (v != 0)
    817    {
    818       q = u / v;
    819       r = u % v;
    820       u = v;
    821       v = r;
    822       u0 = u2;
    823 //      v0 = v2;
    824       u2 = u1 - q*u2;
    825 //      v2 = v1 - q*v2;
    826       u1 = u0;
    827 //      v1 = v0;
    828    }
    829 
    830    s = u1;
    831    //t = v1;
    832    if (s < 0)
    833       return s + R->ch;
    834    else
    835      return s;
    836 #endif
    837 }
    838 
    839731static inline number nvInversM (number c, const coeffs r)
    840732{
    841   long inv=nvInvMod((long)c,r);
     733  long inv=npInvMod((long)c,r);
    842734  return (number)inv;
    843735}

  • libpolys/coeffs/modulop.h

    r75def9 r458174a  
    99#include "misc/auxiliary.h"
    1010
    11 // defines are in struct.h
     11
    1212// define if a*b is with mod instead of tables
    13 //#define HAVE_MULT_MOD
    14 // define if a/b is with mod instead of tables
    15 //#define HAVE_DIV_MOD
     13//#define HAVE_GENERIC_MULT
     14// define if 1/b is from tables
     15//#define HAVE_INVTABLE
    1616// define if an if should be used
    1717//#define HAVE_GENERIC_ADD
     18
     19//#undef HAVE_GENERIC_ADD
     20//#undef HAVE_GENERIC_MULT
     21//#undef HAVE_INVTABLE
     22
     23//#define HAVE_GENERIC_ADD 1
     24//#define HAVE_GENERIC_MULT 1
     25//#define HAVE_INVTABLE 1
    1826
    1927// enable large primes (32749 < p < 2^31-)
    … …  
    2129#define NV_MAX_PRIME 32749
    2230#define FACTORY_MAX_PRIME 536870909
     31
     32#ifdef USE_NTL_XGCD
     33//ifdef HAVE_NTL // in ntl.a
     34//extern void XGCD(long& d, long& s, long& t, long a, long b);
     35#include <NTL/ZZ.h>
     36#ifdef NTL_CLIENT
     37NTL_CLIENT
     38#endif
     39#endif
    2340
    2441struct n_Procs_s; typedef struct  n_Procs_s  *coeffs;
    … …  
    4158//    return (number)res;
    4259// }
    43 #ifdef HAVE_MULT_MOD
     60#ifdef HAVE_GENERIC_MULT
    4461static inline number npMultM(number a, number b, const coeffs r)
    4562{
    … …  
    165182  return 0 == (long)a;
    166183}
    167 
    168 // inline number npMultM(number a, number b, int npPrimeM)
    169 // {
    170 //   return (number)(((long)a*(long)b) % npPrimeM);
    171 // }
     184static inline BOOLEAN npIsOne (number a, const coeffs)
     185{
     186  return 1 == (long)a;
     187}
     188
     189static inline long npInvMod(long a, const coeffs R)
     190{
     191   long s, t;
     192
     193#ifdef USE_NTL_XGCD
     194   long d;
     195   XGCD(d, s, t, a, R->ch);
     196   assume (d == 1);
     197#else
     198   long  u, v, u0, v0, u1, v1, u2, v2, q, r;
     199
     200   assume(a>0);
     201   u1=1; u2=0;
     202   u = a; v = R->ch;
     203
     204   while (v != 0)
     205   {
     206      q = u / v;
     207      //r = u % v;
     208      r = u - q*v;
     209      u = v;
     210      v = r;
     211      u0 = u2;
     212      u2 = u1 - q*u2;
     213      u1 = u0;
     214   }
     215
     216   assume(u==1);
     217   s = u1;
     218#endif
     219#ifdef HAVE_GENERIC_ADD
     220   if (s < 0)
     221      return s + R->ch;
     222   else
     223      return s;
     224#else
     225  #if SIZEOF_LONG == 8
     226  s += (s >> 63) & R->ch;
     227  #else
     228  s += (s >> 31) & R->ch;
     229  #endif
     230  return s;
     231#endif
     232}
     233
     234static inline number npInversM (number c, const coeffs r)
     235{
     236  n_Test(c, r);
     237#ifndef HAVE_GENERIC_MULT
     238  #ifndef HAVE_INVTABLE
     239  number d = (number)(long)r->npExpTable[r->npPminus1M - r->npLogTable[(long)c]];
     240  #else
     241  long inv=(long)r->npInvTable[(long)c];
     242  if (inv==0)
     243  {
     244    inv = (long)r->npExpTable[r->npPminus1M - r->npLogTable[(long)c]];
     245    r->npInvTable[(long)c]=inv;
     246  }
     247  number d = (number)inv;
     248  #endif
     249#else
     250  #ifdef HAVE_INVTABLE
     251  long inv=(long)r->npInvTable[(long)c];
     252  if (inv==0)
     253  {
     254    inv=npInvMod((long)c,r);
     255    r->npInvTable[(long)c]=inv;
     256  }
     257  #else
     258  long  inv=npInvMod((long)c,r);
     259  #endif
     260  number d = (number)inv;
     261#endif
     262  n_Test(d, r);
     263  return d;
     264}
     265
    172266
    173267// The folloing is reused inside gnumpc.cc, gnumpfl.cc and longrat.cc

  • m4/cpu-check.m4

    r75def9 r458174a  
    4949
    5050AS_CASE([$host_cpu],
     51dnl the following settings seems to be better on itanium processors
     52  [ia64*], [
     53      AC_DEFINE(HAVE_GENERIC_ADD,1,use branch for addition in Z/p otherwise it uses a generic add)],
    5154dnl the following settings seems to be better on i386 and x86_64 processors
    52   [i*86*|x86_64*], [AC_DEFINE(HAVE_MULT_MOD,1,multiplication is fast on the cpu: a*b is with mod otherwise using tables of logartihms)],
    53 dnl the following settings seems to be better on itanium processors
    54 dnl AC_DEFINE(HAVE_MULT_MOD,1,)
    55   [ia64*], [AC_DEFINE(HAVE_GENERIC_ADD,1,use branch for addition in Z/p otherwise it uses a generic add)],
     55dnl AC_DEFINE(HAVE_GENERIC_MULT,1,)
     56  [i*86*|x86_64*], [
     57            AC_DEFINE(HAVE_GENERIC_ADD,1,use branch for addition in Z/p otherwise it uses a generic add)
     58            AC_DEFINE(HAVE_GENERIC_MULT,1,multiplication is fast on the cpu: a*b is with mod otherwise using tables of logartihms)
     59            ],
    5660dnl the following settings seems to be better on sparc processors
    5761  [sparc*], [
    58             AC_DEFINE(HAVE_MULT_MOD,1,multiplication is fast on the cpu: a*b is with mod otherwise using tables of logartihms)
    59             AC_DEFINE(HAVE_DIV_MOD,1,division using extend euclidian algorithm otherwise using tables of logartihms)
     62            AC_DEFINE(HAVE_GENERIC_ADD,1,use branch for addition in Z/p otherwise it uses a generic add)
    6063            ],
    6164dnl the following settings seems to be better on ppc processors
    6265dnl testet on: ppc_Linux, 740/750 PowerMac G3, 512k L2 cache
    63   [powerpc*|ppc*], [AC_DEFINE(HAVE_MULT_MOD,1,multiplication is fast on the cpu: a*b is with mod otherwise using tables of logartihms)],
     66  [powerpc*|yyppc*], [AC_DEFINE(HAVE_GENERIC_MULT,1,multiplication is fast on the cpu: a*b is with mod otherwise using tables of logartihms)],
    6467  []
    6568)
Note: See TracChangeset for help on using the changeset viewer.