Участник:Vvnikolaev/Решето Эратосфена - История изменений

Vvnikolaev: /* Существующие реализации алгоритма */

2016-11-30T18:01:35Z

Существующие реализации алгоритма

← Предыдущая версия		Версия от 18:01, 30 ноября 2016
Строка 85:		Строка 85:
	== Существующие реализации алгоритма ==		== Существующие реализации алгоритма ==
	Однопоточные реализации с различными улучшениями:		Однопоточные реализации с различными улучшениями:
	# Однопоточная реализация ~~с некоторыми улучшениями~~: http://e-maxx.ru/algo/eratosthenes_sieve		# Однопоточная реализация: http://e-maxx.ru/algo/eratosthenes_sieve
	# Однопоточная реализация, работающая за сублинейное время: http://e-maxx.ru/algo/prime_sieve_linear		# Однопоточная реализация, работающая за сублинейное время: http://e-maxx.ru/algo/prime_sieve_linear

Vvnikolaev: /* Существующие реализации алгоритма */

2016-11-30T18:01:22Z

Существующие реализации алгоритма

← Предыдущая версия		Версия от 18:01, 30 ноября 2016
Строка 84:		Строка 84:

	== Существующие реализации алгоритма ==		== Существующие реализации алгоритма ==
	Однопоточные реализации с различными ~~улчшениями~~:		Однопоточные реализации с различными улучшениями:
	# Однопоточная реализация с некоторыми улучшениями: http://e-maxx.ru/algo/eratosthenes_sieve		# Однопоточная реализация с некоторыми улучшениями: http://e-maxx.ru/algo/eratosthenes_sieve
	# Однопоточная реализация, работающая за сублинейное время: http://e-maxx.ru/algo/prime_sieve_linear		# Однопоточная реализация, работающая за сублинейное время: http://e-maxx.ru/algo/prime_sieve_linear

Vvnikolaev: /* Масштабируемость алгоритма и его реализации */

2016-11-30T18:00:49Z

Масштабируемость алгоритма и его реализации

← Предыдущая версия		Версия от 18:00, 30 ноября 2016
Строка 76:		Строка 76:
	[[File:Weak_scaling_sieve.png]]		[[File:Weak_scaling_sieve.png]]

	При одном процессе, число <math> n \approx 5000000 </math>. Видно, что при фиксированном отношении сложности задачи к числу процессов, время решения задачи растет. Это связано с тем, что при распараллеливании появляются дополнительные накладные расходы, а так же с тем, что задача распараллеливается не полностью. При увеличении ~~числа процессов~~ в <math> 64 </math> раза, время выполнения увеличилось в <math> 5 </math> раз.		При одном процессе, число <math> n \approx 5000000 </math>. Видно, что при фиксированном отношении сложности задачи к числу процессов, время решения задачи растет. Это связано с тем, что при распараллеливании появляются дополнительные накладные расходы, а так же с тем, что задача распараллеливается не полностью. При увеличении сложности задачи в <math> 64 </math> раза (и одновременно числа процессов, потому что производилось исследование слабой масштабируемости), время выполнения увеличилось в <math> 5 </math> раз.

	== Динамические характеристики и эффективность реализации алгоритма ==		== Динамические характеристики и эффективность реализации алгоритма ==

Vvnikolaev: /* Макроструктура алгоритма */

2016-11-30T17:57:13Z

Макроструктура алгоритма

← Предыдущая версия		Версия от 17:57, 30 ноября 2016
Строка 22:		Строка 22:
	== Макроструктура алгоритма ==		== Макроструктура алгоритма ==
	Алгоритм можно разбить на 2 части:		Алгоритм можно разбить на 2 части:
	# Первая часть — создается булев массив длины n ~~и заполняется единицами~~		# Первая часть — создается и заполняется единицами булев массив длины <math>n</math>
	# Вторая часть — последовательно рассматривается каждое, еще не помеченное число, и с помощью него производится фильтрация бо́льших чисел		# Вторая часть — последовательно рассматривается каждое, еще не помеченное число, и с помощью него производится фильтрация бо́льших чисел

Vvnikolaev: /* Вычислительное ядро алгоритма */

2016-11-30T17:56:45Z

Вычислительное ядро алгоритма

← Предыдущая версия		Версия от 17:56, 30 ноября 2016
Строка 18:		Строка 18:

	== Вычислительное ядро алгоритма ==		== Вычислительное ядро алгоритма ==
	Основное время работы приходится на шаг №3 алгоритма. Можно показать, что сложность составляет <math>O(nlog(log(n)))</math>.		Основное время работы приходится на шаг №3 алгоритма. Можно показать, что сложность алгоритма составляет <math>O(nlog(log(n)))</math>.

	== Макроструктура алгоритма ==		== Макроструктура алгоритма ==

Vvnikolaev: /* Математическое описание алгоритма */

2016-11-30T17:56:27Z

Математическое описание алгоритма

