# Ćwiczenia 2, grupa śr. 14-16, 6 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 |
| ----------------------:| -----| --- | --- | --- | --- | --- | --- | --- | --- |
Krzysztof Chorzempa | | | | | | | | | |
Maciej Ciepiela | X | | X | | X | | X | | X |
Szymon Fica | X | | X | | X | | | | X |
Agnieszka Grala | X | | X | | X | | | | X |
Karolina Jędraszek | X | X | X | | ==X== | | X | | X |
Katarzyna Jodłowska | X | | X | | X | | | | X |
Dominik Kiełbowicz | | | | | | | | | |
Michał Kolasa | | | | | | | | | |
Rafał Krysa | X | X | | | X | | | | |
Miłosz Krzysiek | ==X== | X | X | | X | | X | | X |
Łukasz Kulczycki | | | | | | | | | |
Leon Lepkowski | X | | X | | X | | | | ==X== |
Hanna Makowska | X | | X | | X | | | | X |
Jan Marek | X | | X | | X | X | | X | X |
Cezary Miłek | X | | X | | X | | | | X |
Anna Pierzchała | X | | X | | X | X | X | | X |
Alan Pietrasz | X | X | X | X | X | X | X | X | X |
Kacper Ponikowski | X | | X | | X | | | | X |
Dominik Walecko | X | | X | | X | | X | | X |
Michał Włodarczak | X | X | ==X== | X | X | | | | X |
:::

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

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

Suamtor prefiksowy działa na zasadzie wyliczenia wartości przeniesień w czasie logarytmicznym, a potem wykorzystaniem ich do szybkiego wyliczenia wyniku.

Według definicji z wykładu:
Jesteśmy w stanie wyliczyć bit przeniesienia na podstawie funkcji popagacji i generacji.
te wartości będą nam potrzebne do liczania kolejnych wartości przeniesień.

Naiwne wyliczenie tego nie da nam znaczącej przewagi, ale istnieje własność która umożliwi nam wyliczenie wartości Ci szybciej:
Te wzory pozwalają nam na wyliczenie wszystkich wartości przeniesienia w czasie logarytmicznym (według obrazka):
Po obliczeniu wartości Ci jesteśmy w stanie wyliczyć wartości bitów wyników równolegle, więc wykonujemy dodawanie w czasie logarytmicznym.
**Analiza bramek**
**Analiza czasowa**

## Zadanie 2
:::success
Autor: Rafał Krysa
:::

## Zadanie 3
:::success
Autor: Michał Włodarczak
:::
**1**
**2**
**Połączenie 1 i 2**

Rozmiar:
1. n bloków "A" => n*4 (4 bramki w bloku "A")
2. ilość bloków "B" dąży do n => "B"* n*(1/2 + 1/4 + 1/8 ...) = "B"* n * 1 = n * 5 (5 bramek w bloku "B")
3. Łącznie rozmiar => 4n+5n = 9n

Czas: 2*logn + 1 => O(logn) przejscie 2 razy po drzewie o wysokosci logn oraz wyliczenie sumy na koniec

## Zadanie 4
:::success
Autor: Alan Pietrasz
:::

## Zadanie 5
:::success
Autor: Karolina Jędraszek
:::

*Przedstaw strukturę układu i algorytm działania
układu mnożącego dwie liczby w naturalnym kodzie binarnym (tj.
liczby nieujemne, bez znaku). Zapisz ten algorytm w postaci
pseudokodu (użyj zmiennych reprezentujących rejestry układu,
zmiennych pomocniczych, instrukcji przypisania, dodawania,
przesunięcia bitowego i pętli) Wykonaj mnożenie za pomocą tego
algorytmu liczb 4-bitowych A = 9 i B = 3.*


Mnożymy A = a_(n-1) + ... + a_0
B = b_(n-1) + ... + b_0

Kroki (Appendix):
1) Jeśli najmniej znaczący bit A to jeden, to dodaj do P B w postaci b_(n-1)...b_0, wpp do P dodaj 0...0. Zapisz sumę w P.

2) Rejestry P i A są przesunięte w prawo, przy czym C_out sumy zostaje przeniesione do najbardziej znaczącego bitu w P, najmniej znaczący bit P (przed przesunięciem) do najbardziej znaczącego bitu A (po przesunieciu A).

**Algorytm(A, B):**

wczytaj A, B;
P = 0;
    
