诡秘深奥的现代魔法 1.2 下

这个系列好久没写了,刚刚依靠光速浏览看到了第三章的结尾,于是回顾以前的章节开始认认真真读第二遍了。看以前的写的内容感觉就像习题解答一样无趣,于是多一点理解少一点习题,有趣的习题当然还是要写的,没写出来的习题也应该在这个仓库里面,如果没有的话大概是我不会做。

1.2 过程与它们所产生的计算

1.2.4  求幂

这里介绍了求幂的一种\Theta(\log(n))时间界。特别舒爽。下面的习题里面的迭代计算过程的求幂比较简单,后面的练习 1.17 也没什么难点。

对数步骤的求幂已经很让人奇异了,下面还有对数步骤的斐波那契数。

练习 1.19

这一题别看说什么变换族,什么让你证明,实际上挺容易的。

a\leftarrow bq+aq+ap
b\leftarrow bp+aq
.

根据题意,只要再推一下 b 就可以得出新的 p 和 q 了。

b\leftarrow (bp+aq)p+(bq+aq+ap)q
.

最后得出

p'=p^2+q^2\\q'=2pq+q^2
.

用 a 代入没错。

我们来看看这个变换具体是怎么工作能不断规约的,类似之前的求幂过程,不过感觉从右往左看更好理解。

我数学弱,符号不知道用得对不对。

T_{pq}^6 \leftrightarrow T_{p_{2}q_{2}}^3 \leftrightarrow T_{p_{2}q_{2}}(T_{p_{2}q_{2}}^2) \leftrightarrow T_{p_{2}q_{2}}T_{p_{3}q_{3}}

1.2.5 最大公约数 1.2.6 素数监测

这两小节给出了两个数学函数的实现,但是没有多少新知识,习题挺麻烦的,有些还没有做。

书上关于费马小定理的描述纯粹是用嘴说公式,直接给公式反而还好看些(P34)。

a^{n} \equiv a \pmod{n}
.

另外这个看公式就能知道,这个方法会有很大的运算,所以如果用C之类的语言基本上必须解决精度问题。(update: 实际上即使是无限精度的语言在验证大素数的时候如果要硬来也是作死的,有专门的幂取余算法。)

总结

1.2 小节的标题是过程与它们所产生的计算,实际上就是在教我们递归,如何用递归的思维来解决问题(找零钱等等),用递归有什么后果,比如说递归的计算过程是如何展开的(递归计算过程和迭代计算过程)。

大家都知道,Lisp 是不递归不死星人写的。递归真的是很有力的武器,仔细想想所谓的栈、树、剪枝等等,从递归的角度来看只不过是再简单不过的计算过程,因为递归函数的计算过程本身就是树,剪枝无非就是函数返回而已。

递归的本质很简单,就是缩小问题的规模知道能简单的求解。这种规约的方法是很自然的:理解一个亿就必须拆分成十个百万,理解百万就必须拆分成十个十万……直到将问题简华成“十”,这时候就不需要答案了,你的小伙伴:双手就能给你答案。学数学的时候也是,三角形就是正方形的一般所以面积要除以二……整个数学就是这样建立起来的。

虽然可能迭代速度更快更好(毕竟很多语言不支持尾递归优化),但是正如过早优化是万恶之源所说,过早关注性能同样也不是可取的吧。或许程序员在以命令式编程的时候已经熟悉了迭代,但毕竟是机器的语言。当然并不是说迭代一文不值,而是并不是像现在这样几乎一切都用迭代,比如说“山上有个庙……”是循环输出这个字符串呢,还是作为一个函数在最后调用自己呢?实际上后者更为贴近本质;而如果是轮子转动,太阳升起落下,当然本质上就是迭代的范畴的事情就用迭代干。

诡秘深奥的现代魔法 1.2 下》上有2条评论

  1. Pingback引用通告: 诡秘深奥的现代魔法 – SICP 读书笔记 0 | 蛋炒饭

发表评论

电子邮件地址不会被公开。 必填项已用*标注