# Ćwiczenia 2, grupa śr. 17-19, 16. marca 2022

###### tags: `SYK21` `ćwiczenia` `pwit`

## Deklaracje

Gotowość rozwiązania zadania należy wyrazić poprzez postawienie X w odpowiedniej kolumnie! Jeśli pożądasz zreferować dane zadanie (co najwyżej jedno!) w trakcie dyskusji oznacz je znakiem ==X== na żółtym tle.

**UWAGA: Tabelkę wolno edytować tylko wtedy, gdy jest na zielonym tle!**

:::danger
| | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 |
| ----------------------:| ----- | --- | --- | --- | --- | --- | --- | --- | --- |
Grzegorz Bielecki | | | | | | | | | |
Kamila Brzozowska | X | X | X | X | X | | X | X | |
Adam Ciężkowski | X | X | X | X | X | X | X | | |
Natalia Czerep |==X== | X | X | X | X | | X | | |
Jan Dalecki | X | X | X | ==X== | X | | X | X | |
Marko Golovko | | | | | | | | | |
Adam Górkiewicz | X | X | X | X | X |==X==| X | X | X |
Piotr Gunia | X |==X==| X | X | X | | X | | |
Krzysztof Jadłowski | X | X | X | X | X | | ==X== | X | |
Magdalena Jarecka | X | X | X | X | X | X |X | X | |
Mikołaj Jaszcza | X | X | X | X | X | X | X | X | X |
Monika Jędrzejkowska | | | | | | | | | |
Michał Kierul | X | X | X | X | | | | | |
Damian Lukas | | | | | | | | | |
Karol Ochman-Milarski | | | | | | | | | |
Piotr Piesiak | | | | | | | | | |
Damian Ratajski | | | | | | | | | |
Aleksandra Rozkrut | X | X | | | | | X | X | |
Marcin Sarnecki | X | X | X | X | X | X | X | X | X |
Maria Szlasa | X | X |==X==| X | X | | X | X | |
Mateusz Burdyna | X | X | X | | | | | | |
Nikola Wrona | X | X | X | X | | | X | X | |
Marcin Wróbel | X | X | X | X | X | X | X | X | ==X== |
:::

:::info
**Uwaga:** Po rozwiązaniu zadania należy zmienić kolor nagłówka na zielony.
:::

## Lista 1, Zadanie 8

:::success
Autor: Mikołaj Jaszcza
:::
Białe bloki na górze reprezentują sumatory 1 bitowe (tworzą razem sumator RCA), które także obliczają propagację dla każdego bitu.
Blok C oblicza propagację dla danego przedziału bitów, i przekazuje dalej generację przez cały przedział bitów obliczoną przez sumator.

Propagacja przedziału jest iloczem (AND - tj. p0 AND p1 AND p2 AND p3) propagacji pojedynczych pozycji. Natomiast generacja w trywialny sposób jest równoważna z wartością carry-out sumatora RCA przy carryin=0 (zauważmy, że jej wartość jest znana już po 2k+1 jednostkach czasu, niezależnie od "wejściowych" c0, gdzie k to liczba bitów w bloczku RCA).

Sygnał jest propagowany w "dół" drzewa (zgodnie ze schematem u góry)
poprawne są kolejne wartości Pij, Gij
dla coraz większych przedziałów (niżej w drzewie), wyznaczone dzięki wzorom
=> P(i, k) = P(i, j) * P(j+1,k)
=> G(i, k) = (Gj+1, k)+ (Pj+1, k) * G(i, j).

Następnie mając poprawne powyższe wartości
obliczane są wartości carry-out "ck" (chodzi tu o działania mające miejsce w "bloczku" B) bloczku przy otrzymanym carry in (indeksy poniżej na bazie indeksów bloczku B)
c(k + 1) = G(i,k) + P(i,k)c(i). Więc następnie każdy sumator poprawnie oblicza odpowiednie bity sumy.

n=b*k
k-rozmiar bloku
b-liczba bloków

Pełny sumator jednobitowy ma 5 bramek, więc cały sumator k-bitowy będzie miał 5k bramek (i będzie działał w czasie 2k+1).

