---
# System prepended metadata

title: 'Ćwiczenia 3, grupa śr. 14-16, 13 marca 2024'
tags: [pwit, ćwiczenia, SYK24]

---



---


---
# Ćwiczenia 3, grupa śr. 14-16, 13 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   |
| ----------------------:| -----| --- | --- | --- | --- | --- | --- |
Krzysztof Chorzempa      |      |     |     |     |     |  X  |  X  | 
Maciej Ciepiela          |  X   |  X  |     |     |  X  |  X  |  X  |
Szymon Fica              |  X   |  X  |     |     |  X  |  X  |  ==X==  | 
Agnieszka Grala          |   X   |   X  |     |     |  X   |   X  |  X   | 
Karolina Jędraszek       |==X==     | X    |     |     |  X   |  X   |   X  | 
Katarzyna Jodłowska      |   X   |  X   |     |     |   X  |  X   |  X   | 
Dominik Kiełbowicz       |      |     |     |     |     |     |     | 
Michał Kolasa            |      |     |     |     |     |     |     | 
Rafał Krysa              |   X   |  X   |     |     |     |   X  |  X   | 
Miłosz Krzysiek          |   X   |  X   |     |     |  X   |  ==X==   |  X   | 
Łukasz Kulczycki         |      |     |     |     |     |     |     | 
Leon Lepkowski          |   X   |   ==X==   |     |     |     |   X   |   X   | 
Hanna Makowska           |   X   |  X   |     |     |     |  X   | X    |
Jan Marek                |   X  |  X  |     |     |     |     |     |
Cezary Miłek             |   X   |  X   |     |     |  X   |  X   |   X  | 
Anna Pierzchała          |  X   | X   |     |     |  X  |  X  |  X  | 
Alan Pietrasz            |   X   |  X   |     |     |   ==X==  |  X   |  X   | 
Kacper Ponikowski        |    X  |     |     |     |     |     X|  X   | 
Dominik Walecko          |      |   X  |     |     |     |  X   |  X   | 
Michał Włodarczak        |   X   |  X   |     |     |     |  X   |  X   | 
:::



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




## Zadanie 1
:::success
Autor: 	Karolina Jędraszek
:::
*Czym jest kodowanie Bootha (ang. Booth encoding/recording)? Pokaż, w jaki sposób użyć tego kodowania w układzie mnożącym dwie liczby w naturalnym kodzie binarnym. Następnie uzasadnij, że zmodyfikowany układ można użyć do mnożenia liczb ze znakiem. Jakich dalszych modyfikacji to wymaga?*

**Kodowanie Bootha** polega na redukcji bloku jedynek w liczbie.
np. 7 = 111 = 2^3 - 1 = 100(-1)

Ogólny schemat:
Wszystkie jedynki (poza pierwszą od prawej) w bloku zamieniamy na 0, pierwszą z prawej zmieniamy na (-1), następnie z lewej strony dostawiamy 1.

**Mnożenie liczb bez znaku:**

