source: git/kernel/polys-impl.cc @ b1dfaf

spielwiese
Last change on this file since b1dfaf was b1dfaf, checked in by Frank Seelisch <seelisch@…>, 14 years ago
patch from Kai (checked for problems under Windows OS: no problems) git-svn-id: file:///usr/local/Singular/svn/trunk@13210 2c84dea3-7e68-4137-9b89-c4e89433aadc
  • Property mode set to 100644
File size: 3.4 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#include <kernel/mod2.h>
22
23#include <omalloc/omalloc.h>
24#ifdef PDEBUG
25#undef NO_INLINE3
26#define NO_INLINE3
27#endif
28#include <kernel/polys-impl.h>
29
30#include <kernel/structs.h>
31#include <kernel/febase.h>
32#include <kernel/numbers.h>
33#include <kernel/polys.h>
34#include <kernel/ring.h>
35#include <kernel/p_Procs.h>
36#include <kernel/dError.h>
37
38#ifdef PDEBUG
39int pDBsyzComp=0;
40#endif
41
42/***************************************************************
43 *
44 * Storage Managament Routines
45 *
46 ***************************************************************/
47
48
49poly pHeadProc(poly p)
50{
51  return pHead(p);
52}
53
54
55static inline unsigned long GetBitFields(long e,
56                                         unsigned int s, unsigned int n)
57{
58#define Sy_bit_L(x)     (((unsigned long)1L)<<(x))
59  unsigned int i = 0;
60  unsigned long  ev = 0L;
61  assume(n > 0 && s < BIT_SIZEOF_LONG);
62  do
63  {
64    assume(s+i < BIT_SIZEOF_LONG);
65    if (e > (long) i) ev |= Sy_bit_L(s+i);
66    else break;
67    i++;
68  }
69  while (i < n);
70  return ev;
71}
72
73// Short Exponent Vectors are used for fast divisibility tests
74// ShortExpVectors "squeeze" an exponent vector into one word as follows:
75// Let n = BIT_SIZEOF_LONG / pVariables.
76// If n == 0 (i.e. pVariables > BIT_SIZE_OF_LONG), let m == the number
77// of non-zero exponents. If (m>BIT_SIZEOF_LONG), then sev = ~0, else
78// first m bits of sev are set to 1.
79// Otherwise (i.e. pVariables <= BIT_SIZE_OF_LONG)
80// represented by a bit-field of length n (resp. n+1 for some
81// exponents). If the value of an exponent is greater or equal to n, then
82// all of its respective n bits are set to 1. If the value of an exponent
83// is smaller than n, say m, then only the first m bits of the respective
84// n bits are set to 1, the others are set to 0.
85// This way, we have:
86// exp1 / exp2 ==> (ev1 & ~ev2) == 0, i.e.,
87// if (ev1 & ~ev2) then exp1 does not divide exp2
88unsigned long p_GetShortExpVector(poly p, ring r)
89{
90  assume(p != NULL);
91  if (p == NULL) return 0;
92  unsigned long ev = 0; // short exponent vector
93  unsigned int n = BIT_SIZEOF_LONG / r->N; // number of bits per exp
94  unsigned int m1; // highest bit which is filled with (n+1)
95  unsigned int i = 0, j=1;
96
97  if (n == 0)
98  {
99    if (r->N <2*BIT_SIZEOF_LONG)
100    {
101      n=1;
102      m1=0;
103    }
104    else
105    {
106      for (; j<=(unsigned long) r->N; j++)
107      {
108        if (p_GetExp(p,j,r) > 0) i++;
109        if (i == BIT_SIZEOF_LONG) break;
110      }
111      if (i>0)
112      ev = ~((unsigned long)0) >> ((unsigned long) (BIT_SIZEOF_LONG - i));
113      return ev;
114    }
115  }
116  else
117  {
118    m1 = (n+1)*(BIT_SIZEOF_LONG - n*r->N);
119  }
120
121  n++;
122  while (i<m1)
123  {
124    ev |= GetBitFields(p_GetExp(p, j,r), i, n);
125    i += n;
126    j++;
127  }
128
129  n--;
130  while (i<BIT_SIZEOF_LONG)
131  {
132    ev |= GetBitFields(p_GetExp(p, j,r), i, n);
133    i += n;
134    j++;
135  }
136  return ev;
137}
138
139#endif // POLYS_IMPL_CC
Note: See TracBrowser for help on using the repository browser.