---
# System prepended metadata

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

---

# Ćwiczenia 3, grupa cz. 16-18, 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   |
| ----------------------:| -----| --- | --- | --- | --- | --- | --- |
Marcin Banak             |   X   |  X   |     |     |     |  X   |   X  | 
Bartosz Borecki          |   X   |     |     |     |     |  X   |  X   | 
Karol Burczyk            |   X   |     |     |     |     |   X  |   X  | 
Yelyzaveta Ilman         |  X    |==X==|     |     |     |X     | X    | 
Antoni Kamiński          |   X   |  X   |     |     |     |  X   |  X   | 
Jan Kamyk                |  X   |  X  |     |     |     |  X  |     | 
Bartosz Kruszewski       | X    | X   |     |     |     |  X  | ==X==   | 
Hanna Laszkiewicz        |   X   |  X   |     |     |     |     X|   X  | 
Kaja Matuszewska         |      |     |     |     |     |     |     | 
Dominik Muc              |      |     |     |     |     |     |     | 
Krzysztof Ostrowski    |   X   | X    |     |     |     |  X   |    X | 
Franciszek Przeliorz     |   X   |  X   |     |     |     |  X   |  X   |
Yaryna Rachkevych        |   X   |     |     |     |     |   X  |  X   | 
Piotr Thamm              |   X   |   X  |     |     |     |   ==X==  |    X | 
Taras Tsehenko           |  ==X==  |  X   |     |     |     |  X   |  X  | 
:::

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


:::danger
|                        | 2.8  |
| ----------------------:| -----|
Marcin Banak             |      | 
Bartosz Borecki          |      | 
Karol Burczyk            |      | 
Yelyzaveta Ilman         |      | 
Antoni Kamiński          |      | 
Jan Kamyk                |      | 
Bartosz Kruszewski       |      | 
Hanna Laszkiewicz        |      | 
Kaja Matuszewska         |      | 
Dominik Muc              |      | 
Krzysztof Ostrowski      |      |
Franciszek Przeliorz     |      |
Yaryna Rachkevych        |      |
Piotr Thamm              |      | 
Taras Tsehenko           |      | 
:::





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




## Zadanie 1
:::success
Autor: Taras Tsehenko
![zad1](https://hackmd.io/_uploads/SkM98ceAT.png)
:::


A = (1100). Traktujemy A jako liczbę bez znaku i używamy kodowania Bootha 
Dostajemy (10(-1)00). Ale nasz algorytm uruchamiamy dalej dla n będącego rozmiarem oryginalnej liczby A. W trzeciej iteracji odejmiemy liczbę 4.

Jeśli A ma więcej bloków jedynek, np A = (1101), to $A*B = (1100) *B + (0001)*B 


## Zadanie 2
:::success
Autor: Yelyzaveta Ilman	
#### Algorytm
```
n - liczba bitów
B - dzielnik
A - liczba którą dzielimy
P - acc

Powtóż n razy:
        Jeśli P jest ujemne:
            - Przesuń (P, A) w lewo
            - Dodaj B do P
        Wpp:
            - Przesuń (P, A) w lewo
            - Odejmij B od P (dodaj dopełnienie M)
            
        Jeśli P jest ujemne:
            - A_0 = 0
        Wpp:
            - A_0 = 1
Jeżeli P jest ujemne:
        P = P + B
wpp:
A = wymik
P = reszta
```
   
 #### Poprawność dzielenia tą metodą
 
Poprawność uzasadnimy odwołując się do poprawności restoring devision.
*Cel*: pokazać, że dają takie same wyniki

Niech $r$<sub>$k$</sub> to wartość pary rejestrów $PA$ po $k$-tym kroku (na początku $0$)

Rozważmy sens poszczególnych kroków w obydwu algorytmach:

Na początku mamy $r$<sub>$k$</sub>
Przesuwając w lewo, obliczamy $2r$<sub>$k$</sub>

Jeżeli $2r$<sub>$k$</sub> - $2^n * b$ $\ge$ 0 ($P$ jest nieujemne)

1. **restoring:** nie przewracamy poprzedniej wartości 
            $r$<sub>$k+1$</sub> = $2r$<sub>$k$</sub> - $2^n * b$ 
2. **non-restoring:** początkowa wartość P była nieujemna -> dodajemy dopełnienie $B$
    $r$<sub>$k+1$</sub> = $2r$<sub>$k$</sub> - $2^n * b$ 
    
*wpp*

1) **restoring:** przewracamy starą wartość
$r$<sub>$k+1$</sub> = 2$r$<sub>$k$</sub>
w kolejnym kroku: 
$r$<sub>$restoring$</sub> = $2r$<sub>$k+1$</sub> - $2^n * b$ = $4r$<sub>$k$</sub> - $2^n * b$ 
2) **non-restoring:** skończyliśmy z $r$<sub>$k+1$</sub> =  $2r$<sub>$k$</sub> - $2^n$ *$b$
w kolejnym kroku: 
$r$<sub>$non-restor$</sub> = $2$($2r$<sub>$k$</sub> - $2^n *b$) + $2^n * b$

