追溯数学原理，探求高效编程的奥秘
STL之父Alexander A. Stepanov力作，Amazon广泛好评

这是一本内容丰富而又通俗易懂的书籍，由优秀的软件设计师 Alexander A. Stepanov 与其同事 Daniel E. Rose 所撰写。作者在书中解释泛型编程的原则及其所依据的抽象数学概念，以帮助你写出简洁而强大的代码。
只要你对编程相当熟悉，并且擅长逻辑思考，那么就可以顺利阅读本书。Stepanov 与 Rose 会清晰地讲解相关的抽象代数及数论知识。他们首先解释数学家想要解决的问题，然后告诉大家如何把这些数学解法转化为泛型编程算法，并编写出高效而优雅的代码。为了演示数学原理在当前许多领域之中的运用，作者会以相关的数学结论及泛型算法来实现一套实用的公钥加密系统。
在阅读本书的过程中，你将掌握高效编程的思路，并学会怎样在保持效率的前提下，对适用范围较窄的算法做推广。这可以让你深刻地领悟到：数学与编程相结合有着什么样的意义。无论采用何种编程语言与编程范式，数学思想都能给编程工作带来巨大的价值。

通过阅读本书，你将学到：
怎样对一种拥有四千年历史的算法做推广，在推广过程中如何保持算法的清晰与高效
经典的难题、美妙的定理，以及连续和离散之间那种健康的张力
一种寻找最大公约数（GCD）的简单算法，以及对该算法所做的现代抽象
强大的抽象数学方法
抽象代数怎样给泛型编程提供核心思路
怎样通过公理、证明、理论以及模型等数学技巧，来整理算法及数据结构方面的知识
看似简单的编程任务里面，隐藏着哪些出人意料的问题，我们可以从中获得什么样的经验
如何对理论知识做实际的运用

作者简介
Alexander A. Stepanov　从1972年开始编程，1977年由苏联移民美国之后，继续从事编程工作。他编写过操作系统、编程工具、编译器与各种程序库，其对编程基础的研究工作先后得到了通用电气（GE）、纽约理工大学（Polytechnic University）、贝尔实验室（Bell Labs）、惠普（HP）、SGI 及 Adobe 的支持，2009年Amazon 旗下的搜索技术公司 A9.com 开始支持这项工作。1995年他因C++标准模板库的设计，获得了《Dr. Dobb’s Journal》的程序设计杰出贡献奖（Excellence in Programming Award）。

Daniel E. Rose　是一位研究科学家，曾在 Apple、AltaVista、Xigo、Yahoo 及 A9.com 从事管理工作。他广泛地研究搜索技术，关注针对索引压缩的底层算法，以及 Web 搜索中的人机交互等问题。Rose 曾在 Apple 公司带领团队创建了Macintosh的桌面搜索机制。

要想成为优秀的程序员，就必须理解泛型编程的原则；要想理解泛型编程的原则，就必须学会抽象；要想学会抽象，就必须知道它所依据的数学基础。本书将编程和数学有机地结合在一起，从历史的角度来追溯数学原理，将对泛型编程有益的思维与技术提炼成许多条原则，并通过严谨的数学证明，培养你的逻辑推理能力，同时，通过简明的学者传记和有趣的实例，帮助你了解数学史及计算机技术的发展脉络，掌握高效编程的思路，提高编程效率。
本书共14章。第1章作为引言，简要介绍全书内容；第2章介绍一种古老的乘法算法，以及该算法的改进方式；第3章初步介绍数字的一些性质并给出一种寻找素数的高效算法；第4章介绍寻找最大公约数的算法；第5章介绍一些重要的数学定理；第6章介绍抽象代数；第7章讲解如何泛化乘法算法；第8章介绍一些新的抽象数学结构，并讲解怎样运用这些结构来解决一些新的问题；第9章介绍泛型编程的基础组成部分，即公理系统、定理和模型；第10章介绍泛型编程中的概念，并展示一些看似简单的编程任务中所蕴含着的微妙问题；第11章继续研究一些基本的编程任务，并介绍如何运用与该问题相关的理论知识实现各种实用算法；第12章讲解硬件方面的限制怎样促使旧算法演化出新版本，并针对GCD展示一些新的运用方式；第13章介绍如何将数学结论和算法成果结合在一起应用于密码学；第14章总结本书提到的一些基本观念。

