const size_t currentSeed = unpredictableSeed(); static if(vdebug){write("UT: lSR. "); writeln("seed: ", currentSeed);} rndGenInUse.seed(currentSeed); //initialize the random generator const size_t M = uniform(1U,size_t.max/2, rndGenInUse); //set universe size to some integer. auto lSR = lSR(M); assert((lSR & (lSR - 1)) == 0); assert(lSR * lSR < M); const auto check = powersOfTwo.find(lSR).array; if(lSR < size_t.max/2) assert((check[1]) > sqrt(to!float(M)));
This function returns the lower square root of the given input. It is needed by the indexing functions high(x), low(x) and index(x,y) of elements in the tree. Also, this is the universe size of a child of a node. The lower square root is defined by 2^{\lfloor(\lgu)/2\rfloor}