I understood how Horner's method reduces the complexity(number of operations) while evaluating a polynomial.
I have a character array derived from a string
String s = "hi how are you"
char[] array = {'h' , 'i', ' ', 'h', 'o', 'w', ' ', 'a', 'r', 'e,' ' ', 'y', 'o', 'u'}
I want to generate hash for set of characters, in successive windows of same size, example 0..3, 1..4, 2..5 etc.
Let's say I want to generate hash for characters 0(inclusive) through 3(exclusive), polynomial is $ax^2+bx+c$ where $a = array[0], b = array[1], c = array[2] $ . I am using following code.
int BASE = 31, MOD = 1000000007;
public long firstHash(char[] array, int start, int end) {
long hash = 0;
for (int i = start; i < end; i++) {
hash = (hash * BASE + array[i]) % MOD;
}
return hash;
}
I can see how this function evaluates the polynomial. I am using MOD to prevent overflows.
Now, if I want to generate hash for characters 1(inclusive) through 4(exclusive), it should be in constant time if we use hash generated for 0..3. New equation would be $bx^2+cx+d$. All that I have to do is subtract $ax^2$, multiply the result with x and add new element which is array[3]
$$ previousHash = ax^2+bx+c\\ newHash = x\times (previousHash - ax^2)+d \\ = x\times (ax^2+bx+c-ax^2)+d \\ = bx^2+cx+d \\ $$
I am using following code for successive hash generations
int BASE = 31, MOD = 1000000007;
public long successiveHash(char[] array, int start, int end, long previousHash) {
long base = 1;
for (int i = start; i < end - 1; i++) {
base = (base * BASE) % MOD;
}
return ((previousHash - ((array[start - 1] * base) % MOD)) * BASE + array[end - 1]) % MOD;
}
But, I am confused because of MOD. Although I know the multiplication and addition rule for % operator, I couldn't prove the successiveHash function. For smaller windows, it seems fine. But, if I generate hash for larger windows like 1..7, it is giving me negative values for hash.
I think I get the math part correct but implementation wrong.
Any help in correcting this function is of great help.
%
to negative numbers, and beware of wraparound/overflow/underflow. $\endgroup$ – D.W.♦ Apr 8 '18 at 3:38