计算机\程序设计

这是一本内容丰富而又通俗易懂的书籍，由优秀的软件设计师 Alexander Stepanov 与其同事 Daniel Rose 所撰写。作者在书中解释泛型编程的原则，及其所依据的抽象数学概念，以帮助你写出简洁而强大的代码。

　　只要你对编程相当熟悉，并且擅长逻辑思考，那么就可以顺利阅读本书。Stepanov 与 Rose 会清晰地讲解相关的抽象代数及数论知识。他们首先解释数学家想要解决的问题，然后告诉大家如何把这些数学解法转化为泛型编程算法，并编写出高效而优雅的代码。为了演示数学原则在当前许多领域之中的运用，作者会以相关的数学结论及泛型算法来实现一套实用的公钥加密系统。

　　在阅读本书的过程中，你将掌握高效编程的思路，并学会怎样在保持效率的前提下，对适用范围较窄的算法做推广。这可以令读者深刻地领悟到：数学与编程相结合有着什么样的意义。无论采用何种编程语言与编程范式，数学思想都能给编程工作带来巨大的价值。

本书主要内容：

■怎样对一种拥有四千年历史的算法做推广，在推广过程中如何保持算法的清晰与高效

■经典的难题、美妙的定理，以及连续和离散之间那种健康的张力

■一种寻找最大公约数（GCD）的简单算法，以及对该算法所做的现代抽象

■强大的抽象数学方法

■抽象代数怎样给泛型编程提供核心思路

■怎样通过公理、证明、理论以及模型等数学技巧，来整理算法及数据结构方面的知识

■看似简单的编程任务里面，隐藏着哪些出人意料的问题，我们可以从中获得什么样的经验

■如何对理论知识做实际的运用

[美]　亚历山大 A. 斯捷潘诺夫(Alexander A. Stepanov)　丹尼尔 E.罗斯（Daniel E. Rose）著：暂无相关简介

爱飞翔　译：暂无简介

本书是从数学到泛型编程的一次精彩之旅。
书中讲解了与乘法、素数及最大公约数有关的古老算法，并展示了历代数学家对这些算法所做的探索。他们既想对求解的方法做推广，以扩大其适用范围，又想对计算的步骤做简化，以提升其运算效率。
就前一方面来看，近代数学的发展（尤其是数论与抽象代数这两个分支）为算法的推广提供了很大的帮助。数论令人更加深刻地了解到数字中的奥妙，并给高速计算提供了灵感，而抽象代数则使得那些本来只能处理整数的算法，逐渐变得可以处理分数、实数、复数，乃至多项式。这种泛化还发生在数据之间的运算上面，比方说，通过连加可以实现求积，然而如果把其中的运算由加法换为乘法，那么效果就会从求积变成求幂。
就后一方面来看，计算机的出现使得算法的效率有了很大的提升空间。我们可以根据运算步骤及数据所具备的特征来发挥电脑硬件与软件所拥有的特性。
作为全书主题的泛型编程体现了上述两个方面的融合。它既借鉴了数学中的抽象思维及知识整理办法，又利用了计算机编程语言所提供的泛型与优化机制。这使得某些因实际问题而起的原始算法，在经过千百年的深化和抽象之后，终于可以变得更加普适、更加高效。
作者把这些对泛型编程有益的思维与技术提炼成许多条原则，并通过严谨的数学证明来培养读者的逻辑推理能力。此外，书中还有几篇简明的学者传记，使大家能够了解数学史及计算机技术的发展脉络。将这些内容与公钥加密系统等有趣的实例结合起来，可以指导我们把数学知识更好地转化为泛型编程的成果。
在翻译过程中，我得到了机械工业出版社华章分社诸位工作人员的帮助，在此深表谢意。
由于译者水平有限，书中难免出现错误与疏漏之处，请大家发邮件至eastarstormlee@gmail.com，或访问 github.com/jeffreybaoshenlee/fm2gp-errata/issues 留言，给我以批评和指教。

