Консультация № 191354
17.09.2017, 17:03
0.00 руб.
17.09.2017, 17:28
0 24 1
Здравствуйте уважаемые эксперты!
Занимаюсь переделкой библиотеки численного анализа НИВЦ МГУ и при разборе процедуры вычисления простых чисел типа "решето Эратосфена" столкнулся с одной проблемой вспомогательного характера:
там для вычисления количества простых чисел в диапазоне от 1 до N использует ся формула:
не больше [ 1.6N / lnN + 1 ] , если N <= 200 ,
или не больше [ N / (lnN-2) + 1 ] , если N > 200.

То, что их количество после вчисления получается действительно "не больше" - та и есть. Однако эта формула при расчёте потребного количества ячеек массива для хранения результата, выдаёт ответ с изрядным завышением. И если такой завышения для диапазона простых чисед от 1 до 100 вполне терпимо, то когда речь идёт о миллионах, миллиардах и т.д., то в этом случае пустых ячеек без результата получается просто бешеное количество.
Сам я программирую расчёт количества так:
Код:
Если N <= 200 То
Количество = 1.6*N / LOG(N) + 1
Иначе
Количество = N / (LOG(N) - 2) + 1


И у меня вопрос:
- ошибся я;
- ошибка у них там в алгоритме;
- если никто не ошибся, есть ли формулы вычисляющее более "разумное" количество предполагаемых простых чисел?

Обсуждение

давно
Мастер-Эксперт
17387
18345
17.09.2017, 19:04
общий
17.09.2017, 19:06
Адресаты:
Цитата: Вадим Исаев ака sir Henry
Однако эта формула при расчёте потребного количества ячеек массива для хранения результата, выдаёт ответ с изрядным завышением. И если такой завышения для диапазона простых чисед от 1 до 100 вполне терпимо, то когда речь идёт о миллионах, миллиардах и т.д., то в этом случае пустых ячеек без результата получается просто бешеное количество.


А откуда Вам известно про увеличение завышения с увеличением N?

Вы используете исходные формулы с исключённой функцией взятия целой части?


Об авторе:
Facta loquuntur.
давно
Мастер-Эксперт
425
4118
18.09.2017, 05:51
общий
18.09.2017, 05:54
Адресаты:
Цитата: Гордиенко Андрей Владимирович
А откуда Вам известно про увеличение завышения с увеличением N?

Как раз из вычислений размера массива для хранения результата.
Мне предварительно нужно вычислить размер массива для хранения результата. И если для N=100 эта формула мне вычисляет, что нужно 35 ячеек (из них 26 занято, 9 свободно), для N=1000 нужно 204 ячейки (из них 179 занято, 35 свободно), для N=1000000 нужно 84645 ячеек (78509 занято, 6134 свободно).
Цитата: Гордиенко Андрей Владимирович
Вы используете исходные формулы с исключённой функцией взятия целой части?

Никак нет, сэр. Компилятор на такие вольности сразу говорит "учи матчасть, сынок" и посылает в тундру за ягелем.
Об авторе:
Я только в одном глубоко убеждён - не надо иметь убеждений! :)
давно
Мастер-Эксперт
17387
18345
18.09.2017, 06:53
общий
Адресаты:
Возможно, Вас утешит то, что с увеличением доля свободных ячеек уменьшается. А по поводу используемых Вами формул: они отличаются от исходных тем, что в них отсутствует функция взятия целой части, как я понимаю, сравнивая их.
Об авторе:
Facta loquuntur.
давно
Мастер-Эксперт
425
4118
18.09.2017, 07:20
общий
Цитата: Гордиенко Андрей Владимирович
А по поводу используемых Вами формул: они отличаются от исходных тем, что в них отсутствует функция взятия целой части, как я понимаю, сравнивая их.

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

