We’re all familiar with residuals, and there are many, many examples of residuals in our lives.
For example, if today is Wednesday, and you want to know the day of the week 100 days from now, you can divide 100 by 7 (because there are 7 days in a week), then add 1 to today, and you know that 100 days from now is Thursday.
For example, if you have 11 apples and eat 3 apples a day, how many days can you eat them? You can divide 11 by 3, you get 3, you have a remainder of 2, so you can eat it for four days, which is 3+1 = 4, and you end up with an extra remainder, like we didn’t have three apples on the last day.
As another programming example, the concept of paging is often used in lists. If YOU were to show 923 pieces of data, 10 per page, how would you calculate the total number of pages? I think you take 923 and divide it by 10, and you get 920 with a remainder of 3, so your total number of pages is 920+1=923.
After looking at these three examples, have you noticed the rule that the remainder is always in a fixed range?
If you take any integer and divide it by 7, the remainder must be somewhere between 0 and 6. So when we know today is Monday, isn’t it amazing that we can know what day of the week the 10,000th, 100,000th day after today is?
Integers have no bounds, but the remainder can be kept within certain bounds by some relation. From a week point of view, no matter what day you are on, it falls somewhere between Monday and Sunday.
Take the example from last week. If today is Monday, how many weeks will there be in the 100 days from today? If you take 100 and divide it by 7, you get 14 with a remainder of 2, which means there are 14 weeks out of 100 with 2 more days. To put it another way, we could say that in those 100 days, your first day, your eighth day, your 15th day, and so on, are all considered the same day in the world of remainder, because they all have a remainder of 1, and they’re all Mondays. Similarly, day 2, day 9, day 16 all have a remainder of 2, and they’re all Tuesday.
Because these numbers have the same remainder, they’re all grouped together, and this is called the congruence theorem, which says that if two integers A and b have the same remainder divided by a positive integer m, we can say that a and B are congruent to module m.
In fact, the odd and even numbers that we often talk about are actually an application of the same cotheorem. Of course, in this application, the magnitude of this is 2, 2 divided by 2 has a remainder of 0, so it’s even; 3 divided by 2 has a remainder of 1, so it’s odd. 2 and 4 have a remainder of 0 divided by 2, so they’re both in the same category. They’re both even. 3 and 5 divided by 2 have a remainder of 1, so they’re both in the same category, they’re both odd. We have infinitely many integers, so how can we manage them comprehensively and multi-dimensionally? The congruence theorem is actually for classification.
So no matter what your modulus is, you’re going to end up with a remainder in the same range. Let’s say we divide the top by 7 to get the day of the week; We divide by 2, we get odd even. So in this way, we can divide infinitely many integers into finitely many classes.
This, in our computers, is very useful. You’re probably familiar with hashes. In every programming language, there are Hash functions. Hashing is also sometimes translated as hashing. In simple terms, it is the compression of an input of any length into an output of a fixed length through hashing. It’s essentially what you do by taking remainder, okay?
Here’s a practical example, using data access as an example:
If you want to read and write a million data records quickly, the ideal situation for high-speed access is of course to create a contiguous space to store the data, thus reducing addressing time. However, due to constraints, we do not have a contiguous address space that can accommodate 1 million records. What should we do?
See if the system can provide several small contiguous Spaces, each of which can hold a certain number of records. For example, if we find 100 small contiguous Spaces, that is, these Spaces are separated from each other, but are contiguous inside and large enough to hold 10,000 records continuously, then we can use the remainder and the homology theorem to design a hash function and realize the structure of hash table.
Consider the following formula:
In this formula, x represents the number waiting to be converted, size represents the size of the finite 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 decide where to store your data.
We can specify which space to store a record in by recording the remainder of the label module 100. Suppose you have two records with record labels 1 and 101. So let’s put all of these modules that have remainder 1 after 100 into the first available space. In the same way, put 2, 102, 202, etc. with remainder of 2 into the second available space, and put 100, 200, 300, etc. into the 100th available space.
In this way, we can group the data and store them in different address Spaces according to the rapid numerical changes of the remainder. The remainder itself is so simple that it adds little to the addressing time.
In addition, in order to increase the randomness of the data hash, we can also add a large random number MAX into the formula. Suppose that the random number MAX is 590199, then we recalculate the record marked 1, and the final calculation result is 0, while for the record marked 101, If the random number MAX is 627901, the corresponding result should be 2. In this way, the two records that were previously allocated to space 1 will be allocated to different available space under the new calculation formula. The formula above can be written as follows:
When MAX is used, records assigned to the same space are more “random” and more suitable for applications that require data reshuffling, such as encryption algorithms, data distribution in MapReduce, and high-speed query and location of records.
Taking encryption algorithm as an example, introducing MAX random number can enhance the security of encryption algorithm. For example, if we want to encrypt a set of three digits, let’s set an encryption rule like this:
- First add a large random number to each three-digit digit number, ten and hundreds.
- Then divide each digit by 7, replacing the remaining digit with the remainder.
- Finally swap the first and third digits.
Let’s say we want to encrypt the number 625, so let’s try that. Let’s say I choose 590127 for my random number. The hundred, ten, and ones bits add this random number, and you get 590133,590129,590132. And then you divide each of these by 7 and you get 5,1,4. Finally, we get the encrypted number 415. Because the encrypter knows the encryption rules, the divisor 7 used for the remainder, the quotient of the division, and the random number 590127 introduced, the encrypter can calculate the original data 625 when he gets 415.
So now that we have the remainder, is it interesting to have a new understanding of it?
The above articles refer to the Geek Time course, for learning purposes, and for those who are interested, check out portal