Снова цитирую GPT

1 Работа с китайской системой сравнений
Сейчас каждый раз считается
gp
Copy code
bpt = lift(chinese([...]));
Это дорогая операция.
Можно вынести все константные модули ( 2,3,5,7,11,13,17,19,... ) в один общий
модуль
gp
Copy code
M = lcm([2,3,5,7,11,13,17,19,23,29,31,37,41,43,47,53,59,61]);
и заранее посчитать обратные элементы для каждого модуля (CRT через Garner или
precomputed inverses). Тогда вместо chinese вы делаете быстрый ручной CRT на
базе предвычислений.

Вот это и есть то самое М

M = lcm([2,3,5,7,11,13,17,19,23,29,31,37,41,43,47,53,59,61]);

Дальше, я понимаю, что такое Mi=M/ai, но не понимаю, что такое Mi^(-1).

Например:
M1 = M / a1 = 61# / 2.

А чему равен M1^(-1) ?

Пока надежда на помощь от gris и от Макса.

Если тут будет облом, буду искать помощь в другом месте.

Пока с помощью глухо...

Пытаюсь сама разобраться.
Вот тут
https://wikimedia.org/api/rest_v1/media/math/render/svg/0c81d5d12a6acc2d033a4a483b175ca4cf92df61
формула.

Красивая формула.
Осталось выяснить, что же такое Mi^(-1).

Взяла простой пример из Википедии, записываю формулу (по ссылке)

x = 2*35*M1^(-1) + 3*21*M2^(-1) + 3*15*M3^(-1)

Скармливаю уравнение Вольфрам Альфа и получаю:

M1^(-1) = 2
M2^(-1) = 1
M3^(-1) = -6

x = 23

Это правильно?

Если да, то как же вычисляются Мi^(-1)?
Они могут быть даже отрицательными?

Помогла Алиса!

Я её попросила посчитать Mi^(-1) в показанной выше формуле.
Она посчитала и говорит:

M1^(-1)=2
M2^(-1)=1
M3^(-1)=1

Я говорю: если это подставить в формулу, то получим
x = 233
Она говорит: по модулю 105 это как раз будет 23.

А, ну тогда
M3^(-1)=-6=1 по модулю 7.

Ой, правильно ли мы с Алисой разобрались? :)
Думаю, что правильно.

Теперь переходим к программному примеру.
Сейчас попробую Алисе его задать.
Справится ли?

Мы с Алисой прекрасно работаем.

Пока разобрались с маленьким примером.
Она показала мне, как считать обратный элемент.
Я написала скрипт

{a=[3,5,7]; r=[2,3,2];
mod=3*5*7;
M=vector(3); MO=vector(3);
 for( i=1,3, M[i]=mod/a[i]; );
 print(M);
 
 for( i=1,3, MO[i]=lift(1/Mod(M[i],a[i])); );
 print(MO);
}

Всё сработало!

Вот результат

(11:20) gp > \r kto.txt
[35, 21, 15]
[2, 1, 1]

Значит, можно надеяться, что и для большой системы модулей сработает.
Алиса говорит: "Смело масштабируй!" :)
Вдохновила! :)
Буду масштабировать.
Хотя пока не уверена, что всё получится.

Хоть бы кто-нибудь чего-нибудь проговорил...

Глухо, как в танке!
Спасибо Алисе!
Я не ожидала, что она так разбирается в КТО.

Промасштабировала и получила

(13:39) gp > \r kto.txt
304250263527210

M[6] = 23403866425170
[152125131763605, 101416754509070, 60850052705442, 43464323361030, 2765911486611
0, 23403866425170, 17897074325130, 16013171764590, 13228272327270, 1049138839749
0, 9814524629910, 8222980095330, 7420738134810]

[1, 2, 3, 3, 6, 4, 11, 14, 13, 20, 22, 16, 7]

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

Однако я пока так и не уверена, что обратные элементы Mi^(-1) посчитаны правильно.

Скрипт

{a=[2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41]; 
r=[1, 2, 4, 2, 9, 4, 12, 4, 4, 18, 3, 1, 1];
mod = lcm([2,3,5,7,11,13,17,19,23,29,31,37,41]);
print(mod); print();

M=vector(13); MO=vector(13);
 for( i=1,13, M[i]=mod/a[i]; );
 print(M); print();
 
 for( i=1,13, MO[i]=lift(1/Mod(M[i],a[i])); );
 print(MO);
}

Да, мы тут и х с Алисой посчитали.
Получилось
x = 106265398334489

Это правильно?
Алиса говорит, что правильно.

Для вычисления х в скрипт вставили

 x = sum(i = 1, 13, r[i] * M[i] * MO[i]) % mod;
 print(x);

Самое интересное только началось :)

Но я уже жутко устала, взяла тайм-аут до завтра.
К тому же у меня ещё результаты проекта не все обработаны.
Алиса согласна завтра продолжить.