Ни капельки не утешит. Хотелось бы поменьше бессмысленных расходов компьютерных ресурсов.
Об авторе:
Я только в одном глубоко убеждён - не надо иметь убеждений! :)
давно
Мастер-Эксперт
17387
18345
18.09.2017, 08:52
общий
Адресаты:
Цитата: Вадим Исаев ака sir Henry
Ни капельки не утешит. Хотелось бы поменьше бессмысленных расходов компьютерных ресурсов.

К сожалению, ни асимптотическая формула из теоремы о распределении простых чисел, ни любая другая формула из известных мне и пригодных для использования не дают точного количества простых чисел. Кроме того, они не гарантируют, что ячеек хватит. Поэтому, наверное, авторы рассмотренного Вами алгоритма использовали формулу, дающую запас ячеек. И это не бессмысленно.

А точное определение количества ячеек эквивалентно вычислению всех простых чисел от до Вряд ли это уменьшит расход компьютерных ресурсов.

Впрочем, может быть, Вас заинтересует то, что написано здесь. Правда, обсуждать это я не готов в силу нехватки математического образования.

Возможно, Сергей Евгеньевич Лангваген сумеет Вам помочь. Он, по-моему, единственный на нашем портале действующий эксперт с хорошим знанием математики.
Об авторе:
Facta loquuntur.
давно
Мастер-Эксперт
425
4118
18.09.2017, 09:04
общий
Адресаты:
Ага, я Вас понял. Большое спасибо!
Собственно то, что кол-во ячеек берётся с запасом, это я понял из надписей на страничке с функцией. Просто эта функция составлялась достаточно давно (в конце 60-ых, максимум начало 70-ых годов) и я думал что математика с тех пор совершила в этой области какие-нибудь выдающиеся открытия, позволяющие оценить кол-во простых чисел с большей точностью.
В любом случае спасибо!
Об авторе:
Я только в одном глубоко убеждён - не надо иметь убеждений! :)
давно
Посетитель
7438
7205
18.09.2017, 10:47
общий
Адресаты:
Хочу предложить чисто программисткое решение:
Не выделять всю память сразу, а фрагментами по 10-100, на Ваш вкус.
По мере заполнения. Видим, что заполнился очередной фрагмент, перевыделяем память с увеличением на один фрагмент.
Об авторе:
"Если вы заметили, что вы на стороне большинства, —
это верный признак того, что пора меняться." Марк Твен
давно
Посетитель
7438
7205
18.09.2017, 11:20
общий
18.09.2017, 11:21
Адресаты:
Оптимизированное решето Эратосфена, если надо. На phyton
[code lang=python]n = input("n=")
lst=[2]
for i in xrange(3, n+1, 2):
if (i > 10) and (i%10==5):
continue
for j in lst:
if j*j-1 > i:
lst.append(i)
break
if (i % j == 0):
break
else:
lst.append(i)
print lst[/code]
Взято отсюда
Об авторе:
"Если вы заметили, что вы на стороне большинства, —
это верный признак того, что пора меняться." Марк Твен
давно
Мастер-Эксперт
17387
18345
18.09.2017, 15:07
общий
Адресаты:
Здравствуйте, Сергей Евгеньевич!

Извините, пожалуйста, за беспокойство.

Может быть, у Вас есть что добавить по существу консультации?
Об авторе:
Facta loquuntur.
давно
Мастер-Эксперт
425
4118
18.09.2017, 19:03
общий
Адресаты:
Если говорить в общем, то выделение памяти для одного куска будет примерно равно по времени (ну, чуть меньше) выделению сразу целого куска памяти для всего. Потом фоновая функция управления памятью всё равно будет собирать куски в один массив, чтобы ускорить время обращения к нему.
Об авторе:
Я только в одном глубоко убеждён - не надо иметь убеждений! :)
давно
Мастер-Эксперт
425
4118
18.09.2017, 19:06
общий
Адресаты:
Цитата: Лысков Игорь Витальевич
Оптимизированное решето Эратосфена, если надо.