Schemat bloczku B:

CZAS DZIAŁANIA:
(2k+1)+(2*log(b))+(2*log(b))+(2k+1) - 2

2k+1 sumatory rca na początku
2*log(b) przejście drzewa w dół
2*log(b) przejście drzewa w góre
2k+1 sumator rca na końcu
-2 -> ponieważ w korzeniu drzewa nie ma potrzeby wyznaczania generacji oraz propagacji (o ile nie sprawdzamy potencjalnego overflow)

obliczenie liczby bramek w przedstawionym rozwiązaniu (z podziałem na czynniki):
5*n -> sumatory pełne 1 bitowe (po 5 bramek, n bitów)
n -> liczenie propagacji dla każdego pojedynczego bitu, każdy z nich musi przekazać odpowiednią wartość do bloku C aby wyliczyć propagację całego bloczku - łącznie jest ich n
b -> skoro jest b bloczków typu C, a każdy blok ma po jednym "wielkim" AND (tj obliczanie propagacji)
5*(b-1) - każdy blok typu B ma 5 bramek (patrz. schemat wklejony powyżej), a bloczków typu B jest b-1 (własności bitowe).

Zatem podsumowując -> 5*n+n+b+5*(b-1)

## Zadanie 1

:::success
Autor: Natalia Czerep
:::

9 = 1001
3 = 0011

0011
A=1001

------
0011
0000
0000
0011

A = 1001
B = 0011
P = 0000
## Zadanie 2

:::success
Autor: Piotr Gunia
:::



Przesunięcie arytmetyczne - "rozsmarowanie" bitu znaku


## Zadanie 3

:::success
Autor: Maria Szlasa
:::
Wykonaj zadanie 1. dla układu stosującego przesuwanie przez zera (ang. shifting over zeros).

**Wskazówka: “Appendix J”, str. 45.**

**Struktura**

**Algorytm**
1. Jeśli najmniej znaczący bit A wynosi 1 to B dodaj do P i sumę umieść w P. Wpp Przejdź do drugiego kroku.
2. P i A przesuń w prawo, carry-out przenieś do najwyższego bitu P, a najmniejszy bit P przenieś do skrajnego prawego bitu A. Fragment bitów przeniesionych z P do A nie jest używany w pozostałej części algorytmu.

**$9\cdot3$**

| | start | 1a | 2 | 2 | 2 | 1a | 2 |
| --------- | ----- | ---- | -------- | -------- | -------- | -------- | -------- |
| A | 1001 | 1001 | **1**100 | **11**10 | **011**1 | **011**1 | **1011** |
| B | 0011 | 0011 | 0011 | 0011 | 0011 | 0011 | 0011 |
| P | 0000 | 0011 | 0001 | 0000 | 0000 | 0011 | 0001 |
| $c_{out}$ | 0 | 0 | 0 | 0 | 0 | 0 | |

## Zadanie 4

:::success
Autor: Jan Dalecki
:::

Kodowanie Bootha:

Każdy ciąg n jedynek w zapise binarnym liczby zastępujemy przez liczbę n+1 bitową gdzie wszytkie bity są równe 0 oprócz najstarszego bitu, a najmłodszy bit jest ustawiany na $\hat{1}$ co oznacza odjęcie $2^{i}$ gdzie $i$ to pozycja $\hat{1}$.

Np.

+ $111111 \rightarrow 100000\hat{1} = 63 = 64 - 1$
+ $11011110 \rightarrow 10\hat{1}1000\hat{1}0 = 222 = 192 + 30 = (256 - 64) + (32 - 2)$

Re-kodowanie Bootha:

Patrzymy na aktualny najmłodszy bit w rejestrze A oraz dodatkowo na ostatnio przeglądany bit.

W i+1 kroku mamy następujące przypadki:

$a_i = 0$, $a_{i-1} = 0$ dodaj $0$ do rejestru P.
$a_i = 0$, $a_{i-1} = 1$ dodaj B do rejestru P.
$a_i = 1$, $a_{i-1} = 0$ odejmij B z rejestru P.
$a_i = 1$, $a_{i-1} = 1$ dodaj $0$ do rejestru P.

