Hashing: Quadratic Probing

Thread Starter

zulfi100

Joined Jun 7, 2012
656
Hi,
My book shows following sequence:
9, 10, 8, 13, 5, 18, 0, 6, 12, 15, 3, 7, 11, 1, 17, 16, 2, 14, 4

I am trying to regenerate it. I am able to find:
h(k) = 9%19 = 9
h(k) + 1 power 2 = 10 % 19 = 10
h(k) - 1 power 2 = 8 % 19 = 8
h(k) + 2 power 2 = 13 % 19 = 13
h(k) - 2 power 2 = 5 % 19 = 5
h(k) + 3 power 2 = 18 % 19 = 18
h(k) - 3 power 2 = 0
h(k) + 4 power 2 = 9 + 16 = 25 % 19 = 6
h(k) - 4 power 2 = 9 -16 = -7 %19 = -7 which is wrong, it should be 12. I know 19 -7 = 12. But i dont know how to get it.

They are using the formula:

h(K), h(K) + 1, h(k) -1, h(k) + 4, h(K) - 4, .... h(K) + (TSIZE -1)power 2 / 4, h(k) - (TSIZE -1) power 2 /4 all divided modulo TSize.
where j =4 & table size = 19 & assuming h(K) = 9.
Some body please guide me how to solve it.

Zulfi.
 

MrAl

Joined Jun 17, 2014
11,389
Hello there,

Calculating Mod is different for negative numbers than for positive numbers. Look that up you'll find more information.

For example, if the rule for Mod(-x,N) is to add N to -x until we get a number greater that zero, then we would get:
-7+19=12

What what i understand rules for Mod negative numbers vary so you'll have to simply do a few calculations to find out which rule they are using. it looks like that one above though., but test more results to be sure or look it up in your book if you have one.

Just to note, the next two numbers in the sequence, 15 and 3, do result from using the above rule.
 

WBahn

Joined Mar 31, 2012
29,979
In most languages, the % operator is NOT the modulo operator, it is the remainder operator. When the dividend and the divisor are both positive, they produce the same result. But when one (or both) is negative they may or may not produce the same result. It depends on how integer division is defined and there are two options -- round toward zero or round toward negative infinity. As is commonly the case, each option has pros and cons and so, as is commonly the case, some languages choose one and other languages choose the other.

In either case, most languages (I know of no exception) that support both integer division and the remainder operator require that the following relationship hold true:

if a, b, q, r are integer types, then if

q = a / b AND r = a % b

then it is required that

a = q * b + r

Note that if a<0 and b>0, then if (a/b) rounds toward zero the only way the last equation can hold is if r < 0.

If you want the principal modulus (i.e., 0 <= r < b) for b>0, then YOU are responsible for ensuring that this will happen. The easiest way is to ensure that both a and b are positive before applying the remainder operator. If b>0 (as is usually the case when you care about modulo division), then you can do something like

while (a < 0) a += b;

Unless you are doing something unusual, this loop should only execute a few times (usually just zero or one times), so the performance hit is very small.

Another way is to adjust the result after the remainder operator is applied

while (r < 0) r += b;

In principle, this should always execute either zero or once, so you should be able to get away with a simple if statement instead of a while statement.
 
Top