qsieve

qsieve Mercurial Source Tree


Root/src/StaticRelations.cc

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
/*! @file
 * @brief
 * implementation of class StaticRelations
 */
 
#include "StaticRelations.H"
 
CRelation* StaticRelations::GLS[StaticFactorbaseSettings::MaxSize] = {NULL};
int StaticRelations::Filling_GLS = 0;
 
filebuf StaticRelations::FileBuffer;
ostream StaticRelations::StaticRelations_to_file(&StaticRelations::FileBuffer);
istream StaticRelations::StaticRelations_from_file(&StaticRelations::FileBuffer);
 
 
void StaticRelations::Load()
{
  // reading static relations from file
#ifdef VERBOSE_NOTICE
  cout << "Reading static relations from file..." << endl;
#endif
  StaticRelations_from_file.seekg(0,ios::beg);
  while (StaticRelations_from_file.peek()=='G' || StaticRelations_from_file.peek()=='U')
   {
     if (StaticRelations_from_file.peek()=='U')
      {
#ifdef VERBOSE_WARN
        cerr << "skipping obsolete/invalid relation." << endl;
#endif
        StaticRelations_from_file.ignore(1000000,'\n');
        continue;
      }
     CRelation* GL = new CRelation();
     GL->combine(StaticRelations_from_file);
     GL->optisize(); // Relation optimieren (dense<->sparse, etc.)
     GLS[GL->relevant_factor]=GL; ++Filling_GLS; // insert relation into linear system of equations
     StaticRelations_from_file.ignore(1,'\n');
   }
  if (StaticRelations_from_file.peek()!=EOF)
   {
     cerr << "Static Relations: garbage detected. Giving up. Please validate." << endl;
     exit(1);
   }
  StaticRelations_from_file.clear();
#ifdef VERBOSE_NOTICE
  cout << "Recover: " << StaticRelations::Count() << " static relations read." << endl;
#endif
}
 
void StaticRelations::insert(CRelation *GL, const bool do_multi_combine_init /* =true */)
{
  /* Any new relation is inserted into the linear system of equations.
     If the relation is redundant or if it leads to a factorization,
     this will be detected automatically. */
 
#ifdef IS_CLIENT
  // the Client does not manage any system of equations (which is instead handled by the server!)
  // so: delete the relation, do stats and return
  if (GL->relevant_factor >= 0) ++Filling_GLS;
  delete GL;
  return;
#else 
  if (GL->relevant_factor==CRelation::dynamic_factor || GL->relevant_factor==CRelation::special_factor)
    { delete GL; return; } // save it to background storage and delete it in main memory
 
#ifdef IS_SERVER
  // if this function is called by multiple threads, it is a critical section!
  // therefore we have to protect it with a mutex...
  static CCriticalSection::Mutex my_read_mutex;
  static CCriticalSection::Mutex my_write_mutex;
  CCriticalSection CriticalSection_Read(my_read_mutex); // enter Critial Section
  CCriticalSection CriticalSection_Write(my_write_mutex,false); // do not enter Additional Critical Section yet
#endif
   
  if (do_multi_combine_init)
   {
     CRelation::SMulticombineData *pMD=new(CRelation::SMulticombineData);
     GL->set_MulticombineData(pMD);
     GL->multi_combine_init();
   }
    
  while (!GL->empty())
    {
      if (GL->relevant_factor>=StaticFactorbase::Size())
       {
         MARK;
         cerr << "value too big!" << endl;
         exit(1);
       }
      CRelation *pos = GLS[GL->relevant_factor];
      if (pos!=NULL)
    {
          // an entry for this relation already exists -> we can combine it!!
#if 1 /* toggle minimization of relations (1=on/0=off) */
          if (
           (GL->Relation_sparse) && (pos->Relation_sparse) // both are sparse
               && GL->SizeOfRelation()<=pos->SizeOfRelation()
           && GL->second_largest_factor_in_Relation()<=pos->second_largest_factor_in_Relation()
             )
        {
              /* weniger Primzahlen in der Relation bedeuten schnelleres Abarbeiten.
         Da beide Relationen äquivalent sind, können sie problemlos so
         getauscht werden, dass die platzsparende im Gleichungssystem verbleibt.
         Andererseits bestimmt das Maximum der zweitgrößten Faktoren zweier
         Relationen die nächste Verknüpfung. Also ist auch dies zu minimieren.
                 Beim Zielkonflikt wären beide Kriterien also abzuwägen. Dies geschieht
         hier nicht. Nur wenn beide Kriterien zugleich die Lage nicht
                 verschlechtern, werden die Relationen getauscht.
 
                 Please note, that swapping the two relations does not change the the result of
                 the combine operation. But it may help to speed-up later combinations and/or
                 and/or reduces memory consumption.
              */
 
#ifdef IS_SERVER
              // if we can retrieve the write lock immediately, then
              // we perform the optimization, otherwise we simply continue...
              if (!CriticalSection_Write.try_enter())
              {
#if defined(VERBOSE_INFO) || 1
                static unsigned int count = 0;
                ++count;
                if ((count&0x1f)==0)
                 cout << "Elided optimizations due to write-locked Static Relations: " << count << endl;
#endif                
              }
              else
              {
#if defined(VERBOSE_INFO) || 1
                static unsigned int count = 0;
                ++count;
                if ((count&0x1f)==0)
                 cout << "Performed optimizations due to unlocked Static Relations: " << count << endl;
#endif                
#endif
          GL->multi_combine_exit();
          GLS[GL->relevant_factor]=GL;
          std::swap(pos,GL); // swap relations
              GL->use_MulticombineData_from(*pos);
              pos->invalidate_MulticombineData();
              GL->multi_combine_init();
#ifdef IS_SERVER             
              CriticalSection_Write.leave();
              }
#endif             
        }
#endif
          // biggest factor has to be eliminated
      GL->multi_combine_main(*pos);
    }
      else
    {
      GL->multi_combine_exit();
          GL->dispose_MulticombineData();
 
#ifdef IS_SERVER
      CriticalSection_Write.enter();
#endif   
 
      GLS[GL->relevant_factor]=GL; // insert relation into linear system of equations
      Filling_GLS++; // one more relation in the system of linear equations
 
#ifdef IS_SERVER
      CriticalSection_Read.leave();
#endif
 
          GL->save(StaticRelations_to_file);
          // usleep(11000); // only for debugging: simulate slow filesystem
          StatusReport();
      return;
    }
    }
 
  GL->multi_combine_exit();
  GL->dispose_MulticombineData();
 
  // the relation is redundant:
  // -> we cannot insert it into the static factorbase,
  // -> it can yield a factor instead!
  // -> compute quadratic congruency!
  const bool complete = GL->ComputeQuadraticCongruence();
  delete GL;
  if (complete)
   {
     // Game over, we have won!
     // leave the program...
     ExitManager::StopFactorization(); // try to stop the program successfully...
     exit(0); // this line should not be reached!
   }
#endif
}
Source at commit 0bf643a2ed03 created 11 years 9 months ago.
By Nathan Adams, fixing Sieving and modifications

Archive Download this file

Branches

Tags

Page rendered in 0.74863s using 11 queries.