Нет, не надо. У меня другая задача - перевести процедуры с "древнеегипетского" Фортрана на современный. Это будет использоваться в учебном процессе - буду гонять студней по переводу их же, с последующей разборкой ошибок. А то они, змеи сидящие на четвереньках, привыкли из инета брать готовое, думать не хотят.
Об авторе:
Я только в одном глубоко убеждён - не надо иметь убеждений! :)
давно
Советник
165461
578
19.09.2017, 11:58
общий
Адресаты:
Количество простых, меньших х, при 17 <= x <= exp(100) удовлетворяет неравенствам:
x/log(x) < п(x) < x/(log(x) - 2).
См. здесь.
Похоже, что формулы у Вас правильные. Если не секрет, где Вы взяли вторую формулу?
давно
Мастер-Эксперт
17387
18345
19.09.2017, 19:22
общий
Адресаты:
Цитата: Лангваген Сергей Евгеньевич
Если не секрет, где Вы взяли вторую формулу?

В тексте вопроса указано, что вторая формула взята из программы-первоисточника, находящейся в библиотеке численного анализа НИВЦ МГУ.
Об авторе:
Facta loquuntur.
давно
Советник
165461
578
19.09.2017, 20:09
общий
Адресаты:
Первая 1.6*N/ln N + 1 из исходной программы, это понятно.
Хотелось узнать, из какого источника взята формула N/(log N - 2) +1.
давно
Мастер-Эксперт
17387
18345
19.09.2017, 20:17
общий
19.09.2017, 20:17
Адресаты:
Из той же программы.
Цитата: Вадим Исаев ака sir Henry
не больше [ 1.6N / lnN + 1 ] , если N <= 200 ,
или не больше [ N / (lnN-2) + 1 ] , если N > 200.
Об авторе:
Facta loquuntur.
давно
Советник
165461
578
19.09.2017, 20:54
общий
Адресаты:
Мне казалось, что вторые формулы отличаются. Действительно, они совпадают, с точностью до взятия целой части. Тогда зачем они выписаны дважды? Впрочем, это неважно. Прошу прощения за невнимательность.
Значит, вопрос заключается в следующем:
1. Верно ли, что эти формулы дают сильно завышенное количество простых чисел?
2. Есть ли способ улучшить оценку количества простых чисел?
Правильно я понял?
давно
Мастер-Эксперт
17387
18345
19.09.2017, 20:56
общий
Адресаты:
Да, Вы правильно поняли.
Об авторе:
Facta loquuntur.
давно
Мастер-Эксперт
425
4118
20.09.2017, 05:25
общий
20.09.2017, 06:31
Адресаты:
Цитата: Лангваген Сергей Евгеньевич
Если не секрет, где Вы взяли вторую формулу?

Клянусь своей треуголкой, это не я.
К сожалению, на страничке с описанием, ссылку на которую я давал в вопросе, у них нет источников, откуда они эту формулу взяли. На многих страничках других процедур расчётов такие ссылки на "теорию" имеются, а вот тут нету. Не исключено, что проводились какие-то собственные исследования по этому вопросу.
Цитата: Лангваген Сергей Евгеньевич
1. Верно ли, что эти формулы дают сильно завышенное количество простых чисел?

Если делать оценку "доли" пустых ячеек для ответа, то выглядит всё неплохо - 25% незанятых для N=100 и 7% незанятых для N=1000000. Однако если отойти от чистой математики, то "автобус" (ресурсы компьютера ) у нас не резиновый. Лишние 50 килобайт оперативной памяти могут иметь решающее значение, когда количество данных (с учётом кодов программ, естественно) забивается примерно равным количеству оперативной памяти. Тут то и наступает переломный момент. В связи с тем, что компьютер начинает использовать виртуальную память, время расчётов может увеличится в 1000 раз, а то и больше. Конечно, если комплектовать комп диском типа SSD, то ситуация будет получше, но я столько не зарабатываю, а государство щедростью никогда не отличалось...

