# Lista 3


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


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

### Uzasadnienie, że algorytm działa
:::

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

mój:

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

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

**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:
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)?
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:
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ć**

## Zadanie 6
:::success

**Graf przepływu sterowania**


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


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

:::

Zamienne ilustracje:

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


:::

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