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

[sundayafternuun]

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

[VAL]

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

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

Если чисел действительно много, а размеры относительно невелики, возможно эффективно будет искать НОДы через каноническое разложение.

[sundayafternuun]

забыл сказать, что числа весьма большого размера

[VAL]

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

забыл сказать, что числа весьма большого размера

А точнее?
Сколько чисел и какого порядка?

[Cash]

Если у нас есть $N$ чисел, ограниченных величиной $S$, то примерные оценки таковы
Алгоритм Евклида: $C\log{S} \cdot N^2$
Разложение на простые множители: $C_1\log{\log{S}} \cdot N^2+C_2 N S^{\alpha}$, где $ \alpha \in [0.15, 0.5]$ зависит от алгоритма разложения на множители

-- Ср окт 24, 2012 11:03:55 --

(Оффтоп)

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

[sundayafternuun]

около 5 тысяч чисел. длина числа в среднем 150 десятичных знака.

[ИСН]

Ну, это разве много. "Сразу бы убил - сегодня бы уже вышел".

[VAL]

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

около 5 тысяч чисел. длина числа в среднем 150 десятичных знака.

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

А с другой стороны стоит ли заморачиваться? 12 миллионов раз найти НОД 150-значных чисел... Хороший мат.пакет за несколько минут должен управится.

[Cash]

Делайте в лоб бинарным алгоритмом. За несколько часов прожует.

[VAL]

Cash в сообщении #635149 писал(а):

Делайте в лоб бинарным алгоритмом. За несколько часов прожует.

Зачем несколько часов?
Сейчас сгенерировал 5000 чисел из указанного диапазона и нашел все попарные НОД. На все (вместе с генерированием) ушло 2 минуты 18 секунд.

[nnosipov]

VAL в сообщении #635153 писал(а):

Сейчас сгенерировал 5000 чисел из указанного диапазона и нашел все попарные НОД. На все (вместе с генерированием) ушло 2 минуты 18 секунд.

Интересно, а сколько среди этих НОДов не единиц получилось?

[ИСН]

Наверное, что-то вроде $1-{6\over\pi^2}$

[nnosipov]

Вот и интересно проверить.

[VAL]

nnosipov в сообщении #635156 писал(а):

VAL в сообщении #635153 писал(а):

Сейчас сгенерировал 5000 чисел из указанного диапазона и нашел все попарные НОД. На все (вместе с генерированием) ушло 2 минуты 18 секунд.

Интересно, а сколько среди этих НОДов не единиц получилось?

7390559 единиц из 12497500. Т.е. примерно 0.5913629926 от общего числа.
В то время как $\frac6{\pi^2}\approx0.6079271016$.

-- 24 окт 2012, 18:07 --

При повторном запуске получилось 0.6108954591. Так что, в среднем нормально получается. Но разброс большой.

[Руст]

Для случайных или для случая когда все попарные mod ы малы, можно считать чуть эффективнее, разбивая множество в бинарное дерево и учитывая, что если найдены $(x_i,x_k),k\in S, (x_j,x_k),k\in S$, то в начале можно найти $a_i=\operatorname{lcm}(x_i,x_k),k\in S, a_j=\operatorname{lcm}(x_j,x_k),k\in S$ и $\gcd$ находится из $(x_i,x_j)=\gcd(a_i,a_j)(\frac{x_i}{a_i},\frac{x_j}{a_j})$. Это должно сокращать вычисления по сравнению с вычислением по алгоритму Евклида для каждой пары.