на главнуюВсе эхи RU.ALGORITHMS
войти ?

Re: Целочисленные операции.

От Alex Mizrahi (2:5020/400) к Jaroslav Triaskin

В ответ на Заголовок предыдущего сообщения в треде (Имя Автора)


From: "Alex Mizrahi" <udodenko@users.sourceforge.net>

JT>>> Какими алгоритмомаи они пользуются, ибо сопроцессор, как я
JT>>> понимаю, не задействован, но всё равно например 2 числа с 200
JT>>> значащими числами перемножаются практически мгновенно.

AM>> А сколько они по-твоему должны будут перемножаться? Процессор делает
AM>> порядка миллирда операций в секунду, тут два числа как не перемножай,
AM>> будет мгновенно.
JT> Справедливо для малого количества чисел в мантисе. Как только захотим
JT> перемножить два числа состоящие, напрмер, из 1000 цифр каждое, то тут
JT> уже затык, ибо, как я понимаю, нет железки которая на входе получает
JT> два числа и за такт на выходе их произведение? Или я не прав?

Hу давай прикинем, ты говорил о двух 200-значных числах. Умножение
столбиком (очень примерно!) можно оценить как сложение двухсот 200-значных
чисел. Это 40000 операций. Сложение и умножение десятичных чисел можно
реализовать через таблицу (да, ту самую "таблицу умножения"!), положим,
процессор осилит обращение к таблице за три такта. Итого 120 000 тактов.
Из милларда. Это 120 000 / 1 000 000 000 = 0.000120.
Т.о. нечто вроде 0.12 миллисекунд. Это по алгоритму, которому учат во
втором классе школы, если я не ошибаюсь.

Спомощью компьютера, конечно, лучше считать не десятичными цифрами.
А, например, на 32-битном процессоре может иметь смысл каждую цифру
представить 32-битным целым. Тогда можно пользоваться нативными операциями
сложения и умножения. За сколько тактов они работают я не знаю, но, говорят,
зачастую затык не в них, а в обращении к памяти.

JT>>> А также вопрос, как построены алгоритмы деления и умножения для
JT>>> чисел с такой огромной мантиссой? Я использовал - повторное
JT>>> сложение и вычитание, но даже написанное на C/Pascal работает на
JT>>> порядок медленнее, чем в данных программах. :-(

AM>> Что такое "повтороное сложение и вычитание"?

JT> 3*4=3+3+3+3=12
JT> 15/4=15-4-4-4=3 ост 3.

Мда... По-моему бесперспективность этого подхода показывают ещё где-то
в первом классе, а ко второму учат умножать в столбик.

Hасчёт "на порядок медленнее" ты нас, видимо, обманываешь. Потому что уже
где-то на 16 знаках оно будет считать миллиарды лет.


--- ifmail v.2.15dev5.4
* Origin: Demos online service (2:5020/400)

Ответы на это письмо:

From: Username
Заголовок следующего сообщения в треде может быть длинным и его придется перенести на новую строку

From: Username
Или коротким

FGHI-url этого письма: area://RU.ALGORITHMS?msgid=<1187386355@killer>+2c532cd3