Root/
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 |
---|