Przykład A = -9, B = 3

$A = 10111$
$B = 00011$

Krok 1.

$PA = 00000|10111$, $a_0 = 1 \, \ a_{-1} = 0 \overset{-b}\rightarrow PA=11101|10111 \rightarrow PA=11110|11011$

Krok 2.

$PA = 11110|11011$, $a_0 = 1 \, \ a_{-1} = 1 \overset{+0}\rightarrow PA=11110|11011 \rightarrow PA=11111|01101$

Krok 3.

$PA = 11111|01101$, $a_0 = 1 \, \ a_{-1} = 1 \overset{+0}\rightarrow PA=11111|01101 \rightarrow PA=11111|10110$

Krok 4.

$PA = 11111|10110$, $a_0 = 0 \, \ a_{-1} = 1 \overset{+b}\rightarrow PA=00010|10110 \rightarrow PA=00001|01011$

Krok 5.

$PA = 00001|01011$, $a_0 = 1 \, \ a_{-1} = 0 \overset{-b}\rightarrow PA=11110|01011 \rightarrow PA=11111|00101$

Wynik : $PA = 1111100101 = -27 = ab$

#### Poprawność algorytmu

Zakładamy, że liczba $a$ jest ujemna, a liczba $b$ nieujemna. Dla każdego bloku jedynek na bitach $j:i \ \ (j \ge i)$ zapisu binarnego liczby $a$ wykonamy wpierw odjęcie liczby $b2^{i}$, a po $j-i+1$ przesunięciach dodamy liczbę $b2^{j+1}$. W rezultacie zamienimy sumę:

$$b\sum_{k=i}^{j}2^k = b 2^i\frac{1-2^{j-i+1}}{-1} = b2^i(2^{j-i+1} -1) =b2^{j+1} - b2^{i}$$

Krok i+1. (Napotykamy na pierwszą 1)

Na bitach rejestru $2n-1:n-i$ mamy zapisaną liczbę 0.

Odejmujemy liczbę $b$ na rejestrze P i przesuwamy arytmetycznie w prawo.
Na $2n-1:n-i-1$ bitach będziemy mieli liczbę $-b2^{i}$.

W kolejnych krokach dokonujemy już tylko przesunięcia, aż napotkamy kolejną jedynkę.

Wykonaliśmy $j-i+1$ przesunięć w prawo zatem na $2n-1:n-j-1$ będzie liczba $-b2^{i}$. Dodajemy $b2^{j+1}$ i wykonujemy przesunięcie w prawo. Na $2n-1:n-j-2$ bitach znajdzie się liczba $b2^{j+1} - b2^{i}$.

Dalsze bloki obliczane są w analogiczny sposób z dodatkowym założeniem, że dodajemy liczby do sumy otrzymanej z wcześniejszych operacji zapisanej na wcześniejszych bitach.

Zauważmy, że może nie starczyć nam kroków do przeprowadzenia pełnej sekwencji dla bloku jedynek. W takim przypadku najstarszy bit liczby $a$ musi być 1 czyli zgodnie z naszymi założeniami.

Rozważmy sekwencję jedynek które zapisane są na bitach $n-1:i$ liczby $a$. Możemy założyć, że do ostatniego 0 (bit $i-1$) w zapisie binarnym $a$ obliczyliśmy poprawnie sumę:

$$b\sum_{k=0}^{i-1}2^ka_{k}$$

Mamy do dodania taką sumę: $-2^{n-1}b + b\sum_{k=i}^{n-2}2^{i}$

$$-2^{n-1} + \sum_{k=i}^{n-2}2^{i} = -2^{n-1} + 2^{i}\frac{1-2^{n-i-1}}{-1} = -2^{n-1} + 2^i(2^{n-i-1} - 1) = -2^i$$

W przypadku kodowania Bootha odejmiemy wpierw liczbę $-b2^{i}$ i do końca będziemy wykonywać już tylko przesunięcia arytmetyczne. Zatem otrzymamy poprawny wynik.

#### Układ


## Zadanie 5

