Научный форум dxdy

Математика, Физика, Computer Science, Machine Learning, LaTeX, Механика и Техника, Химия,
Биология и Медицина, Экономика и Финансовая Математика, Гуманитарные науки




На страницу Пред.  1, 2, 3, 4
 Re: У квадруплета есть центр может кому интересно.
Dmitriy40 в сообщении #1738166 писал(а):
Ну то есть по факту нет никакого выигрыша, всё равно надо проверять простые до корня.
А то что можно проверять лишь одним делением вместо деления каждого из чисел кортежа - это не то чтобы прям очевидно, но и не является каким-то секретом.

То, что разных способов всяких навороченных полно, никто не спорит, смысл не столько в скорости, сколько бог на него тут показываю, что с ростом интервалы близнецы не становятся меньше, а их количество растёт, потому что появление блокеров растёт намного меньше, чем кандидатов, и чем больше интервал, тем больше близнецов, это позволяет сделать лему о наличии близнец на интервале, хотя, наверное, подобного также много, но то подобное, а это просто моё наблюдение, да, фактически вы правы, бьём до корня, но только сразу 2 числа, а не одно, не знаю, очевидно нет, в выигрыше, но должно одно число до корня или сразу 2 тоже до корня, а об экономичности для больших свои методы, как я и не собирался бить рекорды числа больших величин, больше моей задрыпаной 100 миллионов в интернете пруд пруди, и говорит вот нашли все 1005 до. Не имеет просто смысла, смысл в постоянном росте таких чисел, а не в их длине, и то, что блокеры до 4-ой степени явно снижают количество блокеров, это факт, и факт необходимый... для.

 Re: У квадруплета есть центр может кому интересно.
Dmitriy40 в сообщении #1738166 писал(а):
А то что можно проверять лишь одним делением вместо деления каждого из чисел кортежа - это не то чтобы прям очевидно, но и не является каким-то секретом.

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

 Re: У квадруплета есть центр может кому интересно.
wrest в сообщении #1738171 писал(а):
Я вот не припомню, чтобы хоть где-то в наших кортежных темах явно применялось пробное деление для проверки на простоту.
Мои ускорители для пентадекатлона и прочих (и кортежей типа 19-252) с 2022г именно так и работают. Правда там оптимизация пошла сильно дальше и деления заменены на векторные сложения по модулю, но принцип проверок на малые простые для удаления составных чисел остался.

 Re: У квадруплета есть центр может кому интересно.
Dmitriy40 в сообщении #1738175 писал(а):
Правда там оптимизация пошла сильно дальше и деления заменены на векторные сложения по модулю, но принцип проверок на малые простые для удаления составных чисел остался.

Ну это-то понятно. Я имел в виду нашу суету вокруг pari/gp, а внутри pari/gp от же ispseudoptime(n,0) производит проброе деление:
Код:
#ifdef LONG_IS_64BIT
  /* 16294579238595022365 = 3*5*7*11*13*17*19*23*29*31*37*41*43*47*53
   *  7145393598349078859 = 59*61*67*71*73*79*83*89*97*101 */
  if (!iu_coprime(N, 16294579238595022365UL) ||
      !iu_coprime(N,  7145393598349078859UL)) return 0;
#else
  /* 4127218095 = 3*5*7*11*13*17*19*23*37
   * 3948078067 = 29*31*41*43*47*53
   * 4269855901 = 59*83*89*97*101
   * 1673450759 = 61*67*71*73*79 */
  if (!iu_coprime(N, 4127218095UL) ||
      !iu_coprime(N, 3948078067UL) ||
      !iu_coprime(N, 1673450759UL) ||
      !iu_coprime(N, 4269855901UL)) return 0;
#endif

То что вы на праймориальных колёсах ездите в ваших ускорителях, конечно можно назвать и "пробным делением", но все-таки это другое. По крайней мере не то, что я имел в виду, говоря что
wrest в сообщении #1738171 писал(а):
не припомню, чтобы хоть где-то в наших кортежных темах явно применялось пробное деление

:D

 Re: У квадруплета есть центр может кому интересно.
wrest в сообщении #1738179 писал(а):
То что вы на праймориальных колёсах ездите в ваших ускорителях, конечно можнотназвать и "пробным делением", но все-таки это диугое.
В первых версиях было именно деление, только потом оптимизировал.
А праймориалы используются лишь по причине удобства - сразу гарантируют взаимную простоту модулей для КТО, не надо каждый раз об этом заботиться.

-- добавлено через 25 минут --

wrest в сообщении #1738171 писал(а):
Я вот не припомню, чтобы хоть где-то в наших кортежных темах явно применялось пробное деление для проверки на простоту.
И всё же было:
Dmitriy40 в сообщении #1623573 писал(а):
Плюс я перед первой ispseudoprime проверяю ещё несколько десятков простых модулей начального числа x командой for(j=npr+1,#pr, if(!setsearch(m[j],x%pr[j]), next(2)); );, это ускоряет с 30с до 21с.
Dmitriy40 в сообщении #1606993 писал(а):
Вот кстати, увеличив массив m[] до 2^9 (дальше заметного выигрыша уже нет) и добавив перед проверкой цепочки ещё одну предпроверку
forprime(p=67,#m, if(!setsearch(m[p],x%p), next(2)); );
можно ускорить программу с 5м11с до 1м4с, почти впятеро!

Это именно что пробное деление и проверка остатка на допустимость по списку. Если остаток недопустим, то одно из чисел кортежа не простое.

 [ Сообщений: 50 ]  На страницу Пред.  1, 2, 3, 4


Соглашение о конфиденциальности | Общие правила

Powered by phpBB © 2000, 2002, 2005, 2007 phpBB Group