Hey guys, I am having issues understanding how exactly to mod something to avoid overflow.
say i have this hash function:
int universalHash(const string &x,int B) {
long long sum;
long long power;
sum=0;
pow = 1;
for (int i=0;i<(signed)x.length();i++) {
// cout << "sum= " << sum << endl;
// cout << "pow= " << pow << endl;
sum = sum + (x[i]-'a') * power;
power = power*26;
}
return sum;
}
This is wrong because it will cause an overflow so I have to do this equation Mod B (where B is the table size (997) and the string I am passing in is the letters a through p in order.
I found that these are the rules for mod B arithmetic:
x + y Mod B = ((x Mod B) + (y Mod B)) Mod B
x * y Mod B = ((x Mod B) * (y Mod B)) Mod B
Here was my attempt that was not giving the correct answer (28).
int universalHash(const string &x,int B) {
long long sum;
long long pow;
sum=0;
pow = 1;
for (int i=0;i<(signed)x.length();i++) {
cout << "sum= " << sum << endl;
cout << "pow= " << pow << endl;
sum += (((x[i]-'a')%B) * (pow%B))%B;
pow = ((pow%B)*(26%B));
}
return sum;
}