爱飞翔
2017年4月

译者序
致谢
作者简介
作者附言
第1章　内容提要　1
1.1　编程与数学　1
1.2　从历史的角度来讲解　2
1.3　阅读准备　3
1.4　各章概述　3
第2章　算法初谈　5
2.1　埃及乘法算法　6
2.2　改进该算法　9
2.3　本章要点　12
第3章　古希腊的数论　13
3.1　整数的几何属性　13
3.2　筛选素数　15
3.3　实现该算法并优化其代码　18
3.4　完美数　23
3.5　毕达哥拉斯学派的构想　26
3.6　毕氏构想中的严重缺陷　28
3.7　本章要点　31
第4章　欧几里得算法　33
4.1　雅典与亚历山大　33
4.2　欧几里得的最大公度量算法　36
4.3　缺乏数学成就的一千年　40
4.4　奇怪的0　42
4.5　求余及求商算法　44
4.6　用同一份代码来实现求余及求商　47
4.7　对最大公约数算法进行验证　49
4.8　本章要点　51
第5章　现代数论的兴起　52
5.1　梅森素数与费马素数　52
5.2　费马小定理　57
5.3　消去　59
5.4　证明费马小定理　63
5.5　欧拉定理　65
5.6　模运算的应用　69
5.7　本章要点　69
第6章　数学中的抽象　71
6.1　群　71
6.2　幺半群与半群　74
6.3　与群有关的定理　77
6.4　子群及循环群　80
6.5　拉格朗日定理　82
6.6　理论与模型　86
6.7　举例说明范畴理论与非范畴理论　89
6.8　本章要点　92
第7章　推导泛型算法　94
7.1　厘清算法所应满足的要求　94
7.2　对模板参数A提出要求　95
7.3　对模板参数N提出要求　98
7.4　提出新的要求　100
7.5　将乘法算法改编为幂算法　102
7.6　对运算本身加以泛化　103
7.7　计算斐波那契数　106
7.8　本章要点　109
第8章　更多代数结构　110
8.1　斯蒂文、多项式及最大公约数　110
8.2　哥廷根与德国数学　115
8.3　埃米·诺特与抽象代数的诞生　120
8.4　环　121
8.5　矩阵乘法与半环　124
8.6　半环的运用：社交网络与最短路径　125
8.7　欧几里得整环　127
8.8　域及其他的代数结构　128
8.9　本章要点　129
第9章　整理数学知识　132
9.1　证明　132
9.2　数学史上的第一个定理　135
9.3　欧几里得与公理化方法　137
9.4　与欧氏几何并立的其他几何学　139
9.5　希尔伯特的形式化方法　141
9.6　皮亚诺与他的公理　144
9.7　用皮亚诺公理来构建算术体系　147
9.8　本章要点　149
第10章　编程的基本概念　150
10.1　亚里士多德与抽象　150
10.2　值与类型　152
10.3　concept　153
10.4　迭代器　156
10.5　迭代器的种类、所支持的操作及所具备的特性　157
10.6　区间　160
10.7　线性搜索　162
10.8　二分搜索　163
10.9　本章要点　167
第11章　置换算法　169
11.1　置换与换位　169
11.2　交换两个区间内的元素　172
11.3　旋转　175
11.4　利用循环来执行旋转　178
11.5　倒置　182
11.6　空间复杂度　186
11.7　内存自适应算法　187
11.8　本章要点　188
第12章　再论最大公约数算法　189
12.1　硬件的限制催生出更为高效的算法　189
12.2　Stein 算法的推广　192
12.3　贝祖等式　194
12.4　扩展最大公约数算法　198
12.5　最大公约数算法的运用　202
12.6　本章要点　203
第13章　实际运用　204
13.1　密码学　204
13.2　素数测试　206
13.3　米勒–拉宾素数测试　209
13.4　RSA算法的步骤及原理　211
13.5　本章要点　214
第14章　全书总结　215
延伸阅读　217
附录A　记法　222
附录B　常用的证明办法　225
附录C　写给非 C++ 程序员看的C++ 知识　228
参考文献　237
中英文词汇对照表　241