2014 dxdy logo

Научный форум dxdy

Математика, Физика, Computer Science, Machine Learning, LaTeX, Механика и Техника, Химия,
Биология и Медицина, Экономика и Финансовая Математика, Гуманитарные науки


Правила форума


Посмотреть правила форума



Начать новую тему Ответить на тему На страницу 1, 2  След.
 
 Алгоритм для поиска НОК
Сообщение02.03.2016, 13:24 
Аватара пользователя


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

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

 Профиль  
                  
 
 Re: Алгоритм для поиска НОК
Сообщение02.03.2016, 14:15 
Заслуженный участник
Аватара пользователя


19/12/10
1546
INGELRII в сообщении #1103590 писал(а):
Чтобы там не было операций сложнее сложений-вычитаний и двоичных сдвигов вправо-влево?

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

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

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

INGELRII в сообщении #1103590 писал(а):
В принципе, зная два числа и их НОД, можно найти и НОК по всем известной формуле.

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

 Профиль  
                  
 
 Re: Алгоритм для поиска НОК
Сообщение02.03.2016, 15:04 
Аватара пользователя


07/02/12
1403
Питер
INGELRII в сообщении #1103590 писал(а):
Чтобы там не было операций сложнее сложений-вычитаний и двоичных сдвигов вправо-влево?

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

 Профиль  
                  
 
 Re: Алгоритм для поиска НОК
Сообщение02.03.2016, 15:07 
Аватара пользователя


11/08/11
1135
whitefox в сообщении #1103597 писал(а):
Ну если вопрос эффективности не стоит,

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

whitefox в сообщении #1103597 писал(а):
А формулу для трёх и более чисел знаете?

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

-- 02.03.2016, 15:11 --

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

 Профиль  
                  
 
 Re: Алгоритм для поиска НОК
Сообщение02.03.2016, 15:21 
Аватара пользователя


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

 Профиль  
                  
 
 Re: Алгоритм для поиска НОК
Сообщение02.03.2016, 15:26 
Заслуженный участник
Аватара пользователя


19/12/10
1546
INGELRII в сообщении #1103603 писал(а):
Ничего проще чем: сначала найти НОК для пары чисел из заданных, затем НОК для найденного на предыдущем шаге и еще одного числа из заданных, и так далее делать шаги, пока массив заданных чисел не исчерпается - нет, не знаю.

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

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

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

 Профиль  
                  
 
 Re: Алгоритм для поиска НОК
Сообщение02.03.2016, 15:28 
Аватара пользователя


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

 Профиль  
                  
 
 Re: Алгоритм для поиска НОК
Сообщение02.03.2016, 15:37 
Заслуженный участник
Аватара пользователя


19/12/10
1546
Что написано, то и означает. :D
Вы же Кнута читали.
Покажу на примере двух чисел:
$$(a^{-1},b^{-1})^{-1}=\frac1{(\frac1a,\frac1b)}=\frac{ab}{(\frac{ab}a,\frac{ab}b)}=\operatorname{lcm}(a,b)$$

 Профиль  
                  
 
 Re: Алгоритм для поиска НОК
Сообщение02.03.2016, 15:47 
Аватара пользователя


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

 Профиль  
                  
 
 Re: Алгоритм для поиска НОК
Сообщение02.03.2016, 15:50 
Заслуженный участник
Аватара пользователя


19/12/10
1546
Ну красивая же. :D
А насчёт эффективности ... никто и не обещал.

 Профиль  
                  
 
 Re: Алгоритм для поиска НОК
Сообщение02.03.2016, 17:12 
Заслуженный участник
Аватара пользователя


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

 Профиль  
                  
 
 Re: Алгоритм для поиска НОК
Сообщение02.03.2016, 20:16 
Аватара пользователя


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

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

 Профиль  
                  
 
 Re: Алгоритм для поиска НОК
Сообщение02.03.2016, 21:20 
Заслуженный участник


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

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

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

 Профиль  
                  
 
 Re: Алгоритм для поиска НОК
Сообщение02.03.2016, 21:30 
Заслуженный участник


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

 Профиль  
                  
 
 Re: Алгоритм для поиска НОК
Сообщение02.03.2016, 21:31 
Аватара пользователя


11/08/11
1135
Dmitriy40 в сообщении #1103702 писал(а):
Пример: сложение и умножение вещественных чисел

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

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

-- 02.03.2016, 21:32 --

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

 Профиль  
                  
Показать сообщения за:  Поле сортировки  
Начать новую тему Ответить на тему  [ Сообщений: 18 ]  На страницу 1, 2  След.

Модераторы: Модераторы Математики, Супермодераторы



Кто сейчас на конференции

Сейчас этот форум просматривают: нет зарегистрированных пользователей


Вы не можете начинать темы
Вы не можете отвечать на сообщения
Вы не можете редактировать свои сообщения
Вы не можете удалять свои сообщения
Вы не можете добавлять вложения

Найти:
Powered by phpBB © 2000, 2002, 2005, 2007 phpBB Group