Модифицировать программу (практическая помощь)

[svb]

-- Вт сен 23, 2014 13:04:08 --

Исходники на паскале я выложил ранее. Картинки говорят, что выбранный подход не так уж плох и его можно рекомендовать. Пока не использованы специальные методы оптимизации - основное внимание было уделено алгоритму построения решета. Основная процедура очень простая:

(Оффтоп)

procedure sieve(i:qword);
var nsi:qword;
    ii:word;
    j,jj,a,k,k2:dword;
label 1,2;
begin
  a:=trunc(sqrt(Nseg*(i+1)));
  p:=p0;  {базовое решето}
  if i=0 then begin
    for ii:=1 to 7 do p[pr[ii]]:=true;
    p[1]:=false;
    j:=1;k:=pr17[j];
    while k<=a do begin
      jj:=19*k;
      while jj<Nseg do begin
        p[jj]:=false;
        repeat
          jj:=jj+k+k;
        until (jj>=Nseg)or p[jj];
      end;
      inc(j);
      k:=pr17[j];
    end;
    exit;
  end;
  j:=1;k:=pr17[j];nsi:=Nseg*i;
  while k<=a do begin
    if k>=Nseg then begin
      jj:=k-nsi mod k;
      if jj<Nseg then p[jj]:=false;
      goto 1;
    end;
    if p0[k] then begin
      jj:=k-nsi mod k;
      k2:=k shl 1;
      if (not odd(jj)) then jj:=jj+k;
      2:
      if jj>=Nseg then goto 1;
      if not p[jj] then begin jj:=jj+k2;goto 2 end;
      p[jj]:=false;
      jj:=jj+k2;
      goto 2;
    end;
    1:
    inc(j);if j=92160 then j:=0;
    k:=k+d17[j];
  end;
end;

[Nataly-Mak]

svb
ну что же, высокоскоростной генератор вы сделали, отличный результат.
Теперь можно приступать к поиску квадрата Стенли 5-го порядка

К сожалению, все участники процесса никак не хотят объединиться в дружный коллектив, каждый сам по себе.
Кто что нашёл, кто что проверил - всё покрыто мраком неизвестности.

Долго думала, как бы мобилизовать всех. Ничего нового не придумала, как провести конкурс по данной проблеме. Может быть, кого-то заинтересует.
Конкурс стартовал вчера
http://primesmagicgames.altervista.org/wp/competitions/

Обсуждение конкурсной задачи предлагаю вести в теме "Дьвольские магические квадраты из простых чисел".

[Nataly-Mak]

svb
кстати, о вашей программе поиска пандиагональных квадратов 6-го порядка.
Сравнила в работе вашу программу и программу alexBlack, ваша работает быстрее.
У меня к вам просьба: выложите, пожалуйста, ссылку для скачивания этой программы, чтобы мне не искать (программа называется Diab_v5). У меня-то программа есть; может, ещё кому будет интересно посмотреть вашу программу.
Желательно выложить ссылку в теме "Дьявольские магические квадраты из простых чисел".

Ну, а потом... если вы захотите использовать эту программу для поиска решения конкурсной задачи для $n=6$, что вполне возможно, вам придётся модифицировать программу, потому что проверять по одной магической константе, как сейчас, очень нудно.
Я проверила уже порядка 100 потенциальных магических констант, решение не найдено.
Мы с вами давно начали эту проверку, несколько первых потенциальных констант были проверены вами, я продолжила. Тогда прервала проверку, вот сейчас возобновила.
Ну просто интересно: где же второй такой квадратик?

[Nataly-Mak]

svb в сообщении #910522 писал(а):

Для проверки реализован простенький вариант поиска последовательностей КПППЧ.

Небольшое тестирование этой процедуры.



Искала 22-ку, найденную Dmitry40. Очень долго не могла подобрать номер сегмента, видно, к старости слаба умишком стала
Надо было подобрать номер сегмента, чтобы выйти примерно на начало нужного интервала.
Ну, вот на иллюстрации видно, на какое начало я вышла-таки после многочисленных проб.
Программа 22-ку нашла. Правда, в файл почему-то не записала.

Господа!
24-ку никто не желает поискать по программе svb
Замечу, что до $10^{15}$ её можно не искать, как утверждает Dmitry40, её там нет.

[svb]

В программе много неудобств - было не до них, все хотелось быстрее проверить. Сейчас вот надо срочно изменить режим КПППЧ - постоянный сдвиг буфера с набором чисел сделан по недоразумению и лучше организовать циклическую индексацию. Таких мелочей так много, что не до красот интерфейса. Прошу меня извинить за сырую программу и сильно не ругать.