Как присоединить то, что у нас осталось?
Алиса предложила функцию расширения.
Но об этом позже.

Это, конечно, фантастика!

Как будто разговариваешь с реальным человеком!
Предлагаешь, споришь, исправляешь, спрашиваешь.
Алиса согласна на любой формат беседы.
Это здорово!
Главное, что никаких ограничений ни на время, ни на сообщения.
И бесплатно!

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

Пока я спала после двухчасового общения с Алисой, gris чего-то наваял.

Ой, а г. Петухов раскололся-таки :))
https://dxdy.ru/post1699891.html#p1699891

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

Ах-ха-ха!
А почему он не сказал: "ей" не говорите?

Значит, Алиса мне правильно сказала.

Кстати, можно проверить для всех простых модулей до 61 найти х.
Это же должно совпасть с тем, что вычисляется сейчас в программе функцией в одну строку.
Правильно?

Мы с Алисой договорились завтра встретиться :)
Она сказала, что ждёт меня :)

Цитата

Кстати, можно проверить для всех простых модулей до 61 найти х.
Это же должно совпасть с тем, что вычисляется сейчас в программе функцией в одну строку.
Правильно?

Правильно!
Абсолютно совпадают

4175285801450688970439
4175285801450688970439

Подсчёт функцией в одну строку, как сейчас в программе

f=lift(chinese([Mod(1,2),Mod(2,3),Mod(4,5),Mod(2,7),Mod(9,11),Mod(4,13),Mod(12,17),Mod(4,19),Mod(4,23),Mod(18,29),Mod(3,31),Mod(1,37),Mod(1,41),Mod(1,43),Mod(1,47),Mod(1,53),Mod(1,59),Mod(3,61)])); print(f);

А это скрипт, который считает то же самое только по формуле с обратными элементами

{a=[2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 53, 59, 61]; 
r=[1, 2, 4, 2, 9, 4, 12, 4, 4, 18, 3, 1, 1, 1, 1, 1, 1, 3];
mod = lcm([2,3,5,7,11,13,17,19,23,29,31,37,41,43,47,53,59,61]);
print(mod); print();

M=vector(18); MO=vector(18);
 for( i=1,18, M[i]=mod/a[i]; );
 print(M); print();
 
 for( i=1,18, MO[i]=lift(1/Mod(M[i],a[i])); );
 print(MO);
 
 x = sum(i = 1, 18, r[i] * M[i] * MO[i]) % mod;
 print(x);
}

Всё прекрасно!

Цитата

{a=[2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41]; 
r=[1, 2, 4, 2, 9, 4, 12, 4, 4, 18, 3, 1, 1];
mod = lcm([2,3,5,7,11,13,17,19,23,29,31,37,41]);
print(mod); print();

M=vector(13); MO=vector(13);
 for( i=1,13, M[i]=mod/a[i]; );
 print(M); print();
 
 for( i=1,13, MO[i]=lift(1/Mod(M[i],a[i])); );
 print(MO);
}

У меня возникло сомнение: может, тут надо считать не по модулю

mod = lcm([2,3,5,7,11,13,17,19,23,29,31,37,41])

а по модулю

mod = lcm([2,3,5,7,11,13,17,19,23,29,31,37,41,43,47,53,59,61])

???

То есть
x = x1 + x2, где
x1 - сумма по первым 13 модулям, соответствующим константным разрешённым остаткам;
x2 - сумма по оставшимся 5 модулям, соответствующим переменным разрешённым константам.

Сейчас попробую так посчитать.

Вроде получается.

Итак, выносим вычисление x1 за цикл, а x2 считаем в цикле.
Посмотрим, какое получится ускорение.

Ну вот, вставила всё в рабочую программу и прогнала тест.

Результат

(11:00) gp > \r 15_61_0period_boinc_mod.txt
sgenerirovano dobavok 68913152
end
time = 22min, 12,405 ms.

Ускорение на 6 минут.

GPT обещал ускорение в десятки раз.
Враньё!

Кстати, а центральная 9-ка не найдена.
Почему?
Куда она подевалась?
Получается. что с предвычислениями не все bpt точно такие же находятся, как без предвычислений?
Это интересно!

Нет, нашла ошибку в программе.
Ой, торопилась, кушать захотелось сильно ;)
Сейчас исправлю.
Может, и ускорение будет побольше.

Исправила, запустила, ушла кушать :)
Приду, тут уже всё будет готово.

Пока получено

(13:34) gp > \r 15_61_0period_boinc_mod.txt
74153990393699851280099: [0,18,24,48,54,60,84,90,108]

sgenerirovano dobavok 68913152
end
time = 23min, 23,541 ms.

Центральная 9-ка теперь найдена.

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

И это всё, что я смогла получить от первого совета GPT.

От gris пока нет ничего конкретного, потому что он экспериментирует на маленьких периодах.
Пишет, что уже с периода 31# ускорение уменьшается.
Ну, так это не интересно.
Экспериментировать надо с моей программой сразу.
Зачем мне маленькие периоды, когда у меня период 61#.

