Где “Специальные Числа”, упомянутые в Конкретной используемой Математике?
Нет, не будет. Ты едва увидишь это. Где-то менее 1000 раз в секунду эта нить просыпается и почти ничего не делает, прежде чем снова заснуть.
Редактировать:
Я должен был проверить. Работая на Java 1.5, этот тест
@Test
public void testSpeed() throws InterruptedException {
long currentTime = System.currentTimeMillis();
int i = 0;
while (i < 1000)
{
Thread.sleep(1);
i++;
}
System.out.println("Executed in " + (System.currentTimeMillis() - currentTime));
}
выполнялся со скоростью примерно 500 снов в секунду на моей 3-ГГц машине. Я полагаю, что C # должен быть примерно таким же. Я предполагаю, что кто-то сообщит с номерами C # для этого чрезвычайно важного реального эталонного теста. Между прочим, не было заметного использования процессора.
7 ответов
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:
- Golomb's Sequence
- Binomial Coefficients
- Rencontres Numbers
- Stirling Numbers
- Eulerian Numbers
- Hyperfactorials
- Genocchi Numbers
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 k times when finding a maximum in an array of n elements is p[n][k] = StirlingCycle[n, k+1]/n!. From this, we can derive that on the average, approximately Log(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).
Гармонические числа появляются почти везде! Числа Стирлинга (первого и второго рода) возникают во множестве задач комбинаторики и разбиения. Числа Эйлера также встречаются в нескольких местах, в первую очередь в перестановках и коэффициентах функций полилогарифма.
Многие из упомянутых вами чисел используются при анализе алгоритмов. Возможно, у вас нет этих чисел в вашем коде, но они вам понадобятся, если вы хотите оценить, сколько времени потребуется для выполнения вашего кода. Вы также можете увидеть их в своем коде. Некоторые из этих чисел связаны с комбинаторикой, подсчетом количества способов, которыми что-то может произойти.
Иногда недостаточно знать, сколько существует возможностей, потому что вам нужно перечислить возможности. Том 4 TAOCP Кнута , который находится в стадии разработки, дает вам необходимые алгоритмы.
Вот пример использования чисел Фибоначчи как части задачи численного интегрирования.
Гармонические числа являются дискретным аналогом логарифмов, поэтому они появляются в разностных уравнениях, как логарифмы в дифференциальных уравнениях. Вот пример физического применения гармонических средних , связанных с номерами гармоник. См. Книгу Гамма , где можно найти множество примеров действия гармонических чисел, особенно главу «Это гармонический мир».
Не обязательно магическое число из упомянутой вами ссылки, но тем не менее -
0x5f3759df
- пресловутое магическое число, используемое для вычисления обратного квадратного корня из числа дает хорошую первую оценку Аппроксимации корней Ньютона, которую часто приписывают работе Джона Кармака - больше информации здесь .
Не связано с программированием, да? :)
Эти специальные числа могут помочь в решении вычислительных задач разными способами. Например:
Вы хотите выяснить, когда ваша программа для вычисления НОД двух чисел займет больше всего времени: Попробуйте 2 последовательных числа Фибоначчи.
Вы хотите получить приблизительную оценку факториала большого числа, но ваша факториальная программа занимает слишком много времени: используйте приближение Стирлинга .
Вы проверяете простые числа, но для некоторых чисел вы всегда получаете неправильный ответ: это может быть вы Вы используете тест Ферма на простое число, и в этом случае ваши виноваты числа Кармихила .
Самый распространенный общий случай, который я могу придумать, - это цикл. В большинстве случаев вы указываете цикл, используя синтаксис типа (start; stop; step) , в этом случае можно сократить время выполнения, используя свойства задействованных чисел.
Например, суммирование всех чисел от 1 до n, когда n велико в цикле, определенно медленнее, чем использование идентификатора sum = n * (n + 1) / 2 .
Подобных примеров великое множество. Многие из них находятся в криптографии, где безопасность информационных систем иногда зависит от подобных уловок. Они также могут помочь вам с проблемами производительности, проблемами с памятью, потому что, зная формулу, вы можете найти более быстрый / более эффективный способ вычисления других вещей - вещей, которые вас действительно волнуют.
Для получения дополнительной информации проверьте wikipedia или просто попробуйте Project Euler. Вы довольно быстро начнете находить закономерности.
суммирование всех чисел от 1 до n при большом n в цикле определенно медленнее, чем использование тождества sum = n * (n + 1) / 2 .
Существует большое количество такие примеры. Многие из них находятся в криптографии, где безопасность информационных систем иногда зависит от подобных уловок. Они также могут помочь вам с проблемами производительности, проблемами с памятью, потому что, зная формулу, вы можете найти более быстрый / более эффективный способ вычисления других вещей - вещей, которые вас действительно волнуют.
Для получения дополнительной информации проверьте wikipedia или просто попробуйте Project Euler. Вы довольно быстро начнете находить закономерности.
суммирование всех чисел от 1 до n при большом n в цикле определенно медленнее, чем использование тождества sum = n * (n + 1) / 2 .
Существует большое количество такие примеры. Многие из них находятся в криптографии, где безопасность информационных систем иногда зависит от подобных уловок. Они также могут помочь вам с проблемами производительности, проблемами с памятью, потому что, зная формулу, вы можете найти более быстрый / более эффективный способ вычисления других вещей - вещей, которые вас действительно волнуют.
Для получения дополнительной информации проверьте wikipedia или просто попробуйте Project Euler. Вы довольно быстро начнете находить закономерности.
где безопасность информационных систем иногда зависит от подобных уловок. Они также могут помочь вам с проблемами производительности, проблемами с памятью, потому что, зная формулу, вы можете найти более быстрый / более эффективный способ вычисления других вещей - вещей, которые вас действительно волнуют.Для получения дополнительной информации проверьте wikipedia или просто попробуйте Project Euler. Вы довольно быстро начнете находить закономерности.
где безопасность информационных систем иногда зависит от подобных уловок. Они также могут помочь вам с проблемами производительности, проблемами с памятью, потому что, зная формулу, вы можете найти более быстрый / более эффективный способ вычисления других вещей - вещей, которые вас действительно волнуют.Для получения дополнительной информации проверьте wikipedia или просто попробуйте Project Euler. Вы довольно быстро начнете находить закономерности.
Связано ли это напрямую с программированием? Несомненно, связаны, но я не знаю, насколько близко.
Специальные числа, такие как е, пи и т. Д., Встречаются повсюду. Не думаю, что кто-то будет спорить об этих двоих. Golden_ratio также появляется с поразительной частотой во всем, от искусства до других специальных чисел (посмотрите на соотношение между последовательными числами Фибоначчи.)
Различные последовательности и семейства чисел также встречаются во многих местах в математике. а значит, и в программировании. Прекрасное место для поиска - это Энциклопедия целочисленных последовательностей .
Я предполагаю, что это вещь для опыта. Например, когда я изучал линейную алгебру много-много лет назад, я узнал о собственных значениях и собственных векторах матрицы. Я' Признаюсь, что я совсем не осознавал значения собственных значений / собственных векторов, пока не увидел их в использовании в различных местах. В статистике с точки зрения того, что они говорят вам о неопределенности оценки из ковариационной матрицы, о размере и форме доверительного эллипса с точки зрения анализа главных компонент или о долгосрочном состоянии марковского процесса. В численных методах, где они говорят вам о сходимости метода, будь то оптимизация или решатель ODE. В машиностроении, где вы видите их как основные напряжения и деформации.
с точки зрения анализа главных компонент или долгосрочного состояния марковского процесса. В численных методах, где они говорят вам о сходимости метода, будь то оптимизация или решатель ODE. В машиностроении, где вы видите их как основные напряжения и деформации. с точки зрения анализа главных компонент или долгосрочного состояния марковского процесса. В численных методах, где они говорят вам о сходимости метода, будь то оптимизация или решатель ODE. В машиностроении, где вы видите их как основные напряжения и деформации.