Sieving.H

Go to the documentation of this file.

#ifndef SIEVING_HEADER_
#define SIEVING_HEADER_

#include "qsieve-fwd.H"
#include "StaticFactorbase.H"
#include <cmath>



extern int LogicalSieveSize; // sieving interval will be [-LogicalSieveSize,LogicalSieveSize] for each MPQS polynomial



// !!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!
// !!! IMPORTANT !!! #define and typedef MUST match !!!
// !!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!
#ifndef TSIEVEELEMENTSIZE
#warning "TSIEVEELEMENTSIZE not defined. Using default value: 1"
#define TSIEVEELEMENTSIZE 1 /* 1 = signed char, 2 = signed short int, 4 = signed int, 0 = no assembler inline code (=generic code) */
#endif

// if ASM_386 is defined, then TSIEVEELEMENTSIZE defines the type which is used in inline-assembler subroutines

#if TSIEVEELEMENTSIZE == 0
 typedef signed char TSieveElement; // must be signed!
 #define log_SieveEntryMultiplier 1 /* sieve entries are casted to TSiebelement using this multiplier */
 #ifdef ASM_386
  #warning "assembly code is disabled for sieving!"
 #endif
#elif TSIEVEELEMENTSIZE == 1
 typedef signed char TSieveElement; // must be signed!
 #define log_SieveEntryMultiplier 1 /* sieve entries are casted to TSiebelement using this multiplier */
#elif TSIEVEELEMENTSIZE == 2
 typedef signed short int TSieveElement; // must be signed!
 #define log_SieveEntryMultiplier 16 /* sieve entries are casted to TSiebelement using this multiplier */
#elif TSIEVEELEMENTSIZE == 4
 typedef signed int TSieveElement; // must be signed!
 #define log_SieveEntryMultiplier 256 /* sieve entries are casted to TSiebelement using this multiplier */
#else
 #error "invalid value for TSIEVEELEMENTSIZE"
#endif

/*
  The sieve needs less memory (and less cache), if TSieveElement is chosen
  of the smallest possible type. Sieving is faster for short types.

  On the other hand, the granularity to detect relations is worse for
  shorter datatypes than for longer ones.

  You have also to consider processor specific effects (eg. alignment penalties)!

  Following datatypes are possible:
    - signed char (1 byte)
    - signed short int (2 bytes)
    - signed int (4 bytes)
    - float, double (floating point types, several (>3) bytes)

  Size of types may vary between systems. I haven't checked, whether
  the program works for other constraints than
    int >= 4 bytes, short int >= 2 bytes.

  Important remark:
   If you use floating point types for TSieveElement (which I don't
   recommend anymore), then calling "ceil" is counterproductive (and such
   calls should be removed in the source code).  But there is really no
   reason, why one should do sieving using floating point types.
*/

/*
  about: log_SieveEntryMultiplier <VALUE>
  (-> refer TSIEVEELEMENTSIZE)

  Sieve entries are casted to TSieveElement using this multiplier to gain a
  better accuracy.  If the TSieveElement is of floating point type, then
  log_SieveEntryMultiplier can be set to 1. In all other cases you should
  set it to the highest possible value, such that the sieving threshold (for
  numbers usually to factorize) fits into TSieveElement.

  In order not to miss any detection of a relation when using short datatypes,
  you must use "ceil" while subtracting hits in the sieve. (Thereby the
  sieve gets close meshed.)
*/



#if defined(IS_SERVER) || defined(IS_VALIDATOR)

 // The server does no sieving, but the server source code needs some
 // information about how sieving is done. Additionally the server sources
 // contain some code that is depending on data structures defined here. We
 // could eliminate these lines by conditional compiling (#ifdef IS_SERVER),
 // but this would be to bloated. Instead of this, we provide a stubby class
 // for the SERVER to satisfy the linker.
 
class SieveControl : protected StaticFactorbaseSettings
{
 private:
  static const int FBLowestStartIndex = 5;
  /* This is the first index of the factorbase to sieve with.
     This value needs to be greater than 1, because the first two factors of
     the factorbase are -1 and (probably) 2. Fore these two numbers as well
     as for multiplier of kN we are unable to sieve. (Well, at least it would
     be more difficult.) For a fast, but dirty sieving you can choose a
     greater value as well.  But the higher the value is, the more relations
     remain undetected...
   */

