# Ć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
:::

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$_$k$ 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$_$k$
Przesuwając w lewo, obliczamy $2r$_$k$

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

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

*wpp*

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

Czyli $r$_$restoring$ = $r$_$non-restor$
Algorytm działa poprawnie.

#### Przykład

:::

## 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
:::





Machanie rękami zaprezentowane w paincie

## Zadanie 6
:::success

Autor: Piotr Thamm


| 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]