← Предыдущая версия		Версия от 17:56, 30 ноября 2016
Строка 15:		Строка 15:
	# Повторяются шаги 3 и 4 пока возможно		# Повторяются шаги 3 и 4 пока возможно

	~~На практике на шаге 3 зачеркивать числа можно начиная с <math>p^2</math>, и, соответственно~~ алгоритм заканчивает свою работу при <math>p^2 > n</math>.		Соответственно алгоритм заканчивает свою работу при <math>p^2 > n</math>.

	== Вычислительное ядро алгоритма ==		== Вычислительное ядро алгоритма ==

Vvnikolaev: /* Математическое описание алгоритма */

2016-11-30T17:54:59Z

Математическое описание алгоритма

← Предыдущая версия		Версия от 17:54, 30 ноября 2016
Строка 11:		Строка 11:
	# Выписываются подряд все натуральные числа от <math>2</math> до <math>n</math>		# Выписываются подряд все натуральные числа от <math>2</math> до <math>n</math>
	# Берется <math>p = 2</math>		# Берется <math>p = 2</math>
	# Зачеркиваются числа от <math>p^2</math> до <math>n</math> с шагом <math>p</math> (то есть все числа от <math>2</math> до <math>n</math>, кратные <math>p</math>)		# Зачеркиваются числа от <math>p^2</math> до <math>n</math> с шагом <math>p</math> (то есть все числа от <math>2</math> до <math>n</math>, кратные <math>p</math>, кроме него самого)
	# Ищется первое не зачеркнутое число в списке, превышающие <math>p</math>, и это значение присваивается переменной <math>p</math>		# Ищется первое не зачеркнутое число в списке, превышающие <math>p</math>, и это значение присваивается переменной <math>p</math>
	# Повторяются шаги 3 и 4 пока возможно		# Повторяются шаги 3 и 4 пока возможно

Vvnikolaev: /* Математическое описание алгоритма */

2016-11-30T17:54:39Z

Математическое описание алгоритма

← Предыдущая версия		Версия от 17:54, 30 ноября 2016
Строка 11:		Строка 11:
	# Выписываются подряд все натуральные числа от <math>2</math> до <math>n</math>		# Выписываются подряд все натуральные числа от <math>2</math> до <math>n</math>
	# Берется <math>p = 2</math>		# Берется <math>p = 2</math>
	# Зачеркиваются числа от <math>2p</math> до <math>n</math> с шагом <math>p</math> (то есть все числа от <math>2</math> до <math>n</math>, кратные <math>p</math>)		# Зачеркиваются числа от <math>p^2</math> до <math>n</math> с шагом <math>p</math> (то есть все числа от <math>2</math> до <math>n</math>, кратные <math>p</math>)
	# Ищется первое не зачеркнутое число в списке, превышающие <math>p</math>, и это значение присваивается переменной <math>p</math>		# Ищется первое не зачеркнутое число в списке, превышающие <math>p</math>, и это значение присваивается переменной <math>p</math>
	# Повторяются шаги 3 и 4 пока возможно		# Повторяются шаги 3 и 4 пока возможно

Vvnikolaev: /* Математическое описание алгоритма */

2016-11-30T17:54:17Z

Математическое описание алгоритма

← Предыдущая версия		Версия от 17:54, 30 ноября 2016
Строка 10:		Строка 10:

	# Выписываются подряд все натуральные числа от <math>2</math> до <math>n</math>		# Выписываются подряд все натуральные числа от <math>2</math> до <math>n</math>
	# ~~Положим~~ <math>p = 2</math>		# Берется <math>p = 2</math>
	# Зачеркиваются числа от <math>2p</math> до <math>n</math> с шагом <math>p</math> (то есть все числа от <math>2</math> до <math>n</math>, кратные <math>p</math>)		# Зачеркиваются числа от <math>2p</math> до <math>n</math> с шагом <math>p</math> (то есть все числа от <math>2</math> до <math>n</math>, кратные <math>p</math>)
	# Ищется первое не зачеркнутое число в списке, превышающие <math>p</math>, и это значение присваивается переменной <math>p</math>		# Ищется первое не зачеркнутое число в списке, превышающие <math>p</math>, и это значение присваивается переменной <math>p</math>

Vvnikolaev: /* Общее описание алгоритма */

2016-11-30T17:53:41Z

Общее описание алгоритма

← Предыдущая версия		Версия от 17:53, 30 ноября 2016
Строка 4:		Строка 4:

	== Общее описание алгоритма ==		== Общее описание алгоритма ==
	'''Решето́ Эратосфе́на''' — алгоритм нахождения всех простых чисел до некоторого целого числа <math>n</math>. Приписывается древнегреческому математику Эратосфену Киренскому (откуда и название). Алгоритм проходит список всех чисел от <math>2</math> до <math>n</math> и на каждом шаге убирает часть ~~чисел~~, не являющихся простыми. Таким образом происходит фильтрация («решето» в названии).		'''Решето́ Эратосфе́на''' — алгоритм нахождения всех простых чисел до некоторого целого числа <math>n</math>. Приписывается древнегреческому математику Эратосфену Киренскому (откуда и название). Алгоритм проходит список всех чисел от <math>2</math> до <math>n</math> и на каждом шаге убирает часть из них, не являющихся простыми. Таким образом происходит фильтрация («решето» в названии).

	== Математическое описание алгоритма ==		== Математическое описание алгоритма ==