Integer overflow in universal hashing implementation

Question

For one of my pet projects I would like to create an arbitrary number of different integer hashes. After a bit of research I figured that universal hashing is the way to go. However, I struggle with the (numpy) implementation. Say I'm trying to use the hash family h(a,b)(x) = ((a * x + b) mod p) mod m and my x can be anywhere in the range of uint32. Then choosing p >= max(x) and a, b < p means that in the worst case a * x + b overflows not only uint32 but also uint64. I tried to find an implementation which solves this problem but only found clever ways to speed up the modulo operation and nothing about overflow.

Any suggestions for how to implement this are greatly appreciated. Thanks :-)

kennytm · Accepted Answer · 2017-04-20 23:53:35Z

1

(x + y) % z == ((x % z) + (y % z)) % z. So you could take the modulus before doing the sum:

Cast a and x to uint64. (Multiply two uint32 will never overflow uint64).
Compute h = (a * x) % p + b
Return (h - p) if h > p else h. (Alternatively: return h % p)

answered Apr 20, 2017 at 23:53

kennytm

526k111 gold badges1.1k silver badges1k bronze badges

Sign up to request clarification or add additional context in comments.

1 Comment

vrtsig Over a year ago

well, that was easy. Thanks! :-)

Collectives™ on Stack Overflow

Integer overflow in universal hashing implementation

1 Answer 1

1 Comment

Your Answer

Hot Network Questions

Collectives™ on Stack Overflow

1 Answer 1

1 Comment

Your Answer

Sign up or log in

Post as a guest

Related