# Ćwiczenia 3, grupa cz. 10-12, 14 marca 2024

###### tags: `SYK24` `ć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 |
| ----------------------:| -----| --- | --- | --- | --- | --- | --- |
Borys Adamiak | X | | | | | X | X |
Michał Chawar | X | | | | X | X | X |
Julia Cygan | X | | | | | X |==X==|
Maciej Dengusiak | X | | | | | X | X |
Patryk Flama | X | | | | | X | X |
Szymon Fluder | | | | | | X | X |
Aleksandra Jędrzejak | X | X | | | | X | X |
Mikołaj Karapka | X | | | | | X | X |
Viktoriia Kashpruk | X | X | | | X | X | X |
Wiktor Małek | X | X | | | | X | X |
Błażej Molik | X | X | | | | ==X== | X |
Andrzej Morawski | | | | | | | |
Konrad Oleksy | | | | | | | |
Lucjan Pucelak | X | | | | | X | X |
Aleksandra Sęk | | | | | | ==X== | |
Radosław Śliwiński | | | | | | | |
Piotr Traczyński | | | | | | X | X |
Katarzyna Trzos |==X== | X | | | X | X | X |
Piotr Warząchowski | X | X | | | | X | X |
Olga Zaborska | X | X | | | | X | X |
:::

Tu można zadeklarować zadanie **8** z **listy 2**:

:::danger
| | 2.8 |
| ----------------------:| -----|
Borys Adamiak | |
Michał Chawar | |
Julia Cygan | |
Maciej Dengusiak | |
Patryk Flama | |
Szymon Fluder | |
Aleksandra Jędrzejak | |
Mikołaj Karapka | |
Viktoriia Kashpruk | |
Wiktor Małek | |
Błażej Molik | |
Andrzej Morawski | |
Konrad Oleksy | |
Lucjan Pucelak | |
Aleksandra Sęk | |
Radosław Śliwiński | |
Piotr Traczyński | |
Katarzyna Trzos | |
Piotr Warząchowski | |
Olga Zaborska | |
:::

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

## Zadanie 1
:::success
Autor: Katarzyna Trzos
:::

Dwa przypadki:

1. Liczba A składa się z pojedyńczego bloku jedynek, np. A = -2 = (1110).
Traktując A jako liczbę bez znaku mamy A = 100(-1)0 = 16 - 2. W układzie mnożącym
nie uwzględniamy (czyli "nie mamy") skrajnie lewej jedynki (bo nie rozszerzamy liczby A o jeden bit), to naszym A jest 00(-1)0, czyli -2.

2. A składa się z wielu bloków jedynek, np:

$-13*B=(10011)*B = (10000)*B + (4-1)*B$

## Zadanie 2
:::success
Autor: Piotr Warząchowski
Zasada działania układu dzielącego dwie liczby bez znaku w wersji nonrestoring division opiera się na iteracyjnym odejmowaniu (lub dodawaniu, w przypadku negatywnego wyniku poprzedniej operacji) dzielnika od przesuwanego reszty i aktualizacji wyniku dzielenia na każdym kroku. Metoda ta nie przywraca oryginalnej wartości reszty po każdej iteracji, stąd nazwa "nonrestoring".

Oto szczegółowy opis kroków:

1. **Inicjalizacja**: Reszta inicjalizowana jest wartością dzielnej, a rejestr wynikowy (iloraz) ustawiany jest na 0. Długość rejestru reszty jest zwykle podwajana w stosunku do dzielnika, aby umożliwić przesunięcia bitowe.
2. **Iteracje**: Proces dzielenia wykonuje iteracje, gdzie każda z nich zawiera następujące kroki:

a. **Przesunięcie w lewo**: Zarówno reszta jak i iloraz są przesuwane o jeden bit w lewo. To zwiększa wartość ilorazu i przygotowuje miejsce na nowy bit ilorazu.

b. **Odejmowanie lub dodawanie**: Jeśli aktualna reszta jest nieujemna, odejmujemy dzielnik od reszty. W przypadku, gdy reszta jest ujemna (co nie powinno zdarzyć się przy liczbach bez znaku, ale jest rozważane dla ogólności metody), dodajemy dzielnik do reszty.

