кортежи последовательных простых. ключ к 19-252

[Dmitriy40]

gris
Обратный элемент к a по взаимно простому модулю p вычисляется в PARI без циклов: lift(Mod(1/a,p)).

[gris]

Dmitriy40, так и было сказано, но я решил проверить:)
Так интересно, выложены ли векторы где-нибудь? Хотя можно и посчитать...

[Dmitriy40]

gris в сообщении #1699892 писал(а):

Так интересно, выложены ли векторы где-нибудь?

Что за векторы? И зачем их выкладывать если быстрее посчитать заново?

[gris]

Кстати, какая функция даёт скалярное умножение векторов? Типа
[1,2,3]*[3,2,4]=1*3+2*2+3*4=19. Вроде есть такое умножение

[Dmitriy40]

gris в сообщении #1699898 писал(а):

Кстати, какая функция даёт скалярное умножение векторов? Типа
[1,2,3]*[3,2,4]=1*3+2*2+3*4=19. Вроде есть такое умножение

Используйте умножение матриц (вектор-строку на вектор-столбец):

? a=[1,2,3]; b=[3,2,4]; a*b~
%1 = 19

[Yadryara]

Про вычисление обратного элемента именно на PARI легко было найти по запросу "обратный элемент" в сообщениях Дмитрия. Как уже многократно говорилось, нет никакого стёба: очень много инфы для ускорения есть в кортежных темах.

Кстати, выше я приводил результат ускорения. Да, я делал предвычисление по КТО, но обратный элемент не использовал.

[Yadryara]

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

Да, я делал предвычисление по КТО, но обратный элемент не использовал.

Не применяя других идей, а просто расписав эту же идею аккуратнее, снизил время счёта юнита с 2 минут 54 секунд до 1 минуты 57 секунд.

Чтобы убедиться что программа работает правильно, в качестве постоянных остатков взял те которые подходят к максимальной центральной 15-ке в интервале $0-61\#$.

{kort=117201182126413058067773;forprime(p=2,41,
print1("rost",p,"=",kort%p,"; "));}

По этой команде PARI мне сразу напечатал 13 постоянных разрешённых остатков:

rost2=1; rost3=2; rost5=3; rost7=1; rost11=5; rost13=2;
rost17=15; rost19=7; rost23=22; rost29=16; rost31=21; rost37=13; rost41=24;

Вставил их в программу и запустил. Время счёта для этого юнита получилось такое же и все матрёшки, начиная с 9-ки, комп нашёл:

117201182126413058067833: [0,18,24,48,54,60,84,90,108]

117201182126413058067803: [0,30,48,54,78,84,90,114,120,138,168]

117201182126413058067791: [0,12,42,60,66,90,96,102,126,132,150,180,192]

117201182126413058067773: [0,18,30,60,78,84,108,114,120,144,150,168,198,210,228]

117201182126413058067773: [0,18,30,60,78,84,108,114,120,144,150,168,198,210,228]
 8191


1min, 57,327 ms

[Yadryara]

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

до 1 минуты 57 секунд.

Применение идеи Дмитрия (которая минимум дважды публично предъявлялась) вкупе с балансировкой параметра, уменьшило время до 1 минуты 36 секунд.

Итого, пока удалось ускорить в 8.6 раза: $827 sec \to 96 sec$

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

[DemISdx]

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

Применение идеи Дмитрия (которая минимум дважды публично предъявлялась) вкупе с балансировкой параметра, уменьшило время до 1 минуты 36 секунд.

Очень даже не плохо.

(Оффтоп)

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

16.02.25 15:31
...
117874823602517802732361277: [0,6,24,36,66,84,90,104,114,126,150,156,182,204,216,234,240]
valids=14
code=32375
...
end
16.02.25 17:32

Т.е. два часа работало.
Потом по ссылке НМ, опубликованной у нее, на пост Дмитрия, почитал.
Внес изменения. Посчитал снова.

Исправленная версия
16.02.25 18:56
Type ? for help, \q to quit.
Type ?17 for how to get moral (and possibly technical) support.

parisize = 8000000, primelimit = 500000
...
117874823602517802732361277: [0,6,24,36,66,84,90,104,114,126,150,156,182,204,216,234,240]
valids=14
code=32375
...
end
16.02.25 19:12

16-ть минут - это явно быстрее получилось.
Конечно тест не один делался и даже не пять.
К примеру статистика на эту задачу была как:

ID компьютера   40
Время выполнения   1 часов 48 мин. 31 сек.

Но когда это кого волновало???
Как тогда, так и сейчас.
Ехала болела...

Понятное дело, что на быстром компе получается иное соотношение:
для первого варианта, с вставленным замером времени, получается Time: 25min, 27,098 ms
для второго варианта, с вставленным замером времени, получается Time: 2min, 54,611 ms

[Yadryara]

DemISdx, это про какую задачу речь? Только что разговор шёл про поиск центральных 15-к.

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

Например, считать 2-й период 61#. Центральных 15-к там конечно заметно меньше, не 1147 как в первом периоде, а примерно 785, но зато почти все найденные будут новыми.

Ну или можно посчитать 62-й период 59#.

[DemISdx]

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

DemISdx, это про какую задачу речь?

Мне казалось вполне очевидно, что раз это середина февраля, то это значит, что это самое первое приложение...

[Yadryara]

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

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

Ну вот появилась. Она не принципиально новая, но в сочетании с другой дала-таки некоторый эффект.

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

1 минуты 36 секунд.

Ныне комп укладывается на разных юнитах в 88-89 секунд. Итого, ускорение в 9.2 раза.

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

[Yadryara]

gris в сообщении #1699564 писал(а):

Но я в ней не разбирался подробно, надеясь, что это сделают более опытные товарищи.

Ваша надежда сбылась. Разобрались и ускорили в 9 раз. Не прибегая к другим языкам программирования, оставаясь в рамках вашего любимого PARI. Теперь ответите на мои вопросы?

[maxal]

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

Обратный элемент к a по взаимно простому модулю p вычисляется в PARI без циклов: lift(Mod(1/a,p)).

Чуть быстрее будет: gcdext(a,p)[1]

[Dmitriy40]

maxal в сообщении #1700326 писал(а):

Чуть быстрее будет: gcdext(a,p)[1]

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

-- 31.08.2025, 19:04 --

Не сильно оно быстрее:

? forprime(p=11,1e9, x=lift(Mod(1/7,p)));
time = 17,801 ms.
? forprime(p=11,1e9, x=gcdext(7,p)[1]);
time = 14,556 ms.
? z=nextprime(1e9)
%1 = 1000000007
? forprime(p=11,1e9,x=lift(Mod(1/p,z)));
time = 25,553 ms.
? forprime(p=11,1e9,x=gcdext(p,z)[1]);
time = 21,545 ms.