  static void set_logVal_for_Primenumber(const int pos, const TSieveElement val, const TSieveElement dirtyval);
  static void set_logVal_for_Primepower(const int pos, const TSieveElement val);

 public:
  friend void StaticFactorbase::compute_StaticFactorbase();
};


// two dummy static functions, not inlined because they must be linked...
void SieveControl::set_logVal_for_Primenumber(const int, const TSieveElement, const TSieveElement)
{
  //cout << "set_logVal_for_Primenumber: do nothing..." << endl;
  // do nothing, as the server doesn't need this information!
}

void SieveControl::set_logVal_for_Primepower(const int, const TSieveElement)
{
  //cout << "set_logVal_for_Primepower: do nothing..." << endl;
  // do nothing, as the server doesn't need this information!
}

#else /* IS_SERVER not defined */

// these are the "full" declarations
#include <iosfwd>
#include <gmp.h>
#include "utils.H"
#include "mpz_wrapper.H"
using namespace my_mpz_wrapper;

using std::ostream;
using std::istream;

using std::cout;
using std::cerr;


extern int SieveOffset;
/* In general the logical sieve interval for each mpqs polynomial will exceed
   the size of the physical sieve. The logical sieve has to be sieved in
   several parts/steps. SieveOffset is the offset of the logical sieve at
   the starting point of a physical sieve.
 */


extern TSieveElement SieveArray_[PhysicalSieveSize+64+8] __attribute__ ((aligned (64))); // memory for the sieve
TSieveElement* const SieveArray = &SieveArray_[64];
// SieveArray[-64..-1] are -1 (for fast value-based end-of-loop range detections)
// SieveArray[0..PhysicalSieveSize-1] contain actually sieve values
// SieveArray[PhysicalSieveSize..PhysicalSieveSize+7] contain dummy values


extern TSieveElement log_Primzahl_of_PrimePowers[StaticFactorbase::max_additional_Powers];
// converted logarithms for further powers of prime numbers


extern mpz_t n, kN, r;
extern double Factor_Threshold;

