程序员的数学笔记2--余数

上一节程序员的数学笔记1--进制转换是介绍了进制，特别是十进制和二进制之间的转换，移位操作和逻辑操作。

今天介绍的是余数，看完本节笔记，你会发现生活中有很多东西都有余数的影子。

余数

余数的特性

整数是没有边界的，它可能是正无穷，也可能是负无穷。

但余数却总是在一个固定的范围内。假如除数是 m，那么余数的范围就是 0~(m-1)。

生活中，余数可以用来算星期，web 编程中可以用于分页。

同余定理

两个整数 a 和 b，如果它们除以正整数 m 得到的余数相等，我们就可以说 a 和 b 对于模 m 同余。

同余定理可以用来做分类，或者说是均分操作。因为可以将对同个正整数 m 相除得到的余数相等的分在同一个类中。

哈希函数

每个编程语言都有对应的哈希函数，哈希有时候也被翻译为散列，它是指将任意长度的输入，通过哈希算法压缩为某一固定长度的输出。这其实就是一个求余的过程。

例如，假设对于 100 万条数据记录，要做到高速存取，最理想情况是开辟一个连续的空间存放这些数据，减少寻址的时间，但很多时候条件并不允许。这个时候我们可以考察一下，系统是否可以提供若干个较小的连续空间，每个空间可以存放一定数量的记录。比如找到100个较小的连续空间，每个空间可以容纳 1 万条数据连续存放。那么我们可以采用余数和同余定理来设计一个散列函数，并实现哈希表的结构。

这个函数可以如下所示：

f(x) = x mod size

x表示等待被转换的数值，size表示有限存储空间的数量，mod表示取余操作。通过余数，你就能将任何数值，转换为有限范围内的一个数值，然后据这个新的数值，来确定将数据存放在何处。

而在我们这个例子中，size=100，那么对于记录标号分别是 1 和 101 的两条数据，根据上述公式进行取余操作，得到的余数都是 1，那么它们就会分到同一个存储的空间中。

这种的做法好处不仅是设定一个存放分类的规则，而且取余操作简单快速，不会增加寻址时间。

更进一步，如果想增加数据散列的随机程度，可以加入一个较大的随机数 MAX，如下所示：

f(x) = (x + MAX) mod size

比如对标号为 1 的记录，随机数是590199，那么计算结果是得到余数为 0，而标号为 101，随机数变成 627901，对应余数是 2。这样在新的计算公式下，这两个记录就分配到不同的存储空间了。

这种做法更适合需要将数据重新洗牌的应用场景，比如加密算法、MapReduce 中的数据分发、记录的高速查询和定位等。

举个例子，对于一个加密算法，如果我们要加密一组三位数，那我们设定一个这样的加密规则：

1. 先对每个三位数的个、十和百位数，都加上一个较大的随机数。
2. 然后将每位上的数字都除以 7，用所得到的余数代替原来的三位数；
3. 最后将第一位和第三位交换。

这就是一个基本的加密变换过程。

例如对数字 625 加密，根据刚刚的规则，随机数采用 590127，百、十和个位数都分别加上这个随机数，分别得到的是 590133、590129、590132，接着分别除以 7，得到的余数分别是 5,1,4，然后交换得到最终的结果是 415。而如果需要解密，因为加密的人会知道加密规则、随机数和求余所用的除数 7 以及求余操作中的商，就可以解密还原回原来的数字。

更多的采用余数和求余操作的应用例子：

• 尾号限行
• 最大公约数、模幂运算(DES、AES、RSA)，凯撒密码，孙子定理
• 进制的转换，应该说十进制转换成其他进制都是循环求余操作

关于余数的一些应用例子，你是否还想到其他的应用呢？

可以在后台回复，和我进行交流！

欢迎关注我的微信公众号--机器学习与计算机视觉，或者扫描下方的二维码，大家一起交流，学习和进步！

如果你觉得我写得不错，可以给我点个好看哦！