1

I want to use a pairwise independent hashing to implement an algorithm.

According to this answer on Obtaining a k-wise independent hash function, it seems that it is enough to compute (a*x + b) % p % m for mapping an integer x (which is smaller than p) to {0,1,...,m-1}.

Then I saw the following open source implementation: enter image description here. That seems to implement the above algorithm for p=2^31-1.

Can anyone help me make sense of it?

It seems that by doing & MOD, the code is actually computing (modulo 2^31) and not (modulo 2^31-1)? What does line 113 (seen on the screenshot) actually do? Why would you shift result and add it again?

M A
  • 209
  • 2
  • 7
  • 1
    I am afraid you won't get any answers unless you integrate the code from the screenshot as code block inside your question text. Also you should add the link to the OpenSource file you are talking about, to make your source transparent. And you need to make the reference to "line 113" obvious in some other way. Then your question would at least be easier to follow and to understand. Right now it lacks a great deal of information because of the image. Most users if not all users do not follow any links when reading a question but just skip to the next. – Antares May 05 '20 at 06:12
  • Thanks for the feedback, @Antares. I edited the question as you suggested. – M A May 06 '20 at 19:48
  • BTW: signed overflow is undefined in C. – wildplasser May 06 '20 at 19:50

0 Answers0