c. **Aktualizacja ilorazu**: W zależności od wyniku operacji w kroku 2b, najmniej znaczący bit ilorazu jest aktualizowany: ustawiany na 1, jeśli odjęliśmy dzielnik (co wskazuje na to, że część dzielnej była wystarczająco duża, aby pomieścić dzielnik), lub pozostawiany jako 0, jeśli dodaliśmy dzielnik.

3. **Korekta**: W metodzie nonrestoring zwykle nie ma potrzeby korekty na końcu, ponieważ liczby są bez znaku i nie powinno dochodzić do ujemnych reszt.
4. **Wynik**: Po wykonaniu odpowiedniej liczby iteracji, iloraz znajduje się w rejestrze ilorazu, a ostateczna reszta w rejestrze reszty.

**Uzasadnienie poprawności metody**:
Metoda jest poprawna, ponieważ w każdej iteracji dokładnie analizujemy, czy obecna część dzielnej może pomieścić dzielnik, i odpowiednio aktualizujemy iloraz. Przesuwanie reszty i ilorazu w lewo na każdym kroku odpowiada mnożeniu przez 2, co jest zgodne z binarnym systemem pozycyjnym i pozwala na efektywne budowanie ilorazu bit po bicie.

**Dowod**
Zauwazmy ze w momencie inicjalizacji Restoring dividion === Unrestoring division.

Jedyna roznica pojawia sie w miejscu gdy 2 * rk - 2^n * b < 0. W restoring division zmienilibysmy wynik na 2rk i kolejny krok policzylby 2 * 2rk - 2^n * b

W unrestoring zignorujemy to i pojawi sie 2 (2rk - 2^n * b) + 2^n * b = 4rk - 2^n * b

wiec widzimy ze jest to rownoważne, zatem nonrestoring division działa.

# Przyklad

1. **`00000 1110`** - Dzielna (**`14`** w systemie dziesiętnym) to **`1110`** w systemie binarnym. Część po lewej stronie będzie budowana jako wynik dzielenia, zaczynając od **`00000`**.
2. **`00001 110`** - Pierwszy krok to przesunięcie w lewo (1(i)-b), przesuwając wszystkie bity w obszarze wyniku o jedną pozycję w lewo i ściągając następny bit dzielnej.
3. **`11110 1100`** - Teraz odejmujemy dzielnik (**`3`** w systemie dziesiętnym, **`011`** w systemie binarnym) od przesuniętej dzielnej (krok 1(ii)-b), używając dopełnienia do dwóch do wykonania odejmowania. Ponieważ wynik jest ujemny (wskazany przez prowadzącą **`1`**), ustawiamy bit wyniku na **`0`**.
4. **`11101 100`** - Kolejne przesunięcie w lewo wyniku (krok 2(i)-a).
5. **`+00011`** - Przygotowujemy się do dodania dzielnika (w dodawaniu dopełnienia do dwóch, które jest takie samo jak dzielnik, ponieważ jest dodatni) (krok 2(ii)-a).
6. **`00000 1001`** - Wynik dodania dzielnika do ostatniego ujemnego wyniku (z kroku 3) (krok 2(iii)).
7. **`00001 001`** - Kolejne przesunięcie w lewo wyniku (krok 3(i)-b), przygotowując się do następnego odejmowania lub dodawania.
8. **`+11101`** - Zamierzamy odjąć dzielnik, ponieważ poprzedni wynik był nieujemny (dodaliśmy w ostatnim kroku).
9. **`11110 0010`** - Wynik odejmowania (krok 3(ii)). Ponieważ jest ujemny, ustawiamy kolejny bit wyniku na **`0`**.
10. **`11100 010`** - Kolejne przesunięcie w lewo wyniku (krok 4(i)-a).
11. **`+00011`** - Dodajemy dzielnik ponownie, ponieważ poprzedni wynik był ujemny (krok 4(ii)-a).
12. **`11111 0100`** - Wynik dodawania. Jest nadal ujemny, więc ustawiamy kolejny bit wyniku na **`0`**.
13. **`+00011`** - Ponieważ ostatni wynik jest ujemny, wykonujemy końcowy krok przywracania, dodając dzielnik po raz ostatni.
14. **`00010`** - Końcowy wynik dodawania, który jest resztą. Reszta jest dodatnia, więc nie są potrzebne żadne dodatkowe zmiany.
15. Wynik, który został zbudowany w lewej części to **`0100`** (co w systemie dziesiętnym daje **`4`**), a reszta to **`00010`** (**`2`** w systemie dziesiętnym). Zatem **`14`** podzielone przez **`3`** daje w wyniku **`4`** i resztę **`2`**.