:::success
Autor: Adam Ciężkowski
:::

Dla liczb $n$-bitowych robimy $n$ razy:

["W locie" korzystamy z kodowania Bootha.]
1) * Jeśli natrafimy na 1 (z daszkiem), odejmujemy
* Jeśli natrafimy na 1 (bez daszku), dodajemyA
* Jeśli natrafimy na 0, nie robimy nic
2) * Robimy shift w prawo (biorąc pod uwagę bit znaku)


## Zadanie 6

:::success
Autor: Adam Górkiewicz
:::
Zadanie pomnożenia dwóch liczb $A = [a_{n - 1}a_{n - 2}\dots a_0]_2$ oraz $B = [b_{n - 1}b_{n - 2}\dots b_0]_2$ możemy sprowadzić do dodania do siebie $n$ liczb $X_i$, gdzie $X_i = A \cdot b_i \cdot 2^i$, ponieważ
$$ \sum X_i = \sum A \cdot b_i \cdot 2^i = A \sum b_i \cdot 2^i = A \cdot B.$$
Możemy wyznaczyć liczby $X_i$ równolegle czasie stałym.
Sumator CSA jest w stanie w czasie stałym wczytać trzy liczby oraz zwrócić dwie liczby, których suma jest równa sumie liczb wejściowych.
Drzewo Wallace'a ma strukturę $W$ warstw sumatorów CSA.
Sumatory CSA w danej warstwie przyjmują jako kanały wejściowe kanały wyjściowe z warstwy poprzedniej.
Jeżeli liczba kanałów wyjściowych z warstwy poprzedniej nie jest podzielna przez $3$, nadmiarowe kanały ''bypassują'' warstwę i stają się kanałami wejściowymi warstwy następnej.
Liczba kanałów wyjściowych z danej warstwy jest około $\frac{3}{2}$-krotnie mniejsza od liczby kanałów wejściowych.
W związku z tym, dla $W = O(\log_{\frac{3}{2}} n) = O(\log n)$, liczba kanałów wyjściowych z ostatniej wastwy wyniesie $2$.
Owe kanały następnie wpuszczane są do dowolnego szybkiego addera, który dodaje je w czasie $O(\log n)$ (przykładowo CLA).
Złożoność całego algorytmu wyniesie $O(\log n)$.

## Zadanie 7

:::success
~~Autor: Krzysztof Jadłowski~~ (nieobecny podczas prezentacji)
:::



przykład użycia:
A - 9(1001) , B- 3(0011)
Prześledźmy co znajduje się w rejestrach w ciągu wykonywania algorytmu:
## 1.
### I)
A- 1001 -> 0010, B- 0011 , P - 0000 -> 0001(przeniesienie z A)
### II-IV)
A - 0010 -> 0010(ujemny wynik), B - 0011, P- 0001 ->0001(ujemny wynik)
## 2.
### I)
A- 0010 -> 0100, B-0011, P-0001 -> 0010

### II-IV)
A - 0100 -> 0100, B- 0011, P - 0010 -> 0010
## 3.
### I)
A- 0100 -> 1000, B- 0011 , P - 0010 -> 0100

### II-IV)
A - 1000-> 1001, B- 0011, P - 0100 -> 0001
## 4.
### I)
A - 1001 -> 0010, B- 0011, P- 0001 -> 0011

### II-IV)
A - 0010 -> 0011, B- 0011, P - 0011 -> 0000

Ostatecznie
9/3 = 3 reszta 0

## Zadanie 8

:::success
Autor: Marcin Sarnecki
:::


<u>Algorytm:</u>

Powtórz n razy:

Jeśli P < 0:
a) Przesuń rejestr (PA) w lewo
b) Dodaj zawartość rejestru B do rejestru P.
W przeciwnym razie:
a) Przesuń rejestr (PA) w lewo
b) Odejmij zawartość rejestru B od P
Jeśli P < 0:
a) Ustaw najmniej znaczący bit A na 0
W przeciwnym razie:
a) Ustaw najmniej znaczący bit A na 1

Na końcu jeśli P < 0:
Dodaj zawartość rejestru B do rejestru P.

