Алгоритм для поиска НОК

[INGELRII]

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

Но есть ли алгоритм, наподобие хотя бы евклидова, для поиска НОК? Чтобы там не было операций сложнее сложений-вычитаний и двоичных сдвигов вправо-влево? Я такого нигде не нашел, и придумать не смог.

[whitefox]

INGELRII в сообщении #1103590 писал(а):

Чтобы там не было операций сложнее сложений-вычитаний и двоичных сдвигов вправо-влево?

Ну если вопрос эффективности не стоит, можно попеременно вычислять члены двух последовательностей:

$x_1=a,\ x_{n+1}=x_n+a;\ y_1=b,\ y_{n+1}=y_n+b$

первый общий член и будет $\operatorname{lcm}(a,b)$

INGELRII в сообщении #1103590 писал(а):

В принципе, зная два числа и их НОД, можно найти и НОК по всем известной формуле.

А формулу для трёх и более чисел знаете?

[bondkim137]

INGELRII в сообщении #1103590 писал(а):

Чтобы там не было операций сложнее сложений-вычитаний и двоичных сдвигов вправо-влево?

А умножение в Вашем случае - тоже слишком тяжелая операция? Железо - это какой-то старый контроллер?

[INGELRII]

whitefox в сообщении #1103597 писал(а):

Ну если вопрос эффективности не стоит,

Ладно, поставим дополнительно вопрос эффективности А то для такого наивного алгоритма я предвижу некоторые неприятности для чисел типа $100500$ и $100501$, например.

whitefox в сообщении #1103597 писал(а):

А формулу для трёх и более чисел знаете?

Ничего проще чем: сначала найти НОК для пары чисел из заданных, затем НОК для найденного на предыдущем шаге и еще одного числа из заданных, и так далее делать шаги, пока массив заданных чисел не исчерпается - нет, не знаю.

-- 02.03.2016, 15:11 --

bondkim137
Ну допустим, нам надо с достаточно высокой частотой принимать на вход данные и в побыстрее выдавать их кратное. Тогда да, умножение и деление может испортить нам малину. Я предлагаю все же принять задачу как данность и решать именно ее, а не отвлекаться на вопросы типа какой процессор, сколько потоков, не роняли ли системный блок при переноске.

[bondkim137]

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

[whitefox]

INGELRII в сообщении #1103603 писал(а):

Ничего проще чем: сначала найти НОК для пары чисел из заданных, затем НОК для найденного на предыдущем шаге и еще одного числа из заданных, и так далее делать шаги, пока массив заданных чисел не исчерпается - нет, не знаю.

Для трёх чисел:

$\operatorname{lcm}(a,b,c)=(a^{-1},b^{-1},c^{-1})^{-1}$

Здесь $(x,y,z)$ означает $\gcd(x,y,z),$ как это часто и пишут. Для большего числа чисел формула аналогична.

[INGELRII]

whitefox
...где $a^{-1}$ означает?

[whitefox]

Что написано, то и означает.
Вы же Кнута читали.
Покажу на примере двух чисел:

$$(a^{-1},b^{-1})^{-1}=\frac1{(\frac1a,\frac1b)}=\frac{ab}{(\frac{ab}a,\frac{ab}b)}=\operatorname{lcm}(a,b)$$

[INGELRII]

Поздравляю, Вам удалось меня затроллить То есть, я так понимаю, надо расширить алгоритм на рациональные числа. То есть пара числитель-знаменатель, далее по формулам сложения дробей... Тут-то при нахождении числителя умножение и вылезет. Кроме того, вылезет поиск НОД при нахождении знаменателя. И все это каждый раз, как мы складываем-вычитаем. Это только в теории формула красивая, а на практике вон оно че.

[whitefox]

Ну красивая же.
А насчёт эффективности ... никто и не обещал.

[Евгений Машеров]

Алгоритм поиска наибольшего общего кратного для двух простых чисел (собственно, и не только простых, для чисел с НОД=1) должен выдавать их произведение. Следовательно, он либо не проще умножения, либо существует некий метод умножения много быстрее существующего. Первое весьма правдоподобно, но, значит, пользы от особого метода для НОК сравнительно с вычислением через НОД и умножение нет, второе маловероятно, но вдруг? Приз будет побольше просто нового алгоритма для НОК, хотя вряд ли удастся его получить.

[INGELRII]

У все того же дяди Кнута читаем, что для двух случайных натуральных чисел веротность иметь НОД равный единице - это $\frac{6}{\pi^2}$ (и давайте воздержимся от холивара на тему "что есть два случайных натуральных числа", а то тема разрастется на пятьдесят страниц), значит вероятность иметь НОД больше единицы около $0.35$. Уже не так мало, чтобы не давать некий достаточно хороший выигрыш по времени в таких случаях. Есть к чему стремиться.

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

[Dmitriy40]

INGELRII
Вы не учитываете что в реальной практике возможны и нередки случаи противоречия теоретическим оценкам, например умножение может быть быстрее сложения ... (Пример: сложение и умножение вещественных чисел, сложение требует двух нормализаций, до и после, умножение лишь одной после, если нормализация выполняется дольше умножения, а такое вполне реально, матричные умножители никто не отменял, то налицо парадокс.) А во многих современных архитектурах умножение конечно медленнее сложения, но вовсе не так катастрофично, как следует из Кнута и теории алгоритмов. Просто потому, что его специально ускоряют, аппаратными методами. И заменять имеющуюся аппаратную команду даже самым лучшим и быстрым алгоритмом выгодно весьма редко.

По теме, я думаю алгоритм нахождения НОК будет не быстрее алгоритма НОД, а тогда добавка к НОД умножения и деления (которое можно в 60% случаев и не выполнять) не слишком заметна. Наверное. И как правильно сказали выше, уж точно не будет быстрее умножения.

Хотя ради спортивного интереса мне бы тоже хотелось взглянуть на алгоритм нахождения НОК без нахождения НОК и быстрее чем приведённый выше со сложениями.

[venco]

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

[INGELRII]

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

Пример: сложение и умножение вещественных чисел

Но я веду речь не о вещественных числах, внезапно. Пример не засчитан.

Чей-то вас всех уносит мыслью по древу. Не, я и сам не против поговорить за королей и капусту, но может, разберемся для начала с моим первоначальным вопросом? А потом все вместе переместимся в Свободный Полет и уж там как пообщаемся, как пообщаемся, на самые отвлеченные темы!

-- 02.03.2016, 21:32 --

venco
А вот ваша мысль ближе к делу. Пожалуй, это и впрямь решение.