# Ćwiczenia 2, grupa cz. 16-18, 7 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 | 8 | 9 |
| ----------------------:| -----| --- | --- | --- | --- | --- | --- | --- | --- |
Marcin Banak | X | X | X | | | | | | |
Bartosz Borecki | X | X | ==X== | | X | | X | | X |
Karol Burczyk | X | X | X | X | ==X== | | | | X |
Yelyzaveta Ilman | X | X | X |X | X | | | | ==X==|
Antoni Kamiński | X | X | X | X | | | | | |
Jan Kamyk | X | X | X |==X==| X | | | | X |
Bartosz Kruszewski | X | X | X | X | X | | X | | X |
Hanna Laszkiewicz | X | ==X== | X | X | X| | | | X |
Kaja Matuszewska | | | | | | | | | |
Dominik Muc | | | | | | | | | |
Krzysztof Ostrowski | ==X== | X | X | X | X | | | | X |
Franciszek Przeliorz | X | X | X | | | | | | X |
Yaryna Rachkevych | X | X | | | | | | | |
Piotr Thamm | X | | | | X | | X | | |
Taras Tsehenko | X | X | X | | ==X== | X | X | | X |
:::

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

## Zadanie 1
:::success
Autor: Krzysztof Ostrowski
:::

Sumator liczący wynik liniowo, aby wyliczyć wynik na $_n$-tym bicie, musiał "poczekać" na ewentualne przeniesienie z $_{n-1}$-go bitu.
W tym rozwiązaniu przeniesienia liczone są równolegle i interpretowane w dalszych obliczeniach.


P i G są liczone według następującego wzoru:

ta zależnośc pozwala przyspieszyć znacząco obliczenia.

### Liczba bramek:

dla $n$ bitów:

kwadrat na początku: $2 \space bramki$
kwadrat zamalowany: $3 \space bramki$
kwadrat zaokrąglony: $2 \space bramki$

poziomów: $\log_2n$
bramek na jeden poziom: $\frac n2$

$$\Sigma =2n + 3 \cdot \frac 2n \cdot \log_2n + 2n =$$
$$ =4n + \frac {6 \cdot \log_2n}n$$

### Czas działania:

dla $n$ bitów:

bramki na "jednym poziomie" działają równoleglr

kwadrat na początku: $1$
kwadrat zamalowany: $2$
kwadrat zaokrąglony: $2$

poziomów: $\log_2n$
czas na jeden poziom: $2$ (kwadrat zamalowany)

$$\Sigma =1 + 2 \cdot \log_2n + 2 =$$
$$ = 2 \cdot \log_2n + 3$$

## Zadanie 2
:::success
Autor: Hanna Laszkiewicz

:::

## Zadanie 3
:::success
Autor: Bartosz Borecki
czas: 2nlogn + 2nlogn - 1 + 2{xor} = 4nlogn + 1
:::

## Zadanie 4
:::success
Autor: Jan Kamyk
:::


Niech:
n - liczba bitów
c - liczba bloków C
k - szerokość bloku C

c = n/k

Czas:
log(n/k) + log(n/k) + 3k

Rozmiar:
1. Adder - 5 bramek => 5n
2. Bloki C - 2 bramki na obliczenie małych p i g oraz 3 bramki na policzenie dużych P i G => 5n
3. Bloki B - każdy blok ma 5 bramek a jest ich około c (ponieważ c * (1/2 + 1/4 + 1/8 +...) = c) => 5c

## Zadanie 5
:::success
Autor: Karol Burczyk
:::

## Zadanie 6
:::success
Autor: Taras Tsehenko

Rozszerz układ(algorytm) mnożenia z poprzedniego zadania na liczby w kodzie uzupełnieniowym:
a) Załóż, że argument A jest liczbą bez znaku, a argument B jest liczbą w kodzie uzupełnieniowym. Czy w tym wypadku układ wymaga modyfikacji?
b) Teraz również argument A może być liczbą w kodzie uzupełnieniowym. Jakie modyfikacje w układzie(algorytmie) są konieczne?

