« September 2021 | Main

October 23, 2021

米勒拉宾素数检验

今年 1024 程序员节公司搞活动,让我做一次分享。我在分享会上谈及程序优化时,说道优化算法减少时间复杂度的优化往往比优化代码本身更优化。举的一个例子就是检测一个整数是否是素数的问题。

米勒拉宾素数检验法比普通方法有数量级上的性能提高。当时我说道,这个算法的原理其实并不复杂,其证明过程有高中数学知识就可以理解,并不需要多深奥的数学知识。

会后,有同学提出了疑问。他怀疑一个高中生真的能看懂 wikipedia 上的解释 。仔细读了一遍后,我认为,对于中学生来说,难懂的可能只是其中的一些专有术语罢了,那些中学数学课本上没有引入。其内核还是挺好懂的。而且,这篇中文版写的(以及排版)不太好,远没有英文版清晰 。或许只要看英文版就立刻明白了。

我也许可以写一篇没那么多术语,但也不够严谨的解释。

说道素数检验法,最基本的方法就是按素数的定义,拿这个整数去除比它小的所有大于 2 的整数,看是否全部不能整除。当然,我们可以做一些明显的优化:只用去除比它平方根小的数字,如果可能,尽量选取素数(剔除明显不必测试的数字,比如偶数)。

再进一步,我们可以运用费马小定理:即,对于一个素数 p,取任何一个整数 a , a^p 对 p 取模一定为 a 。若 a 不是 p 的倍数的话,这等价于 a ^ (p-1) 对 p 取模为 1 。

这个定理有非常多的证明方法,用数学归纳法证明最容易理解 。这肯定没超过中学的数学知识。

我们可以采用费马小定理去测试一个数字是否为素数:任取整数 a ,测试 p 。如果 a ^ (p-1) 对 p 取模不为 1 ,那 p 就不是素数,反之,它有一定概率是一个素数。

如果我们不断的选择不同的 a 去测试 p ,只要有一个 a 能证明 p 不是素数它就不是,反之,测试的 a 越多,p 就越可能是素数。

如果 p 通过了费马小定理的检验,它是素数的概率不算特别高。如果我们能找到一个改进的算法,可以让概率提升会更好。 米勒拉宾素数检验法就是对费马小定理检验法的一个改进。它可以让一个合数更难通过检验,同时,特别适合计算机计算(单次检验的计算复杂度较费马小定理检验并没有太大的提升)。

这个算法可以这样表述:假设一个整数 p 是一个大于 2 的素数,那么 p - 1 就是一定是一个偶数,可以表示为 2^s * d 的形式,其中 d 为一个奇数。换句话说,我们可以把 p - 1 的 2 因子都提取出来。

此时,对于任何比 p 小的整数 a , 以下两个形式之一必然成立:

  1. a ^ d 对 p 取模为 1 。
  2. a ^ (2^r * d) 对 p 取模为 -1 。(r 为 0 到 s-1 之间的某个整数)

反之,如果 p 是一个合数,我们任取一个 a ,带入上面的式子去计算,一定全部不成立。若通过这一系列计算可以证明 p 是一个合数,就可以把 a 称为 p 是合数的一个凭证 (witness) 。若 a 不能证明 p 是一个合数,那么它就有极大概率是一个素数。

让我们随机选取 a ,多次检验 p ,要么很快的证明 p 是一个合数,要么知道 p 是素数的概率非常大。

虽然这是个随机化算法,但是如果 p 的范围有限,比如在计算机中一定能放入一个字长中,那么我们就能事先找到一组合适的 a ,100% 确定 p 是否是素数。

例如,如果 p 是一个 32 位整数,我们只要选取 { 2, 7, 61 } 三个凭据,依次测试 p ,如果 p 全部通过,就能确定 p 一定是素数;如果把 p 放宽到 64 位整数,则需要七个特定的数字。这一点一定能被证明(因为数字集是有限的)。

对于特定范围的整数,找到更合适的凭据集是个有意义的工作 。在这个网站上列出了目前的成果。