Czyli $r$<sub>$restoring$</sub> = $r$<sub>$non-restor$</sub> 
Algorytm działa poprawnie.




 #### Przykład
 ![image](https://hackmd.io/_uploads/HkPGD5eC6.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: Jan Kamyk	
:::

![zad5_polecenie](https://hackmd.io/_uploads/HkCFW0KR6.png)

![zad5_1](https://hackmd.io/_uploads/SJ-3WAYR6.png)

![zad5_2](https://hackmd.io/_uploads/H1s2ZCKC6.png)

![zad5_3](https://hackmd.io/_uploads/S17abRK0T.png)

Machanie rękami zaprezentowane w paincie


## Zadanie 6
:::success

Autor: Piotr Thamm

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



| i   | $Rd_{\circ} (l)$                                          | $Rd_{\bullet}(l)$                                        |
| --- | --------------------------------------------------------- | -------------------------------------------------------- |
| 1   | {(x,?), (y,?), (t,?), (i,?), (z,?)}                       | {(x,1), (y,?), (t,?), (i,?), (z,?)}                      |
| 2   | {(x,1), (y,?), (t,?), (i,?), (z,?)}                       | {(x,1), (y,2), (t,?), (i,?), (z,?)}                      |
| 3   | {(x,1), (y,2), (t,?), (i,3), (z,?)}                       | {(x,1), (y,2), (t,?), (i,3), (z,?)}                      |
| 4   | {(x,1), (y,2), (t,5), (i,3), (z,?), (x,6), (y,7), (i,8)}  | {(x,1), (y,2), (t,5), (i,3), (z,?), (x,6), (y,7), (i,8)} |
| 5   | {(x,1), (y,2), (t,5), (i,3), (z,?), (x,6),  (y,7), (i,8)} | {(x,1), (y,2), (t,5), (i,3), (z,?), (x,6), (y,7), (i,8)} |
| 6   | {(x,1), (y,2), (t,5), (i,3), (z,?), (x,6), (y,7), (i,8)}  | {(x,6), (y,2), (t,5), (i,3), (z,?), (y,7), (i,8)}        |
| 7   | {(x,6), (y,2), (t,5), (i,3), (z,?), (y,7), (i,8)}         | {(x,6), (y,7), (t,5), (i,3), (z,?), (i,8)}               |
|   8 |   {(x,6), (y,7), (t,5), (i,3), (z,?), (i,8)}| {(x,6), (y,7), (t,5), (z,?), (i,8)}                                                         |
|   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: Bartosz Kruszewski	
:::

**a) definicja**
Analiza przepływu danych to zbadanie jak dane zmieniają się podczas działania programu (pod kątem przypisania). Pozwala to na optymalizację kodu.

**b) fakt**
*<nr_instrukcji, {<zmienna, wartość funkcji lub wartość nieznana>, ...}>*

Fakty propagujemy według następującej zasady:
- jeżeli poprzednia wartość się nie zmienia to przerzucamy ją dalej
- jeżeli mamy zejście dwóch ścieżek i wartości są różne lub nieznane to przerzucamy dalej wartość nieznaną

**c) fakty dla przykładu z zadania**
```
1. [x := 10]
    in: {(x, ?), (y: ?), (z: ?)}
    out: {(x, 10), (y: ?), (z: ?)}

2. [y := x + 10]
    in: {(x, 10), (y: ?), (z: ?)}
    out: {(x, 10), (y: 20), (z: ?)}

3. [z := y + x] 
    in: {(x, 10), (y: 20), (z: ?)}
    out: {(x, 10), (y: 20), (z: 30)}
```

**Optymalizacja kodu**
Wartość $x$ jest przypisywana tylko w 1. instrukcji i później się nie zmienia, więc możemy od razu wyliczyć $y$. 

Wartość $y$ też nie jest już później przypisywana ponownie, więc postępujemy tak samo dla $z$.

Optymalizuje to ilość operacji arytmetycznych.
```
[x := 10] [y := 20] [z := 30]
```