inline TSieveElement log_DynamicLargePrime (const int p)
{
#if defined(ASM_386) && TSIEVEELEMENTSIZE == 1 && log_SieveEntryMultiplier == 1
 #ifdef DEBUG
  #warning "assembler i386 TSIEVEELEMENT log lookup enabled"
 #endif

  register TSieveElement logval;

#if 0
  // "old" crafted i386 assembler code, very fast,
  // we assume 8103<p<=1318815734, otherwise result is either 10 or 21.
  asm ( \
       "movb $21,%[L] \n\t" \
       "cmpl $485165195,%[P] # exp(20) \n\t" \
       "sbbb $0,%[L] \n\t" \
       "cmpl $178482300,%[P] # exp(19) \n\t" \
       "sbbb $0,%[L] \n\t" \
       "cmpl $65659969,%[P] # exp(18) \n\t" \
       "sbbb $0,%[L] \n\t" \
       "cmpl $24154952,%[P] # exp(17) \n\t" \
       "sbbb $0,%[L] \n\t" \
       "cmpl $8886110,%[P] # exp(16) \n\t" \
       "sbbb $0,%[L] \n\t" \
       "cmpl $3269017,%[P] # exp(15) \n\t" \
       "sbbb $0,%[L] \n\t" \
       "cmpl $1202604,%[P] # exp(14) \n\t" \
       "sbbb $0,%[L] \n\t" \
       "cmpl $442413,%[P] # exp(13) \n\t" \
       "sbbb $0,%[L] \n\t" \
       "cmpl $162754,%[P] # exp(12) \n\t" \
       "sbbb $0,%[L] \n\t" \
       "cmpl $59874,%[P] # exp(11) \n\t" \
       "sbbb $0,%[L] \n\t" \
       "cmpl $22026,%[P] # exp(10) \n\t" \
       "sbbb $0,%[L]" \
       : [L] "=&q" (logval) : [P] "r" (p) : "cc");
#endif


   static const int TREE[14] __attribute__ ((aligned (64))) =
    // heap of floor(exp(x+6)) values
     {
       // TREE[0..1], x: 4, 12, 
       22026, 65659969,
       // TREE[2..5], x: 2, 6, 10, 14,
       2980, 162754, 8886110, 485165195,
       // TREE[6..13], x: 1, 3, 5, 7, 9, 11, 13, 15
       1096, 8103, 59874, 442413, 3269017, 24154952, 178482300, 1318815734
     };

  // compute ceil(ln(p)) for 403<p<=2147483647
  // via binary tree search (without branch instructions).
  // (out of range values: 7 for 0<=p<404, 22 for (unsigned int)(p)>2147483647)

#if 0
  // i386 standard code,
  // ugly slow, because of memory access latencies
  asm ( \
       "xorl %%ecx,%%ecx \n\t" \
       "cmpl $1202604,%[P] \n\t" \
       "setnc %%cl \n\t" \
       "cmpl %[P],%[F](,%%ecx,4) \n\t" \
       "rclb $1,%%cl \n\t" \
       "cmpl %[P],%[F]+4*2(,%%ecx,4) \n\t" \
       "rclb $1,%%cl \n\t" \
       "cmpl %[P],%[F]+4*6(,%%ecx,4) \n\t" \
       "rclb $1,%%cl \n\t" \
       "addb $7,%%cl \n" \
       : [L] "=&c" (logval) : [F] "o" (TREE[0]), [P] "r" (p) : "cc");
#endif

#if 1
  // crafted Athlon code, i386 compatible,
  // fast, because most latencies are resolved
  asm ( \
       "xorl %%ecx,%%ecx \n\t" \
       "cmpl $65659969,%[P] \n\t" \
       "sbb $-1,%%cl \n\t" \
       "cmp $22026,%[P] \n\t" \
       "sbb $-1,%%cl \n\t" \
       "cmpl $1202604,%[P] \n\t" \
       "sbb $-1,%%cl \n\t" \
       "cmpl %[P],%[F]+4*2(,%%ecx,4) \n\t" \
       "lea (,%%ecx,4),%%eax \n\t" \
       "adcb $0,%%al \n\t" \
       "cmpl %[P],%[F]+4*6(,%%ecx,8) \n\t" \
       "adcb $0,%%al \n\t" \
       "cmpl %[P],%[F]+4*7(,%%ecx,8) \n\t" \
       "adcb $7,%%al \n" \
       : [L] "=&a" (logval) : [F] "o" (TREE[0]), [P] "r" (p) : "cc", "ecx");
#endif



#if 0 || defined(DEBUG)
  // remark: do not use std::log(), as it might be ambiguous for some
  // versions of g++ (-> see utils.H)
  if (logval!=ceil(log_SieveEntryMultiplier*log(p)))
   {
     MARK;
     cout << "P: " << p << " log:" << static_cast<int>(logval) << "  " << ceil(log_SieveEntryMultiplier*log(p)) << endl;
     exit(1);
   }
#endif
  return logval;
#else
  // generic version
  return static_cast<TSieveElement>(ceil(log_SieveEntryMultiplier*log(p)));
#endif
}


class SieveControl : protected StaticFactorbaseSettings
{
 private:
  static const int FBLowestStartIndex = 5;
  /* factorbase elements below this index will be elided while sieving.
     Index must be greater than 1, because the first two elements of the
     static factorbase are -1 and probably 2. For these values (and the
     prefactor of kN) sieving is not (easily) possible.
     For fast (very) dirty-sieving a greater value can be chosen. But too
     big indices decrease rate of detection of relations.
   */

  inline static double DirtyFactor(const int i)
   {
     if (i<FBLowestStartIndex+4) return 1.0;
     return 1.0/sqrt(i); // a function slowly going towards 0
   }
  /*
     DirtyFactor denotes the weight, with which the i-th prime number of the
     static factor base will hin into the sieve, if the hit is "dirty".

     Example:
      If you sieve the normal way using a prime number p, then you have a hit
      every p-th position in the sieve. This hit will be weighted by log(p).

      If  p is "dirty" then a hit will be weighted using DirtyFactor*log(p) for
      *every* sieve entry! Only if a relation is detected later, then this
      error (dirty-sieving effect) will be corrected to check, whether the
      hit would be a hit under normal circumstances. -- Doing this speeds up
      the sieving because less primes (especially the lower ones) need to be
      sieved at the cost of correcting the effect later. As normally only a
      small fraction of the sieve entries lead to relations, this shouldn't
      be a problem if the dirty prime numbers are dynamically adapted to the
      rate of hits.

      A DirtyFactor of 1.0 behaves neutral compared with normal sieving except
      for (potential) rounding errors, but it speeds up the sieving.

      The smaller the DirtyFactor, the more prime numbers can be dirty.
      (However, the rate of detection per sieve interval decreases in favour
      of sieving speed.)

      A DirtyFactor of 1/n behaves roughly as if each n-th dirty prime
      number would be a member in every relation.
   */

protected:
  static TSieveElement log_PrimeNumbers[StaticFactorbase::MaxSize] __attribute__ ((aligned (16)));
private:
   static unsigned int PhysicalSieveIntervalIndex; // number of the current physical interval to sieve with
   // starts with 0 for the start of each new logical sieve interval
   // and is increased by 1 for each new physical sieve interval

