Три дня назад в паблике "Как компьютеры умножают/делят" я привёл метод "программного ускорения" работы компа при выполнении операций умножение/деление.
Многие комментаторы обрушились на меня с критикой: кому нужно твоё "программное ускорение", если давно уже есть "аппаратное". Но у меня есть к ним такие возражения:
1. Аппаратное ускорение - это надёжная работа триггеров и транзисторов в математическом процессоре компа. Вопрос: всегда ли они будут так безупречно работать?
- в процессор может прилететь "пуля" из нагана террориста или диверсанта (хотя если честно, то тогда от компа мало что останется)
- путь "пуля" - это нейтрон или электрон, который "выбивает" токопроводящую жилку в микросхеме. Или же это ЭМИ, которое прожигает эту жилку. Жилки нет, процессор накрылся - комп "сломался". Можно починить, но это иногда может занять до нескольких часов.
- а если нет времени/денег/мспециалиста для починки - надо выкинуть комп?
- а если сломавшийся комп нужен "здесь и сейчас" и это вопрос жизни/смерти?
Тогда надо отключать "аппаратное ускорение" и использовать "Метод ХренЗнаетКого" работающий "ХренЗнаетСколько" времени.
Мои комментаторы правы: я не знаю как умножают современные компьютеры. Поэтому и предлагаю вашему вниманию свой метод "Мультиплекс", который я придумал ещё в 89-ом году, столкнувшись с "черепашьими скоростями умножения" на советском супервычислителе М-13.
(а вдруг этот метод действительно до сих пор никто кроме меня не придумал?)
Метод Маэстро "Мультиплекс"
Итак, в процессоре ЭВМ в двух математических регистрах находятся числа:
Х⁷Х⁶Х⁵Х⁴_Х³Х²Х¹Х⁰ и Y⁷Y⁶Y⁵Y⁴_Y³Y²Y¹Y⁰
и их надо перемножить.
У процессора есть два "внутренних рабочих регистра Z и Σ. По первому для процесса суммирования будет гоняться "1" по разрядам, во втором будут накапливаться "временнуая информация" (для точно результата без переполнения там нам мало 1 байта, надо уже 2).
. Σ⁷Σ⁶Σ⁵Σ⁴_Σ³Σ²Σ¹Σ⁰_ᛊ⁷ᛊ⁶ᛊ⁵ᛊ⁴_ᛊ³ᛊ²ᛊ¹ᛊ⁰
Нам надо "столбиком" умножить Х и Y, "школьным способом":
. Х⁷Х⁶Х⁵Х⁴_Х³Х²Х¹Х⁰
. х Y⁷Y⁶Y⁵Y⁴_Y³Y²Y¹Y⁰
. —————————
. Х⁷Х⁶Х⁵Х⁴_Х³Х²Х¹Х⁰
. Х⁷Х⁶Х⁵Х⁴_Х³Х²Х¹Х⁰
. Х⁷Х⁶Х⁵Х⁴_Х³Х²Х¹Х⁰
. Х⁷Х⁶Х⁵Х⁴_Х³Х²Х¹Х⁰
Х⁷Х⁶Х⁵Х⁴_Х³Х²Х¹Х⁰
Х⁷Х⁶Х⁵Х⁴_Х³Х²Х¹Х⁰
. Х⁷Х⁶Х⁵Х⁴_Х³Х²Х¹Х⁰
. Х⁷Х⁶Х⁵Х⁴_Х³Х²Х¹Х⁰
. ——————————————————
. Σ⁷ Σ⁶ Σ⁵Σ⁴_Σ³Σ²Σ¹Σ⁰_ ᛊ⁷ ᛊ⁶ ᛊ⁵ ᛊ⁴_ ᛊ³ ᛊ² ᛊ¹ ᛊ⁰
То есть умножая Ц1 на Ц1 - мы получаем Ц2. Возникает "переполнение" и по сути нам нужен лишь старшие биты этого Ц2
Алгоритм умножения:.
1.Сдвигаем Z влево
....при переполнении младшего полубайта - пробежаться по старшим разрядам, меняя 1 на 0 пока не впишем 1 вместо 0
2. Если Y⁰=1, то Z⁰=X⁷
3. Сдвигаем Х влево по кругу
4. Сдвигаем Y вправо по кругу
5. Обрабатываем следующий полубайт числа, выполняя 1-4
У меня сложилась интересная переписка с комментатором KAP13 , в ходе "препирательств" с которым я и вспомнил свою прогу от 89 года.
Для проверки он посоветовал мне попробовать перемножить два простых числа. Что я и делаю сейчас.
Проверка на умножении 10х5
1010
. х 0101
. ———
. 1010
. 0000
. 1010
. 0000
. ————
. 11_0010 =50
Вычисления:
1. Y⁰=1 <<Z=0. Z⁰=X³=1 <X=0101 >Y=1010 Z=1
2. Y⁰=0. <<Z=10. Z⁰=X³=0 <X=1010 >Y=0101. Z=10
3. Y⁰=1. <<Z=100 Z⁰ =X³=1 <X= 0101 >Y=1010. Z=101
4. Y⁰=0. <<Z=1010 Z⁰=X³ =0. <X= 1010. >Y=0101. Z=1010 - перeнесли Х
Подставляем на Y⁰ следующий его разряд >>Y=0010 Y⁰=0. <<Z=10100 - переполнение!
1-ое ⁰Z=1. ¹Z=0100. ——> ⁰Z=10 ¹Z=0100. Z=10_0100
2.-ое. ⁰Z=101. ¹Z=0010. ——> ⁰Z=110 ¹Z=0010. Z=110_ 0010
3-е. ⁰Z=0001. ¹Z=0010. ——> ⁰Z=0010 ¹Z=0010. Z=11_0010_ 0010
Подставляем на Y⁰ cледующий его разряд. >>Y=0001
5.. Y⁰=1 <<Z=101000. Z⁰=X³=1 <X=0101 >Y=1010 Z=101001
2. Y⁰=0. <<Z=101_0010!. Z⁰=X³=0 <X=1010 >Y=0101. Z=1100_0100
3. Y⁰=1. <<Z=1_1000_1000 Z⁰ =X³=1 <X= 0101 >Y=1010. Z=1_1000_10001
4. Y⁰=0. <<Z=11_0001_0010! Z⁰=X³ =0. <X= 1010. >Y=0101. Z=11_0010_0010. перeнесли Х второй раз
Подставляем на Y⁰ его последний разряд >>Y=0000 Y⁰=0.
<< Z =110_0100_0100
Итого >>Z=11_0010_0010 , Берём только старшие (6 бит?) Z= 11_0010
Кажись работает мой "метод"?
Во всяком случае в 89-ом на Балхаше он точно работал
@Маэстро
14.05.24
Комментарии
Сразу извиняюсь, но не могу понять почему вы сдвинули на два разряда влево, а не вправо или же не оставили без сдвига?
Так понятно? 2 строчки там добавил
Если вас действительно интересует тема вычислительной архитектуры и алгоритмов, можете почитать каноническую литературу. Там много чего интересно в плане аппаратной реализации арифметико-логических устройств можете почерпнуть.
Нет не интересует. Мне интереснее придумывать "свой способ". И кажется я понимаю, что имел в виду КАР13, когда говорил о "побитном сложении". Завтра напишу новый паблик ... Только тот способ, наверное, сейчас и применяется для "программного ускорения" в компах
Чукча не читатель, чукча писатель?
Чем предлагаемое Вами лучше того, что проходят ещё старшеклассники и младшекурсники технических вузов.
Алгоритмы быстрого умножения чисел: от столбика до Шенхаге-Штрассена / Хабр (habr.com)
Выглядит как какой-то ад. В примитивном процессоре операция сложения занимает 1 такт, операция сдвига - тоже 1 такт.
Скорость умножения N-разрядных классическим способом столбиком занимает максимум 2*N тактов - по 1 сдвигу и опциональному сложению на каждый разряд.
Ваш алгоритм я не понял, текстом непонятно "кто на ком стоял". Я потому и просил либо на псевдоязыке, либо блок-схемой.
Но даже по примеру видно что скорость его больше 2*N.
Сходу могу вам предложить самый быстрый алгоритм умножения - собираете множители друг за другом - X3X2X1X0Y3Y2Y1Y1 и по этому адресу в заранее подготовленной таблице берете результат. Точно так же можно вычислять синус для целочисленных преобразований.
Для особо упоротых объясняю, как достигается надёжность работы компьютеров в критическом оборудовании. Вот есть самолёт, например мой любимый А320. У него нет штурвала, есть джойстики и управление рулями полностью электронное, те положение рублей выставляет Компьютер на основе кучи сигналов и положения джойстика. Любая электроника или система может поломаться с какой то вероятностью. Чтобы самолёт мог перевозить пассажиров, это вероятность должна быть ниже определённой величины. Очень маленькой.
Так вот, есть компьютер с большой вероятностью поломки. Что делают конструкторы? Берут 4 компьютера одного производителя и шесть другого. Первые четыре, попарно объединяются в две коробочки и называются ELAC. Вторые шесть SEC. Каждая коробочка получает по два идентичных канала. Выходные сигналы каналов сравнивают, и в случае их не совпадения, коробочка считается отказавшей до конца полёта, а управление передаётся следующей. Пилот тож может принудительно коробочки переключить. И так, у нас пять коробочек, десять каналов от двух разных независимых производителей чтобы исключить пересекающиеся ошибки конструкции и по, и каждая коробочка способна управлять самолетом.
Вероятности отказа коробочек в таком случае умножаются и вероятность отказа всей системы становится достаточно ничтожной.
Вероятности умножаются только для независимых событий.
Вспоминаем, как упала ракета Ариан-5.
Автор, на таком говне тебе не заработать. Займись чем нибудь более разумным, например, программированием...
Всегда.
И на 100%.
Зрители в корень, как завещал Кузьма Прутков сто лет назад.
В очередной раз математически ерунда написана, но это же не просто статья, она же еще и на ДЗЕНЕ присутствует, а его читает наша молодежь и по слабоумию копипастит в своих рефератах!
Обратите внимание, что запись столбиком со сдвигом Х7...Х0 влево корректна только для случая когда все Y7...Y0 равны "1", иначе соответствующее слагаемое тоже должно быть 0.
У Вас еще нет Z, первым шагом регистр надо инициализировать.
Что значит "переполнение полубайта"? Полубайта какого регистра? Старшие разряды чего?
Вы же сами в алгоритме писали что Y сдвигается вправо по кругу, а тут бац - и уже не циклический сдвиг, а какая-то подстановка.
Для умножения двух 4-битных чисел нам надо использовать 10-битный временный регистр?
11-битный?
А сложность (время выполнение) какая?
А где в алгоритме второй-то регистр, который Σ?
В перемножении двух 8-битных чисел даже на 8080 нет проблем вместить все временные значения и результат в регистры, не задействуя ни стек ни память; а уж для результата, влезающего в 8 бит проще использовать предрассчитанную таблицу.