---
# System prepended metadata

title: 'Ćwiczenia 3, grupa cz. 10-12, 14 marca 2024'
tags: [pwit, ćwiczenia, SYK24]

---

# Ć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
:::
![IMG_0336](https://hackmd.io/_uploads/SkBsZBxAp.jpg)
![IMG_0337](https://hackmd.io/_uploads/S1HiZSgCa.jpg)

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.
![image](https://hackmd.io/_uploads/BkYhhdYCT.png)

**Przykład**
![image](https://hackmd.io/_uploads/BykChdK0a.png)
![image](https://hackmd.io/_uploads/Skb16dtAa.png)
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	
:::

![image](https://hackmd.io/_uploads/Hyts9NeCT.png)

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	
:::
![image](https://hackmd.io/_uploads/BJ9m3V10a.png)
![image](https://hackmd.io/_uploads/SJAnVSeAT.png)


| $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,?)}

![zad_7_first_it](https://hackmd.io/_uploads/rynWSBxCp.jpg)

Zauważmy, że:

![zad_7_second_it](https://hackmd.io/_uploads/S1ER4SlR6.jpg)

Optymalizacja:

![zad_7_optimized](https://hackmd.io/_uploads/HyaoVrxC6.jpg)

:::

