# Ćwiczenia 3, grupa śr. 12-14, 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 |
| ----------------------:| -----| --- | --- | --- | --- | --- | --- |
Mikołaj Balwicki | | | | | | | |
Małgorzata Galińska | ==X== | X | | | | X | X |
Maria Hreniak | X | ==X== | | | | X | X |
Jakub Jankowski | X | X | | | | X | X |
Mikołaj Kalitka | X | X | | | | X | X |
Julia Konefał | X | X | | | | ==X== | X |
Julia Kulczycka | X | X | | | | X | X |
Cecylia Łyjak | | | | | | | |
Adam Majchrowski | X | X | | | ==X== | X | X |
Piotr Mańkowski | | | | | | | |
Piotr Salamon | X | X | | | | X | ==X== |
Maciej Szałasz | X | X | | | | X | X |
:::

Tutaj można zadeklarować zaległe zadania **6** i **8** z **listy 2**:

:::danger
| Imię i nazwisko | 2.6 | 2.8 |
| ----------------------:| -----| -----|
| | |
| | |
:::

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

## Zadanie 1
:::success
Autor: Małgorzata Galińska
:::

Kodowanie Bootha polega na dodaniu dodatkowej wartości bitu: (-1). Tym sposobem możemy wyrażać długie ciągi jedynek …0111110… jako …10000(-1)0… i czasami dzięki temu oszczędzać czas przy mnożeniu dwóch liczb. Jeśli liczba A to powyższa liczba i mamy wymnożyć ją przez B, to zamiast 5 razy mnożyć B i 4 razy do siebie dodawać, wymnożymy B raz przez 1 i raz przez (-1) i dodamy te dwie liczby do siebie.

W układzie mnożącym dwie liczby w naturalnym kodzie binarnym będziemy sprawdzać dwa sąsiednie bity jakiej są postaci:
• 10 – rozpoczyna się ciąg jedynek, odejmujemy od wyniku B
• 11 – jesteśmy w ciągu jedynek, nie robimy nic
• 00 – jesteśmy w ciągu zer, nie robimy nic
• 01 – koniec ciągu jedynek, dodajemy do wyniku B

Inicjalizacja: Dodaj jedną dodatkową pozycję bitową po prawej stronie liczby A, ustawiając ją na 0.
1. Podział liczby A: Podziel A na grupy bitów o długości 2 (11, 00, 01, 10).
2. Iteracje:
• Dla każdej grupy bitów w A:
o Jeśli bity to "00" lub "11", pozostaw P bez zmian.
o Jeśli bity to "01", wykonaj operację P + B.
o Jeśli bity to "10", wykonaj operację P - B.
3. Przesunięcie bitowe: Po każdej iteracji przesuń bity P i A w prawo o jedno miejsce.

Aby mnożyć liczby ze znakiem należy zmienić zwykłe przesunięcie w prawo na arytmetyczne przesunięcie w prawo, aby móc zachować poprawny znak wyniku.
Zmodyfikowany algorytm:

Inicjalizacja: Dodaj jedną dodatkową pozycję bitową po prawej stronie liczby A, ustawiając ją na 0.
1. Podział liczby A: Podziel A na grupy bitów o długości 2 (np., 00, 01, 10).
5. Iteracje:
• Dla każdej grupy bitów w A:
o Jeśli bity to "00" lub "11", pozostaw P bez zmian.
o Jeśli bity to "01", wykonaj operację P + B.
o Jeśli bity to "10", wykonaj operację P - B (jeśli B jest ujemne, to jest to jednoznaczne z dodaniem liczby przeciwnej do B)
6. Przesunięcie bitowe: Po każdej iteracji przesuń bity P i A arytmetycznie w prawo o jedno miejsce. Dzięki temu zachowujemy znak P.

Przykład działania:

## Zadanie 2
:::success
Autor: Maria Hreniak
:::


PRZYKŁAD DZIELENIA:



## Zadanie 3
:::danger
Autor: do zadeklarowania następnym razem
:::

## Zadanie 4
:::success
Autor: Jakub Jankowski

