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

👁 0.7K 17:28 - 15/мая/24  Maestro47g (11 ме­ся­цев 1 неде­ля)
Аватар пользователя 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

Блог поль­зо­ва­те­ля Maestro47g | Вой­ди­те или за­ре­ги­стри­руй­тесь, чтобы от­прав­лять ком­мен­та­рии

Комментарии

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

.               1010
.           1010

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

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

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

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

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

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

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

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

Аватар пользователя Александр Мичуринский
Александр Мичур... (9 лет 11 месяцев)

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

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

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

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

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

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

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

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

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

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

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

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

Аватар пользователя Александр Мичуринский
Александр Мичур... (9 лет 11 месяцев)

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

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

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

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

Аватар пользователя Александр Мичуринский
Александр Мичур... (9 лет 11 месяцев)

smile9.gif

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

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

Все­гда.

И на 100%.

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

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

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

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

Нам надо "стол­би­ком" умно­жить  Х и 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 бит проще ис­поль­зо­вать пред­рас­счи­тан­ную таб­ли­цу.

 
Загрузка...