Сколько будет 10х5, если умножать по методу "Мультиплекс"

Аватар пользователя Maestro47g

Три дня назад в паблике "Как компьютеры умножают/делят" я привёл метод "программного ускорения" работы компа при выполнении операций умножение/деление.
Многие комментаторы обрушились на меня с критикой: кому нужно твоё "программное ускорение", если давно уже есть "аппаратное". Но у меня есть к ним такие возражения:
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

Авторство: 
Авторская работа / переводика
Комментарий автора: 

Прошу тех читателей, которым статья понравилась: 1- пройти ко мне на Дзен-канал, 2- подписаться на меня там, 3- "минутку" полистать статью. Тогда я там смогу подключить монетизацию и "копейку подзаработать". 

Как пройти на Д-канал? Жми:

https://m.dzen.ru/id/5d55536d46f4ff00ad95dc8c

Комментарии

Аватар пользователя Дохлик
Дохлик(10 лет 4 месяца)

.               1010
.           1010

Сразу извиняюсь, но не могу понять почему вы сдвинули на два разряда влево, а не вправо или же не оставили без сдвига?

Аватар пользователя Maestro47g
Maestro47g(7 месяцев 6 дней)

Так понятно? 2 строчки там добавил

Аватар пользователя БК 0010
БК 0010(7 лет 1 месяц)

я не знаю как умножают современные компьютеры

Если вас действительно интересует тема вычислительной архитектуры и алгоритмов, можете почитать каноническую литературу. Там много чего интересно в плане аппаратной реализации арифметико-логических устройств можете почерпнуть.

Аватар пользователя Maestro47g
Maestro47g(7 месяцев 6 дней)

Нет не интересует. Мне интереснее придумывать "свой способ". И кажется я понимаю, что имел в виду КАР13, когда говорил о "побитном сложении". Завтра напишу новый паблик ... Только тот способ, наверное, сейчас и применяется для "программного ускорения" в компах

Аватар пользователя Александр Мичуринский

Мне интереснее придумывать "свой способ"

Чукча не читатель, чукча писатель?

Чем предлагаемое Вами лучше того, что проходят ещё старшеклассники и младшекурсники технических вузов.

Алгоритмы быстрого умножения чисел: от столбика до Шенхаге-Штрассена / Хабр (habr.com)

Аватар пользователя KAP13
KAP13(8 лет 7 месяцев)

Выглядит как какой-то ад. В примитивном процессоре операция сложения занимает 1 такт, операция сдвига - тоже 1 такт.
Скорость умножения N-разрядных классическим способом столбиком занимает максимум 2*N тактов - по 1 сдвигу и опциональному сложению на каждый разряд.

Ваш алгоритм я не понял, текстом непонятно "кто на ком стоял". Я потому и просил либо на псевдоязыке, либо блок-схемой.
Но даже по примеру видно что скорость его больше 2*N.

Сходу могу вам предложить самый быстрый алгоритм умножения - собираете множители друг за другом - X3X2X1X0Y3Y2Y1Y1 и по этому адресу в заранее подготовленной таблице берете результат. Точно так же можно вычислять синус для целочисленных преобразований.

Аватар пользователя Assert
Assert(9 лет 1 месяц)

Для особо упоротых объясняю, как достигается надёжность работы компьютеров в критическом оборудовании. Вот есть самолёт, например мой любимый А320. У него нет штурвала, есть джойстики и управление рулями полностью электронное, те положение рублей выставляет Компьютер на основе кучи сигналов и положения джойстика. Любая электроника или система может поломаться с какой то вероятностью. Чтобы самолёт мог перевозить пассажиров, это вероятность должна быть ниже определённой величины. Очень маленькой.

Так вот, есть компьютер с большой вероятностью поломки. Что делают конструкторы? Берут 4 компьютера одного производителя и шесть другого. Первые четыре, попарно объединяются в две коробочки и называются ELAC. Вторые шесть SEC. Каждая коробочка получает по два идентичных канала. Выходные сигналы каналов сравнивают, и в случае их не совпадения, коробочка считается отказавшей до конца полёта, а управление передаётся следующей. Пилот тож может принудительно коробочки переключить. И так, у нас пять коробочек, десять каналов от двух разных независимых производителей чтобы исключить пересекающиеся ошибки конструкции и по, и каждая коробочка способна управлять самолетом.

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

Аватар пользователя Александр Мичуринский

Вероятности умножаются только для независимых событий.

Вспоминаем, как упала ракета Ариан-5. 

Аватар пользователя Assert
Assert(9 лет 1 месяц)

Автор, на таком говне тебе не заработать. Займись чем нибудь более разумным, например, программированием... 

Аватар пользователя Александр Мичуринский

smile9.gif

Аватар пользователя Anter1999
Anter1999(7 лет 1 месяц)

Вопрос: всегда ли они будут так безупречно работать?

Всегда.

И на 100%.

Зрители в корень, как завещал Кузьма Прутков сто лет назад.

Аватар пользователя RusEngineer
RusEngineer(8 лет 4 месяца)

Аватар пользователя BuDDiE
BuDDiE(7 лет 4 месяца)

В очередной раз математически ерунда написана, но это же не просто статья, она же еще и на ДЗЕНЕ присутствует, а его читает наша молодежь и по слабоумию копипастит в своих рефератах! 

Нам надо "столбиком" умножить  Х и Y, "школьным способом":

Обратите внимание, что запись столбиком со сдвигом Х7...Х0 влево корректна только для случая когда все Y7...Y0 равны "1", иначе соответствующее слагаемое тоже должно быть 0.

Алгоритм умножения:.

1.Сдвигаем Z влево

У Вас еще нет Z, первым шагом регистр надо инициализировать.

при переполнении младшего полубайта - пробежаться по старшим разрядам

Что значит "переполнение полубайта"? Полубайта какого регистра? Старшие разряды чего?

Подставляем на Y⁰ следующий его разряд >>Y=0010

Вы же сами в алгоритме писали что Y сдвигается вправо по кругу, а тут бац - и уже не циклический сдвиг, а какая-то подстановка.

3-е.                 ⁰Z=0001. ¹Z=0010. ——> ⁰Z=0010 ¹Z=0010.  Z=11_0010_ 0010

Для умножения двух 4-битных чисел нам надо использовать 10-битный временный регистр?

<< Z =110_0100_0100

11-битный?

А сложность (время выполнение) какая?

У процессора есть два "внутренних рабочих регистра Z и Σ. По первому для процесса суммирования будет гоняться "1" по разрядам, во втором будут накапливаться "временнуая информация"

А где в алгоритме второй-то регистр, который Σ?

В перемножении двух 8-битных чисел даже на 8080 нет проблем вместить все временные значения и результат в регистры, не задействуя ни стек ни память; а уж для результата, влезающего в 8 бит проще использовать предрассчитанную таблицу.