The previous section on math notes for programmers 1– Base conversion is an introduction to base, especially conversion between decimal and binary, shift operations, and logical operations.

Today we are going to talk about the remainder. After reading this note, you will find that there are many things in life that have the shadow of the remainder.

remainder

Properties of remainder

An integer has no boundary, it could be plus infinity or minus infinity.

But the remainder is always within a fixed range. ** If the divisor is m, then the remainder ranges from 0 to (m-1).

In life, the remainder can be used to calculate the week, and in Web programming it can be used for pagination.

With Chinese remainder theory

If two integers a and b have the same remainder by dividing them by a positive integer m, we can say that a and B are congruent to module m.

The congruence theorem can be used for classification, or equipartition operations. Because you can divide the remainder of the same positive integer m into the same class.

The hash function

Every programming language has its own hash function, which is sometimes translated as a hash. ** It refers to the compression of an input of any length into a fixed length output by a hash algorithm. ** This is just a process of taking the remainder.

For example, if you have a million data records and want to access them at high speed, the ideal situation is to create a contiguous space to store the data and reduce the addressing time, but many times this is not possible. At this point we can examine whether the system can provide several small contiguous Spaces, each space can hold a certain number of records. For example, find 100 small contiguous Spaces, each of which can hold 10,000 pieces of data. Then we can use the remainder and the congruence theorem to design a hash function, and realize the structure of the hash table.

This function could look like this:

f(x) = x mod size
Copy the code

X represents the number waiting to be converted, size represents the amount of limited storage space, and mod represents the mod operation. With the remainder, you can convert any number into a finite range of numbers, and then use that new number to determine where to store the data.

In our example, size=100, then for the two data with record labels 1 and 101, the remainder obtained is 1 according to the above formula, then they will be divided into the same storage space.

The advantage of this approach is not only to set a rule for storing categories, but also to make residuals easy and fast without increasing addressing time.

Further, if you want to increase the randomness of the data hash, you can add a large random number MAX, as shown below:

f(x) = (x + MAX) mod size
Copy the code

For example, for the record labeled 1, the random number is 590199, then the result of calculation is 0, and for the record labeled 101, the random number becomes 627901, corresponding to the remainder is 2. Thus, under the new calculation formula, the two records are allocated to different storage space.

This approach is better suited for applications where data is reshuffled, such as encryption algorithms, data distribution in MapReduce, and high-speed query and location of records.

For example, for an encryption algorithm, if we want to encrypt a set of three digits, let’s set an encryption rule like this:

  1. First add a large random number to each three-digit digit number, ten and hundreds.
  2. Then divide each digit by 7, replacing the original three-digit number with the remainder.
  3. Finally swap the first and third digits.

This is a basic encryption transformation process.

For example, if the number 625 is encrypted, 590127 is used as the random number according to the rules just mentioned. The 100, 10 and ones digits are added to the random number respectively, and the results are 590133, 590129 and 590132 respectively. Then divide by 7 respectively, and the remainder is 5,1,4 respectively. And then you swap and you get 415. If decryption is required, because the encryptor will know the encryption rules, the random number and the divisor 7 used in the remainder operation, and the quotient in the remainder operation, it can be decrypted and restored to the original number.

More examples of applications using remainder and remainder operations:

  • Tail restrictions
  • Maximum common divisor, modular power operation (DES, AES, RSA), Caesar code, Sun Tzu theorem
  • Conversion of base, should say decimal conversion to other base is a circular operation

Do you have any other applications in mind for the remainder?

Can leave a message to reply, and I carry on the communication!

Welcome to follow my wechat official account – Machine Learning and Computer Vision, or scan the qr code below, we can communicate, learn and progress together!