“特殊号码”在哪里？ 具体数学中提到使用？
我正在网上浏览《具体数学》的内容。 我至少听说过提到的大部分功能和技巧，但有一整节是关于特殊数字的。 这些数包括斯特林数、欧拉数、调和数等。 现在我从来没有遇到过这些奇怪的数字。 它们如何帮助解决计算问题？ 它们一般用在什么地方？
I was glancing through the contents of Concrete Maths online. I had at least heard most of the functions and tricks mentioned but there is a whole section on Special Numbers. These numbers include Stirling Numbers, Eulerian Numbers, Harmonic Numbers so on. Now I have never encountered any of these weird numbers. How do they aid in computational problems? Where are they generally used?
如果你对这篇内容有疑问，欢迎到本站社区发帖提问 参与讨论，获取更多帮助，或者扫码二维码加入 Web 技术交流群。
绑定邮箱获取回复消息
由于您还没有绑定你的真实邮箱，如果其他用户或者作者回复了您的评论，将不能在第一时间通知您！
发布评论
评论（7）
调和数几乎无处不在！ 音乐和声、快速排序分析...
斯特林数（第一类和第二类）出现在各种组合和划分问题中。
欧拉数也出现在多个地方，最明显的是在多对数函数的排列和系数中。
Harmonic Numbers appear almost everywhere! Musical Harmonies, analysis of Quicksort...
Stirling Numbers (first and second kind) arise in a variety of combinatorics and partitioning problems.
Eulerian Numbers also occur several places, most notably in permutations and coefficients of polylogarithm functions.
你提到的很多数字都用于算法分析。 您的代码中可能没有这些数字，但如果您想估计代码运行所需的时间，则需要它们。 您也可能会在代码中看到它们。 其中一些数字与组合学相关，计算某件事可能发生的方式。
有时仅仅知道有多少种可能性是不够的，因为您需要枚举可能性。 Knuth 的 TAOCP 第 4 卷（正在进行中）提供了您需要的算法。
以下是使用 斐波那契数 的示例作为数值积分问题的一部分。
调和数是对数的离散模拟，因此它们出现在差分方程中，就像对数出现在微分方程中一样。 以下是调和平均值的物理应用示例，与谐波数有关。 请参阅Gamma一书，了解谐波数实际应用的许多示例，尤其是章节“这是一个和谐的世界。”
A lot of the numbers you mentioned are used in the analysis of algorithms. You may not have these numbers in your code, but you'll need them if you want to estimate how long it will take for your code to run. You might see them in your code too. Some of these numbers are related to combinatorics, counting how many ways something can happen.
Sometimes it's not enough to know how many possibilities there are because you need to enumerate over the possibilities. Volume 4 of Knuth's TAOCP, in progress, gives the algorithms you need.
Here's an example of using Fibonacci numbers as part of a numerical integration problem.
Harmonic numbers are a discrete analog of logarithms and so they come up in difference equations just like logs come up in differential equations. Here's an example of physical applications of harmonic means, related to harmonic numbers. See the book Gamma for many examples of harmonic numbers in action, especially the chapter "It's a harmonic world."
这些特殊数字可以通过多种方式帮助解决计算问题。 例如：
您想知道您的程序何时计算 2 个数字的 GCD 将花费最长的时间：尝试 2 个连续的斐波那契数。
您想要粗略估计大量数字的阶乘，但您的阶乘程序花费的时间太长：使用 斯特林近似。
您正在测试素数，但对于某些数字，您总是会得到错误的答案：可能您正在使用费马的素数测试，在这种情况下 卡迈克尔数是你的罪魁祸首。
我能想到的最常见的一般情况是循环。 大多数时候，您使用
(start;stop;step)类型的语法指定循环，在这种情况下，可以通过使用所涉及数字的属性来减少执行时间。例如，当 n 在循环中很大时，对从 1 到 n 的所有数字求和肯定比使用恒等式
sum = n*(n + 1)/2慢。类似这样的例子还有很多。 其中许多涉及密码学，其中信息系统的安全有时取决于类似的技巧。 它们还可以帮助您解决性能问题、内存问题，因为当您知道公式时，您可能会找到更快/更有效的方法来计算其他事情 - 您真正关心的事情。
欲了解更多信息，请查看维基百科，或者尝试一下欧拉计划。 您将很快开始找到模式。
These special numbers can help out in computational problems in many ways. For example:
You want to find out when your program to compute the GCD of 2 numbers is going to take the longest amount of time: Try 2 consecutive Fibonacci Numbers.
You want to have a rough estimate of the factorial of a large number, but your factorial program is taking too long: Use Stirling's Approximation.
You're testing for prime numbers, but for some numbers you always get the wrong answer: It could be you're using Fermat's Prime test, in which case the Carmicheal numbers are your culprits.
The most common general case I can think of is in looping. Most of the time you specify a loop using a
(start;stop;step)type of syntax, in which case it may be possible to reduce the execution time by using properties of the numbers involved.For example, summing up all the numbers from 1 to n when n is large in a loop is definitely slower than using the identity
sum = n*(n + 1)/2.There are a large number of examples like these. Many of them are in cryptography, where the security of information systems sometimes depends on tricks like these. They can also help you with performance issues, memory issues, because when you know the formula, you may find a faster/more efficient way to compute other things -- things that you actually care about.
For more information, check out wikipedia, or simply try out Project Euler. You'll start finding patterns pretty fast.
这些数字中的大多数都计算某些类型的离散结构（例如，斯特林数计算子集和循环）。 这样的结构，以及因此的这些序列，隐含地出现在算法分析中。
OEIS 有一份广泛的列表，几乎列出了具体数学中出现的所有序列。 该列表的简短摘要：
您可以浏览各个序列的 OEIS 页面，以获取有关这些序列“属性”的详细信息（尽管不完全是应用程序，如果这是的话）你最感兴趣的是什么）。
另外，如果您想了解这些序列在算法分析中的实际用途，请翻阅 Knuth 的《计算机编程艺术》索引，您会发现许多对这些序列“应用”的参考。 约翰·D·库克 (John D. Cook) 已经提到了斐波那契数和斐波那契数的应用。 谐波数； 这里还有一些例子：
斯特林循环数出现在寻找数组最大元素的标准算法的分析中（TAOCP Sec. 1.2.10）：多少求最大值时当前最大值需要更新多少次？ 事实证明，在
n元素数组中找到最大值时，最大值需要更新k次的概率为p[n][k ] = StirlingCycle[n, k+1]/n!。 由此，我们可以得出，平均而言，大约需要Log(n)更新。Genocchi 数字的出现与计算BDD的数量有关。 “薄”（TAOCP 7.1.4 练习 174）。
Most of these numbers count certain kinds of discrete structures (for instance, Stirling Numbers count Subsets and Cycles). Such structures, and hence these sequences, implicitly arise in the analysis of algorithms.
There is an extensive list at OEIS that lists almost all sequences that appear in Concrete Math. A short summary from that list:
You can browse the OEIS pages for the respective sequences to get detailed information about the "properties" of these sequences (though not exactly applications, if that's what you're most interested in).
Also, if you want to see real-life uses of these sequences in analysis of algorithms, flip through the index of Knuth's Art of Computer Programming, and you'll find many references to "applications" of these sequences. John D. Cook already mentioned applications of Fibonacci & Harmonic numbers; here are some more examples:
Stirling Cycle Numbers arise in the analysis of the standard algorithm that finds the maximum element of an array (TAOCP Sec. 1.2.10): How many times must the current maximum value be updated when finding the maximum value? It turns out that the probability that the maximum will need to be updated
ktimes when finding a maximum in an array ofnelements isp[n][k] = StirlingCycle[n, k+1]/n!. From this, we can derive that on the average, approximatelyLog(n)updates will be necessary.Genocchi Numbers arise in connection with counting the number of BDDs that are "thin" (TAOCP 7.1.4 Exercise 174).
不一定是您提到的参考文献中的神奇数字，但尽管如此 -
-- 臭名昭著的神奇数字，用于通过对牛顿近似值进行良好的初步估计来计算数字的平方根倒数根源，通常归功于 John Carmack 的工作 - 更多信息请点击此处。
与编程无关吧？ :)
Not necessarily a magic number from the reference you mentioned, but nonetheless --
-- the notorious magic number used to calculate inverse square root of a number by giving a good first estimate to Newton's Approximation of Roots, often attributed to the work of John Carmack - more info here.
Not programming related, huh? :)
这与编程直接相关吗？ 肯定有关系，但我不知道有多密切。
特殊数字，例如 e、pi 等，随处可见。 我认为没有人会争论这两件事。 Golden_ratio 也以惊人的频率出现，从艺术到其他特殊数字本身（看看连续斐波那契数之间的比率。）
各种序列和数字族也出现在数学中的许多地方，因此也出现在编程中。 整数序列百科全书是一个值得一看的好地方。
我会建议这是一个经验的事情。 例如，当我在很多很多年前学习线性代数时，我了解了矩阵的特征值和特征向量。 我承认，在我看到特征值/特征向量在各种地方使用之前，我根本没有意识到它们的重要性。 在统计学中，它们告诉您协方差矩阵估计的不确定性、置信椭圆的大小和形状、主成分分析或马尔可夫过程的长期状态。 在数值方法中，它们告诉您方法的收敛性，无论是优化还是 ODE 求解器。 在机械工程中，您将它们视为主要应力和应变。
Is this directly programming related? Surely related, but I don't know how closely.
Special numbers, such as e, pi, etc., come up all over the place. I don't think that anyone would argue about these two. The Golden_ratio also appears with amazing frequency, in everything from art to other special numbers themselves (look at the ratio between successive Fibonacci numbers.)
Various sequences and families of numbers also appear in many places in mathematics and therefore, in programming too. A beautiful place to look is the Encyclopedia of integer sequences.
I'll suggest this is an experience thing. For example, when I took linear algebra, many, many years ago, I learned about the eigenvalues and eigenvectors of a matrix. I'll admit that I did not at all appreciate the significance of eigenvalues/eigenvectors until I saw them in use in a variety of places. In statistics, in terms of what they tell you about uncertainty of an estimate from a covariance matrix, the size and shape of a confidence ellipse, in terms of principal component analysis, or the long term state of a Markov process. In numerical methods, where they tell you about convergence of a method, be it in optimization or an ODE solver. In mechanical engineering, where you see them as principal stresses and strains.
Reddit 中的讨论
Discussion in Reddit