conversion to base-R numbers
-
01-11-2019 - |
Question
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)
No correct solution
Licensed under: CC-BY-SA with attribution
Not affiliated with cs.stackexchange