Jest to algorytm dzielenia bez przywracania, który unika przywracania poprzedniej wartości, jeśli wynik odejmowania jest ujemny; zamiast tego bezpośrednio przechodzi do następnego kroku.
:::

## Zadanie 3
:::success
Autor: Viktoriia Kashpruk
Algorytm dzielenia SRT modyfikuje algorytm dzielenia bez reszty (non-restoring) poprzez optymalizację operacji, minimalizując liczbę kroków potrzebnych do obliczenia ilorazu i reszty. Dokonuje tego poprzez inteligentny wybór operacji w oparciu o wartość reszty, minimalizację operacji dodawania i odejmowania oraz efektywne obsługiwanie przypadków specjalnych, co prowadzi do szybszych i bardziej efektywnych obliczeń dzielenia.

**Przykład**
Algorytm najpierw przesuwa wszystkie rejestry tak, aby B był większy lub równy 1/2. Następnie mamy trzy opcje:
a) Jeśli $-1/4\leq r < 1/4$, to reszta jest zbyt mała, aby coś do niej dodać lub odjąć, więc dodajemy zero i mnożymy resztę przez 2.
b) Jeśli $r<-1/4$, to reszta jest zbyt mała, więc po pomnożeniu przez dwa dodajemy B i ustawiamy 1 w wyniku.
c) Jeśli $r \geq 1/4$, to reszta jest zbyt duża, więc pomnażamy resztę przez 2, odejmujemy B i ustawiamy 1 w wyniku.

Dzięki tej procedurze, działającej na zasadzie podziału liczby na największe możliwe części, otrzymujemy wynik. Po wykonaniu algorytmu, zostanie nam reszta mniejsza niż 1 oraz dwie liczby, których suma daje oczekiwany wynik. Algorytm ten działa szybko, gdy dane są tak dobrane, że wiele bitów w wyniku jest zerami, co eliminuje konieczność dodawania lub odejmowania B.
:::

## Zadanie 4
:::danger
Autor: do zadeklarowania na następnych ćwiczeniach
:::

## Zadanie 5
:::success
Autor: Michał Chawar
:::


Aby przyspieszyć mnożenie przekonwertujemy sobie ($n$ bitową) liczbę $a$ w systemie binarnym na system czwórkowy. Wtedy zredukujemy liczbę cyfr w $a$ o połowę, jednak utrudnimy sobie dodawanie $b$ do rejestru $P$.

Niech $a' = [ (a_{n}a_{n-1})_2(a_{n-1}a_{n-3})_2...(a_{1}a_{0})_2 ]_4$. Wtedy w $i$-tym kroku rozważamy pary $(a_{2i+1}a_{2i})$, które jednak mogą przyjmować jedną z wartości $0, 1, 2, 3$. Przy $0$ nic nie robimy, przy $1$ dodajemy liczbę $b$, przy $2$ dodajemy liczbę $2 \cdot b$, lecz przy $3$ musimy dodać liczbę $2b+b=3b$, której nie osiągniemy przesunięciem bitowym. Ponownie więc użyjemy kodowania Booth'a na całej liczbie $a$ i określimy interesujące nas pary używając dodatkowo bitu $a_{2i-1}$ w następujący sposób ($x$ to liczba, którą będziemy dodawać do $P$ w tym kroku):

| $a_{2i+1}$ | $a_{2i}$ | $a_{2i-1}$ | $x$ | Zamiana $\ \ \ \rightarrow$ | $a_{2i+1}$ | $a_{2i}$ | $a_{2i-1}$ |
| -------- | -------- | -------- | -------- | -------- | -------- | -------- | -------- |
| $0$ | $0$ | $0$ | $0$ | | $0$ | $0$ | $0$ |
| $0$ | $0$ | $1$ | $b$ | początek jedynek | $0$ | $1$ | $?$ |
| $0$ | $1$ | $0$ | $b$ | nie zamieniamy nic | $0$ | $1$ | $0$ |
| $0$ | $1$ | $1$ | $2b$ | początek jedynek | $1$ | $0$ | $?$ |
| $1$ | $0$ | $0$ | $-2b$ | koniec jedynek | $\overline1$ | $0$ | $0$ |
| $1$ | $0$ | $1$ | $-b$ | nałożenie (-2 + 1) | $\overline1$ | $1$ | $?$ |
| $1$ | $1$ | $0$ | $-b$ | koniec jedynek | $0$ | $\overline1$ | $0$ |
| $1$ | $1$ | $1$ | $0$ | | $0$ | $0$ | $0$ |

