4.5 Applications of Congruences Flashcards
Hashing Functions:
Ideal hashing function?
How can memory locations be assigned so that customer records can be retrieved quickly? The
solution to this problem is to use a suitably chosen hashing function. Records are identified
using a key, which uniquely identifies each customer’s records. For instance, customer records
are often identified using the Social Security number of the customer as the key. A hashing
function h assigns memory location h(k) to the record that has k as its key.
In practice, many different hashing functions are used. One of the most common is the function :
h(k) = k mod m
m = number of available memory locations.
-Hashing functions should be easily evaluated so that files can be quickly located.
-Furthermore, the hashing function should be onto, so that all memory locations are possible.
Given func satisfies these.
What is one unwanted characterstic of hashing? and how to resolve?
Because a hashing function is not one-to-one (because there are more possible keys than
memory locations), more than one file may be assigned to a memory location. When this happens, we say that a collision occurs. One way to resolve a collision is to assign the first free
location following the occupied memory location assigned by the hashing function.
Linear Probing function:
In Example 1 we used a linear probing function, namely, h(k, i) = h(k) + i mod m, to look
for the first free memory location, where i runs from 0 to m − 1. There are many other ways to
resolve collisions.
Pseudorandom Numbers:
Randomly chosen numbers are often needed for computer simulations. Different methods have
been devised for generating numbers that have properties of randomly chosen numbers. Because
numbers generated by systematic methods are not truly random, they are called pseudorandom
numbers.
procedure for generating pseudorandom numbers:
Linear congruential method:
We choose four integers:
the modulus m, multiplier a,
increment c, and seed x0, with
2 ≤ a < m, 0 ≤ c < m, and 0 ≤ x0 < m.
We generate a sequence of pseudorandom numbers {xn}, with 0 ≤ xn < m for all n, by successively using the recursively defined function
xn+1 = (axn + c) mod m.
Example xn+1 = (7xn + 4) mod 9 with seed = 3, contains 9 diff numbers before repeating.
a pure multiplicative generator
A linear congruential generator with increment c = 0 is used.
For example, the pure multiplicative generator with modulus
2^31 − 1 and multiplier 7^5 = 16,807 is widely used. With these values, it can be shown that
2^31 −2 numbers are generated before repetition begins.
Analysis of this method:
A more superior method?
Pseudorandom numbers generated by linear congruential generators have long been used
for many tasks.
Unfortunately, it has been shown that sequences of pseudorandom numbers generated in this way do not share some important statistical properties that true random numbers
have.
Because of this, it is not advisable to use them for some tasks, such as large simulations.
For such sensitive tasks, other methods are used to produce sequences of pseudorandom numbers, either using some sort of algorithm or sampling numbers arising from a random physical
phenomenon.
Check bits in general:
Congruences are used to check for errors in digit strings. A common technique for detecting
errors in such strings is to add an extra digit at the end of the string. This final digit, or check digit,
is calculated using a particular function. Then, to determine whether a digit string is correct, a
check is made to see whether this final digit has the correct value.
Parity Check Bits:
what can it detect and what it can’t?
Digital information is represented by bit string, split into blocks of a specified size. Before each block is stored or transmitted, an extra bit, called a parity check bit, can
be appended to each block. The parity check bit xn+1 for the bit string x1x2 … xn is defined by
xn+1 = x1 + x2 + ⋯ + xn mod 2.
even 1s, xn+1 = 0
odd 1s, xn+1 = 1
I can detect odd number of errors, not even.
Universal Product Codes (UPCs)
UPCs Retail products are identified by their Universal Product Codes (UPCs). The most
common form of a UPC has 12 decimal digits: the first digit identifies the product category, the
next five digits identify the manufacturer, the following five identify the particular product, and
the last digit is a check digit. The check digit is determined by the congruence
3x1 + x2 + 3x3 + x4 + 3x5 + x6 + 3x7 + x8 + 3x9 + x10 + 3x11 + x12 ≡ 0 (mod 10).
International Standard Book Number (ISBN-10)
ISBNs All books are identified by an International Standard Book Number (ISBN-10), a
10-digit code x1x2 … x10, assigned by the publisher. (Recently, a 13-digit code known as ISBN-13 was introduced to identify a larger number of published works)
An ISBN-10 consists of blocks identifying the language,
the publisher, the number assigned to the book by its publishing company, and finally, a check
digit that is either a digit or the letter X (used to represent 10). This check digit is selected so
that
x10 ≡ ∑ 9 i=1 i.xi (mod 11),
or equivalently, so that
∑10 i=1 i.xi ≡ 0 (mod 11)
check digit of an ISBN-10 can be an X.
Several kinds of errors often arise in identification numbers, they are:
A single error, an error in one
digit of an identification number, is perhaps the most common type of error.
Another common
kind of error is a transposition error, which occurs when two digits are accidentally interchanged.
Can we detect single error in ISBN? Explain
Suppose that x1x2 … x10 is a valid ISBN (so that ∑10
i=1 xi ≡ 0 (mod 10)).
(where we include the possibility
that one of the two digits is the check digit X, representing 10).
Suppose that this ISBN has been
printed with a single error as y1y2 … y10. If there is a single error, then, for some integer j, yi = xi
for i ≠ j and yj = xj + a, where −10 ≤ a ≤ 10 and a ≠ 0. Note that a = yj − xj is the error in the
jth place. It then follows that
∑10 i=1 i.yi = (∑10 i=1 i.xi)+ ja ≡ ja ≢ 0 (mod 11).
These last two congruences hold because ∑10
i=1 xi ≡ 0 (mod 10) and 11̸| ja, because 11̸| j and
11 ̸| a. We conclude that y1y2 … y10 is not a valid ISBN. So, we have detected the single
error.
Detect transposition error in ISBN:
Now suppose that two unequal digits have been transposed. It follows that there are distinct
integers j and k such that yj = xk and yk = xj
, and yi = xi for i ≠ j and i ≠ k. Hence,
∑10 i=1 i.yi = (∑10 i=1 i.xi) + (jxk − jxj) + (kxj − kxk)
≡ (j − k)(xk − xj) ≢ 0 (mod 11),
because ∑10i=1 xi ≡ 0 (mod 10) and
11̸| (j − k) and 11̸| (xk − xj).
We see that y1y2 … y10 is not
a valid ISBN. Thus, we can detect the interchange of two unequal digits.
