---

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


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ę).
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ć.


**Dlaczego to działa?**

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




#### Poprawność algorytmu

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

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.

* $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`

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

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


**Graf przepływu sterowania**


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


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


## 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, ?).