Как писать быстрые программы

[wrest]

Yadryara в сообщении #1722112 писал(а):

Не только вероятность, но и скорость увеличивается.

Это почти одно и то же :) Если верятность найти цепочку больше, то цепочки попадаются чаще -> скорость больше.

[Yadryara]

wrest в сообщении #1722113 писал(а):

Это почти одно и то же :) Если верятность найти цепочку больше, то цепочки попадаются чаще -> скорость больше.

Нет, не всегда! То-то и оно, что сейчас как раз не так:

Yadryara в сообщении #1722112 писал(а):

Даже несмотря на то, что интервал (а значит и среднее число цепочки) вырос на два порядка, серия с одним простым опять выиграла у всех остальных.

Вы понимаете что вероятность того, что примерно 30-35-значное число — простое, гораздо ниже той, при котором это число оказывается либо произведением двух (pq), либо трёх простых чисел в первых степенях (pqr).

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

[wrest]

Yadryara в сообщении #1722116 писал(а):

Вы понимаете что вероятность того, что примерно 30-35-значное число — простое, гораздо ниже той, при котором это число оказывается либо произведением двух (pq), либо трёх простых чисел в первых степенях (pqr).

Нет, не понимаю, нужна отдельная тема, не эта

[Dmitriy40]

Yadryara в сообщении #1722089 писал(а):

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

Как раз очень даже существенно: одно дело оптимизировать данный алгоритм на всё том же PARI и совсем другое дело написать новый алгоритм на асме/C. Это очень сильно разные задачи. И оптимизироваться по скорости они тоже будут очень разными методами/подходами, вот совсем разными.

Yadryara в сообщении #1722089 писал(а):

Существенно: сравнивать скорости программ на одном и том же компе и в одном потоке.

И это тоже ограничивает простор фантазии: у моих программ скорость может расти нелинейно с ростом количества потоков выполнения (не хватает на все потоки трафика кэша L3 и памяти и суммарная скорость падает). А уж про глюки своеобразность PARI в многопотоке я уже всем уши прожужжал. Потому если оптимизировать под многопоточность, то решения могут быть другими, по итогу более медленными в один поток, но быстрее суммарно в много потоков. Это конечно усложняет разработку и тестирование, но просто напоминаю что скорость однопотока - не догма и не факт что это лучше всегда. Да, ради простоты сначала оптимизируется однопоток, а потом ломаем голову как улучшить и многопоток тоже, но не всегда так, я часто пишу изначально под многопоток (даже если тестирую в однопотоке, в частности корректность, но методы/алгоритмы разрабатываю именно под многопоток, даже ценой замедления однопотока).

Yadryara в сообщении #1722089 писал(а):

Любые 100 штук D(24,>=6).

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

Yadryara в сообщении #1722089 писал(а):

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

Очевидно что написанная на нормальном компилируемом языке (например С) программа будет быстрее программы на PARI. А написанная на асме - скорее всего ещё быстрее. Мне просто лень на асме писать свою библиотеку работы с длинными числами (а конкретно операцию умножения по модулю больше 2^64 для isprime), но по идее можно воспользоваться готовыми библиотеками (или выдрать кусок кода из исходника PARI). Но методы оптимизации под AVX (асм или C) кардинально отличаются от методов оптимизации под PARI и потому смена языка - существенно!

Yadryara в сообщении #1722089 писал(а):

Вполне можно уточнить у автора.

Вот это и бесит, что автор поленился сразу указать существенные моменты и провоцирует на дополнительные вопросы. Да, можно и уточнить. А можно было подумать и написать всё важное сразу. Тут не чат, диалоги затягиваются на часы и дни, пока переуточнишь всё важное - проще самому додумать за автора (и не факт что правильно!) и уже 5 раз решить задачу, чем переспрашивать "а что тут имел в виду? а тут? а вот тут?".

Yadryara в сообщении #1722112 писал(а):

Я исхожу из того что это ещё не сделано. По крайней мере, в законченном удобоваримом виде я этого вроде не видел.

Чем не устраивает оценка по HL1, Вами же и доработанная до интеграла от и до? Поделить интеграл на длину отрезка интегрирования для получения средней плотности на интервале умеет даже младший школьник. Для не слишком длинных паттернов и не слишком разреженных оно работает хорошо.
UPD: А, стоп, торможу: в HL1 же про простые, а тут про количество делителей.

[wrest]

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