Номер сегмента по началу интервала $N$ я сам нахожу на калькуляторе: $seg=N/510510$

Мои старые программы лежат где-то на моем сайте, который есть в профиле. Все давно запущено, руки не доходят привести в порядок свой компьютер.

[Nataly-Mak]

svb в сообщении #911451 писал(а):

Таких мелочей так много, что не до красот интерфейса. Прошу меня извинить за сырую программу и сильно не ругать.

Перефразируя классика, я сказала бы так: "В программе всё должно быть прекрасно: и алгоритм, и код, и интерфейс"

Цитата:

Номер сегмента по началу интервала $N$ я сам нахожу на калькуляторе: $seg=N/510510$

Ну, я это примерно и предполагала (вы где-то писали о длине сегмента), но делить на калькуляторе страшно не хотелось, поэтому начала подбором, прибрасывая номер сегмента в уме. Так пришлось долго прибрасывать пока, наконец, не попала на начало интервала (около того).
Конечно, на мой взгляд, в программе надо сделать ввод начала интервала, а не номера сегмента, чтобы не морочить голову и не делить на калькуляторе.

Цитата:

Мои старые программы лежат где-то на моем сайте, который есть в профиле. Все давно запущено, руки не доходят привести в порядок свой компьютер.

А, ну тогда отошлём всех интересующихся на ваш сайт, который можно найти в профиле.

[Dmitriy40]

svb в сообщении #910522 писал(а):

Улучшен генератор простых чисел. Время генерации решета сопоставимо
с результатом программы primesieve 3.6.

Простите, но это излишне смелое утверждение.
Primeseive (и я тоже) делает много подготовительной работы перед началом генерации чисел, зато потом можно генерить сегменты один за другим на три порядка быстрее (да-да, в тысячи раз!). Вы же делаете эту подготовительную работу для каждого сегмента заново. Потому хотя время генерации одного сегмента и сопоставимо (primeseive: 6.5с, Ваша: ~6.5c, моя: 32с), но вот время генерации двух и более сегментов - у Вас сильно медленнее. Зато не требуется столько памяти (сотни мегабайтов).

Вот тесты всех трёх программ в одинаковом диапазоне размером 51051000 (100 ваших сегментов, 1000 сегментов ждать устал) с одинаковой начальной точки (1e18, на 1е19 памяти не хватает, а со свопом замеры скорости бессмысленны).
Primeseive:

Sund09:

Моя:


Обратите внимание, primeseive сгенерила все 100 сегментов всего за 8 секунд. Вместе с подготовкой.
Моя справилась за 35с, причём на каждый сегмент тратилось меньше 0.04с (на скрине время указано для 10-ти сегментов), и 32с заняла подготовка. Моя сразу искала все КПППЧ любой длины.
Ваша работала 11 минут, на каждый сегмент тратилось 6.5с.

В задаче поиска КПППЧ время генерации простых чисел критично, дальнейшие проверки занимают менее 3% общего времени. Вот в задачах поиска квадратов и кубов бОльшую часть времени занимает попытка построения квадрата/куба и там скорость генератора простых чисел влияет мало.

PS. 2000 сегментов (миллиард проверенных чисел) с той же начальной точки primeseive сгенерила за 23.7с, моя затратила 106с. Вашу ждать 3.5ч не стал.
В окрестности 1e16 скорость primeseive на моём компе 7с/млрд (514млрд/ч), моей 27с/млрд (130млрд/ч).

[Nataly-Mak]

Dmitriy40
просьба, ради научного любопытства
если не трудно, покажите, пожалуйста, результат работы вашей программы поиска 22-ки в интервале, приведённом в моём тестировании программы svb
post911358.html#p911358

(желательно показать и результат того же тестирования программы svb на вашем компьютере, так как мой и ваш компьютеры отличаются быстродействием)

[svb]

Dmitriy40 в сообщении #911750 писал(а):

svb в сообщении #910522 писал(а):

Улучшен генератор простых чисел. Время генерации решета сопоставимо
с результатом программы primesieve 3.6.

Простите, но это излишне смелое утверждение.
Primeseive (и я тоже) делает много подготовительной работы перед началом генерации чисел, зато потом можно генерить сегменты один за другим на три порядка быстрее (да-да, в тысячи раз!). Вы же делаете эту подготовительную работу для каждого сегмента заново. Потому хотя время генерации одного сегмента и сопоставимо (primeseive: 6.5с, Ваша: ~6.5c, моя: 32с), но вот время генерации двух и более сегментов - у Вас сильно медленнее. Зато не требуется столько памяти (сотни мегабайтов).