   static unsigned int BestPSI[2];
   // indices of the two best PhysicalSieveIntervals

   static TSieveElement PhysicalSieveIntervalThresholdCorrector[1024];
   // idea: the logical sieve interval differs slightly in quality for different
   // physical sieve intervals. So let's roughly correct the threshold for
   // each physical sieve interval from time to time. This may increase the quality of
   // detected relations.
   // SieveControl::GetLogThreshold() will always add this correction value to its
   // computed value. So it behaves totally neutral. You may change these values on the fly...
   // initial default values: 0, therefore neutral and no correction.

  static TSieveElement log_PrimeNumbers_dirty[StaticFactorbase::MaxSize] __attribute__ ((aligned (16)));
    // these are the converted logarithms of primenumbers from the static factorbase

  static TSieveElement raw_log_Threshold, log_Threshold, log_ThresholdDeltaHint; // will be initialized later!
  static int myFBStartIndex, myFBStartIndexHint;
  static signed int DirtinessPegel;

public:
  inline static TSieveElement GetRawLogThreshold() { return raw_log_Threshold; }
  inline static TSieveElement GetLogThreshold()
   {
     return log_Threshold+PhysicalSieveIntervalThresholdCorrector[PhysicalSieveIntervalIndex];
   }
  inline static TSieveElement GetLogDirtyCorrection() { return raw_log_Threshold-log_Threshold; }
  inline static void RenewThresholds()
   {
     log_Threshold+=log_ThresholdDeltaHint;
     log_ThresholdDeltaHint=0; // reset
     myFBStartIndex=myFBStartIndexHint;
   }
  static void RecalibrateThresholds();
  static void create_sieve_image(int* &Image, int mySieveOffset);

  inline static int FBStartIndex() { return myFBStartIndex; }
  static void compute_SieveThreshold();
  static bool Hit_after_DirtyCorrection(const signed int SievePos, TSieveElement Value);

  inline static TSieveElement PrimzahlSieveWeight(const int i)
   {
     // returns the weight of the prime concerning the sieve;
     // usually this is the (scaled) logarithm which has been put
     // in the table before.
     // This function encapsulates access to this value to make it read-only.
     return log_PrimeNumbers[i];
   }
  inline static TSieveElement PrimzahlSieveWeight_dirty(const int i)
   {
     // returns the weight of the prime concerning the sieve, if the
     // prime has been marked as "dirty" before, that is: for performance
     // reasons we omit using this prime for sieving.
     // Usually this value is used to lower the threshold beforehand.
     // This function encapsulates access to this value to make it read-only.
     return log_PrimeNumbers_dirty[i];
   }

private:

  static void set_logVal_for_Primenumber(const int pos, const TSieveElement val, const TSieveElement dirtyval);
  static void set_logVal_for_Primepower(const int pos, const TSieveElement val);

  static void IncreaseDirtiness(void)
   {
     // decrease threshold and increment index for first element to sieve with
     if (myFBStartIndexHint>(StaticFactorbase::Size()>>2)) return; // this would be far too much dirtiness!
     log_ThresholdDeltaHint-=PrimzahlSieveWeight_dirty(myFBStartIndexHint);
     ++myFBStartIndexHint;
#ifdef VERBOSE_INFO
     cout << "suggested Dirtiness now " << myFBStartIndexHint << endl;
#endif
   }

  static void DecreaseDirtiness(void)
   {
     // increment threshold and decrement index for first element to sieve with
     if (myFBStartIndexHint<=FBLowestStartIndex) return; // impossible to decrease
     log_ThresholdDeltaHint+=PrimzahlSieveWeight_dirty(--myFBStartIndexHint);
#ifdef VERBOSE_INFO
     cout << "suggested Dirtiness now " << myFBStartIndexHint << endl;
#endif
   }