另外一个很容易想到的进一步优化是对需要检验的整数集做依次 hash ,散列到若干更小的集合中,对每个集合就只需要选取更少数量的凭据即可。例如,对于 32 bit 整数,我们用一个简单的 hash 算法,散列到 1024 个子集中,每个子集就只有 22bit 个整数,这样的集合只需要一次检验就够了。这方面的工作可见 https://www.techneon.com/


那么,如何证明呢?让我们从费马小定理开始。

如果 p 是一个素数,那么 a ^ (p-1) 对 p 取模就必定为 1 。(此处 a 不为 p 的倍数)

当 p 大于 2 时, p - 1 一定是一个偶数。所以,a ^ (p-1) 一定是一个完全平方数(有整数平方根)。假设它的平方根是 x 。那么, x * x 对 p 取模为 1 ,等价于 x * x - 1 可以被 p 整除。也可以写成 (x+1) (x -1) 可以被 p 整除。

如果 p 是素数,那么,p 就一定可以整除 x+1 或 x -1 两者其一。这就是欧几里得引理。证明很简单,这里就不展开了。注意:当 p 不是素数时,上面的结论是不成立的。比如当 p 等于 15 ,x 等于 4 的时候,p 可以整除 (x+1)(x-1) ,但即不可以整除 x+1 也不可以整除 x-1 。

这样,我们就可以推导出,x 对 p 取模,要么为 1 要么为 -1 (p-1) 。

当 p 是素数时,我们不断的对 a ^ (p-1) 取平方根后,对 p 取模,我们总会得到 1 或 -1 。如果我们得到 -1 , 那么前面的形式二就是成立的;反之,如果我们得到的不是 -1 ,那只能是 1 。这个迭代过程一直得到 1 的话,会一直把 2 这个因子完全除去,最终会满足形式一。

这个原理的逆反就是说,如果 p 是一个合数,以下两个形式必须全部成立:

  1. a ^ d 对 p 取模不等于 1 。
  2. a ^ (2^r * d) 对 p 取模不等于 -1 。(r 大于等于 0 且小于 s )

这就是 米勒拉宾素数检验 了。

October 12, 2021

球面地图网格的设计

最近几年有很多基于球体地图的游戏,包括今年颇有好评的戴森球计划。

大多数在球面打格子分割地图的游戏,会采用六边形网格。但是,只靠正六边形网格无法铺满整个球面。必然会留下 12 个五边形。因为用正六边形铺满球面时,其实是在尝试用正 20 面体逼近球体。如果我们将正 20 面体做平面展开,每个三角形面中划分多个正三角形,每 6 个三角形合成一个正六边形,但中间的 12 个交接点必然是 5 个三角形缝合。只要处理好这个五边形,尝试用六边形网格做游戏是个合适的选择。

据戴森球计划的开发日志所述,开发团队也曾考虑过六边形网格方案,后来觉得不合适又回归四边形。我猜想多少和戴森球计划参照的游戏原型异星工厂是四边形网格有点关系。我也觉得在四边形网格上设计这种传送带游戏更舒适。不过,相比目前戴森球计划中用的方案:从赤道到两极,沿着纬线圈一圈圈减少网格数量;我更喜欢网格能完全对齐的方案。

如果像戴森球计划那样,往高维铺建筑,能用的格子越来越少,就很难让建筑沿经线对齐。看起来不整洁,而且为这类自动化游戏中开展大规模生产必备的蓝图功能的实现制造不必要的麻烦。

让我们考虑回平面地图,考虑如何把一张地图映射回球面。像文明那样,我们可以让地图的东西循环相接。但这样的世界实际上是一个圆柱体。那么让南北也循环相接如何?那其实是个面包圈世界,远非球面。因为我们一直向北走,越过北极就突然来到了南极,未免和现实世界相差太远。

其实,除了上面所述用正 20 面体逼近球面外;我们还可以选择用正六面体。这在天文领域有非常成熟的方案:NASA 就用 COBE Quadrilateralized Spherical Cube 来绘制天体的地图。我们把整个球面划分为 6 个对等的区域,每个区域都用 n * n 的四边形网格即可。除了 8 个顶点附近少许网格的拓扑关系有些特殊外,其它均与普通的平面网格无异。

这里有一篇文章详细讲述了如何在球面实现这样的地图