2014 dxdy logo

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

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


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


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



Начать новую тему Ответить на тему На страницу Пред.  1, 2
 
 Re: Алгоритм для поиска НОК
Сообщение02.03.2016, 22:01 
Заслуженный участник
Аватара пользователя


11/03/08
9996
Москва
INGELRII в сообщении #1103685 писал(а):
Насчет алгоритмов умножения быстрее, чем школьный метод умножения одного числа на цифры другого и последующего суммирования строк (и как частный случай, двоичного варианта этого же метода), прочитать можно там же; я был в шоке, когда узнал.


Да есть они, есть, и Карацуба, и Шенхаге-Штрассен. Только они для длинных чисел. Карацуба для чисел длинее 320-640 бит лучше обычного, Шёнхаге-Штрассен лучше Карацубы для десяти тысяч десятичных знаков. А тут что-то для достаточно малых предполагается.

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


04/05/09
4589
Ещё можно заметить, что для таких больших чисел разница между умножением и делением становится несущественной.

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


07/02/12
1439
Питер
А для маленьких, в современных реалиях (при аппаратной поддержке), она впринципе небольшая и может быть съедена доп. расходами на 'расширение' алгоритма Евклида. Особенно, если учесть конвеерную архитектуру процессоров и не пользоваться результатом деления сразу.
(но идея отличная)

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

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



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

Сейчас этот форум просматривают: katzenelenbogen


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

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