Iloraz znajduje się w rejestrze A. Reszta znajduje się w rejestrze P.
Jeśli reszta jest ujemna, należy dodać do niej wartość B.

Różnica pomiędzy algorytmami restoring i nonrestoring polega na tym, że w wersji
nonrestoring jeśli po odjęciu wartości B wartość P stanie się ujemna, to nie przywracamy poprzedniej wartości poprzez dodanie wartości B.

| P | A | B | wykonana operacja|
| -------- | -------- | -------- | -------- |
| 00000 | 1001 | 00011 | inicjalizacja |
| 00001 | 001? | 00011 | Shift w lewo |
| 11110 | 001? | 00011 | odjęcie B od P |
| 11110 | 0010 | 00011 | ustawienie najmniej znaczącego bitu A na 0 |
| 11100 | 010? | 00011 | Shift w lewo |
| 11111 | 010? | 00011 | dodanie B do P |
| 11111 | 0100 | 00011 | ustawienie najmniej znaczącego bitu A na 0 |
| 11110 | 100? | 00011 | Shift w lewo |
| 00001 | 100? | 00011 | dodanie B do P |
| 00001 | 1001 | 00011 | ustawienie najmniej znaczącego bitu A na 1 |
| 00011 | 001? | 00011 | Shift w lewo |
| 00000 | 001? | 00011 | odjęcie B od P |
| 00000 | 0011 | 00011 | ustawienie najmniej znaczącego bitu A na 1 |

*Uzasadnienie poprawności*
Zauważmy, że działanie tego algorytmu jest podobne do działania algorytmu restoring division
Gdy P jest dodatnie, algorytm działa tak samo jak restoring division
Gdy P jest ujemne, to nie wykonujemy restore w rejestrze P, więc
wartość w rejestrze P jest mniejsza o B niż w sytuacji gdybyśmy zrobili restore
następnie po przesunięciu w lewo P w następnym kroku wartość w P jest mniejsza o 2B niż gdybyśmy zrobili restore,
ale skoro P jest ujemne to ten algorytm doda B do P
stąd otrzymamy odpowiednią wartość P, tak jak w algorytmie restoring division.

## Zadanie 9

:::success
Autor: Marcin Wróbel
:::
**Przedstaw algorytm dzielenia metodą SRT (ang. SRT division).**
Dzielimy **a** przez **b** obie są liczbami n bitowymi
Zapisujemy a do rejestru A (długość n)
Zapisujemy b do rejestru B (długość n)
Zapisujemy 0 do rejestru P (długość n+1, zapis U2)

1. Jeśli rejestr B ma k zer wiodących w zapisie n bitowym przesuń rejestr B oraz rejestr (PA) w lewo o k bitów
2. For i=n-1 to 0:
+ a) Jeśli 3 najbardziej znaczące bity P są sobie równe:<BR>przesuń rejestr (PA) w lewo, ustaw najmniej znaczący bit A na 0

+ b) Jeśli 3 najbardziej znaczące bity P nie są sobie równe i P jest ujemne:<BR>przesuń rejestr (PA) w lewo, ustaw najmniej znaczący bit A na -1, dodaj B do P.
- c) w przeciwnym przypadku:<BR>przesuń rejestr (PA) w lewo, ustaw najmniej znaczący bit A na 1, odejmij B od P.
End loop
3. Jeśli reszta ( P ) jest ujemna popraw wynik (A) odejmując od niego 1, oraz dodając B do P
4. Rejestr P musi być przesunięty o k bitów w prawo (odwracając przesunięcie z kroku 1)
5. A to iloraz, P to reszta