Трудно не согласиться...

Большое спасибо за ваш отклик.

[Dmitriy40]

Nataly-Mak в сообщении #911751 писал(а):

Dmitriy40
просьба, ради научного любопытства
если не трудно, покажите, пожалуйста, результат работы вашей программы поиска 22-ки в интервале, приведённом в моём тестировании программы svb
post911358.html#p911358

(желательно показать и результат того же тестирования программы svb на вашем компьютере, так как мой и ваш компьютеры отличаются быстродействием)

Да уж, ради научного любопытства пришлось полчаса подождать

Sand09:

Не так уж и отличаются у нас компы, по крайней мере в этой программе, у Вас было 1582с.

Моя:

Тут 1.36с - подготовительная работа.
У меня вывод статистики заточен под миллиарды, потому расширил диапазон чуточку, до круглых миллиардов. На точном интервале полное время 65с.

[Nataly-Mak]

Dmitriy40
Спасибо, научное любопытство полностью удовлетворено

[Dmitriy40]

svb в сообщении #911767 писал(а):

Большое спасибо за ваш отклик.

Чтобы не выглядело совсем уж как только ругань Вашей программы, позволю себе дать пару советов по ускорению генераци простых чисел. За что заранее извиняюсь. :)

1. До 510510 всего 42331 простое число, можно в set_pr17 найти их все и сохранить в массив pr[], расширив его соответственно. Буфер в 510510 boolean у Вас и так уже есть, а больше ничего и не нужно. Самым наипростым решетом вычеркиваем оттуда числа и всё. Это займёт намного меньше секунды. Правда сильно это не ускорит.

2. Вы вычеркиваете не только простые, но и составные числа, всего 92160 штук на каждый сегмент. В то же время простых среди них не более половины, а чем дальше сегмент от начала, тем меньше. В интересном сейчас диапазоне около $10^{15}$ их уже меньше 15 тысяч, т.е. в 6 раз меньше. Потому предлагаю вычеркивать лишь точно простые, а находить их вспомогательным решетом на базе уже найденных в п.1 первых простых чисел. Для этого используйте новый массив p1[Nseg] of boolean, который двигайте от Nseg (досюда простые числа уже найдены в п.1) дальше шагами по Nseg пока не пройдёте границу $\sqrt{N_{seg}(i+1)}$, вычёркивайте из него составные числа (используя найденный в начале массив простых), оставшиеся простые по мере нахождения вычеркивайте из основного массива.
Оценим количество операций для сравнения даст ли это ускорение. Оценку проведём для практически интересного сейчас Nseg=$2 \cdot 10^{10}$ (около $10^{16}$). Чтобы вычеркнуть из основного решета все составные числа надо не менее $\pi(\sqrt{10^{16}})<6\cdot10^6$ первых простых чисел (до $10^8$). Чтобы их все найти надо обработать 196 первых сегментов. Считаем, из 196 сегментов проводится не более 1229 вычёркиваний (простых меньших $\sqrt{196\cdot510510}$), из основного решета менее 5818159 вычёркиваний, в сумме менее 6млн. Сейчас Вы делаете $92160\sqrt{196\cdot510510}=921876255$ вычёркиваний. В 158 раз больше! Конечно будут накладыне расходы на организацию двойного решета, но они уменьшат выигрыш на несколько процентов всего лишь. А все процедуры у Вас уже написаны, осталось добавить пару массивов и вызывать их в другом порядке. Требования к памяти увеличатся всего на один массив p1[Nseg] (а можно и вообще основной использовать) и массив простых pr1[1229]. Слёзы. Зато можно ускорить раз в 100!
После реализации этого пункта размер сегмента перестаёт быть привязанным к произведению простых чисел и можно его выбирать произвольно (пригодится в п.5 и далее). Я для себя выбрал ровно 1млн, такой влазит в L2 кэш (см. п.5-п.7) и удобен для человека.

3. Если не гнаться за числами $10^{18}$ и более, то можно просто сначала найти все простые числа до $\sqrt{N_{seg}(i+1)}$, сохранить их в массив pr[6млн] (для чисел до $10^{16}$) и потом просто из каждого нового сегмента их вычёркивать. Когда их не хватит (сегменты уйдут далеко вперёд), то один раз запустить вспомогательное решето, нагенерить ещё десяток тысяч простых чисел (ну сколько найдётся в одном сегменте), сохранить их в массив (увеличив его размер или выделив заранее с большим запасом) и продолжить работу. 6млн простых чисел хапнут всего 25МБ памяти (они гарантировано int32), не так уж и много. Можно выделить и 70МБ памяти, туда влезут все простые до 316млн, их хватит для проверки чисел до $10^{17}$. Ну а для чисел около $10^{18}$ памяти будет нужно уже 200МБ. Что тоже не смертельно. Правда ускорения почти не даст, полторы тысячи вспомогательных вычёркиваний на фоне 6млн незаметны.