лень на асме писать свою библиотеку работы с длинными числами (а конкретно операцию умножения по модулю больше 2^64 для isprime), но по идее можно воспользоваться готовыми библиотеками (или выдрать кусок кода из исходника PARI).

Из pari выдрать не выйдет: они сами используют для длинной арифметики GMP.

[Dmitriy40]

wrest в сообщении #1722139 писал(а):

Из pari выдрать не выйдет: они сами используют для длинной арифметики GMP.

Вы это уже говорили и я даже отвечал: выдрать вместе с GMP (если в GMP нет готовой ispseudoprime). Насколько я понимаю, для работы с длинными числами от ОС надо всего две функции, выделения и освобождения памяти, всё остальное делается внутренними функциями, это нетрудно переделать под любой API и любую ОС.

[wrest]

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

Насколько я понимаю, для работы с длинными числами от ОС надо всего две функции, выделения и освобождения памяти, всё остальное делается внутренними функциями, это нетрудно переделать под любой API и любую ОС.

GMP это "низкоуровневая" библиотека, она собирается под конкретный набор команд, размер кэшей конкретной архитектуры cpu и проч. Ну, не буду настаивать. Выдрать так выдрать.
В pari есть и своя библиотека, но её производительность хуже чем GMP.

[Yadryara]

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

Как раз очень даже существенно:

Вы похоже всё-таки не понимаете что я имел в виду, когда говорил что существенно, а что нет. Я смотрел со стороны заказчика, а не программиста. Вот примерный диалог между ними:

— Тебе какая программа нужна?
— Та, которая будет быстро находить вот такие-то кортежи.
— А какими по величине эти кортежи должны быть?
— Несущественно. Скажем, не более чем 100-значными.
— А на каком языке программа должна быть написана?
— Несущественно. Лишь бы она у меня быстро работала.
— А по какому алгоритму она должна работать, поиск осуществлять по паттернам?
— Несущественно, я хочу чтобы программа кортежи быстрее искала и находила. То есть такую программу, у которой выше именно скорость нахождения кортежей.

Вы ещё не прокомментировали ваш счёт. Я правильно понял, что с подъёмом в горы средняя скорость нахождения, не упала, а наоборот пока что возросла с 16 до 20 кортежей в час?

[Dmitriy40]

Yadryara в сообщении #1722157 писал(а):

Вы похоже всё-таки не понимаете что я имел в виду, когда говорил что существенно, а что нет. Я смотрел со стороны заказчика, а не программиста. Вот примерный диалог между ними:

Хорошо, на это ответ простой: писать надо не на PARI. И оптимизировать тоже не на PARI. На асм не настаиваю, кто-то и на C неплохо пишет. А лучше всего - под конкретную аппаратуру заказчика (например вдруг у него GPU есть хороший или он согласен такой купить под эту задачу).

А наилучшее решение будет - взять мою таблицу (если там есть 100 кортежей, я не считал) и просто выдать их на экран из вектора. Мгновенно! Скорость - наивысшая (ограничивается лишь скоростью вывода на экран или записи в файл, надеюсь хоть это не надо будет оптимизировать по скорости)! И строго согласно Вашим условиям! Вам такую программу сделать? А сами что, не можете написать print([...]) с вектором из 100 значений?

Yadryara в сообщении #1722157 писал(а):

Вы ещё не прокомментировали ваш счёт. Я правильно понял, что с подъёмом в горы средняя скорость нахождения, не упала, а наоборот пока что возросла с 16 до 20 кортежей в час?

У меня не было отметок времени для каждого кортежа и даже для их групп. Трижды заметил (до 1млрд, до 34млрд, до 110млрд) и всё. И учитывая неравномерность появления кортежей по интервалу меня скорость кортежей не интересует. Потому как мог я уже ответил на Ваш вопрос. Вы можете сами проверить гипотезу о поведении средней скорости - взять показанный код и запустить его в разных диапазонах (после незначительной доработки для измерения скорости) и самостоятельно получить ответ на свой вопрос. И это всяко быстрее чем ждать комментария на форуме от меня.

[Yadryara]

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

Вам такую программу сделать? А сами что, не можете написать print([...]) с вектором из 100 значений?

Риторические вопросы?

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

И это всяко быстрее чем ждать комментария на форуме от меня.

А при чём тут быстрее? Я хотел обратить ваше внимание, что не всё так просто — произошло не замедление, а наоборот ускорение.

