Где используются "Особые числа", упомянутые в "Математике бетона"?
Я просматривал содержимое Concrete Maths онлайн. Я, по крайней мере, слышал большинство упомянутых функций и трюков, но есть целый раздел по специальным номерам. Эти числа включают числа Стирлинга, числа Эйлера, гармонические числа и так далее. Теперь я никогда не сталкивался ни с одним из этих странных чисел. Как они помогают в вычислительных задачах? Где они обычно используются?
7 ответов
Большинство из этих чисел учитывают определенные виды дискретных структур (например, числа Стирлинга подсчитывают подмножества и циклы). Такие структуры и, следовательно, эти последовательности неявно возникают при анализе алгоритмов.
В 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) обновления будут необходимы.
Числа Genocchi возникают в связи с подсчетом числа " BDD", которые являются "тонкими" (TAOCP 7.1.4 Упражнение 174).
Гармонические числа появляются практически везде! Музыкальные гармонии, анализ быстрой сортировки... Числа Стирлинга (первого и второго рода) возникают в различных задачах комбинаторики и разбиения. Эйлеровы числа также встречаются в нескольких местах, особенно в перестановках и коэффициентах функций полилогарифма.
Многие из упомянутых вами чисел используются при анализе алгоритмов. Возможно, у вас нет этих чисел в вашем коде, но они вам понадобятся, если вы хотите оценить, сколько времени займет выполнение кода. Вы можете увидеть их в своем коде тоже. Некоторые из этих чисел относятся к комбинаторике, подсчитывая, сколько способов что-то может произойти.
Иногда недостаточно знать, сколько существует возможностей, потому что вам нужно перечислить их. В четвертом томе TAOCP Кнута приводятся алгоритмы, которые вам нужны.
Вот пример использования чисел Фибоначчи как часть задачи численного интегрирования.
Гармонические числа являются дискретным аналогом логарифмов, поэтому они возникают в разностных уравнениях так же, как логарифмы в дифференциальных уравнениях. Вот пример физического применения гармонических средств, связанных с гармоническими числами. В книге " Гамма " вы найдете множество примеров гармонических чисел в действии, особенно главу "Это гармоничный мир".
Эти специальные числа могут помочь в вычислительных задачах разными способами. Например:
Вы хотите узнать, когда ваша программа для вычисления GCD из 2 чисел займет наибольшее количество времени: Попробуйте 2 последовательных числа Фибоначчи.
Вы хотите получить приблизительную оценку факториала большого числа, но ваша факториальная программа занимает слишком много времени: используйте приближение Стирлинга.
Вы проверяете простые числа, но для некоторых чисел вы всегда получаете неправильный ответ: возможно, вы используете тест Ферма Прайма, и в этом случае числа Carmicheal являются вашими виновниками.
Наиболее распространенный общий случай, о котором я могу подумать, связан с циклом. Большую часть времени вы указываете цикл, используя (start;stop;step) тип синтаксиса, в этом случае может быть возможно сократить время выполнения, используя свойства участвующих чисел.
Например, суммирование всех чисел от 1 до n, когда n велико в цикле, определенно медленнее, чем использование тождества sum = n*(n + 1)/2,
Таких примеров очень много. Многие из них находятся в криптографии, где безопасность информационных систем иногда зависит от подобных трюков. Они также могут помочь вам с проблемами производительности, памяти, потому что, когда вы знаете формулу, вы можете найти более быстрый / более эффективный способ вычисления других вещей - вещей, которые вас действительно волнуют.
Для получения дополнительной информации ознакомьтесь с Википедией или попробуйте Project Euler. Вы начнете находить шаблоны довольно быстро.
Не обязательно магическое число из упомянутой вами ссылки, но тем не менее -
0x5f3759df
- пресловутое магическое число, используемое для вычисления обратного квадратного корня из числа, давая хорошую первую оценку для приближения корней Ньютона, часто приписываемого работе Джона Кармака - больше информации здесь.
Не связано с программированием, а?:)
Это напрямую связано с программированием? Конечно, связано, но я не знаю, насколько близко.
Специальные числа, такие как е, пи и т. Д., Появляются повсюду. Я не думаю, что кто-то будет спорить об этих двух. Golden_ratio также появляется с удивительной частотой во всем, от искусства до других специальных чисел (посмотрите на соотношение между последовательными числами Фибоначчи).
Различные последовательности и семейства чисел также появляются во многих местах в математике и, следовательно, в программировании. Красивое место для поиска - энциклопедия целочисленных последовательностей.
Я предполагаю, что это вещь опыта. Например, когда я взял линейную алгебру много-много лет назад, я узнал о собственных значениях и собственных векторах матрицы. Я признаю, что я совсем не оценил значение собственных значений / собственных векторов, пока не увидел их в использовании в разных местах. В статистике, с точки зрения того, что они говорят вам о неопределенности оценки по ковариационной матрице, о размере и форме доверительного эллипса, с точки зрения анализа главных компонентов, или о долговременном состоянии марковского процесса. В численных методах, где они говорят вам о сходимости метода, будь то в оптимизации или решателя ODE. В машиностроении, где вы видите их как основные напряжения и деформации.