6.a) zasady działania układu się nie zmienają, jedyna rzecz, ktorą musimy zrobić, to zmienic przesunięcie
logiczne na przesunięcie arytmetyczne. Czyli przy przysuwaniu w prawo zamiast zer w P, ddodajemy jedynki.

6.b)
A = a_n-1...a_0
1. if a_i = 0 and a_i-1 = 0, then add 0 to P
2. if a_i = 0 and a_i-1 = 1, then add B to P
3. if a_i = 1 and a_i-1 = 0, then substract B from P
4. if a_i = 1 and a_i-1 = 1 then add 0 to P

:::

$$A*B = (-2^{n-1}*a_{n-1} + \Sigma^{n-2}_{i=0} 2^{i}*a_{i}) * B = (-2^{n-1}*a_{n-1}) * B + (\Sigma^{n-2}_{i=0} 2^{i}*a_{i}) * B $$

Niech $A' = \Sigma^{n-2}_{i=0} 2^{i}*a_{i}$. Wtedy
$A*B = ((-2^{n-1}*a_{n-1}) * B) + A'*B$.

Mnożymy $A'*B$ algorytmem z punktu a) --- liczba kroków algorytmu to $n-1$. W n-tym kroku odejmujemy od naszej sumy częśćiowej liczbę $a_{n-1}*B$.

Jak przekształcić sumator w układ odejmujący?

$C-D = C + (-D)$, zapis bitowy liczby $-D = \neg(D) + 1$
Czyli $C-D = C + \neg(D) + 1$.

## Zadanie 7
:::success
Autor: Bartosz Kruszewski
:::


Działa jak układ z poprzedniej listy,\
ale dodatkowo zapamiętuje przeniesienia,\
oraz "zawraca" je do sumatora w kolejnym cyklu.

Jest to poprawne, poniewaz w kazdym cyklu\
robimy przesuniecie bitowe wyniku,\
a zapamietany bit wstawiamy na zwolnione miejsce.

Rozpoczynamy poprzez załadowanie sumy P i przeniesienia zerami.\
Wykonujemy pierwszą operację arytmetyczną.\
Przenosimy najmniej znaczący bit sumy P do A\
oraz przesuwamy rejestr A w celu zwolnienia miejsca na kolejny bit.\
Nie musimy przenosic n-1 pozostałych, ponieważ w kolejnej iteracji\
bity sumy są przeniesione do kolejnego addera.
Dodawanie działa niezależnie od siebie, ponieważ nie przenosimy\
między nimi reszty. Zwiększa to znacznie prędkość procesu.

Po wykonaniu mnożenia, P to suma i przeniesienie.\
W celu otrzymania wyniku, dodajemy je.

Dzięki zastosowaniu tego układu uzyskujemy dodawanie,
na każdym poziomie obliczania wyniku
(poza ostatnim dodawaniem wartości końcowych obu rejestrów) w czasie stałym,
przez co w rezultacie otrzymujemy możliwość mnożenia w czasie liniowym

## Zadanie 8
:::danger
Autor: do zadeklarowania na następnych ćwiczeniach
:::

## Zadanie 9
:::success
Autor: Yelyzaveta Ilman
Najpierw piszemy algorytm:
Teraz mamy układ:
I przykład (11\3 = 3 z resztą 2)
:::

$C/D = ??$

$D*w + r = C$ i $0<= r < C$

Przed rozpoczęciem algorytmu mamy:

$C = M*A + Q$, gdzie $A = 0$, $Q = C$

A' <- 2A
Q' <- 2Q
A' <- 2A - M

Przypadki:

1. A' jest ujemne

A' = A' + M = 2A

Stan zmiennych:

A' = 2A
Q' = 2Q

$M*A' + Q'= M*2A + 2Q = 2C$

$C = M*A + Q$ ?

1. A' jest dodatnie

Stan zmiennych:

A' <- 2A - M
Q' = 2Q + 1

Było $C = M*A + Q$.

$M*A + Q = M*(A' + M)/2 + (Q' - 1)/2$