Advertisement
sosiris

Find sieve number

Aug 19th, 2015
235
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 1.86 KB | None | 0 0
  1. #include "getSieveNum.h"
  2.  
  3. namespace
  4. {
  5.   //pass the sieve or not
  6.   inline bool pass(const mp::cpp_int& start, const uint32_t steps)
  7.   {
  8.     mp::cpp_int val = start;
  9.     for (uint32_t i = 0; i < steps; ++i)
  10.     {
  11.       if (static_cast<uint32_t>(val) & 1u)
  12.       {
  13.         val += (val + 1) >> 1;
  14.       }
  15.       else
  16.       {
  17.         val >>= 1;
  18.         if (val < start)
  19.         {
  20.           return false;
  21.         }
  22.       }
  23.     }//for()
  24.     return true;
  25.   } //pass()
  26. } //namespace
  27. //Search 'steps'-step sieve number from the start
  28. mp::cpp_int getSieveNum(const mp::cpp_int& start, const uint32_t steps, const uint32_t *refSieve, uint32_t refSieveSize, uint32_t refSieveStep)
  29. {
  30.   //If there's no reference sieve, use the 2-step sieve (4k+3) instead
  31.   const uint32_t defaultSieveNum = 3u;
  32.   if (refSieve == NULL)
  33.   {
  34.     refSieve = &defaultSieveNum;
  35.     refSieveSize = 1;
  36.     refSieveStep = 2;
  37.   }// if(refSieve == NULL)
  38.  
  39.   //Find start's position in the reference sieve
  40.   uint32_t r = static_cast<uint64_t>(start) & ((1ull << refSieveStep) - 1);
  41.   uint32_t pos = 0u;
  42.   while ((pos < refSieveSize) && (r > refSieve[pos]))
  43.   {
  44.     ++pos;
  45.   } //while()
  46.   mp::cpp_int trunc = (start >> refSieveStep) << refSieveStep; //truncated value of start, lower 'refSieveStep' bits are cleared to make room for refSieve
  47.   const mp::cpp_int increment = mp::cpp_int(1u) << refSieveStep;
  48.   const mp::cpp_int maxVal = mp::cpp_int(1u) << steps; //maximal value of search range, if we reaches it, start over from 0
  49.   //Find the sieve number
  50.   while (true)
  51.   {
  52.     for (; pos < refSieveSize; ++pos)
  53.     {
  54.       const mp::cpp_int val = trunc + refSieve[pos];
  55.       if (pass(val, steps))
  56.       {
  57.         return val;
  58.       }
  59.     }
  60.     pos = 0;
  61.     trunc += increment;
  62.     if (trunc >= maxVal)
  63.     {
  64.       trunc = 0;
  65.     }
  66.   } //while()
  67.   return start;
  68. } //getSieveNum()
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement