墨西哥小旅游(二)
由于一些突发情况,我又需要去一趟墨西哥。
由于一些突发情况,我又需要去一趟墨西哥。
由于某些机缘巧合,我碰巧去了一趟墨西哥的 Monterrey,名字听起来和加州的 Monterey 很像……似乎这个城市看起来还行吧,有着墨西哥、南美最高楼。再加上 SIGYAO30'21 在 San Diego 举办,这样去墨西哥也很方便。
作为一个码农,我天天都在用终端,自然需要一个看着舒服用着顺手的终端。这次我就来介绍一下我用过的那些花里胡哨的东西……
\(\newcommand{\d}{\mathrm{d}}\)说到解析方法数质数,由于精度原因,如果要计算 \(\pi(10^{18})\) 的话,64 位浮点数已经不能满足要求了,所以我不得不实现自己的高精度。当然可以选用现成的库,例如著名的 MPFR,但是我觉得这样 overhead 太大了,毕竟我只需要 100 bit 就行了。
既然要实现浮点数,自然得实现一堆函数,其中有四个函数尤为重要:\(\exp, \log, \sin, \cos\)。当然,在实现之前,我们需要参考下别人的实现,例如 libm 。我们这里就拿 \(\exp\) 来举例,并假设我们现在已经支持基本的加减乘除了。
\(\newcommand{\floor}[1]{\left\lfloor #1 \right\rfloor}\)这里我讲讲如何用 Dirichlet series 求一些算术函数的前缀和。这个算法我是在 Project Euler 的论坛里看到的,Lucy_Hedgehog 的帖子。但是他(她?)写的比较粗略,我就稍微写详细一点吧……
\(\newcommand{\eps}{\epsilon} \newcommand{\tO}{\widetilde O} \newcommand{\d}{\mathrm d} \newcommand{\hphi}{\widehat \phi} \newcommand{\hPhi}{\widehat \Phi} \newcommand{\sinc}{\text{sinc}}\)上次我们讲了 [LO],[Galway] 和 [Platt] 的大致思路,似乎一切都已经明了,只剩下最后一个难点了:\(\zeta\) 函数怎么求?这里我们就来介绍一下我 survey 到的几种求 \(\zeta(s)\) 的方法。
\(\newcommand{\eps}{\epsilon} \newcommand{\tO}{\widetilde O} \newcommand{\d}{\mathrm d} \newcommand{\hphi}{\widehat \phi} \newcommand{\hPhi}{\widehat \Phi}\) 前一段时间某群里有人发了一个链接,说的是有人又整出一个新的算 \(M(x) = \sum\limits_{n=1}^x \mu(n)\) 的算法了,时间复杂度 \(\tO(x^{3/5})\),空间复杂度 \(\tO(x^{3/10})\)。然后有人提到目前最快的算 \(M(x)\) 的算法是用解析数论的方法,和 \(\pi(x)\) 类似,时间复杂度 \(\tO(x^{1/2})\),空间复杂度 \(\tO(x^{1/4})\) 。那几篇论文都是针对 \(\pi(x)\),然后说可以拓展到 \(M(x)\),我一时兴起就去学习了一下,整一点理性愉悦的东西。
在这个过程中,我读了好几篇 paper,有几篇没读懂,这里差不多就是对那几篇 paper 的 survey 吧……由于这个领域属于 analytic number theory,而我不懂复分析,所以……几乎所有核心定理的证明我都看不懂……所以由于个人能力原因,文章中可能存在不严谨的地方或者错误,大家意思意思一下吧 →_→
由于内容比较多,所以我可能会拆成好几篇文章来写(又可以水了呢 →_→)。
前一段时间又发现了一件好玩的事:折纸。我小时候就挺喜欢折纸的,不过做的东西比较基础,例如纸船、千纸鹤、青蛙。这次在家里又开始学习了折纸,做了一些简单有趣的小玩意。
之前写过一篇游戏,介绍了几个我认为很有艺术感的游戏,这次聊的游戏更注重解谜,基本上都是一个作为核心玩法的小 puzzle,外加一堆小扩展(是不是太笼统了 = =)。至于这个 puzzle 难度如何……嗯……