:::

## Zadanie 5
:::success
Autor: Adam Majchrowski
:::

## Zadanie 6
:::success
Autor: Julia Konefał
| $l$ | $RD_{\circ} (l)$ | $RD_{\bullet} (l)$ |
| --- | ------------------------------------------------------------------------ | ------------------------------------------------------------------------ |
| 1 | {(x, ?), (y, ?), (t, ?), (i, ?)} | {(x, 1), (y, ?), (t, ?), (i, ?)} |
| 2 | {(x, 1), (y, ?), (t, ?), (i, ?)} | {(x, 1), (y, 2), (t, ?), (i, ?)} |
| 3 | {(x, 1), (y, 2), (t, ?), (i, ?)} | {(x, 1), (y, 2), (t, ?), (i, 3)} |
| 4 | {(x, 1), (y, 2), (t, ?), (i, 3), (t, 5), (x, 6), (y, 7), (i, 8)} | {(x, 1), (y, 2), (t, ?), (i, 3), (t, 5), (x, 6), (y, 7), (i, 8)} |
| 5 | {(x, 1), (y, 2), (t, ?), (i, 3), (t, 5), (x, 6), (y, 7), (i, 8)} | {(x, 1), (y, 2), (i, 3), (t, 5), (x, 6), (y, 7), (i, 8)} |
| 6 | {(x, 1), (y, 2), (i, 3), (t, 5), (x, 6), (y, 7), (i, 8)} | { (y, 2), (i, 3), (t, 5), (x, 6), (y, 7), (i, 8)} |
| 7 | {(y, 2), (i, 3), (t, 5), (x, 6), (y, 7), (i, 8)} | { (i, 3), (t, 5), (x, 6), (y, 7), (i, 8)} |
| 8 | {(i, 3), (t, 5), (x, 6), (y, 7), (i, 8)} | { (t, 5), (x, 6), (y, 7), (i, 8)} |
| 9 | {(x, 1), (y, 2), (t, ?), (i, 3), (t, 5), (x, 6), (y, 7), (i, 8)} | {(x, 1), (t, ?), (i, 3), (t, 5), (x, 6), (i, 8), (y, 9)} |
:::

## Zadanie 7
:::success
Autor: Piotr Salamon
- `Zadanie 7. Kompilator wygenerował kod pośredni, w którym
występuje następujący fragment. W jaki sposób zoptymalizować
go pod względem wydajności? Wymyśl odpowiednią analizę
przepływu danych: a) zdefiniuj ją słownie, b) zastanów się, w
jaki sposób powinien wyglądać pojedynczy fakt w takiej
analizie, c) napisz zbiory faktów prawdziwych na wejściu–do
oraz wyjściu–z każdej instrukcji tego programu.`

RD1◦ = {{x, ?}, {y, ?}, {z, ?}, ... (w każdym zbiorze mogą istnieć jeszcze inne zmienne, tutaj ich nie uwzględniam bo nie zajdą w nich zmiany) }
1: [𝑥 : = 10]
RD1• = {{x, 10}, {y, ?}, {z, ?}}

RD2◦ = {{x, 10}, {y, ?}, {z, ?}}
2: [𝑦 : = 𝑥 + 10]
RD2• = {{x, 10}, {y, 20}, {z, ?}}

RD3◦ = {{x, 10}, {y, 20}, {z, ?}}
3: [𝑧 : = 𝑦 + 𝑥]
RD3• = {{x, 10}, {y, 20}, {z, 30}}

Optymalizacja

RD1◦ = {{x, ?}, {y, ?}, {z, ?}}
1: [𝑥 : = 10]
RD1• = {{x, 10}, {y, ?}, {z, ?}}

RD2◦ = {{x, 10}, {y, ?}, {z, ?}}
2: [𝑦 : = 20]
RD2• = {{x, 10}, {y, 20}, {z, ?}}

RD3◦ = {{x, 10}, {y, 20}, {z, ?}}
3: [𝑧 : = 30]
RD3• = {{x, 10}, {y, 20}, {z, 30}}

:::