Dla i = 0, 1, ... n-1:
    Jeśli najmniej znaczący bit rejestru A (a_(n-1-i)) to 1:
       P = P + B
       C_out = MSB(P) //reszta z dodawania
    Wpp:
        P = P + 0...0
        C_out = 0
    
    LSB_P = LSB(P)
    A = LSB_P,a_(n-1),...,a_1
    P = C_out,p_(n-1),...,p_1

Zwróć A skelone z P

**Dla A = 9 i B = 3:**

> Rejestr A: 1001
> Rejestr B: 0011
> Rejestr P: 0000
> n = 4
>
> Dla i=0:
> LSB(A) = 1
> P = 0011, C_out = 0, LSB( P ) = 1
> P = 0001,
> A = 1100
>
>
> Dla i=1:
> LSB(A) = 0
> P = 0001, C_out = 0, LSB( P ) = 1
> P = 0000
> A = 1110
>
> Dla i=2:
> LSB(A) = 0
> P = 0000, C_out = 0, LSB( P ) = 0
> P = 0000
> A = 0111
>
> Dla i=3:
> LSB(A) = 1
> P = 0000+0011 = 0011, C_out = 0, LSB( P ) = 1
> P = 0001
> A = 1011

wynik: (P sklejone z A) 00011011 = 27

## Zadanie 6
:::success
Autor: Jan Marek
:::


**a)**


Zasada działania taka sama jak przy mnożeniu dwóch liczb w NKB, ale zamiast przesunięcia logicznego o 1 bit rejestrów (Carry-out, P, A) - wykonujemy przesunięcie arytmetyczne tych rejestrów.

- Rejestry A, B (n-bitowe liczby A, B do wymnożenia)
- Rejestr P (również n-bitowy) - wypełniony zerami
- Rejestr Carry-out (1-bitowy)

Rejestry Carry-out, P, A razem tworzą jeden rejestr (2n+1)-bitowy.

- przesuniecie logiczne:

d~2~ d~1~ d~0~ $=>$ 0 d~2~ d~1~

- przesunięcie arytmetyczne:

Rozmazujemy (kopiujemy) bit znaku
d~2~ d~1~ d~0~ $=>$ d~2~ d~2~ d~1~

W danym cyklu działanie jest następując:
- Mnożymy a~i~ = LSB(A) (najmniej znaczący bit liczby A) przez wartość B (czyli liczymy a~i~B).
- Uyskaną wartość sumujemy z aktualną wartością w rejestrze P (czyli teraz w P będzie a~i~B + P).
- W rejestrze Carry-out zapamiętujemy przeniesienie z tego sumowania.
- Na końcu cały rejestr (Carry-out, P, A) przesuwamy o 1 bit w prawo (przesunięcie **arytmetyczne**)

Cykle powtarzamy n razy.

A[0...n-1]
B[0...n-1]
P[0...n-1] = 0
C_out

for (i = n - 1; i >= 0; i--) {

    P' = A[i] * B
    P += P'
    C_out = "przeniesienie z P + P'"
    
    C_out >> 1
    P >> 1
    A >> 1 // oczywiście traktujemy to wszystko jako 1 rejestr
    
}

return P, A // P - starsze n bitów, A - młodsze n bitów

---

A = 9~10~ = 1001~2~
B = -3~10~ = 1101~U2~
P = 0000~2~

0000 1001

I cykl:
1101 1001 +P
1110 1100 >>
II cykl:
1110 1100 +P (+0)
1111 0110 >>
III cykl:
1111 0110 +P (+0)
1111 1011 >>
IV cykl:
1100 1011 +P
1110 0101 >>

Wynik -> 1110 0101~U2~ = $(-2)^7 + 2^6 + 2^5 + 2^2 + 2^0$ = $-128 + 64 + 32 + 4 + 1$ = $-27$

**b)**

$$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: Anna Pierzchała
:::

## Zadanie 8
:::success
Autor: Alan Pietrasz
:::

## Zadanie 9
:::success
Autor: Leon Lepkowski
:::



### Jak działa algorytm dzielenia
Mamy rejestrny A, B i P. W A trzymamy liczbę dzieloną, w B liczbę przez którą dzielimy, a w P dajemy 0.
W każdym kroku (jest ich n dla n bitowych liczba):
1. Robimy shift (P, A) w lewo
2. P = P - B
3. Jeżeli P jest ujemne to najmniejszy bit A ustawiamy na 0, a w przeciwnym wypadku na 1
4. Jeżeli P jest ujemne to zapisujemy tam P + B

Po wykonaniu wszystkich (n) cykli nasz wynik będzie w A, a P będzie miało resztę z dzielenia.