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;
}
This article has been dead for over six months. Start a new discussion instead.