Добрый день, Аркадий! Прошу прощения за некропостинг, но на письмо отвечу.
Я остановился на 40 000, поскольку решето Эратосфена на Рефале оказалось сильно медленным, и его время растёт нелинейно от длины исходного списка. Причём, мне показалось, что даже квадратично. Поэтому результата в 176 100 я просто не дождусь. Время я замерял для переславской реализации Рефала-5. Рефал-5λ сильно медленнее (в разы), поэтому мне стыдно было показывать эти числа 😳. В последующей переписке Антон Орлов продолжил оффтопик, мне уже лень пытаться переписывать его примеры на Рефал. С уважением, Александр Коновалов From: Arkady Klimov arkady.klimov_AT_gmail.com [mailto:refal@botik.ru] Sent: Thursday, October 10, 2019 4:50 PM To: refal@botik.ru Subject: Re: Список всех простых чисел Александр, а можно попросить вас пропустить вариант для 176100 вместо 40000 - тогда результаты (времена) будут сопоставимы. Я подумал еще об одной оптимизации. Сейчас произведение простых формируется сразу, а ведь оно может и не понадобиться. То есть для последнего "поколения" эта работа лишняя. Наверно, лучше накапливать в виде списка, а при подаче на Filter для следующего шага все перемножить. Интересно, для Хаскела это тоже актуально, или там умножение pp*n ленивое? А еще хотелось бы посмотреть статистику по числу (доле) отсеянных (прошедших) через каждый из фильтров (это мне уже как математику интересно). И соответствующие значения lim. Я так понимаю, что количество поколений здесь 4-5, да? Аркадий ср, 9 окт. 2019 г. в 13:13, Александр Коновалов a.v.konovalov87_AT_mail.ru <http://a.v.konovalov87_AT_mail.ru> <refal@botik.ru <mailto:refal@botik.ru> >: Добрый день всем! Нужно спасать рассылку от офтопа. Переписал исходник Сергея Михайловича на Рефал-5. Функции primesE, primesAD и primesA переписаны максимально близко к тексту, ради этого пришлось ввести функции filter, o (композиция функций), bind-right (чтобы связать Mod со вторым аргументом), eq и neq. Рефал не поддерживает ленивые вычисления и бесконечные списки, поэтому все функции на входе принимают последовательность чисел от 2 до 40 000. Понятно, что вызов <filter (o ((neq 0) (bind-right (Mod s.n)))) e.ns> на Рефале будет выполняться медленно. Поэтому я также написал оптимизированные версии primesE-opt и primesA-opt, в которых фильтрация выполняется не функцией высшего порядка, а специально написанной функцией. Функция primesE в этом случае ускорилась на порядок, primesA — незначительно. Замеры времени есть в исходнике. Масштаб величин примерно такой же: primesE на порядок медленнее primesAD, primesAD на порядок медленнее primesA. Функции primesE-opt и primesAD требуют одинакового времени работы, но первая делает гораздо больше шагов. Причина этого расхождения, по-видимому, в длинной арифметике, в вычислении gcd(pp, n), поскольку pp — длинное число. С уважением, Александр Коновалов -----Original Message----- From: Sergei M. Abramov abram_AT_botik.ru <refal@botik.ru <mailto:refal@botik.ru> > Sent: Tuesday, October 8, 2019 10:29 PM To: refal@botik.ru <mailto:refal@botik.ru> Subject: Список всех простых чисел День добрый, всем! Простите, что не про Рефал. Просто не могу вспомнить то, что (как мне помнится) случилось в обстановке рефал-компании на заре моей профессиональной деятельности (практика в НИЦЭВТе или работа в нем). По каким-то причинам я задумался тогда над построением списка всех простых чисел. И в некий момент сам придумал алгоритм, которрый опирался вот на какое определение последовательности простых чисел: 1. Очередное натуральное число n будет простым, если оно взаимнопросто со всеми ранее найдеными простыми числами. или (что то же самое, но уже совсем близко к коду) 2. Очередное натуральное число n -- простое, если gcd(pp,n)==1, где pp -- произведение всех ранее найденых простых чисел. Понятно, что нужна сверхдлинная целочисленная арифметика. Но, gcd(pp,n) обещал посчитаться быстрее, чем деление n по очереди на все сомножители из pp. Я этот алгоритм (точнее подход, поскольку сам алгоритм похитрее, о нем в конце) придумал сам и очень этим гордился. Но потом в рефал-компании кто-то мне дал книжку. Серегей Романенко? Андрей или Алик Климов? Колля Кондратьев? -- не помню. Книжка была кого-то из великих... Дейскстра? Вирт? И, почему-то, мне кажется, что называлась она "Записки из башни слоновой кости". А в книжке, как мне сегодня кажется, были программистсткие побасенки. Ну, и был коротенький шутливый этюд (близко к тексту): ================ Цитата по памяти =============================== Для эффективной генерации всех простых чисел мнe достаточно всего двух ячеек памяти: integer pp, n; n := 2; pp := 1; while ( True ) do begin if ( gcd(pp, n)=1 ) then begin println(n); pp := pp * n; end; n := n + 1; end; ================================================================== С тех пор я узнал, что хотя я и самостоятельно нашел такой подход к генерации простых, но я был не единственным (и, скорее всего, не первым) ПРОСЬБА О ПОМОЩИ: 1. Коллеги, если кто-то может мне дать имя автора, название книги, которая мне помнится, то я буду благодарен. 2. И если есть еще какие-либо ссылки на такой подход к проверке простоты -- gcd(pp, n)=1,-- то тоже полезно. Почему вспомнил? Вспомнил я про эту историю во время очередной своей лекции по Хаскеллю в ЯрГУ. Ну, и сегодня написал немного строк на Хаскелле -- приложены. Взгляните, для интереса. primesAD -- это генератор, прямо в лоб переписан приведенный выше паскале-подобный текст. А теперь поговорим про решето. Решето вообще (не обязательно Эратосфена) -- это когда берем начальное пространство поиска -- например, [2..]. И дальше всегда делаем такую пару операций: 1. Некие первые элементы (один или больше) в текущем прастранстве поиска -- заведомо простые числа -- выдаем их в результат. 2. Затем при помощи только что найденых простых фильтруем (сужаем) пространство поиска. Если брать только одно простое n из пространства поиска и фильтровать предикатом ((/=0).(`mod`n)) -- то это решето Эратосфена. А если брать много заведомо простых из пространства поиска, вычислять их произведение pp и фильтровать предикатом ((==1).(gcd pp)) -- то это решето ... назову решетом Абрамова ;-) Пока Вы мне не подскажете другого автора такого же подхода (или где искать). Три остальные программки в Хаскелле -- это разные варианты решета: primesE, primesE1 -- решето Эратосфена (отличии в изобразительных средствах). primesА -- решето Абрамова. А заканчивается файл статистикой (время счета и память) прогона некоторых тестов в HUGSе и в GHCi. Посмотрите статистику... Шуточный этюд "достаточно две ячейки памяти" имеет нешуточное приложение, как мне кажется ;-) Я уж молчу про то, что gcd по Евклиду (как оно описано в прелюдии хаскелля) не самая эффективная реализация gcd (по Кнуту). Всего доброго, Сергей Абрамов -- _______________ С уважением, Аркадий Климов, с.н.с. ИППМ РАН, +7(499)135-32-95 +7(916)072-81-48