4. Если реализовать п.3, то удвоив требования к памяти можно отказаться от одной из самых долгих операций в цикле вычеркиваний: "jj:=k-nsi mod k;". Деление (и взятие остатка) выполняется весьма медленно, ну по сравнению с другими операциями. На моих тестах исключение операции mod ускоряет программу в 6 раз. Но это уже нетривиальное усложнение программы.

5. Стоит уменьшить размер сегмента до размеров L2 кэша процессоров, а он сейчас обычно 256КБ (или даже L1 в 32КБ). Это может ускорить работу раза в три ... А может и меньше, растут повторные действия.

6. Для уменьшения повторных действий применить битовую упаковку boolean (в дельфи он байтовый, не знаю как в Вашем компиляторе), это позволит путём нестрашного усложнения программы увеличить размер сегмента в 8 раз. С 8-ми кратным сокращением повторяемых действий.

7. Ну и тупо сделать хранение в p0,p[Nseg] только нечётных чисел, это позволит удвоить размер сегмента вообще без накладных расходов.

Прошу прощения если это всё известные Вам вещи. Или если они уже частично реализованы, а я не заметил. :)

PS. Если не гнаться за рекордами, я бы реализовал пункты 1, 2, 5, 7 и всё. 6-й по желанию можно и потом. Дальше ускорение уже не критично, а вот усложнение программы и требования к памяти ... А для первых двух пунктов у Вас уже практически всё готово.

-- 25.09.2014, 18:16 --

Предложения по дальнейшему ускорению генерации простых чисел есть и ещё, но их я и сам ещё не реализовал, потому советовать не осмелюсь. Хотя в primeseive они почти все сделаны ... Просто перечислю:
8. Многопоточность.
9. Вообще не вычёркивать числа, точно не попадающие в сегмент. И определять это заранее, ещё до обработки сегмента.
10. Планировать работу на много сегментов вперёд (особенно предыдущий пункт).
11. В основном сегменте не хранить не только чётных чисел, но также и кратных 3, 5, 7, 11, ...
12. Оптимизировать цикл вычёркиваний чисел, попадающих в сегмент ровно один раз и более одного раза (разбить один цикл на два).
13. Частично развернуть циклы вычёркиваний, чтобы было больше одинаковых процессорных команд подряд (для обработки разных чисел) - для более полной загрузки множества АЛУ в процессоре. Потребует переписываний циклов на ассемблере.
14. Для чтения всего кроме текущего сегмента использовать команды некэшируемой загрузки XMM регистров чтобы не сбивать кэш сегмента. Тоже pure asm required.
15. Ну а дальше уже совсем дебри.

[svb]

Dmitriy40 в сообщении #911925 писал(а):

Чтобы не выглядело совсем уж как только ругань Вашей программы, позволю себе дать пару советов по ускорению генераци простых чисел. За что заранее извиняюсь. :)

Важнее всего найти хотя бы капельку нового, все остальное часто только мешает. Нормально, когда люди ошибаются. Именно в ошибках самое главное. Мир устроен просто, но мы часто не видим этого. Любое общение, любое обсуждение позволяет приблизится к пониманию "истины".

Цитата:

1. До 510510 всего 42331 простое число, можно в set_pr17 найти их все и сохранить в массив pr[], расширив его соответственно. Буфер в 510510 boolean у Вас и так уже есть, а больше ничего и не нужно. Самым наипростым решетом вычеркиваем оттуда числа и всё. Это займёт намного меньше секунды. Правда сильно это не ускорит.

Решето pr[] одинаковое для любых смещений кратных 510510, а, например решето для числа 19, хотя и присутствует в любом сегменте, но со сдвигом относительно базового решета pr[]. Решето pr[] формально занимает 510510, но все, что за пределами 92160 не используется. Если бы удалось при другом хранении этого решета делать нужные нам операции, то это было бы интересно. Нас интересуют пересечения этого решета с простейшими решетками $K=[ki, i=0,1,..]$

Цитата:

2. Вы вычеркиваете не только простые, но и составные числа, всего 92160 штук на каждый сегмент. В то же время простых среди них не более половины, а чем дальше сегмент от начала, тем меньше. В интересном сейчас диапазоне около $10^{15}$ их уже меньше 15 тысяч, т.е. в 6 раз меньше. Потому предлагаю вычеркивать лишь точно простые, а находить их вспомогательным решетом на базе уже найденных в п.1 первых простых чисел.

