1. 4

  2. 4

    Unless I am missing something, the article never explains the purpose of this expression when used with unsigned integers.

    1. 7

      No, sadly, it doesn’t spell it out. The paper linked from the article reveals the use, although at the very last page:

      //  returns  value  in [0,s)
      //  random64  is a function  returning  random 64-bit  words
      uint64_t  openbsd(uint64_t s,uint64_t(*random64)(void)) {
        uint64_t t= (-s) %s;
        uint64_t x;
        } while(x<t);
        return x%s;

      The pseudo code of the same functions contains this line:

      t←(2^L−s) mod s                       {(2^L−s) mod s = 2^L mod s}

      That is , (-n)%n is just a faster way of obtaining 2^L modulo n, where L is the number of bits holding the data type n. Since value 2^L could not be represented in L bits, the formula avoids promotion to the higher container and avoids additional subtractions (2^L-s case, which is equivalent to 2^L for modulo s).