Java教程

7.22日算法日记

本文主要是介绍7.22日算法日记,对大家解决编程问题具有一定的参考价值,需要的程序猿们随着小编来一起学习吧!

引言

我发现如果先自学一遍,然后再写的话记录一个知识点要花费两倍的时间,考虑到中间的损耗,实际要做出一个根据自己理解的文章至少要两天,因此我在想不如和学图形学时一样将日记当作笔记,边学边记,认为简单的就大概记录一下即可。以前笔记记得就很简略,不知为何现在写的却很多(自我感受),发扬一下古风吧。

内容

先记录今天的内容。当然,今天还是要把之前的补一下,FFT与笛卡尔树。

然后在写的时候我发现:FFT和PR有一定的思维共同性,恰好放在一起恐怕也是上天的选择(之类的

Pollard-Rho算法

是一种能快速找到大整数非1与自身的算法。

先把费马小定理放这里:

对于素数p,若a不是p的倍数,有a^{p-1}\equiv 1\qquad(mod \quad p)

不证,有兴趣自己查阅相关资料。满足费马小定理的合数称为费马伪素数。

由此得到费马素性检验方法:

1、随机生成检验子

2、快速幂检测是否符合费马小定理

3、返回结论(时间复杂度为O(klongn)

然而这种方法在int32内尚可接受,但到了int64,误差增加(由于指数原因,而检验方法为线性

因此得出改进算法:米勒-拉宾素性检验

---

我们发现一个规律:

任何一个素数p,都可以将2^{p-1}表示为2^{2^{r}d}的形式,即使是1和2,也能用d来进行控制。

因此,我们考虑当p为素数时,2^{d},2^{2d},2^{2^{2}d}...这些数的性质。

考虑到2^{2^{r}d}本身与1同余,1与任何数之间都互质且为质数,根据二次剩余的欧拉准则:

当p为奇素数且ap互质时,由费马小定理得到a^{p-1}\equiv 1\qquad(mod \quad p),记q=2p+1,得:

a^{2q}\equiv1(mod \quad p),易得a^{q}\equiv\pm 1(mod \quad p),也即:a^{\frac{p-1}{2}}\equiv\pm1(mod \quad p)

因此知:从现态向前,必满足2^{2^{r}d}\equiv1(mod \quad p)直到存在某个r使得其与-1同余或r为0为止。

反向得知:如果满足此条件,则大概率为素数。也就是在费马素性检验中加上了向前验证的部分,根据概率学,这大大提高了精准度(虽然依旧是线性的优化),但我们可以将精确度提高到int64。

Jim Sinclair发现一组int64内绝不出错的检验数字:{2, 325, 9375, 28178, 450775, 9780504, 1795265022},用此做a可保证正确性。(复杂度为O(klog n)

PR算法推理:

OK,我们速成了一下基础知识,引入上述内容的目的在于令大zi家ji对素数有个大致的认识,接下来来继续推PR算法吧。

一般来说,想要找到第一个可除因子,最简单的就是遍历,最多判断一下是否为质数,复杂度最多为O(\sqrt{n}),不提。

另一种被提到的算法(不是去查阅一般不会用的)就是生成随机数去作为除子,emm,复杂度为O(n),不吐槽了。

但随机算法可以通过最大公约数(gcd)算法,也就是用gcd来寻找因子的方法将最差复杂度变为O(\sqrt{n}logn),尽管这依旧比第一个算法复杂,我们可以继续想办法。

我们思考n的情况,n在最糟的情况下应该为某个质数p的平方,也就是说在[1, n]的范围内,只有这个p一个因子,然后在取gcd时,x取0到p-1,从p到(p-1)p都有gcd(xp,n)=p>1的情况,这个数据当然有\sqrt{n}个,这就是他的来源。

---

 根据生日悖论,如在[1, N]范围内生成随机数,则证明得遇到第一个重复的数字前的期望为\sqrt{\frac{\pi N}{2}}个数(基础不牢的证明一定要看看,里面有很多常用基础知识。

那末,如果在[1, n-1]间不断生成随机数,也就是说在大概\sqrt{p}=n^{\frac{1}{4}}个数(p同上)时有模p相同的数,他们的差d就能被p整除,所以这个d一定有n的系数,gcd(d,n)>1。

我思考了一下,这似乎很厉害,但没什么意义,因为不知道到底是哪两个数一样,如果要去寻找相关数据,则要至少花费p\sqrt{n}的时间来进行寻找,而且不一定能找到,也就是说每次都要加入后进行一次比对。

---

虽然不清楚怎么找到的这个公式,但Pollard用了一种随机数生成算法:

f(x)=(x^2+c)\quad mod\quad N

每次取:

x, f(x), f(f(x))

依次类推,作为随机值。

而由于生日悖论,迟早会有一个值与之前的值相同,算法又依赖于前面得到的值,所以算法迟早会进入一个循环。因此被称为ρ(rho)算法。判环我们都知道用Floyd算法即可(快慢)。

而Pollard要求:如果在出现环之后还没有找到答案,就换个c重新生成随机数。

也就是gcd(|t-r|, N)>1 \quad t=f(t),r=f(f(r))

这里我觉得就是玄幻,本质还是生成了个随机数进行运算,和第二种方法除了t-r之外没有任何区别,但是就是能大大加快速度。我不是很理解,因此我做出了一个假设,那就是:

分布问题

我们发现这其实是个统计问题(突然想到zkw的统计的力量),原来是个均匀分布生成的随机数据,我们可以假装[1, n-1]范围内都是1/n这样,然后互相相减后取模,就变成了...很遗憾,是一个极为离散的随机分布,但至少我们知道他不是一个均匀分布。因此我认为此法存在可行可能。

经过验证,在1e16范围内是可行的。而在4处需要特判,可以动手试试为什么。

参考:

算法学习笔记(55): Pollard-Rho算法 - 知乎 (zhihu.com)

Pollard Rho算法浅谈 - 会虎GreyTiger - 博客园 (cnblogs.com)

FFT

之前已经学过了,所以会说的比较简略,大家想学的话一定要动手跟着一步步证明,有一些比较好的参考资料,分享/记录一下。

关于离散傅里叶变换在卷积加速中的应用与优化的相关介绍。

可爱的例题

暂停

只是认为需要个分割,接下来的部分另外发一篇。

这篇关于7.22日算法日记的文章就介绍到这儿,希望我们推荐的文章对大家有所帮助,也希望大家多多支持为之网!