World's most popular travel blog for travel bloggers.

[Solved]: conversion to base-R numbers

, , No Comments
Problem Detail: 

I am reading Algorithms 4th edition by Robert Sedgewick and am stumped at a particular problem. On page 460 of the book the author is describing a technique to hash strings and use prime numbers for modular hashing. Starting from the fourth line:

 If R is greater than any character value, this computation would  be equivalent to treating the String as an N-digit base-R integer,   computing the remainder that results when dividing that number by M. 

Where the algorithm being used to hash a N-character long String is:

int hash = 0; for (int i = 0; i < s.length(); i++)    hash = (R * hash + s.charAt(i)) % M; 

How does the above algorithm result in a base-R integer?

Here M and R are integers (random) and s is the string of length N.

I am assuming that by the 'above computation' the author means the computation within the parentheses => R*hash + s.charAt(i)

Asked By : Deepak

Answered By : Deepak

The iteration results in :

(R^2*C + R^1*B + R^0*A + some constant)mod(M) for the string ABC, the value inside the brackets is a base 16 representation of CBA plus some constant value.

Best Answer from StackOverflow

Question Source : http://cs.stackexchange.com/questions/37194

3.2K people like this

 Download Related Notes/Documents

0 comments:

Post a Comment

Let us know your responses and feedback