source: git/libpolys/polys/monomials/monomials.cc @ 18dab28

jengelh-datetimespielwiese
Last change on this file since 18dab28 was 18dab28, checked in by Hans Schoenemann <hannes@…>, 12 years ago
fix unseless includes of polys-impl.h
  • Property mode set to 100644
File size: 3.3 KB
Line 
1/****************************************
2*  Computer Algebra System SINGULAR     *
3****************************************/
4/* $Id$ */
5
6/***************************************************************
7 *
8 * File:       polys-impl.cc
9 * Purpose:    low-level procuders for polys.
10 *
11 * If you touch anything here, you better know what you are doing.
12 * What is here should not be used directly from other routines -- the
13 * encapsulations in polys.[h,cc] should be used, instead.
14 *
15 ***************************************************************/
16#ifndef POLYS_IMPL_CC
17#define POLYS_IMPL_CC
18
19#include <stdio.h>
20#include <string.h>
21
22#include "config.h"
23
24#include <omalloc/omalloc.h>
25#include <misc/auxiliary.h>
26
27#ifdef PDEBUG
28#undef NO_INLINE3
29#define NO_INLINE3
30#endif
31
32#include <polys/monomials/ring.h>
33#include <reporter/reporter.h>
34#include <coeffs/numbers.h>
35#include <polys/monomials/ring.h>
36#include <polys/monomials/p_polys.h>
37#include <reporter/reporter.h>
38
39#ifdef PDEBUG
40int pDBsyzComp=0;
41#endif
42
43/***************************************************************
44 *
45 * Storage Managament Routines
46 *
47 ***************************************************************/
48
49
50static inline unsigned long GetBitFields(long e,
51                                         unsigned int s, unsigned int n)
52{
53#define Sy_bit_L(x)     (((unsigned long)1L)<<(x))
54  unsigned int i = 0;
55  unsigned long  ev = 0L;
56  assume(n > 0 && s < BIT_SIZEOF_LONG);
57  do
58  {
59    assume(s+i < BIT_SIZEOF_LONG);
60    if (e > (long) i) ev |= Sy_bit_L(s+i);
61    else break;
62    i++;
63  }
64  while (i < n);
65  return ev;
66}
67
68// Short Exponent Vectors are used for fast divisibility tests
69// ShortExpVectors "squeeze" an exponent vector into one word as follows:
70// Let n = BIT_SIZEOF_LONG / pVariables.
71// If n == 0 (i.e. pVariables > BIT_SIZE_OF_LONG), let m == the number
72// of non-zero exponents. If (m>BIT_SIZEOF_LONG), then sev = ~0, else
73// first m bits of sev are set to 1.
74// Otherwise (i.e. pVariables <= BIT_SIZE_OF_LONG)
75// represented by a bit-field of length n (resp. n+1 for some
76// exponents). If the value of an exponent is greater or equal to n, then
77// all of its respective n bits are set to 1. If the value of an exponent
78// is smaller than n, say m, then only the first m bits of the respective
79// n bits are set to 1, the others are set to 0.
80// This way, we have:
81// exp1 / exp2 ==> (ev1 & ~ev2) == 0, i.e.,
82// if (ev1 & ~ev2) then exp1 does not divide exp2
83unsigned long p_GetShortExpVector(poly p, const ring r)
84{
85  assume(p != NULL);
86  if (p == NULL) return 0;
87  unsigned long ev = 0; // short exponent vector
88  unsigned int n = BIT_SIZEOF_LONG / r->N; // number of bits per exp
89  unsigned int m1; // highest bit which is filled with (n+1)
90  unsigned int i = 0, j=1;
91
92  if (n == 0)
93  {
94    if (r->N <2*BIT_SIZEOF_LONG)
95    {
96      n=1;
97      m1=0;
98    }
99    else
100    {
101      for (; j<=(unsigned long) r->N; j++)
102      {
103        if (p_GetExp(p,j,r) > 0) i++;
104        if (i == BIT_SIZEOF_LONG) break;
105      }
106      if (i>0)
107      ev = ~((unsigned long)0) >> ((unsigned long) (BIT_SIZEOF_LONG - i));
108      return ev;
109    }
110  }
111  else
112  {
113    m1 = (n+1)*(BIT_SIZEOF_LONG - n*r->N);
114  }
115
116  n++;
117  while (i<m1)
118  {
119    ev |= GetBitFields(p_GetExp(p, j,r), i, n);
120    i += n;
121    j++;
122  }
123
124  n--;
125  while (i<BIT_SIZEOF_LONG)
126  {
127    ev |= GetBitFields(p_GetExp(p, j,r), i, n);
128    i += n;
129    j++;
130  }
131  return ev;
132}
133
134#endif // POLYS_IMPL_CC
Note: See TracBrowser for help on using the repository browser.