![Screenshot 2024-03-12 at 11.05.10](https://hackmd.io/_uploads/rk8yYjp6T.png)

Obserwacja:
Jeśli najmniej znaczący bit A to 0, to nie musimy wykonywać żadnych obliczeń.
Będziemy więc zamieniali bloki jedynek zgodnie z kodowaniem Bootha.
Aby to zrobić będziemy musieli dodać jeszcze jeden bit A (pamiętający poprzednią ostatnią cyfrę).
![Screenshot 2024-03-12 at 11.06.50](https://hackmd.io/_uploads/ByEDFjTTa.png)
Korzystamy z obserwacji i nie musimy wykonywać dodawania w I. i IV.


**Mnożenie liczb ze znakiem:**
Trzymamy liczby w U2.
Musimy zwrócić uwagę na znak P podczas przesunięcia w prawo

Jeśli B < 0 i A > 0, to wystarczyłoby robić przesunięcia arytmetyczne zamiast logicznych (dla P).
Robimy przesunięcia arytmetyczne dla P, czyli najbardziej znaczący bit P to będzie jego znak, a nie C_out.

Jeśli B < 0 i A < 0, to musimy dodatkowo
Umieć odejmować.

![423944068_388881577111027_6622871219916113645_n](https://hackmd.io/_uploads/SyQCOz1RT.png)

**Dlaczego to działa?**
![Screenshot 2024-03-12 at 12.51.07](https://hackmd.io/_uploads/HyA6ba6aa.png)


Przykład: a = -4 = 1100. Potraktować 1100 jako liczbę bez znaku, tj. 12. Rozszerzamy zapis do 5 bitów i kodujemy Booth'em: 10(-1)00 = 16 - 4

a = 1110, rozszerzamy do 5 bitów: 100(-1)0



## Zadanie 2
:::success
Autor: 	Leon Lepkowski	
:::

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

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

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


#### Poprawność algorytmu
![image](https://hackmd.io/_uploads/Sk5a0PC6T.png)


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

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

## Zadanie 5
:::success
Autor: 	Alan Pietrasz
:::
![image](https://hackmd.io/_uploads/ryX5qXkCp.png)
![image](https://hackmd.io/_uploads/HkG-b4JCa.png)



Algorytm analizuje w każdym kroku ostatnie 2 bity w rejestrze A 1 bit za rejestrem A na ich podstawie dodaje odpowiednią wielokrotność B do rejestru P.
W każdym kroku robimy podwójne przesunięcie.
![image](https://hackmd.io/_uploads/S1TUcmJAT.png)

* $00|0$ - znajdujemy się w środku bloku 0
`+0`
* $00|1$ - znajdujemy się na końcu bloku 1
$00|1$...$111$ = 
$01|0$...$00\overline{1}$
`+b`
* $01|0$ - standardowe dodanie b
`+b`
* $01|1$ - znajdujemy się na końcu bloku 1
$01|1$...$111$ = 
$10|0$...$00\overline{1}$
`+2b`
* $10|0$ - znajdujemy się na początku bloku 1
$01$...$10|0$ = 
$10$...$\overline{1}0|0$
`-2b`
* $10|1$ - znajdujemy się na początku bloku 1 i na końcu poprzedniego bloku 1
$011$...$10|1$...$111$ = 
$100$...$\overline{1}1|0$...$00\overline{1}$
`-2b + b = -b`
* $11|0$ - znajdujemy się na początku bloku 1
$01$...$11|0$ = 
$10$...$0\overline{1}|0$
`-b`
* $11|1$ - znajdujemy się w środku bloku 1
`+0`
![image](https://hackmd.io/_uploads/rkiv5QJ0a.png)

Algorytm pozwala na dwukrotne zredukowanie liczby kroków względem tradycyjnego algorytmu.


## Zadanie 6
:::success
Autor: 	Miłosz Krzysiek	
:::

![Screenshot from 2024-03-12 13-46-36](https://hackmd.io/_uploads/Sk23RTaap.png)

**Graf przepływu sterowania**

![03bb7cb8-b131-4bde-a60a-93674d5fd650](https://hackmd.io/_uploads/H19SRzApT.jpg)

**Zbiory faktów na wejściu do instrukcji $RD_\circ$**

![f403d876-6cc7-4652-86f4-f97baf158b69](https://hackmd.io/_uploads/B1FKFEC6p.jpg)

**Zbiory faktów na wyjściu do instrukcji $RD_\bullet$**

![e1d15553-0716-4226-aa10-ace20d39f8e6](https://hackmd.io/_uploads/rkjuQSA6a.jpg)

## Zadanie 7
:::success
Autor: 	Szymon Fica	
:::

**Definicja**
Analiza przepływu danych w programie komputerowym to zbadanie jak dane zmieniają się w różnych częściach programu (nie pod kątem bezpośrednio ich wartości, a miejsca, gdzie zostały przypisane). Dzięki niej możemy zoptymalizować kod.

**Struktura faktu**
Pamiętamy stan zmiennych na określonej wysokości jako parę
(zmienna, miejsce przypisania).

**zbiory faktów dla instrukcji z przykładu**
```
[x := 10] 1
wejście: {(x, ?), (y: ?), (z: ?)}
wyjście: {(x, 1), (y: ?), (z: ?)}

[y := x+10] 2
wejście: {(x, 1), (y: ?), (z: ?)}
wyjście: {(x, 1), (y: 2), (z: ?)}


[z := y + z] 3
wejście: {(x, 1), (y: 2), (z: ?)}
wyjście: {(x, 1), (y: 2), (z: 3)}
```

Możemy zauważyć, że wartość $x$ jest przypisywana tylko w pierwszej instrukcji i później się nie zmienia. Nie musimy więc w 2. instrukcji uzależniać $y$ od $x$ - możemy od razu je wyliczyć. Wartość $y$ też nie jest już później przypisywana ponownie, więc możemy postąpić tak samo.
W ten sposob unikniemy zbędnych operacji arytmetycznych.
```
[x := 10] 1
[y := 20] 2
[z := 30] 3
```


```
[x:=3]^3
if (użytkownik_wpisał_0) then [x:=3]^4

// x zostało zmienione w 3 lub x zostało zmienione w 4
// fakt jest postaci (zmienna, etykieta, wartość), wartość to jest liczba lub NIE
//optymalizacja: pominąć etykietę

t := x + y
```




Co chcemy wiedzieć przed wejściem do poniższej instrukcji: 
`` [t = x + y] ``


**Definicja**
"Analiza stałych wartości": dla każdej zmiennej x i etykiety l, czy x w każdym wykonaiu programu ma stałą wartość na wejściu do instrukcji o etykiecie l. 

Fakt jest postaci: (zmienna, wartość), gdzie wartość jest ze zbioru $Z \cup NIE$. Stała NIE -- zmienna nie ma stałej wartości na wejściu do l. 






```
[x := 10] 1
wejście: {(x, ?), (y, ?), (z, ?) }
wyjście: {(x, 10)}

[y := x+10] 2
wejście: {(x, 10)}
wyjście: {(x, 10), (y: 20),}


[z := y + z] 3
wejście: {(x, 10), (y: 20)}
wyjście: {(x, 10), (y: 20), (z: 30)}
```


```
{(x, ?), (t, ?)}
[x:=3]^3
{(x, 3), (t, ?)}

if (warunek_zależny_od_wejścia) then  {(x, 3), (t, ?)} [x:=4]^4 {(x,4), (t, ?)}

{(x, 3), (x, 4), (t, ?)}


// x zostało zmienione w 3 lub x zostało zmienione w 4
// fakt jest postaci (zmienna, wartość)

t := x + y
```
{(x, 3), (x, 4), (t, ?)}


t := x + 3
```
{(x, 3), (x, 4), (t, 6), (t, 7)}

A co z pętlą?

To zadanie jeszcze nie jest rozwiązane!!

fakt (x, ?) -- x ma wartość nieznaną, nie-stałą

Na wejściu do instrukcji mamy > 1 ścieżkę wejściową:

jeśli w zbiorach wchodzących z różnych ścieżek wystpują fakty (x, w1) w jednym
a (x, w2) w drugim i w1 \neq w2, to w zbiorze-sumie wystąpi fakt (x, ?).














