Конечно, ведь именно это КТО и гарантирует: общее количество допустимых остатков в периоде в точности равно произведению всех таких количеств для каждого простого модуля. Правильно понимаю?
Да. И это вроде несложно доказывается: каждый элемент
из вектора по одному модулю
при добавлении нового взаимнопростого c
(не обязательно простого, достаточно взаимной простоты) модуля
задаётся формулой
и пробегает все возможные остатки по модулю
(это кажется неочевидным, но на то есть теорема, для неё и требуется взаимная простота
и
), из которых лишь
являются разрешёнными, т.е. каждый элемент из исходного вектора даёт ровно
новых элементов (но при разных
). Т.е. перемножение длин.
Простые модули, да ещё и строго последовательные берутся лишь для упрощения, можно брать любые взаимнопростые.
Но (и летом уже говорил об этом) именно внизу, то есть до 7.858e24 их уже будет меньше, не 293 квадриллиона, а в среднем 215.
Да, так. И всё меньше и меньше с каждым новым простым. Вопрос лишь как получить эти 215e15 из всех 15.26e18 (для 71#) не получая даже всех 293.4e15.
Причём в принципе я даже знаю как от 293.4e15 оставить 215e15: для этого достаточно потребовать чтобы на Mx (которое 67#) из формулы выше про КТО умножалось обязательно 0, что возможно только если элемент из x[] (которых 293.4e15) строго равен
любому из элементов y[] (которых 52) и тогда такой x подходит. И здесь даже не обязательно сравнивать все 89 (для 71#) битов полного числа, достаточно сравнить младшие 16 битов (8 скорее всего маловато, да и не вычислить их, не все команды есть байтовые) и только если они совпали (что будет
ошибочным равенством чисел крайне редко) - проверить и остальные биты. А раз нам не нужны старшие биты чисел x[] для сравнения во внутреннем цикле, то и вычислять их тоже можно лишь младшие 16 битов, т.е. КТО для получения 293.4e15 тоже можно считать только младшие 16 битов, параллельно сразу 8-16 чисел (SSE-AVX). Но сравнить-то надо каждый элемент x[] с каждым элементом y[], т.е. 15.26e18 сравнений. Даже если сравнивать сразу 16 чисел (AVX), то это 1e18 операций только сравнения. Или 5e17 тактов, а это уже больше 4 лет в один поток. Плюс сколько они будут вычисляться. И это только по одному простому (71), а хотелось бы и по 40 простым (до 256), это отсеет почти 80% от 293.4e15. Зато матрицу (размерами 293.4e15 на 40) остатков строить не надо, достаточно вектора (длиной 293.4e15). Зато дальше количество сравнений растёт не как произведение, а как сумма: 215e15 надо сравнить с 54 числами от 73, т.е. всего сравнений 293.4e15*52+293.4e15*52/71*54=293.4e15*52*(1+54/71), менее чем вдвое больше. И для простых с 71 до 256 сумма в скобках 32.3 или 4.9e20 операций сравнения, 260 лет в один поток, только сравнений, без КТО. И всего впятеро уменьшение числа 293.4e15. Как-то снова тухло.
Тоже в общем интересная мысль, тоже надо бы додумать и заценить и время поточнее, и может ещё какая идея стукнет.
-- 25.01.2024, 11:52 --Для сравнения: сейчас, получив каким-то образом в AVX регистре 32 остатка по малому простому (до 128), я семью командами за 2.33 такта получаю 32 флага допустимости полученных остатков по данному простому. Т.е. сравнения выполняются со скоростью 14 чисел на такт. Хм, более чем вдвое медленнее 16-ти чисел за полтакта однако! Интересненько ... Ошибся где-то что ли ... Или и правда можно ускорить вдвое, да ещё и отказавшись от проблемной огромной матрицы ... Заманчиво.