HSC welcomes all external visitors to this site, especially students and members of the academic community. Please use the comments box at the bottom of each page to record any comments or suggestions for improvement.
Simple Hash Function (using mod operation and Horner's method):
Shown below is the implementation of a hash function using the Horner's method.
Note that the msisdn array passed as a parameter to the "findHash" function above is actually a large number and this number cannot be passed directly to the mathematical operands on the c language, so the trick is to pick some of the digits and perform operations on it and then in the next iteration, multiply by the size of the alphabet. For example in a decimal scheme (0..9) a number 123456 can be used in mathematical expressions as ((((1*10+2)*10+3)*10+4)*10+5)*10 +6 and operations like mathematical operators can be done on parts. The modulo fo a large number can be done in parts using the Horner's method as a mod b = ( (a - k1) mod k + k1) mod b.
Rolling Hash Function (using mod operation and Horner's method):
If you have large integer such as 11111111111112333333333455, and one desires to find hash values for each 4 digits one after another. The easiest was is to copy four digits into a smaller array and use the above hash function to generate a hash value, select next four and repeat. However, this method is inefficient in the sense that it "throws" away the previous hash value when finding the hash value of the next four digits (which differ from the previous four by only two digits - remove one and add another). For a still larger number say 1028 digits long and a hash for 50 digits at a time, the computation order is as follows:
979 positions where a 50 digit hash is to be computed
Each 50 digit has computation requires 49 remainder operations and additions.
So the time complexity of the scheme is 97900 operations!
If we can compute the 50 digit hash re-using the already
computed hash of the previous 50 digits in a lesser number
of steps, it can be a significant improvement over the above
mentioned complexity. See the lines 24-32 below using 5
operations (including pow) to find the hash (mod in this
case, for simplicity) of next n digits. The complexity
order is 979 positions * 5 (basic operations) + 100 (for
first hash computations of 50 digits). This computes to
~5000 computations, about 20 times lesser than the above
scheme.
The rolling Hash function is:
Views:
maintainer: rakesh.mawa@hsc.com
Comments
