Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- #include "getSieveNum.h"
- namespace
- {
- //pass the sieve or not
- inline bool pass(const mp::cpp_int& start, const uint32_t steps)
- {
- mp::cpp_int val = start;
- for (uint32_t i = 0; i < steps; ++i)
- {
- if (static_cast<uint32_t>(val) & 1u)
- {
- val += (val + 1) >> 1;
- }
- else
- {
- val >>= 1;
- if (val < start)
- {
- return false;
- }
- }
- }//for()
- return true;
- } //pass()
- } //namespace
- //Search 'steps'-step sieve number from the start
- mp::cpp_int getSieveNum(const mp::cpp_int& start, const uint32_t steps, const uint32_t *refSieve, uint32_t refSieveSize, uint32_t refSieveStep)
- {
- //If there's no reference sieve, use the 2-step sieve (4k+3) instead
- const uint32_t defaultSieveNum = 3u;
- if (refSieve == NULL)
- {
- refSieve = &defaultSieveNum;
- refSieveSize = 1;
- refSieveStep = 2;
- }// if(refSieve == NULL)
- //Find start's position in the reference sieve
- uint32_t r = static_cast<uint64_t>(start) & ((1ull << refSieveStep) - 1);
- uint32_t pos = 0u;
- while ((pos < refSieveSize) && (r > refSieve[pos]))
- {
- ++pos;
- } //while()
- mp::cpp_int trunc = (start >> refSieveStep) << refSieveStep; //truncated value of start, lower 'refSieveStep' bits are cleared to make room for refSieve
- const mp::cpp_int increment = mp::cpp_int(1u) << refSieveStep;
- const mp::cpp_int maxVal = mp::cpp_int(1u) << steps; //maximal value of search range, if we reaches it, start over from 0
- //Find the sieve number
- while (true)
- {
- for (; pos < refSieveSize; ++pos)
- {
- const mp::cpp_int val = trunc + refSieve[pos];
- if (pass(val, steps))
- {
- return val;
- }
- }
- pos = 0;
- trunc += increment;
- if (trunc >= maxVal)
- {
- trunc = 0;
- }
- } //while()
- return start;
- } //getSieveNum()
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement