程序员的数学笔记2余数

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

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

余数

余数的特性

整数是没有边界的&＃xff0c;它可能是正无穷&＃xff0c;也可能是负无穷。

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

生活中&＃xff0c;余数可以用来算星期&＃xff0c;web 编程中可以用于分页。

同余定理

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

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

哈希函数

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

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

这个函数可以如下所示&＃xff1a;

f(x) &＃61; x mod size


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

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

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

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

f(x) &＃61; (x &＃43; MAX) mod size


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

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

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

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

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

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

更多的采用余数和求余操作的应用例子&＃xff1a;

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

关于余数的一些应用例子&＃xff0c;你是否还想到其他的应用呢&＃xff1f;

可以留言回复&＃xff0c;和我进行交流&＃xff01;

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