**Oraz zademonstruj działanie na wybranym przez siebie przykładzie.**
A=9₁₀
B=3₁₀
9₁₀/3₁₀
1001₂/0011₂
| P | A | B | -B | Komentarz|
| ----- | ---- | ----- | ---- | --- |
| 00000 | 1001 | 0011 | 11101 | Początkowy stan |
||||| 1. B ma 2 bity wiodące w zapisie 4-bitowym, SL(B) o 2 bity, SL(PA) o 2 bity |
| 00010 | 0100 | 1100 | 10100 | |
||||| 2.a) SL(PA), nowy bit 0 |
| 00100 | 100**0** | 1100 | 10100 | |
||||| 2.c) SL(PA), nowy bit 1|
| 01001 | 00**01** | 1100 | 10100 | |
||||| 2.c) odejmowanie B od P|
| 11101 | 00**01** | 1100 | 10100 | |
||||| 2.a) SL(PA), nowy bit 0|
| 11010 | 0**010** | 1100 | 10100 | |
||||| 2.b) SL(PA), nowy bit $\overline{1}$|
| 10100 | $\bf010\overline{1}$ | 1100 | 10100 | |
||||| 2.b) dodawanie B do P|
| 00000 | $\bf010\overline{1}$ | 1100 | 10100 | |
||||| 4. Reszta ( P ) jest dodatnia wszystko wynik jest ok |
||||| 5. Bity reszty są przesunięte o 2 bity w prawo |
| 00000 | $\bf010\overline{1}$| 1100 | 10100 | |

**Uzasadnij jego poprawność**
x,y - liczby bez znaku
dzielimy $\frac{x}{y}$
Na początku rejestr
$A = x$
$B = y$
$P = 0$
Dla uproszczenia
Część rejestru ( PA ) reprezentującą resztę będę oznaczał jako X,
Część rejestru ( PA ) reprezentującą iloraz będę oznaczał jako Q,

$\overbrace{10100\qquad1}^{X}\overbrace{\bf01\overline{1}}^{Q}$
$\underbrace{10100}_{P}\qquad\underbrace{1\bf01\overline{1}}_{A}$

---

**Fakt 1.**(pokazany poźniej)
Przed/po każdej iteracji pętli
$P \in <-B,B)$

**Dowód Faktu 1**
Przed/po każdej iteracji pętli
$P \in <-B,B)$

Przed pierwszą iteracją P=0, więc teza zachodzi
Jeśli dzielimy liczby n bitowe, to P ma n+1 bitów,
$P\in<-2^n,2^n-1>$,
w rejestrze B najbardziej znaczący bit jest równy 1
$B\in<2^{n-1},2^n-1>$ ,więc
$<-2^{n-1},2^{n-1}>\subseteq<-B,B>$
$<-2^{n-1},2^{n-1}-1>\subseteq<-B,B)$

2.a Gdy 3 najbardziej znaczące bity są sobie równe, to po SL
2 najbardziej znaczące bity są sobie równe, więc
$P \in <-2^{n}+2^{n-1},2^{n-2}+2^{n-1}+...+1>$
$P \in <-2^{n-1},2^{n-1}-1>$
Skoro B jest równe co najmniej $2^{n-1}$ , to
$P\in<-B,B)$
2.b P jest ujemne, więc
$P \in <-2^n,-1>$
po dodaniu B do P
$P \in <-2^n+2^{n-1},-1+B>$,więc
$P \in <-2^{n-1},B-1>$
$P\in<-B,B)$
3.c P jest dodatnie/równe 0, więc
$P \in <0,2^n-1>$
po odjęciu B od P
$P \in <0-B,2^n-1-2^{n-1}>$
$P \in <-B,2^{n-1}-1>$
$P \in <-B,2^{n-1}-1>$
$P \in <-B,B)$
$P \in <0,B)$

---
$\overbrace{10100\qquad1}^{X}\overbrace{\bf01\overline{1}}^{Q}$
$\underbrace{10100}_{P}\qquad\underbrace{1\bf01\overline{1}}_{A}$

