DaniWeb Forum Index > Software Development > C++

C++ RSS

Arithmetic Overflow problem when hashing

Please support our C++ advertiser: Intel Parallel Studio Home

•

Join Date: Apr 2007

Posts: 110

Reputation: kylcrow is an unknown quantity at this point

Solved Threads: 2

kylcrow

Offline

Junior Poster

Arithmetic Overflow problem when hashing

May 29th, 2009

Hey guys, I am having issues understanding how exactly to mod something to avoid overflow.

say i have this hash function:

 Help with Code Tags 
 c++ Syntax (Toggle Plain Text) 
        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;
}
        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).

 Help with Code Tags 
 c++ Syntax (Toggle Plain Text) 
       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;
}
       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;
}

•

Join Date: Jul 2008

Posts: 2,001

Reputation: ArkM has much to be proud of

Solved Threads: 343

ArkM

Offline

Postaholic

Re: Arithmetic Overflow problem when hashing

May 29th, 2009

If you want to obtain hash index in a table of size B, don't forget:
1. Make unsigned int calculations ( x[i]-a is signed value).
2. Result is sum % B.
3. As usually, no need to avoid integer overflow.
May be better don't invent a square wheel?
Are you familiar with http://www.partow.net/programming/hashfunctions/?