Об авторе:
Я только в одном глубоко убеждён - не надо иметь убеждений! :)
давно
Советник
165461
578
21.09.2017, 10:38
общий
Адресаты:
Вадим, спасибо за подробные пояснения к вопросу.

Источник второй формулы, кажется, известен, см. энциклопедию, раздел "Метод Виноградова".
Лучший результат, но ненамного, должна дать формула
п(x) < (x/ln x)*(1 + 1.2762/ln x)
из этой статьи, которая нашлась совершенно случайно. Самая последняя формула в тексте.

Может быть, заинтересует страничка, где рассматриваются варианты реализации решета Эратосфена, в том числе способы сокращения объема памяти: исключение четных чисел, "битовое сжатие", и "блочное решето". Вариант "блочное решето" предполагает хранение простых чисел только до корня из N.

Успехов.
давно
Мастер-Эксперт
425
4118
21.09.2017, 10:59
общий
Адресаты:
Спасибо. Я сегодня, ближе к ночи предложенную Вами формулу опробую.
Цитата: Лангваген Сергей Евгеньевич
Может быть, заинтересует страничка, где рассматриваются варианты реализации решета Эратосфена, в том числе способы сокращения объема памяти: исключение четных чисел...

Я посмотрю их все, только вот у меня задача несколько другая - не разработка какого-то нового алгоритма, а просто перевод старой библиотеки на новый, современный синтаксис Фортрана, а то студенты порой сдувают с интернета процедуры, даже не попытавшись их опробовать в работе. Приносят, показывают, я им тычу пальцем в строчку с вычисляемым GOTO и прошу объяснить, что бы это значило. Иногда, исключительно из врождённого коварства, даю задание откомпилировать этот код. Я хочу предложить задания для пытливых по преобразованию синтаксиса, потом будем сравнивать с моим переводом и обсуждать, у кого что получилось-неполучилось.
А вообще, в той процедуре, ссылку на которую выкладывал я, уже учтено, что из чётных чисел простое никогда не получится, поэтому там цикл начинается с числа 3 и дальше идёт с прибавлением 2...
Об авторе:
Я только в одном глубоко убеждён - не надо иметь убеждений! :)
давно
Советник
165461
578
22.09.2017, 17:27
общий
Адресаты:
Добрый вечер, Вадим.
Есть результаты?
давно
Мастер-Эксперт
425
4118
24.09.2017, 06:33
общий
Адресаты:
Ага, формула, преложенная Вами, даёт намного меньше "пустых" ячеек:
- для N=1000000 всего 1200, вместо 6100 по старой формуле;
- для N=100, так и вообще пустяки - всего две лишние ячейки.
Правда для нынешних гигабайтов оперативной памяти N=100 это совсем несерьёзно...
Большое спасибо!
Когда возьмёт программу математик,
Он быстро лишнее найдёт.
И от него, как Чингачгука,
Враг программиста не уйдёт.

Теперь компьютер очень дружно,
Считает только то, что нужно!

Об авторе:
Я только в одном глубоко убеждён - не надо иметь убеждений! :)
давно
Посетитель
7438
7205
26.09.2017, 17:22
общий
Адресаты:
Сергей Евгеньевич, с Вас ответ.
Об авторе:
"Если вы заметили, что вы на стороне большинства, —
это верный признак того, что пора меняться." Марк Твен
давно
Советник
165461
578
26.09.2017, 20:48
общий
это ответ
Здравствуйте, Вадим Исаев ака sir Henry!

Лучшие результаты должна давать следующая оценка количества п(x) простых чисел, не превосходящих x:
п(x) [$8804$] (x/ln x)*(1 + 1.2762/ln x) при x>1.
Эта формула была предложена в статье 1999 года, автор Pierre Dusart.
Согласно энциклопедии, в программе НИВЦ МГУ использовалась более ранняя оценка.
5
Форма ответа