Где используются «Особые числа», упомянутые в «Математике бетона»?

Question

Я просматривал содержание Concrete Maths онлайн. Я, по крайней мере, слышал большинство упомянутых функций и трюков, но есть целый раздел по специальным номерам. Эти числа включают числа Стирлинга, числа Эйлера, гармонические числа и так далее. Теперь я никогда не сталкивался ни с одним из этих странных чисел. Как они помогают в вычислительных задачах? Где они обычно используются?

Answer 1

Гармонические числа появляются практически везде! Музыкальные гармонии, анализ Quicksort ... Числа Стирлинга (первого и второго рода) возникают в различных задачах комбинаторики и разбиения. Эйлеровы числа также встречаются в нескольких местах, особенно в перестановках и коэффициентах функций полилогарифма.

Answer 2

Многие из упомянутых вами чисел используются при анализе алгоритмов. Возможно, у вас нет этих чисел в вашем коде, но они вам понадобятся, если вы хотите оценить, сколько времени займет выполнение кода. Вы можете увидеть их в своем коде тоже. Некоторые из этих чисел относятся к комбинаторике, подсчитывая, сколько способов что-то может произойти.

Иногда недостаточно знать, сколько существует возможностей, потому что вам нужно перечислить по возможностям. Том 4 TAOCP Кнута , в процессе, дает алгоритмы, которые вам нужны.

Вот пример использования чисел Фибоначчи как часть задачи численного интегрирования.

Гармонические числа являются дискретным аналогом логарифмов, и поэтому они возникают в разностных уравнениях так же, как логарифмы в дифференциальных уравнениях. Вот пример физического применения средних гармоник , связанных с гармоническими числами. В книге Гамма приведено множество примеров гармонических чисел в действии, особенно в главе «Это гармоничный мир».

Answer 3

Эти специальные числа могут помочь в вычислительных задачах разными способами. Например:

• Вы хотите узнать, когда ваша программа для вычисления GCD из 2 чисел займет наибольшее время: Попробуйте 2 последовательных числа Фибоначчи.

• Вы хотите получить приблизительную оценку факториала большого числа, но ваша факториальная программа занимает слишком много времени: используйте Аппроксимация Стирлинга .

• Вы проверяете простые числа, но для некоторых чисел вы всегда получаете неправильный ответ: возможно, вы используете тест Ферма Прайма, и в этом случае числа Кармишеи являются вашими виновники.

Наиболее распространенный общий случай, о котором я могу думать, - это циклы. Большую часть времени вы указываете цикл, используя синтаксис типа (start;stop;step), и в этом случае можно сократить время выполнения, используя свойства соответствующих чисел.

Например, суммирование всех чисел от 1 до n, когда n велико в цикле, определенно медленнее, чем использование идентификатора sum = n*(n + 1)/2.

Существует множество таких примеров. Многие из них находятся в криптографии, где безопасность информационных систем иногда зависит от подобных уловок. Они также могут помочь вам с проблемами производительности, памяти, потому что, когда вы знаете формулу, вы можете найти более быстрый / более эффективный способ вычисления других вещей - вещей, которые вас действительно волнуют.

Для получения дополнительной информации ознакомьтесь с Википедией или попробуйте Project Euler. Вы начнете довольно быстро находить шаблоны.

Answer 4

Большинство этих чисел учитывают определенные виды дискретных структур (например, числа Стирлинга подсчитывают подмножества и циклы). Такие структуры и, следовательно, эти последовательности неявно возникают при анализе алгоритмов .

В OEIS имеется обширный список, в котором перечислены почти все последовательности, которые появляются в Concrete Math . Краткое резюме из этого списка:

• Последовательность Голомба
• Биномиальные коэффициенты
• Rencontres Numbers
• Числа Стирлинга
• Эйлеровы числа
• Hyperfactorials
• Genocchi Numbers

Вы можете просматривать страницы OEIS для соответствующих последовательностей, чтобы получить подробную информацию о «свойствах» этих последовательностей (хотя это не совсем приложения, если это то, что вас больше всего интересует).

Кроме того, если вы хотите увидеть реальное использование этих последовательностей в анализе алгоритмов, пролистайте указатель Искусства компьютерного программирования Кнута, и вы найдете много ссылок на «приложения» этих последовательностей. Джон Д. Кук уже упоминал о приложениях чисел Фибоначчи и Гармоники; Вот еще несколько примеров:

Номера циклов Стирлинга возникают при анализе стандартного алгоритма, который находит максимальный элемент массива (TAOCP Sec. 1.2.10): Сколько раз должен быть текущий максимум значение будет обновляться при поиске максимального значения? Оказывается, вероятность того, что максимум нужно будет обновлять k раз при нахождении максимума в массиве из n элементов, составляет p[n][k] = StirlingCycle[n, k+1]/n!. Из этого можно сделать вывод, что в среднем потребуется приблизительно Log(n) обновлений.

Числа Генокки возникают в связи с подсчетом "тонких" BDD (TAOCP 7.1.4 Упражнение 174).

Answer 5

Обсуждение в Reddit

Answer 6

Это напрямую связано с программированием? Конечно связано, но я не знаю, насколько близко.

Повсюду появляются специальные цифры, такие как e, pi и т. Д. Я не думаю, что кто-то будет спорить об этих двух. Golden_ratio также появляется с удивительной частотой, во всем, от искусства до других специальных чисел (посмотрите на соотношение между последовательными числами Фибоначчи.)

Различные последовательности и семейства чисел также появляются во многих местах в математике и, следовательно, в программировании. Красивое место для поиска - энциклопедия целых последовательностей .

Я предполагаю, что это опыт. Например, когда я взял линейную алгебру много-много лет назад, я узнал о собственных значениях и собственных векторах матрицы. Я признаю, что я вообще не оценил значение собственных значений / собственных векторов, пока не увидел их в использовании в разных местах. В статистике, с точки зрения того, что они говорят вам о неопределенности оценки по ковариационной матрице, о размере и форме доверительного эллипса, с точки зрения анализа главных компонент или о долгосрочном состоянии марковского процесса. В численных методах, где они говорят вам о сходимости метода, будь то оптимизация или решатель ODE. В машиностроении, где вы видите их как основные напряжения и деформации.

Answer 7

Не обязательно магическое число из ссылки, которую вы упомянули, но тем не менее -

0x5f3759df

- пресловутое магическое число, используемое для вычисления обратного квадратного корня из числа, давая хорошую первую оценку для приближения корней Ньютона , часто приписываемого работе Джона Кармака - подробнее здесь .

Не связано с программированием, а? :)