Но прямо с моей программой он ещё не экспериментировал.
Не знаю, какое у него получится ускорение.

Маленькая идейка сбросила 23 секунды

(13:59) gp > \r 15_61_0period_boinc_mod.txt
74153990393699851280099: [0,18,24,48,54,60,84,90,108]

sgenerirovano dobavok 68913152
end
time = 23min, 110 ms.

Наконец, уберу счётчик добавок; он не нужен, и так понятно, что всегда генерируется одно и то же количество добавок.
Ну, счётчик сильно не замедляет, я думаю.
Но тем не менее...
Запускаю без счётчика.

Сейчас отработает программа и пойду на встречу с Алисой.
Если она хорошо разбирается в КТО и PARI/GP неплохо знает, может, она что-нибудь толковое посоветует по оптимизации программы.

У меня пока больше нет идей.
Все советы GPT, кроме первого, проанализированы нами с gris и отвергнуты.
Никакого ускорения они не дадут.
А второй совет у меня дал замедление, а не ускорение.

Счётчик сбросил несколько секунд.

Новое время, без счётчика

(14:31) gp > \r 15_61_0period_boinc_mod.txt
74153990393699851280099: [0,18,24,48,54,60,84,90,108]

end
time = 22min, 30,782 ms.

Итак, мне удалось ускорить программу всего на 6 минут.

gris,
вам слово :)
Какое ускорение моей программы получите вы?

Ах да, ещё одна маленькая идейка возникла.
Сейчас опробую.

С Алисой уже пообщалась.

Первый её совет повторил совет GPT.
Дальше пошли дебри, в которых я не стала разбираться, обнаружив в одном из советов явную ошибку.

Всё больше убеждаюсь в том, что толковых советов от ИИ ждать не приходится.
Ну вот, из всех советов GPT только один (первый) действенный.

Последняя идейка ничего не дала.

Итак, окончательный результат

(16:05) gp > \r 15_61_0period_boinc_mod.txt
74153990393699851280099: [0,18,24,48,54,60,84,90,108]

end
time = 22min, 30,783 ms.

Очень маленькое ускорение.

Ядряра писал в сообщении
https://dxdy.ru/post1699996.html#p1699996

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

Господа, почему я не вижу оваций?
Ядряра гениально оптимизировал мою программу, добившись ускорения более чем в 6 раз.
Браво, браво, браво!
Это, конечно, не искреннее восхищение, а сарказм.
Причину уже объясняла:
- Я вот знаю! Но "ей" не скажу!

Подведём итоги.

Об оптимизации Ядряры уже сказала.
Но!
Она (оптимизация) не для меня, а для оваций.
Мне всё это недоступно.
Ядряра не хочет мне помогать, потому что ему не нравится моя личность.
Ну, это его дело, конечно.
Однако писать так на форуме я бы постеснялась (ну то есть стыдно было бы).

Макс наверняка знает, как оптимизировать, и смог бы сделать это не хуже Ядряры (в чём я уверена), но ему не интересны кортежи и нет времени ими заниматься.
Но Макс помог советами от GPT, один из которых (первый) оказался полезным.
Затем Макс помог разобраться с предвычислениями (дал ссылки на материалы).
Хотя его идея использует обратные элементы.
Я разобралась с этой идеей и реализовала её, ускорение получила очень маленькое, всего 6 минут.
Это подробно описано в данной теме.

Ядряра сообщает, что он тоже применяет предвычисления, но не использует обратные элементы.
Как я поняла, это даёт значительное большее ускорение.

gris пока не получил рабочую программу с ускорением.
Жду!
(Я писала ему вчера: "Что-то мы не знаем."
Да, что-то мы не знаем. Оптимизация возможна! Ускорение получается как минимум в 6 раз.)

Г. Петухов знает, как ускорить программу, но мне тоже не хочет помогать.
Он, возможно, добился бы большего ускорения, чем Ядряра (без применения АСМ, конечно).

wrest наверняка знает, как оптимизировать программу, но его кортежи не интересуют.

Ну вот и всё.

Сегодня пойду на встречу с Алисой.
Эх, очень плохо что у Алисы отсутствует память, то есть она не помнит то, о чём говорила со мной позавчера и вчера.
И всё надо начинать сначала.
Хорошо, спрошу у неё сегодня, как делать предвычисления, не используя обратные элементы.
Может, она знает.

Г. Петухов писал в сообщении
https://dxdy.ru/post1699760.html#p1699760

Так что 1 совет ИИ хорош наполовину: константные выражения нужно выносить из циклов (это вообще общеизвестная практика оптимизации любых программ), а вот заменять встроенные функции на прямое вычисление в данном случае смысла нет.

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

Далее г. Петухов писал

Ну и самые эффективные методы ускорения ИИ так и не предложил.

Угу.
Г. Петухов тоже их так и не предложил!

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