Na początku oczywiście
$Q = 0$
I poprawny jest niezmiennik, przed każdą iteracją zachodzi:
$\frac{X}{B} + Q*2^{i} = wynik$
gdzie i to zmienna i w pętli for danej iteracji
$wynik$ - matematyczna postać dzielenia $\frac{x}{y}$
**1. Wykonanie przesunięcia o k bitów**
Przesuwamy
$\frac{X*2^k}{B*2^k} + Q*2^{i}*2^k = wynik$
Nadal nierówność będzie zachodzić, bo
$\frac{X*1}{B*1} + 0*2^{i}*2^k = wynik$
$\frac{X}{B} + 0 = wynik$
$\frac{X}{B} + Q*2^{i-1} = wynik$
Nowe wartośći rejestrów to
$X = X*2^k$
$B = B*2^k$
$Q = Q*2^k = Q$ ,bo $Q=0$
**2.a**
$\frac{X-B}{B} + Q*2^i = wynik$
Przesunięcie rejestru (PA) w lewo nie zmienia wartości w X
Q jest teraz o 2 większe w związku z przesunięciem, ale za to i się zmniejszy o 1, więc niezmiennik zostanie zachowany
$\frac{X-B}{B} + (Q*2)*2^{i-1} = wynik$
nowa wartość
$Q=Q*2$

**2.b**
Przesunięcie rejestru (PA) zachowuje niezmiennik,
natomiast odjęcie 1 do A i dodanie B od P, to
$\frac{X+B*2^{i-1}}{B} + (Q - 1)*2^{i-1} = wynik$
Działa, bo:
$\frac{X+B*2^{i-1}}{B} + Q*2^{i-1} - 1*2^{i-1} = wynik$
$\frac{X}{B}+\frac{B*2^{i-1}}{B} + Q*2^{i-1} - \frac{B*2^{i-1}}{B} = wynik$
$\frac{X}{B} + Q*2^{i-1}= wynik$

Nowe wartości rejestrów
$X = X+B*2^{i-1}$
$Q = Q-1$

**2.c**
Przesunięcie rejestru (PA) zachowuje niezmiennik,
natomiast dodanie 1 do A i odjęcie B od P, to
$\frac{X-B*2^{i-1}}{B} + (Q + 1)*2^{i-1} = wynik$
Działa, bo:
$\frac{X-B*2^{i-1}}{B} + Q*2^{i-1} + 1*2^{i-1} = wynik$
$\frac{X}{B}-\frac{B*2^{i-1}}{B} + Q*2^{i-1} + \frac{B*2^{i-1}}{B} = wynik$
$\frac{X}{B}*2^{i-1} + Q = wynik$

Nowe wartości rejestrów
$X = X-B*2^{i-1}$
$Q = Q+1$

**3.**
Niezmiennik zostaje zachowany analogicznie do 2.b
Po wykonaniu mamy stan:
$\frac{X}{B} + Q*2^0 = wynik$
Teraz X to dokładnie rejestr P, a Q to dokładnie rejestr A, więc
$\frac{P}{B} + A = wynik$
Skoro przed wykonaniem tego kroku
$P \in <-B,B)$
to po wykonaniu
$P \in <0, B)$

**4.**
W tym kroku dzielimy $P$ przez $2^k$
wykonując przesunięcie o k bitów w prawo i wirtualnie dzielimy też $B$
$\frac{P}{2^k} \in <0, \frac{B}{2^k})$
$\frac{P}{2^k} \in <0, y)$
Nowa wartość rejestru $P=\frac{P}{2^k}$, więc
$P \in <0, y)$
i wirtualnie traktujemy
$B=\frac{B}{2^k}$, więc
$\frac{P}{B} + A = wynik$
$\frac{P}{y} + A = wynik$
$P \in <0, y)$, więc
A to iloraz, a P to reszta z dzielenia przez y

---

<!-- Rejestr P zawsze przechowuje taką liczbę, że gdy jest ujemny zawsze po dodaniu B otrzymamy liczbę nieujemną, co za tym idzie dodatnią resztę. Wynika to z tego, że B zostało przesunięte w lewo, tak że najbardziej znaczący dodatni bit w B jest równy jeden. -->

**Jaka motywacja stoi za wprowadzeniem tego algorytmu?**
We wcześniejszych implementacjach dzielenia nie pomijamy żadnej operacji dodawania/odejmowania, ale jeżeli iloraz zawiera jakieś bity równe zero,
to moglibyśmy odpowiadające tym bitom operacje dodawania/odejmowania pominąć.
Stąd algorytm SRT division w podstawowej wersji działa szybciej, od poprzednich gdy jakieś bity wyniku są równe 0