Po każdym tak wykonanym kroku przesuwamy rejestry $P$ i $A$ o dwie pozycje, bo rozważyliśmy dwa ostatnie bity.

Przykład ($a=-14=110010_2$ , $b=-11=110101_2$ , $-b=001011_2$):

| $P$ | $A$ | $a_{-1}$ | Tłumaczenie |
| -------- | -------- | -------- | -------- |
| $\ \ \ 0000000$ | $110010$ | $0$ | $100 \Rightarrow -2b$ |
| $+0010110$ | | | $=-2b$ |
| $\ \ \ 0010110$ | $110010$ | | Przesuwamy, $P$ uzupełniamy arytmetycznie |
| $\ \ \ 0000101$ | $101100$ | $1$ | $001 \Rightarrow b$ |
| $+1110101$ | | | $=b$ |
| $\ \ \ 1111010$ | $101100$ | | Przesuwamy |
| $\ \ \ 1111110$ | $101011$ | $0$ | $110 \Rightarrow -b$ |
| $+0001011$ | | | $=-b$ |
| $\ \ \ 0001001$ | $101011$ | | Przesuwamy |
| $\ \ \ 0000010$ | $011010$ | | Wynik |

Otrzymaliśmy $010011010_2=154_{10}=-14 \cdot (-11)$.

## Zadanie 6
:::success
Autor: Błażej Molik
:::

| $l$ | $RD_{\circ}(l)$ | $RD_{\bullet}(l)$ |
| -- | -------- | -------- |
| 1 | (x, ?), (y, ?), (i, ?), (t, ?), (z, ?) | (x, 1), (y, ?), (i, ?), (t, ?), (z, ?) |
| 2 | (x, 1), (y, ?), (i, ?), (t, ?), (z, ?) | (x, 1), (y, 2), (i, ?), (t, ?), (z, ?) |
| 3 | (x, 1), (y, 2), (i, ?), (t, ?), (z, ?) | (x, 1), (y, 2), (i, 3), (t, ?), (z, ?) |
| 4 | (x, 1), (y, 2), (i, 3), (t, 5), (z, ?), (x, 6), (y, 7), (i, 8) | (x, 1), (y, 2), (i, 3), (t, 5), (z, ?), (x, 6), (y, 7), (i, 8) |
| 5 | (x, 1), (y, 2), (i, 3), (t, 5), (z, ?), (x, 6), (y, 7), (i, 8) | (x, 1), (y, 2), (i, 3), (t, 5), (z, ?), (x, 6), (y, 7), (i, 8) |
| 6 | (x, 1), (y, 2), (i, 3), (t, 5), (z, ?), (x, 6), (y, 7), (i, 8) | (x, 6), (y, 2), (i, 3), (t, 5), (z, ?), (y, 7), (i, 8) |
| 7 | (x, 6), (y, 2), (i, 3), (t, 5), (z, ?), (y, 7), (i, 8) | (x, 6), (y, 7), (i, 3), (t, 5), (z, ?), (i, 8) |
| 8 | (x, 6), (y, 7), (i, 3), (t, 5), (z, ?), (i, 8) | (x, 6), (y, 7), (i, 8), (t, 5), (z, ?) |
| 9 | (x, 1) (x, 6), (y, 2), (y, 7), (i, 3), (i, 8), (t, 5), (z, ?) | (x, 1) (x, 6), (y, 9), (i, 3), (i, 8), (t, 5), (z, ?) |

## Zadanie 7
:::success
Autor: Julia Cygan
Definicja: Dla każdej zmiennej x i etykiety I, czy zmienna w każdym wykonaniu ma stałą wartość na wejściu do instrukcji I.

Fakt: ma postać (zmienna, wartość).
Powinno być RDin(1) = {(x,?);(y,?);(z,?)}


Zauważmy, że:


Optymalizacja:


:::