Потому что повыше нашлось гораздо больше кортежей в пересчёте на тот же интервал натурального ряда. И, скорость, то есть количество найденных на временной интервал — тоже больше. Можно ещё так посчитать:

      Счёт     Найдено      Время       Скорость
      * e9     D(24,6)      часов    D(24,6)/час
   0 —  34         112          7             16
  34 — 110         439         20             22
________________________________________________
   0 — 110         551         27             20

[Dmitriy40]

Yadryara в сообщении #1722169 писал(а):

Потому что повыше нашлось гораздо больше кортежей в пересчёте на тот же интервал натурального ряда.

Не вижу такого, по моему всё в пределах флуктуаций (количество найденных кортежей в каждом интервале 10млрд): [36, 51, 53, 48, 41, 48, 56, 46, 58, 59, 56].

Yadryara в сообщении #1722169 писал(а):

Я хотел обратить ваше внимание, что не всё так просто — произошло не замедление, а наоборот ускорение.

Тоже не вижу (время нахождения 5 указанных кортежей):

1029227571: [24, 24, 24, 24, 24, 24], len=6
1112348572: [24, 24, 24, 24, 24, 24], len=6
1460211423: [24, 24, 24, 24, 24, 24], len=6
1594708575: [24, 24, 24, 24, 24, 24], len=6
1770953820: [24, 24, 24, 24, 24, 24], len=6
time = 5min, 38,257 ms.
10091010975: [24, 24, 24, 24, 24, 24], len=6
10091824223: [24, 24, 24, 24, 24, 24], len=6
10427933723: [24, 24, 24, 24, 24, 24], len=6
10494693724: [24, 24, 24, 24, 24, 24], len=6
10537749339: [24, 24, 24, 24, 24, 24], len=6
time = 4min, 58,836 ms.
100064895324: [24, 24, 24, 24, 24, 24], len=6
100074663772: [24, 24, 24, 24, 24, 24], len=6
100350841883: [24, 24, 24, 24, 24, 24], len=6
100506378464: [24, 24, 24, 24, 24, 24], len=6
100566237650: [24, 24, 24, 24, 24, 24], len=6
time = 7min, 20,423 ms.
1000149971049: [24, 24, 24, 24, 24, 24], len=6
1000421334472: [24, 24, 24, 24, 24, 24], len=6
1001305010848: [24, 24, 24, 24, 24, 24], len=6
1001984047323: [24, 24, 24, 24, 24, 24], len=6
1001988092959: [24, 24, 24, 24, 24, 24], len=6
time = 40min, 34,706 ms.

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

[Yadryara]

Dmitriy40

Ещё раз. В таблице которую я привёл, есть какая-то ошибка? За первые 7 часов нашлось 112 кортежей, а за последующие 20 часов — 439 кортежей?

[Dmitriy40]

Yadryara
В таблице вероятно (проверять не буду) ошибок нет.
Выводы из неё сделаны поспешные недостаточно обоснованные.
Потому что я привёл примеры его опровергающие.

[Yadryara]

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

В таблице вероятно (проверять не буду) ошибок нет.

Почему не будете?? Это же очень просто.

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

Потому что я привёл примеры его опровергающие.

Не вижу опровержения, а, наоборот, вижу подтверждение:

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

(количество найденных кортежей в каждом интервале 10млрд): [36, 51, 53, 48, 41, 48, 56, 46, 58, 59, 56].

Очень легко посчитать и общее количество и среднее количество в интервале:

? vecsum ([36, 51, 53, 48, 41, 48, 56, 46, 58, 59, 56])
%1 = 552

? vecsum ([36, 51, 53])/3 + .
%2 = 46.666666666666666666666666666666666667

? vecsum ([48, 41, 48, 56, 46, 58, 59, 56])/8 + .
%3 = 51.500000000000000000000000000000000000

Прекрасно же видно, что во второй части в среднем находится заметно больше кортежей. Ну можно ещё чуть по-другому разбить:

?  vecsum ([36, 51, 53, 48])/4 + .
%4 = 47.000000000000000000000000000000000000

? vecsum ([41, 48, 56, 46, 58, 59, 56])/7 + .
%5 = 52.000000000000000000000000000000000000

[Dmitriy40]

Yadryara
Посчитайте дальше 110e9, здесь всё ещё начальные флуктуации. Уже на 1трлн плотность падает вчетверо!
И работает в 8 раз медленнее (40 мин против 5 мин).