  static void RequestDirtiness(const signed int Level)
   {
     DirtinessPegel+=Level;
     if (DirtinessPegel>1000000)
      {
        DirtinessPegel=0;
        IncreaseDirtiness();
      } else
     if (DirtinessPegel<-1000000)
      {
        DirtinessPegel=0;
        DecreaseDirtiness();
      }
   }

 public:
  static inline void RequestMoreDirtiness(const signed int Level = 1000)
   {
     RequestDirtiness(Level);
   }
  static inline void RequestLessDirtiness(const signed int Level = 50)
   {
     RequestDirtiness(-Level);
   }

  friend void StaticFactorbase::compute_StaticFactorbase();
  friend void initialize_Sieve();
  friend void initialize_Sieve(const int Image[]);
  friend void do_sieving_full_intervals();
  friend void do_sieving_partial_intervals();
};

#include <qsieve.H>
#include <vector>


// just a declaration:
namespace DynamicFactorArrays
{
  extern unsigned int DynamicFactorsInUse;
  extern double DYNFB_threshold;
  void compute_Deltas_for_DynamicFactors(const int offset);
}


// helper class for computing Deltas
class CDeltaComputations : protected StaticFactorbase
{
 private:
             // a bit tricky:
             // the first two values are undefined,
             // then follow pairs of (FBPrime[i]*FBPrime[i+1],D_mod(FBPrime[i]*FBPrime[i+1])
             // then follow the unpaired "normal" values...
             // (see the update()-function to understand this!)
  static int D_mod_FBPrime[StaticFactorbase::MaxSize];
  static signed int D_difference_to_last; // 0 for undefined; all other values represent the real difference
  class CmpqsDmodPUpdater
   {
    public:
     mpz_t act_D;
     CmpqsDmodPUpdater()
      {
        mpz_init_set_d(act_D,-10e40); // to guarantee that the first MPQS interval triggers an update!
        for (int i=0; i<StaticFactorbase::MaxSize; ++i) D_mod_FBPrime[i]=0;
      }
     ~CmpqsDmodPUpdater()
      {
        mpz_clear(act_D);
      }
     void update();
   };

  static CmpqsDmodPUpdater mpqsDmodPUpdater;
  static unsigned int get_A2_mod_FBPrime(const int Nr)
   {
#ifdef DEBUG
     if (Nr<3 || Nr>StaticFactorbase::Size()) { MARK; exit(777); }
#endif
     // A2 := A*2 = 2*D^2; see mpqsPolynom.H: method get_A2_mod(const unsigned int m)
     unsigned int h = numtheory::squaremod(D_mod_FBPrime[Nr],PrimeNumbers[Nr])<<1;
     if (h>=static_cast<unsigned int>(PrimeNumbers[Nr])) h-=PrimeNumbers[Nr];
     return h;
   }
  static unsigned int get_A2_mod_FBPrimePair(const int Nr)
   {
#ifdef DEBUG
     if (Nr&1 || PrimeNumbers[Nr+1]>=46340) { MARK; exit(777); } // see comments above!
#endif
     // A2 := A*2 = 2*D^2; see mpqsPolynom.H: method get_A2_mod(const unsigned int m)
     unsigned int h = numtheory::squaremod(D_mod_FBPrime[Nr+1],D_mod_FBPrime[Nr])<<1;
     if (h>=static_cast<unsigned int>(D_mod_FBPrime[Nr])) h-=D_mod_FBPrime[Nr];
     return h;
   }


 protected:
  static int Delta_of_PrimeNumbers[StaticFactorbase::MaxSize][2] __attribute__ ((aligned (16)));
  static int Delta_of_PrimePowers[StaticFactorbase::max_additional_Powers][2] __attribute__ ((aligned (16)));
  static int LocalPhysInterval_Delta_of_PrimeNumbers[StaticFactorbase::MaxSize][2] __attribute__ ((aligned (16)));
  static int LocalPhysInterval_Delta_of_PrimePowers[StaticFactorbase::max_additional_Powers][2] __attribute__ ((aligned (16)));

 private:
  static void recompute_all_Deltas(const bool DoReallyAll=true);
  static void GetStaticFactorHits(std::vector<unsigned int> &Factors, const signed int SievePos);

