Source code for pbrt, the renderer described in the third edition of "Physically Based Rendering: From Theory To Implementation", by Matt Pharr, Wenzel Jakob, and Greg Humphreys.
For original quadratic probing looks like offset = (originalOffset + c1*step + c2*step*step) % hashTable.size() and in most examples of Wikipedia's article it is shown wich c1=0; c2=1: index = (key + i*i) % SIZE; . Note, that i*i is added to key and not to index.
In the same Wikipedia article there is remark above code example:
For m = 2^n, a good choice for the constants are c1 = c2 = 1/2, as the values of h(k,i) for i in [0,m-1] are all distinct. This leads to a probe sequence of h(k),h(k)+1,h(k)+3,h(k)+6,... where the values increase by 1, 2, 3, ...
i.e. it describes formula index = (index + i) & (SIZE-1) if SIZE is a power of two. That is most used variation of quadratic probing.
mmp
commented
4 years ago
Line at https://github.com/mmp/pbrt-v3/blob/9c707675837967604eeee7ec35789a10c8676c84/src/core/api.cpp#L334 should look like:
Explanation:
For original quadratic probing looks like
offset = (originalOffset + c1*step + c2*step*step) % hashTable.size()and in most examples of Wikipedia's article it is shown wichc1=0; c2=1:index = (key + i*i) % SIZE;. Note, thati*iis added tokeyand not toindex.In the same Wikipedia article there is remark above code example:
i.e. it describes formula
index = (index + i) & (SIZE-1)if SIZE is a power of two. That is most used variation of quadratic probing.For example, it is used in google's dense hash: https://github.com/sparsehash/sparsehash/blob/master/src/sparsehash/internal/densehashtable.h#L650 https://github.com/sparsehash/sparsehash/blob/master/src/sparsehash/internal/densehashtable.h#L119