---
# System prepended metadata

title: Lista 3

---

# Lista 3

![0004A3LYUECLY3H9-C122-F4](https://hackmd.io/_uploads/HJH7NBCap.jpg)


## Zadanie 1
Będziemy teraz rozważać mnożenie dwóch liczb ze znakiem (zapisanych w U2) $a \cdot b$. 
Przypomnijmy sobie z poprzedniej listy algorytm mnożenia dwóch liczb bez znaku, bo do tego będziemy się odwoływać.
```
// oznaczenia
A[n], B[n]     // liczby n-bitowe indeksowane [n-1, ..., 1, 0]
P[n] = [0..0]  // dodatkowy rejestr
PA[2n]         // para rejestrów P i A, tak mi będzie łatwiej pisać

// krok mnożenia (wykonujemy n razy)
if A[0] == 1:        // jeżeli ostatni bit A == 1
    P, c_out = P+B   // dodajemy B do P zapisując też carry out 
PA.shift_right()     // przesuwamy parę w prawo
PA[n-1] = c_out      // za najbardziej znaczący bit P ustawiamy c_out z dodawania

// wynik: PA
```
Schody zaczynają się dla liczb, które mogą być ujemne. 
Jeżeli tylko $b$ może być ujemne, wystarczy zmienić przesunięcie PA na arytmetyczne, cokolwiek to znaczyło, bo w sumie nie czaję.
Jeżeli zarówno $a$ i $b$ mogą być ujemne, sposobem na załatwienie tego jest właśnie **kodowanie Bootha**.

**Tu kończy się idea Julki i wkracza maciek największy szef wszechświata (to nie moje rozwiązanie)**
*Poszłam spać chuju*
<3
:::success
**Kodowanie Bootha** polega na usuwaniu bloków jedynek w celu zamiany wielu dodawań na jedno dodawanie i jedno odejmowanie.
np. dla liczby 15 = 1111, poznany wcześniej algorytm mnożenia wykonałby 4 dodawania. Natomiast jeśli skorzystamy z zależności, że $15 = 16 - 1$ będziemy mogli wykonać 1 dodawanie i jedno odejmowanie; w kodzie Bootha zapiszemy takie obliczenia jako $10000 - 00001 = 1000\bar{1}$ (podkreślenie oznacza odejmowanie).

### Mnożenie liczb bez znaków
"Zamieniamy" bloki w oparciu o o dane zasady:
![image](https://hackmd.io/_uploads/r1Oo-N06p.png)
* jeżeli najmniej znaczący bit A to 0 to nic nie robimy tylko przesuwamy.
* jeżeli zaczynamy blok 1, to odejmujemy B
* jeżeli kończymy blok 1, to dodajemy B

**Zapis $a_i$ oznacza najmniej znaczący bit rejestru A w i-tej iteracji.**

Potrzebujemy tylko dodatkowego bitu L pamiętającego ostatnią wartość najmniej znaczącego bitu:

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

W takim razie będziemy wykonywać tylko operacje II i III, a przy operacjach I oraz IV jedyne co robimy to wykonujemy przesunięcie.

### Liczby ze znakiem
Trzymamy liczby w U2.
Musimy zwrócić uwagę na znak P podczas przesunięcia w prawo.
Zamiast przesunięcia logicznego wykonujemy przesunięcie arytmetyczne.
W przypadku gdy A < 0 i B < 0 musimy dodatkowo umieć odejmować.
**Przykład: $(-6) \cdot (-5)$**
![image](https://hackmd.io/_uploads/SJVTdER6p.png)


### Uzasadnienie, że algorytm działa
![image](https://hackmd.io/_uploads/r1Bqm40TT.png)
:::


## Zadanie 2
:::success
Na poprzedniej liście omawialiśmy algorytm *restoring division* (zadanie 9), w którym, jeżeli wartość rejestru P wychodziła ujemna, to przywracaliśmy poprzednią wartość. Tutaj krok będzie wyglądać trochę inaczej (stąd nazwa *non-restoring*), ale ogólnie działanie jest podobne - po prostu w zależności od wartości P będziemy dodawać lub odejmować B.

**Algorytm**
```
// Dzielenie A/B

// oznaczenia:
A[n], B[n]       // liczby n-bitowe indeksowane [n-1, ..., 1, 0]
P[n+1] = [0..0]  // dodatkowy rejestr
PA[2n+1]         // para rejestrów P i A, tak mi będzie łatwiej pisać

// krok dzielenia (wykonujemy n razy):
if P < 0:
    PA.shift_left()     // 1a. przesuwamy PA o 1 bit w lewo
    P = P + B           // 2a. dodajemy B do P
else:
    PA.shift_left()     // 1b. przesuwamy PA o 1 bit w lewo
    P = P - B           // 2b. odejmujemy B od P
if P < 0:               // 3. ustawiamy ostatni bit A
    A[0] = 0            // ...na 0 jeśli P ujemne
else:
    A[0] = 1            // ...na 1 jeśli P nieujemne
    
// wynik:
wynik = A
reszta = {
    if P >= 0:  P    // jak P wyszło nieujemne, to to jest reszta
    else:       P+B  // jak ujemne, to musimy jeszcze dodać B
}

```
**Przykłady**
z podręcznika:
![image](https://hackmd.io/_uploads/BkVraaa6T.png)

mój:
![image](https://hackmd.io/_uploads/rymNxCTT6.png)

**Uzasadnienie poprawności**
Poprawność uzasadnimy odwołując się do algorytmu *restoring  division* z poprzedniej listy - pokażemy, że dają takie same wyniki; tamten działa jak działania pisemne i ostatnio to było wystarczające uzasadnienie.

*restoring division:*
![image](https://hackmd.io/_uploads/rJK4NAaap.png)

Niech $r_k$ będzie wartością pary rejestrów $PA$ po $k$-tym kroku (początkowa wartość ma indeks 0). W dowodzie pominiemy ustawianie ostatnich bitów $A$, bo ten krok jest identyczny dla obydwu algorytmów. 

Rozważmy sens poszczególnych kroków w obydwu algorytmach:
* Mamy na początku kroku $r_k$
* Przesuwając w lewo, obliczamy wartość $2r_k$
* Jeżeli $2r_k - 2^nb \ge 0$
    * $r_{k+1}=2r_k - 2^nb$ dla algorytmu *restoring* (nie przywracamy starej wartości, bo wynik odejmowania jest nieujemny)
    * Oznacza to też, że początkowa wartość $P$ była nieujemna, czyli w algorytmie *non-restoring* wykonaliśmy to samo działanie.
* W przeciwnym wypadku
    * *restoring* przywraca starą wartość $P$, czyli $r_{k+1}=2r_k$
        * w kolejnym kroku będziemy wyliczać $r_{res}=2r_{k+1} - 2^nb = 4r_k - 2^nb$
    * *non-restoring* skończył z $r_{k+1}=2r_k - 2^nb$
        * w kolejnym kroku będziemy wyliczać $r_{non-res}=2r_{k+1} + 2^nb = 2(2r_k - 2^nb) + 2^nb = 4r_k - 2^nb$
    * WNIOSEK: $r_{res}=r_{non-res}$, więc w tym wypadku też wynik wyjdzie taki sam.
* koniec dowodu; obydwa algorytmy zwracają ten sam, poprawny (na mocy uzasadnienia algorytmu *restoring* z zeszłego tygodnia) wynik :)
:::


## Zadanie 3 
### SRT division
**Motywacja** (coś, czego nie mam do robienia tej listy):
* algorytm z zadania 2 na każdym kroku wykonuje dodawanie lub odejmowanie; nie mamy szans pominąć kroku nawet przy serii 0
* spójrzmy inaczej: aby obliczyć $a/b$ odejmujmy wielokrotności $b$ od $a$ zapamietując, ile razy możemy to zrobić.
* na każdym kroku reszta musi się mieścić w rejestrze $P$
* wcześniej w każdym kroku od aktualnej reszty odejmowaliśmy $b$; zmieńmy taktykę - jeżeli reszta jest "mała" (ma przynajmniej jedno 0 z przodu), przesuńmy ją o w lewo, żeby pominąć wszystkie 0 wiodące i dopiero wtedy odejmijmy (wielokrotność) $b$.
*Potencjalny problem*: jak zapamiętywać całości, przy tych nieregularnych przesunięciach?

**Algorytm**
```
// 0. Załadujmy dane a i b do rejestrów
A[n] <- a, B[n] <- b
P[n+1] = [0..0]

// 1. Jeżeli B ma z przodu k zer, przesuwamy parę rejestry o k bitów w lewo
B.shift_left(k)
PA.shift_left(k)

// 2. Pętla główna (kroki dzielenia)
for i in 0,...,n-1:
    // jeżeli 3 najwyższe bity P są równe
    if P[n-1] == P[n-2] == P[n-3]:
        A[0] <- 0        // ustawiamy ostatni bit na 0
        PA.shift_left(1) // przesuwamy w lewo o 1 bit
    
    // jeżeli nie są równe i P<0
    else if P<0:
        A[0] <- -1        // ustawiamy ostatni bit na -1
        PA.shift_left(1)  // przesuwamy w lewo o 1 bit
        P = P+B           // dodajemy B
        
    // jeżeli nie są równe i P>=0
    else:
        A[0] <- 1        // ustawiamy ostatni bit na -1
        PA.shift_left(1)  // przesuwamy w lewo o 1 bit
        P = P-B           // dodajemy B 
        
// 3. Interpetacja wyniku
// jeśli reszta wyszła ujemna, robimy korektę
if P < 0:
    P = P+B        // dodajemy B do reszty
    A = A-1        // odejmujemy 1 od całości
// na końcu przesuwamy jeszcze PA "z powrotem" o k bitów
PA.shift_right(k)  
```
**Przykład z podręcznika**
![image](https://hackmd.io/_uploads/H1s5rBCaa.png)

**Uzasadnienie poprawności** (na podstawie przykładu z podręcznika)
Pomyślmy o A i B jak o ułamkach dziesiętnych.
Wiemy, że $\frac{8}{3} = \frac{0.8}{0.3}$, co w zapisie binarnym będzie mieć postać $\frac{1000}{0011} = \frac{0.1000}{0.0011}$.
PA jest liczbą w U2, więc tak też ją interpretujemy, czyli np. jeżeli $P=11110$ i $A=0$, to $r = 1.1110 = -\frac{1}{8}$. W tych terminach reszta w każdym kroku spełnia nierówność $-1 \le r \lt 1$.
Przeanalizujmy w końcu algorytm:
* po pierwszym kroku $b \ge \frac{1}{2}$
* jeżeli $-\frac{1}{4} \le r \lt \frac{1}{4}$ (a to zachodzi, kiedy 3 początkowe bity P są równe)
    * wyliczamy $2r$
* jeżeli $r < -\frac{1}{4}$ (czyli $<0$ i początkowe bity nie są równe, bo wpadłoby w pierwszy warunek):
    * wyliczamy $2r + b$
* jeżeli $r \ge \frac{1}{4}$ (trzeci przypadek):
    * wyliczamy $2r - b$

**Chuj z tym nie da się tego zrobić**


## Zadanie 4 (Maciek) ?
Układ z treści:
![image](https://hackmd.io/_uploads/BJ7iPxAa6.png)
Działa o podobnie do dodawania pisemnego - mnożymy liczbę A przez kolejne bity liczby B i sumujemy wynik.
### 1. Układ wykorzystujący tylko jeden sumator CSA i jeden RCA
Wymienimy 3 bramki CSA na jedną i wykorzystamy rejestr oraz przesunięcie 

## Zadanie 5 (Maciek)?
![image](https://hackmd.io/_uploads/ByfBkZAp6.png)
Algorytm mnożenia z wykorzystaniem kodowania Bootha opiera się na wybieraniu następnego działania w oparciu o dwa najmniej znaczące bity liczby A, oraz o ostatnio "wysunięty" bit z liczby A. na ich podstawie określone są kolejne działania:
![image](https://hackmd.io/_uploads/rJJbf-0Tp.png)
Odpowiadają one wykorzystaniu kodowania bootha w systemie 4-kowym, gdzie wykorzystywane są wartości -2,-1,0,1,2.

**Dowód pewnie podobny do zadania 2 ale nie wiem jak go przeprowadzić**
![430870169_7209595879077318_3638182255456564676_n](https://hackmd.io/_uploads/H1S5Sk10a.jpg)



## Zadanie 6
:::success
![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)
:::

 Zamienne ilustracje:
![image](https://hackmd.io/_uploads/BJkU_yJ0p.png)
![431326232_1150614162774759_3840826429822507393_n](https://hackmd.io/_uploads/Hk8ehJJRp.jpg)
![430915722_1050561412686688_126025596205749927_n](https://hackmd.io/_uploads/Bki6gey0T.jpg)







## Zadanie 7
:::success
**Słowne zdefiniowanie analizy przepływu danych**

Analiza przepływu danych to proces analizy programu komputerowego, w którym badamy, jak dane przepływają przez różne części programu. Celem jest zrozumienie, jak wartości danych mogą się zmieniać w różnych punktach programu oraz jak te zmiany mogą wpływać na działanie programu jak całości. Umożliwia nam to idetyfikację potencjalnych optymalizacji kodu.

W przypadku naszego przykładu, można zauważyć, że wartości zmiennej "x" nie zmienia się w trakcie wykonywania programu. Dlatego można zoptymalizować kod poprzez wyeliminowanie niepotrzebnych operacji przypisania. Na przykład, można zmienić instrukcję 2 na [y := 20] i instrukcję 3 na [z :- 30], co pozwoli na uniknięcie dodatkowych operacji arytmetycznych i przyspieszy wykonywanie programu.

**Wygląd pojedynczego faktu w analizie przepływu danych**

W analizie przepływu danych, pojedynczy fakt reprezentuje stan zmiennych w określonym punkcie programu. Składa się on z pary <instrukcja, wartosci zmiennych>, gdzie "instrukcja" oznacza konkretną instrukcję w programie, a "zbiór wartości zmiennych" zawiera informacje o wartościach zmiennych w momencie wykonania tej instrukcji.

**Zbiory faktów prawdziwych na wejściu-do oraz wyjściu-z każdej instrukcji tego programu:**

![157e0f95-0be5-4514-ad17-91188e3affe9 (1)](https://hackmd.io/_uploads/HJlOsSC66.jpg)


:::

### Zadanie 7 przepisane innymi słowami
**a) słowna 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). Poprawna analiza może nam pozwolić **zoptymalizować** kod tak, jak w tym przykładzie.

**b) struktura faktu**
Fakt ma reprezentować stan zmiennych "na wysokości" określonej instrukcji w programie, więc sensowną reprezentacją jest zapamiętywanie pary 
*<instrukcja, wartości zmiennych>*; *wartości zmiennych* to z kolei pary *<zmienna, miejsce przypisania*>

**c) 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 + x] 3
wejście: {(x, 1), (y: 2), (z: ?)}
wyjście: {(x, 1), (y: 2), (z: 3)}
```

**Optymalizacja kodu**
Dzięki analizie mogliśmy zauważyć, że wartość $x$ jest przypisywana tylko w 1. 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
```

