fplll / g6k

The General Sieve Kernel
GNU General Public License v2.0
103 stars 31 forks source link

Simplify gauss_sieve #48

Open cr-marcstevens opened 4 years ago

cr-marcstevens commented 4 years ago

So I don't forget: More simplified code for gauss_sieve in https://github.com/fplll/g6k/blob/master/kernel/sieving.cpp is sketched as follows:

if (queue_begin == 0) queue_begin=1;
// invariant: there are no possible pair-wise reductions for everything below position queue_begin
while (queue_begin < cdb.size())
{
   size_t i = 0;
   for ( ; i < queue_begin; )
   {
      which_one = do_reduce(i, queue_begin);
      if (which_one == 0) // no reduction
          { ++i; continue; } //  just continue with next position i+1
      if (which_one = 2) // reduced queue_begin
          { break; } // causes restart processing same queue_begin
      if (queue_begin >= 2) // reduced i && queue_begin>=2
      {
          // shuffle values such that value @ i is after the value @ queue_begin,
          // while keeping invariant
          // continue with processing same value that moved from position queue_begin to position queue_begin-1,
          // and at same position i (containing the value that was before at position queue_begin-1 )
          // everything below position i has already been checked
          swap(i, queue_begin - 1);
          swap(queue_begin - 1, queue_begin);
          --queue_begin;
      }
      // remaining case is queue_begin==1 but value at position 0 has changed, 
      // so we repeat the reduction attempt with same i (==0) and same queue_begin (==1)
   }
   if (i == queue_begin)
       ++queue_begin;
}

BTW should have same behavior and performance, but no more goto and no more p_index != queue_begin.