 friend void do_sieving_full_intervals();
 friend void do_sieving_partial_intervals();
 friend CRelation::CRelation(const signed int SievePos, short int HitCount /* =0 */);
 friend bool SieveControl::Hit_after_DirtyCorrection(const signed int SievePos, TSieveElement Value);
 friend void DynamicFactorArrays::compute_Deltas_for_DynamicFactors(const int offset);
};


// helper class to encapsulate private data
class CSieveStaticFactors : private CDeltaComputations, protected SieveControl
{
 private:

#if (TSIEVEELEMENTSIZE == 1)
  // helper routines for speeding up asm sieving greatly!
  // idea: since LogValues for prime numbers don't differ for most
  // consecutive static factors (and these values are monotone increasing),
  // we can count runs of LogValues.
  static unsigned short int LogValRuns[128];
  static unsigned short int PrimeNumberDiffs[MaxSize];
  static void init_LogValRuns()
   {
     for (int i=StaticFactorbase::Size()-1; i>1; --i)
      {
        unsigned int h=PrimeNumbers[i]-PrimeNumbers[i-1];
        //if (h>100) cout << "i: " << i << " h: " << h << endl;
        PrimeNumberDiffs[i]=h;
      }

     register TSieveElement LogVal = PrimzahlSieveWeight(StaticFactorbase::Size()-1);
     register unsigned int c = 0;
     int pos = 0;
     for (int i = StaticFactorbase::Size()-1; PrimeNumbers[i]>=PhysicalSieveSize; --i)
      {
        if (SieveControl::PrimzahlSieveWeight(i)==LogVal) ++c;
        else
         {
           if (c>65534)
            {
              MARK;
              cerr << "overflow!" << endl;
            }
           // store length of run of same LogVals
           LogValRuns[pos]=c; c=1; ++pos;
           if (--LogVal != PrimzahlSieveWeight(i))
           {
             cerr << "unexpected LogValue!" << endl;
             MARK;
             exit(1);
           }
         }
      }
     LogValRuns[pos++]=c;
     LogValRuns[pos++]=0; // stop marker
     LogValRuns[pos]=0; // additional stop marker
     //cout << "Runs: " << pos << ": ";
     //for (int i=0; i<pos; ++i) cout << LogValRuns[i] << "  ";
     //cout << endl; 
   }
#endif

  static void create_Tables_for_init_LocalDeltas(int* &Table1, int* &Table2, const int SieveOffset);
  static void init_LocalDeltas() __attribute__ ((deprecated));
  static void init_LocalDeltas(const int Table1[], const int Table2[]);
  static void do_sieving_StaticFactors();

  static int* DefaultHelperTable[2];

public:
 static void initialize()
  {
#if (TSIEVEELEMENTSIZE == 1)
    init_LogValRuns();
#endif
    create_Tables_for_init_LocalDeltas(DefaultHelperTable[0],DefaultHelperTable[1], -LogicalSieveSize);
     // this should be the default for sieving data: starting at -LogicalSieveSize
  }

 static void destruct()
  {
    delete [] DefaultHelperTable[1]; DefaultHelperTable[1]=NULL;
    delete [] DefaultHelperTable[0]; DefaultHelperTable[0]=NULL;
  }

 friend void do_sieving_full_intervals();
 friend void do_sieving_partial_intervals();
 friend int main(const int argc, const char* const argv[]);
};


void do_scanning_Sieve(void);

void do_sieving_Squares();
void do_sieving_DynamicFactors();
void Werteverteilung_im_Sieb_ausgeben(void);

extern void (*do_sieving)(); // function pointer to sieve method that is used
void do_sieving_full_intervals();

#include "DynamicFactorRelations.H"
extern TDynamicFactorRelations DynamicFactorRelations;

#endif /* IS_SERVER not defined */


// this is used to store the sieved dynamic factors.
// Remark: To collect the dynamic factors efficiently in the sieving phase, I decided to make this array global.
//         (The constructor of "CRelation" is called with the number of found dynamic factors for each relation.)
class CHits
{
 public: static const short int MaxHits=64; // "64 dynamic factors should be enough for everyone"
 public: int Faktor;
 private: int Exponent;
 public:
  inline int GetExponent() const { return Exponent; }
 friend CRelation::CRelation(const signed int SievePos, short int HitCount /* =0 */);
};

extern CHits Hits[CHits::MaxHits]; // collected dynamic factors

#endif /* SIEVING_HEADER_ */

---