поиск попарных НОДов

[sundayafternuun]

товарищи! спасибо за советы всем! для 5000 длинных чисел поиск в лоб действительно не долгий. но дело в том что в перспективе количество чисел может возрасти чуть ли не в 100 раз. и тогда временные затраты уже будут существенными.
VAL, какую длину имели сгенерированные вами числа?

[ИСН]

Если чисел много, то их попарных НОДов - многажды много, так что выписывать замучаешься, если бы даже их вычисление доставалось даром. Они Вам точно все нужны?

[sundayafternuun]

действительно именно это и нужно.
ну а если упростить задачу до проверки пар этих чисел на взаимную простоту? как это сделать максимально быстро?

[VAL]

sundayafternuun в сообщении #635389 писал(а):

VAL, какую длину имели сгенерированные вами числа?

150 десятичных знаков.
Вот код:

> r:=rand(10^149..10^150):
> tt:=proc() local i,j;
> for i to 5000 do a||i:=r() od;for i to 4999 do
> for j from i+1 to 5000 do
> igcd(a||i,a||j);
> od od end:
> time(tt());

                               138.312

[Cash]

sundayafternuun в сообщении #635401 писал(а):

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

Проверяете на малые делители, скажем первые 50 простых чисел. Результат записываете в битовый массив. Это значительно сузит список кандидатов. Далее Евклид.

[ИСН]

Ни черта это не сузит. Вернее, сузит список НОДов, отличных от единицы. А толку-то? Каждый из них всё равно придётся находить, и единицы тоже.

[Cash]

Мы будем проверять только пары, не имеющие общих малых простых делителей. Эффект безусловно будет. Ну, например, зачем искать НОД у четных чисел, если нам только нужно знать взаимно просты они или нет?

-- Чт окт 25, 2012 12:22:19 --

Цитата:

Вернее, сузит список НОДов, отличных от единицы

Этого и добиваемся.
Еще раз цитирую задачу:

Цитата:

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

[ИСН]

Да, эффект будет, но слабенький - не в разы. Ведь примерно 61% пар не имеют никаких общих делителей, ни больших, ни малых. Их не удастся отсечь Вашим просеиванием, и придётся прокатывать Евклидом всё равно.

[Cash]

Примерно так, это верно. А я и не обещал многократного сокращения. Полную гарантию взаимной простоты может дать только честное вычисление НОД. А после просеивания практически каждое применение Евклида будет давать единицу.
Кстати, Евклида можно остановить будет чуть раньше. Особенно, если предварительно проверить числа на простоту. Это тоже может дать 5-10% выигрыша.
Да, и, наверное, для таких больших чисел бинарный поиск НОД эффективнее будет?

[sundayafternuun]

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