我在网上浏览了《Concrete Maths》的内容。我至少听说过提到的大多数函数和技巧，但是有一个完整的特殊数字部分。这些数字包括斯特林数、欧拉数、调和数等等。现在我从未遇到过这些奇怪的数字。它们如何帮助计算问题？它们通常在哪里使用？
在《具体数学》中提到的“特殊数字”有哪些用途？
5
- unj2
3
与编程无关。 - Mitch Wheat
13我不同意-虽然“网页上的CRUD”人群比较庞大，但仍有许多科学程序员。 - duffymo
3在我看来，这与编程非常相关。请看我的回答。 - Yuval Adam
7个回答
5
调和数几乎出现在任何地方！音乐和谐，快速排序分析... 斯特林数（第一类和第二类）出现在各种组合和分区问题中。 欧拉数也出现在多个位置，最显着的是排列和多对数函数系数。
- Mitch Wheat
4
你提到的很多数字都用于算法分析。你的代码中可能没有这些数字，但如果想估计代码运行所需时间，就需要它们。有时候仅知道可能性的数量是不够的，因为需要枚举这些可能性。正在进行中的Knuth的TAOCP第4卷给出了所需算法。以下是将Fibonacci数列用于数值积分问题的示例。
调和数是对数的离散模拟，因此它们在差分方程中出现，就像对数在微分方程中出现一样。以下是与调和数相关的调和平均物理应用的示例。请参阅书籍Gamma，了解许多调和数的实际应用，特别是其中的“这是一个调和世界”章节。
- John D. Cook
1
我看到你是一位数学家。能否请您编辑回复并包含具体的例子？ - unj2
3
这些特殊的数字在计算问题中有很多用处。例如：
你想找出计算2个数字的最大公约数所需时间最长的时刻：尝试使用2个连续的斐波那契数。
你想大致估算一个大数的阶乘，但是你的阶乘程序太慢了：使用Stirling逼近。
你正在测试质数，但是对于某些数你总是得到错误的答案：可能是你正在使用费马素性检验，这种情况下Carmicheal数是罪魁祸首。
我能想到的最常见的一般情况是在循环中。大多数情况下，你使用(start;stop;step)类型的语法指定一个循环，在这种情况下，通过使用涉及的数字的属性可以减少执行时间。
sum = n*(n + 1)/2要慢。
有很多类似的例子。其中许多都是在密码学中，信息系统的安全有时取决于这些技巧。它们也可以帮助你解决性能问题、内存问题，因为当你知道公式时，你可能会找到更快/更有效的计算其他事物的方法——那些你真正关心的事物。
欲了解更多信息，请查看维基百科，或者尝试一下Project Euler。你很快就会发现模式。
- sykora
4
谢谢。但是AKS算法是素性测试的胜利者 :)。 - unj2
我认为上面的链接已经损坏了。请尝试使用http://www.cse.iitk.ac.in/users/manindra/algebra/primality_v6.pdf。 - unj2
1我对AKS算法非常了解，我已经使用它工作了相当长的时间。然而，它并不是很容易实现，特别是对于那些不擅长数论的人来说，这种情况下其他（更简单）的测试方法要好得多。 - sykora
抱歉，我并不是在暗示你不知道它们。顺便问一下，你能举个通过这些技巧解决的内存问题的例子吗？谢谢。 - unj2
2
大多数这些数字计算某些离散结构的数量（例如，斯特林数计算子集和循环）。这些结构及其序列隐含地出现在算法分析中。
OEIS有一个详尽的列表，列出了几乎所有在《具体数学》中出现的序列。该列表的简要概述如下：
- Golomb序列 - 二项式系数 - Rencontres数 - 斯特林数 - 欧拉数 - 超阶乘 - Genocchi数
您可以浏览OEIS页面以获取有关这些序列的“特性”的详细信息（如果您最感兴趣的是应用程序，则不完全是应用程序）。
此外，如果您想在算法分析中看到这些序列的实际用途，请翻阅Knuth的《计算机程序设计艺术》索引，您会发现许多关于这些序列的“应用”参考。John D. Cook已经提到了斐波那契数和调和数的应用；以下是更多示例：
斯特林循环数出现在分析找到数组最大元素的标准算法（TAOCP Sec. 1.2.10）时：在找到最大值时，当前最大值需要更新多少次？事实证明，在一个由n个元素组成的数组中查找最大值时，最大值需要更新k次的概率是p[n][k] = StirlingCycle[n, k+1]/n!。由此，我们可以推导出平均需要约Log(n)次更新。
Genocchi数与计算“瘦”BDDs（TAOCP 7.1.4 Exercise 174）的数量有关。
OEIS有一个详尽的列表，列出了几乎所有在《具体数学》中出现的序列。该列表的简要概述如下：
- Golomb序列 - 二项式系数 - Rencontres数 - 斯特林数 - 欧拉数 - 超阶乘 - Genocchi数
您可以浏览OEIS页面以获取有关这些序列的“特性”的详细信息（如果您最感兴趣的是应用程序，则不完全是应用程序）。
此外，如果您想在算法分析中看到这些序列的实际用途，请翻阅Knuth的《计算机程序设计艺术》索引，您会发现许多关于这些序列的“应用”参考。John D. Cook已经提到了斐波那契数和调和数的应用；以下是更多示例：
斯特林循环数出现在分析找到数组最大元素的标准算法（TAOCP Sec. 1.2.10）时：在找到最大值时，当前最大值需要更新多少次？事实证明，在一个由n个元素组成的数组中查找最大值时，最大值需要更新k次的概率是p[n][k] = StirlingCycle[n, k+1]/n!。由此，我们可以推导出平均需要约Log(n)次更新。
Genocchi数与计算“瘦”BDDs（TAOCP 7.1.4 Exercise 174）的数量有关。
- Ashutosh Mehra
1
并不一定是您提到的参考文献中的魔法数字，但尽管如此--
0x5f3759df
——臭名昭著的魔法数字，用于通过给出牛顿根逼近的良好初步估计来计算一个数的倒数平方根，这常被归因于约翰·卡马克的工作- 更多信息在这里。
不涉及编程，是吧？：）
- Yuval Adam
2
3这个回答与问题无关。 :p - ShreevatsaR
我以前见过那个数字。+1，因为链接到了一个解释它到底是用来干什么的文章。 - Samir Talwar
0
这和编程直接相关吗？肯定是有关系的，但我不知道关系有多密切。
特殊数字，如e、pi等等，随处可见。我认为没有人会对这两个数字产生争议。黄金分割在艺术和其他特殊数字本身中也频繁出现（看看连续斐波那契数之间的比率就知道了）。
许多数列和数族在数学和编程中也经常出现。一个美丽的地方是整数序列百科全书。
我建议这是一种经验问题。例如，当我很多年前学习线性代数时，我了解了矩阵的特征值和特征向量。我承认，在我看到它们在各种地方的应用之前，我完全没有意识到特征值/特征向量的重要性。在统计学中，从协方差矩阵中告诉你关于估计不确定性、置信椭圆的大小和形状、主成分分析或马尔可夫过程的长期状态。在数值方法中，它们告诉你一个方法的收敛性，无论是在优化还是在ODE求解器中。在机械工程中，你会看到它们作为主应力和应变。- user85109
网页内容由stack overflow 提供, 点击上面的可以查看英文原文，
原文链接
原文链接