On Fri, Feb 10, 2017 at 7:03 AM, Connor Abbott <cwabbo...@gmail.com> wrote: > On Thu, Feb 9, 2017 at 4:16 PM, Jan Ziak <0xe2.0x9a.0...@gmail.com> wrote: >> Hello >> >> IMPORTANT NOTE: Using the uint32_t data type, quad_hash*quad_hash will >> overflow as soon as the hash table has more than 2**16=65536=64K >> elements. To enable more than 64K elements in hash table, the data >> types need to be changed to uint64_t - unfortunately uint64_t >> arithmetic operations will slow down the hash table in 32-bit OpenGL >> apps. > > This actually doesn't matter, since at the end of the day we only need > the result modulo the table size which is a power of two -- even if > the multiplication overflows, the lowest n bits (if the table size is > 2^n) are still correct, so we get the same answer as long as we use at > least n bits.
Yes, you are right. I sent the post before realizing it. (k+x*x)%m = (k+(x*x)%m)%m = (k+((x*x)%A)%m)%m, A=n*m, A>=m, n>=1 m: hash table size, a power of 2 A: 2**32 in case of uint32_t _______________________________________________ mesa-dev mailing list mesa-dev@lists.freedesktop.org https://lists.freedesktop.org/mailman/listinfo/mesa-dev