Для делителей меньших Nseg это почти обязательно, т.к. с ними связаны основные затраты времени из-за внутренних циклов, к тому же фиксированы затраты памяти. Для делителей больших Nseg отсутствуют внутренние циклы, идет выкидывание не более одного элемента из строящейся решетки, а затраты памяти зависят от диапазона, что меня несколько смущает. Конечно, $\sqrt{N_{seg}(i+1)}$ на практике можно терпеть, но в теории это та же "бесконечность", которую лучше не совать в память.

Цитата:

4. Если реализовать п.3, то удвоив требования к памяти можно отказаться от одной из самых долгих операций в цикле вычеркиваний: "jj:=k-nsi mod k;". Деление (и взятие остатка) выполняется весьма медленно, ну по сравнению с другими операциями. На моих тестах исключение операции mod ускоряет программу в 6 раз. Но это уже нетривиальное усложнение программы.

Я собирался рассмотреть переход от $k$ к $k+1$ для замены этой операции.

Использование специальных средств оптимизации интересно, но намного интереснее и полезнее сначала улучшить основной алгоритм.

Спасибо за ваше сообщение, буду думать.

[Dmitriy40]

П.1 отдельно сам по себе не нужен, а вот как подготовка к п.2 - очень даже.
Про pr[], сдвиг получается той же операцией mod, выдающей jj, а потом просто закольцованное обращение к массиву и всё. Я собирался так делать, потом прикинул выигрыш - доли и доли процента, не стоит заморочек, проще единообразно пройти и первые числа тоже.
Я вообще собирался этот кусок на асме под SSE2 переписать, чтобы воспользоваться 768 битным буфером в XMM регистрах и сократить обращения к памяти. Но усилия не стоят выигрыша.
Уход памяти в бесконечность смущает зря, Вы всё равно ограничены разрядностью чисел int64, т.е. чуть менее $2\cdot10^{19}$, для их проверки достаточно первых 203млн простых чисел, т.е. памяти 810МБ хватит с гарантией. Многовато, но не бесконечность.
В п.2. я ведь набросал примерный алгоритм с требованиями к памяти всего лишь $O(N^{\frac{1}{4}})$ - второе вспомогательное решето. С ним всё равно должно быть быстрее вычеркивания кучи составных чисел.
Переход от $k$ к $k+1$ - это интересно! Но думаю невозможно. Простые числа друг с другом не связаны. Или нам пока неизвестна такая связь. Оптимизацией решета (и вообще поиском простых чисел) занимались такие корифеи ... Я в математике не очень силён, потому просто сохраняю jj между сегментами (а оно в конце обработки сегмента как раз готово к обработке следующего) в отдельном массиве (вместе с самими простыми числами), отсюда и удвоение памяти.

[Dmitriy40]

svb в сообщении #912093 писал(а):

Для делителей меньших Nseg это почти обязательно, т.к. с ними связаны основные затраты времени из-за внутренних циклов, к тому же фиксированы затраты памяти. Для делителей больших Nseg отсутствуют внутренние циклы, идет выкидывание не более одного элемента из строящейся решетки

Чисто "ради научного любопытства" решил поверить эту мысль насчёт основных затрат времени, тем более давно хотел оценить выигрыш от реализации своего п.12 выше (это как раз оно и есть). Добавил в свою программу учёт этого времени отдельно и вот результаты для размера сегмента 400000 (мне так удобнее и достаточно близко к вашему):
для чисел около $10^{12}$ на вычёркивание первых 33861 числа тратится 67% общего времени;
для чисел около $10^{13}$ тратится 55% общего времени;
для чисел около $10^{14}$ тратится 36%;
для чисел около $10^{15}$ тратится 18%;
для чисел около $10^{16}$ тратится 9%;
для чисел около $10^{17}$ тратится 3.5%;
для чисел около $10^{18}$ тратится 1.3%.
Видно, что затраты существенны лишь для малых чисел, уже с $10^{15}$ ускорение вычёркивания первых чисел (многократно попадающих в сегмент) заметного выигрыша не даст.
Кроме того, само это ускорение под вопросом, т.к. после оптимизирующего компилятора (человек! ) два цикла отличаются лишь командой сравнения и успешно предсказываемым условным переходом. Всего две команды из десятка, даже исключив их, практически ничего не выиграем, эти команды выполняются параллельно с прочими вычислениями.

В общем для себя понял, что п.12 имеет смысл делать лишь для чисел где-то от $10^{15}$. Но вероятно оно реализуется автоматом в п.9 и п.10.