# Lista 3 (18 marca 2021), grupa KBa
###### tags: `ask21` `ćwiczenia` `kba`
## 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 |
| --------------------:| ----- | --- | ----- | --- | ----- | --- | --- | ----- |
| Andriy Bernad | X | X | X | X | | | X | | 5
| Wojciech Bogucki| | X | | | | | X | X | 3
| Michał Doros | X | X | X | X | X | X | | ==X== | 7
| Marko Golovko | | X | | | | | | | 1
| Magdalena Jarecka | X | X | X | X | | X | | | 5
| Szymon Jędras | | X | X | | X | X | X | X | 6
| Heorhii Karpenko | ==X== | X | X | X | | | | | 4
| Szymon Kosakowski | X | X | X | | X | | | | 4
| Izabella Kozioł | | | | | | | | | 0
| Franciszek Malinka | X | X | ==X== | X | X | X | X | X | 8
| Filip Pazera | | X | X | | | | X | X | 4
| Franciszek Pindel | | X | ==X== | X | X | X | X | | 6
| Kacper Puchalski | X | X | X | | X | | | | 4
| Kacper Solecki | X | X | X | X | X |==X==| | X | 7
| Andrzej Tkaczyk | | X | | | | | | | 1
| Łukasz Wasilewski | x | x | ~~x~~ | | | | | | 2 !!
| Vladyslav Yablonskyi | X | X | X | X | | | | | 4
| Adam Zyzik | | | | | | | | | 0
:::
## Zadanie 1
:::danger
Autor: Grzegorz Karpenko
:::
### Twierdzenie 1,2:
### Twierdzenie 3:
**Dla dodatnich**:
$\lfloor \frac{2^{32}+2}{3}\cdot\frac{n}{2^{32}} \rfloor = \lfloor \frac{n}{3} + \frac{2n}{3\cdot2^{32}} \rfloor = \lfloor \frac{n}{3} \rfloor$
Z Twierdzenia 3:
Dla $0 \leq n < 2^{31}$ zachodzi:
$0 < 2n < 2^{32}$
$0 < \frac{2n}{3\cdot2^{32}} < \frac{1}{3}$.
**Dla ujemnych**:
$\lfloor \frac{2^{32}+2}{3}\cdot\frac{n}{2^{32}} \rfloor + 1 = \lfloor \frac{2^{32}+2}{3} \cdot \frac{n}{2^{32}} + 1 \rfloor = \lfloor \frac{2^{32}n+2n+3\cdot2^{32}}{3\cdot2^{32}}\rfloor = (Twierdzenie 1) = \lceil \frac{2^{32}n+2n+1}{3\cdot2^{32}} \rceil = \lceil \frac{n}{3} + \frac{2n+1}{3\cdot2^{32}} \rceil = \lceil \frac{n}{3} \rceil$
Z Twierdzenia 3:
Dla $-2^{31} \leq n \leq -1$ zachodzi:
$-\frac{1}{3} < \frac{2n+1}{3\cdot2^{32}} < 0$.
```c=
int32_t przez3(int32_t n){
const int64_t M = ((1ll << 32) + 2) / 3;
return (n * M >> 32) + (n < 0);
}
// Zamiast operatora porówniania możemy wykorzystać zgodnie z zadaniem 6 z listy 2 taki oto wzór dla prównania x<y:
bool lessThanWithSign(int32_t x, int32 y)
{
return (x >> 1) - (y >> 1) >> 31 & 1 | (~x & y & 1) & (x >> 1) - ((y >> 1)+1) >> 31 & 1;
}
```
> [name=Franciszek Malinka] mam bez tego porównania
> :::spoiler
> ```c
> int32_t div3(int32_t x) {
> const int64_t M = 0X55555556; // (2**32 + 2) / 3
> int32_t q = (M * (int64_t)x) >> 32;
> return q + ((q >> 31) & 1);
> }
> ```
> :::
## Zadanie 2
:::info
Autor: Marko Golovko
:::
Standard IEEE 754 określa, że binary16 ma następujący format:
* Bit znaku: 1 bit
* Szerokość wykładnika: 5 bitów
* Mantysa: 11 bitów (10 jawnie zapisanych)
* Bias: 15
1.5625*10^(−1) = 1.25 * 2^(-3)
(-1)^s * 2^(eeeee-15) * 1.mmmmmmmmmm
s = 0
e = 01100
m = 0100000000
16 . Minimalna dodatnia (subnormalna) wartość wynosi 2 ^ −24 ≈ 5,96 × 10 ^ −8. Minimalna dodatnia wartość normalna to 2 ^ −14 ≈ 6,10 × 10 ^ −5. Maksymalna reprezentowalna wartość to (2−2 ^ −10) × 215 = 65504.
32 . Minimalna dodatnia wartość normalna wynosi 2^(-126) ≈ 1.18 * 10^(-38) a minimalna dodatnia (subnormalna) wartość to 2^(-149) ≈ 1.4*10^(-45)
## Zadanie 3
:::info
~~Autor: Łukasz Wasilewski~~
:::
$
3.984375 * 10^(-1) +3.4375 * 10^(-1)+ 1.771 * 10^3
3.984375 * 10^(-1) = 0.3984375 = 51/128 = 2^(-2) * 1.10011
3.4375*10^(-1) = 0.34375 = 11/32 = 2^ (-2) *44/32=2^(-2) *(1+11/32)=2^(-2)*(1.01011)
1.771 * 10^3 = 1771 = 1024+747=2^10*(1.1011101011)
16- bitowy
2^(-2) *1.10011+2^(-2) *(1.01011)+2^10*(1.1011101011) = 2^(-2) * (1.10011+1.01011)+2^10 * (1.1011101011) =
= 2^(-2) * 10.1111000000 + 2^ 10 * 1.1011101011 = 2^(-1) * 1.01111 + 2^10 * 1.1011101011 = 2^10 *(1.0111100000 * 2^(-11)+1.1011101011)=
=2^10*(round(0.0000000000101111) + 1.1011101011) = (0.0000000001+1.1011101011)*2^10 = 1.1011101011 * 2^10 = 11011101011(binarnie, czyli dziesiętnie 1771)
po zmianie kolejności dodawań wynik się nie zmieni ponieważ jeżeli 1.771*10^3 zdominował sumę pozostałych składników to tym bardziej zdominuje
je dodawane osobno
32- bitowy
2^(-2) * 1.10011+2 ^ (-2) * (1.01011)+2^10*(1.1011101011) = 2^(-2) * (1.10011+1.01011)+2^10 * (1.1011101011) =
= 2^(-2) * 10.1111 + 2^10 * 1.1011101011 = 2^(-3)*1.01111 + 2^10 * 1.1011101011 = 2^10* (1.01111*2^(-13)+1.1011101011)=
=2^10 * (0.000000000000101111 + 1.1011101011) = 1.101110101100101111 * 2^10 =11011101011.00101111 (binarnie, czyli dziesiętnie 1771.18359375)
2^10 * (1.1011101011)+2 ^ (-2) * 1.10011+2^(-2)*(1.01011) = 2^10 * (1.1011101011 + 0.00000000000110011) + 2^(-2)*(1.01011) =
=2^10 * (1.10111010110110011 + 0.00000000000101011) = 1.10111010111011110*2^10=11011101011.00101111 (binarnie, czyli dziesiętnie 1771.18359375)
$
Jeżeli zaokrąglamy x do n bitów po przecinku to Guard Bit jest n-tym bitem po przecinku w x, Round Bit jest n+1 bitem po przecinku w x,
zaś sticky bit to wartość logiczna zdania "w x istnieją zapalone bity na pozycjach dalszych niż n+1 po przecinku".
> [name=Franciszek Malinka] mój rozw
:::spoiler
```
f1 = 0.3984375; // 0 01101 1001100000
f2 = 0.34375; // 0 01101 0110000000
f3 = 1771; // 0 11001 1011101011
```
$f_1 = 2^{-2}\cdot 1.10011_{(2)}$
$f_2 = 2^{-2}\cdot 1.011_{(2)}$
$f_3 = 2^{10}\cdot 1.1011101011_{(2)}$
\begin{align}
f_1 + f_2 = 2^{-2}\cdot 1.10011_{(2)}+2^{-2}\cdot 1.011_{(2)} = 2^{-2}(1.10011_{(2)} + 1.011_{(2)}) \\= 2^{-2}\cdot 10.11111_{(2)}=2^{-1}\cdot 1.011111_{(2)}
\end{align}
Nic sie nie psuje, to się mieści w połowie precyzji.
Kolorem $\color{blue}{niebieskim}$ oznaczamy **guard**, kolorem $\color{red}{czerwonym}$ oznaczamy **round**, kolorem $\color{green}{zielonym}$ oznaczamy **sticky**.
\begin{align}
(f_1+f_2)+f_3 &= 2^{-1}\cdot 1.011111_{(2)} + 2^{10}\cdot 1.1011101011_{(2)} \\&= 2^{10}(0.\underbrace{0000000000}_{\text{10 zer}}1011111_{(2)} + 1.1011101011_{(2)})\\&=2^{10}\cdot 1.101110101\color{blue}{1}\color{red}{1}\color{green}{011111}_{(2)}
\end{align}
Wg zasady zaokrąglania do parzystych, dostajemy ostateczny wynik
\begin{align}(f_1 + f_2) + f_3 = 2^{10}\cdot 1.10111011_{(2)} = 1772
\end{align}
Teraz zmieniając kolejność dodawania:
\begin{align}
f_2 + f_3 &= 2^{-2}\cdot 1.011_{(2)} + 2^{10}\cdot 1.1011101011_{(2)}\\&=2^{10}(0.\underbrace{0000000000}_{\text{10 zer}}01011_{(2)} + 1.1011101011_{(2)}) \\&= 2^{10}\cdot 1.101110101\color{blue}1\color{red}0\color{green}{1011}_{(2)}
\end{align}
Guard i sticky są równe 1, ale round jest równy 0, więc zaokrąglamy w dół, zatem
\begin{align}
f_2 + f_3 = 2^{10}\cdot 1.1011101011_{(2)} = f_3
\end{align}
Teraz analogicznie dojdziemy do wniosku, że
\begin{align}
f_1 + (f_2 + f_3) = f_1 + f_3 = f_3 = 1771.
\end{align}
**Definicja:**
- Bit nazywamy **round** jeśli jest pierszym bitem wychodzącym poza precyzję liczby (czyli, który na rozwinięciu dwójkowym liczby jest (dł. mantysy + 1)-wszy).
- Bit **guard** to pierszy bit na lewo od **round**,
- **sticky** to bitowy $\texttt{OR}$ pozostałych, mniej znaczących bitów od **rounda**.
:::
## Zadanie 4
:::danger
Autor: Magdalena Jarecka
:::
>Mamy zmienne «x», «y» i «z» typu «int32_t» ustawione na wybrane przez nas wartości.
>Konwertujemy je do liczb typu «double» zapisanych w zmiennych «dx», «dy» i «dz». Rozważmy poniższe wyrażenia z języka C. Wskaż, które z nich mogą obliczyć się do fałszu. Podaj kontrprzykład – konkretne wartości naszych zmiennych całkowitoliczbowych.
>
>1. (float)x == (float)dx
>2. dx - dy == (double)(x - y)
>3. (dx + dy) + dz == dx + (dy + dz)
>4. (dx * dy) * dz == dx * (dy * dz)
>5. dx / dx == dz / dz
1. int float jest praktycznie tym samym co int na double na float
2. x = -2
y = INT32_MAX = 2147483647
dla x - y występuje negatywny nadmiar co w wynniku daje liczbę dodatnią, a (double)INT32_MAX dają poprawną liczbę (bez nadmiaru, dx - dy = -2147483649)
3. Skoro dx, dy i dz konwertowane wartości z int32_t to wyrażenie zawsze oblicza się do $true$.
:::spoiler Jeśli dx, dy i dz dowolne liczby z zakresu double to dla
dx = 2.501
dy = INT32_MAX
dz = INT32_MAX
(dx + dy) + dz = 4294967296.500999
dx + (dy + dz) = 4294967296.501000
> [name=Franciszek Malinka] no ale przecież te `dx, dy, dz` są konwertowane z intów, nie może być `dx = 2.501`
> > [name=Magdalena Jarecka] dopis poglądowy nie mający wpływu na zadanie
:::
Bo konwersja int -> double jest bezstratna
4. analogicznie do powyżej
6. ok, jeśli wartości są różne od 0, bo będzie jakaś liczba specjalna
> [name=Franciszek Malinka] w 4 nie zawsze jest prawda. Iloczyn intów nie musi sie już mieścić w zakresie `double`, co może generować kłopoty. Kontrprzykład:
> :::spoiler
> `x = MAX_INT, y = 0x40000006, z = MIN_INT + 110`
> -4951759928863062087929167872.000000
> -4951759928863061538173353984.000000
> :::
## Zadanie 5
:::success
Autor: Kacper Puchalski
:::
1. x ^ 0x80000000 XORujemy pierwszy bit znaku
2. ((x & 0x7f800000) >> 23) - 127 obliczamy wartość $exp-bias$
3. (x == y) | ((x | y) == 0x80000000) x==y lub -0=+0
4. ((x >> 1) - (y >> 1) - (~x & y & 1)) >> 31 sprawdzamy znak $x/2 - y/2$ pomniejszone o 1 kiedy x jest parzyste i $y=x+1$
> [name=Franciszek Malinka] w 4. nie wystarczy sprawdzić czy `x < y`. Jeśli `f < 0` oraz `g > 0`, to nie zachodzi `x < y`.
> 4. Porównać $f$ oraz $g$: przypadki:
> - f nieujemne, wtedy wystarczy porównać (ale na intach) czy `x < y` LUB f ujemne, wtedy wystarczy porównać (ale na uintach) czy `x > y` (jeśli `y >= 0`, to faktycznie `f < g`, bo `g > 0` oraz mamy `x > y`; jeśli `y < 0`, to `x > y` "nie patrzy" w zasadzie na bit znaków, a reszta działa tak jak normalnie).
> - obie są zerami, ale z przeciwnymi znakami. Wtedy to samo co w przykładzie 3.
> ```c
> int32_t a = x, b = y;
> f < g <=> ((a >= 0 & a < b) | (a < 0 & x > y)) & ((x|y) != 1<<31)
> ```
> [name=Kacper Solecki]
>```c=
> uint32_t less(uint32_t x, uint32_t y){
> reuturn ((x >> 1) - (y >> 1) - (~x & y & 1)) >> >31;
>}
>
>
>uint32_t zeros = (x & 0x7FFFFFFF) == 0 & (y & >0x7FFFFFFF) == 0 ^ 1; \\ przynajmniej jedno nie jest >zerem \\ x = y = 0
>x ^= 1 << 31;
>y ^= 1 << 31;
>uint32_t esx = x & 0xFF800000; // cecha i znak x>
>uint32_t esy = y & 0xFF800000; // cecha i znak y>
>uint32_t mx = x & 0x007FFFFF; // mantysa x>
>uint32_t my = y & 0x007FFFFF; // mantysa y
>
>uint32_t result = zeros & (less(esx, esy) | (less(esx, esy) ^ 1) & less(mx, my); \\ x < y)
>```
> [name=Krystian Bacławski]
> Idea jak porównać liczby o takich samych znakach?
> ```c
> ( x & y & (y - x)) | (~x & ~y & (x - y))
> (x < 0 & y < 0 & x > y) | (x >= 0 & y >= 0 & x < y)
> ```
## Zadanie 6
:::success
Autor: Kacper Solecki
:::
```c=
int32_t ex(uint32_t x){ //cecha
return ((x & 0x7F800000) >> 23) - 127;
}
uint32_t mant(uint32_t x){ // mantysa
return x & 0x007FFFFF;
}
uint32_t setEx(uint32_t x, int32_t e){ //ustaw cechę
e += 127;
return x & 0x807FFFFF | e << 23;
}
uint32_t setMant(uint32_t x, uint32_t m){ //ustaw mantysę
return x & 0xFF800000 | m;
}
uint32_t fshift(uint32_t x, int32_t i){
int32_t e = ex(x); // cecha x
e += i;
if(i>=0){
if(e > 127) // cecha jest większa niz maksymalna
return setEx(setMant(x, 0), 128); // inf (znaku x)
return setEx(x, e); // znormalizowana
}
// i < 0:
if(e < -126){
uint32_t subnormShift = -e - 126;
if(subnormShift > 23)
return setEx(setMant(x, 0), -127);
// 0 (znaku x), gdy przesuwamy o długość mantysy
// 1 << 23 to jedynka, która jest "przed kropką"
uint32_t subnormMant = (mant(x) | 1 << 23) >> subnormShift;
return setEx(setMant(x, subnormMant), -127); // subnormalna
}
return setEx(x, e); // znormalizowana
}
```
## Zadanie 7
:::info
Autor: Wojciech Bogucki
:::
Najpierw ustalamy znak(jeśli wyjdzie -1, to ustawiamy na 1 i bierzemy liczbę przeciwną, bo szukamy najbardziej wiodącą jedynkę).
Funckja \_\_builtin_clz($i$) zwraca liczbę zer wiodących $i$, więc odejmujemy ją, a potem dodajemy bias.
Potem usuwamy wiodącą jedynkę odpowiednią maską.
Potem wyznaczamy wartości bitów guard, round, sticky(sticky to **OR** bitów, więc wystarczy sprawdzić czy jest większa od zera).
Na końcu obliczamy mantysę, odpowiednio przesuwając liczbę i dodająć zaokrąglenie.
Potem składamy liczbę.
```c=
int32_t int2float(int32_t i) {
// obliczanie znaku
int32_t s = i >> 31;
//ustawienie znaku i poprawienie liczby
if (s == -1) {
i = -i;
s = 1;
}
//znajdowanie jedynki wiodącej
int32_t p = 32 - __builtin_clz(i);
int32_t e = p - 1 + 127;
//usuwanie jedynki wiodącej
i &= (1<<(p-1))-1;
int32_t
guard = 0,
round = 0,
sticky = 0;
//obliczanie bitów guard,round,sticky
if (p > 24) {
guard = ( i >> (p - 23 - 1) ) & 1;
round = ( i >> (p - 23 - 2) ) & 1;
sticky = ( i & ( ( 1 << (p - 23 - 2) ) - 1 ) ) > 0;
}
//obliczanie mantysy
int32_t mantysa =
( p < 24 ? (i << (24 - p)) : (i >> (p - 24)) ) +
((guard & round) | (round & sticky)) ;
return (s << 31) + (e << 23) + mantysa ;
}
```
## Zadanie 8
:::success
Autor: Michał Doros
:::
```c=
int32_t float2int(int32_t f)
{
int32_t s = f >> 31; /* -1 jeśli znak był ujemny */
int32_t e = (f >> 23 & 255) - 127; /* wykładnik po odjęciu bias */
uint32_t m = f << 8 | INT_MIN; /* mantysa 1.xxx... dosunięta do lewej */
if (e <= 30 && e >= 0) //jeśli w tym zakresie to liczba mieści się w incie
{
m >>= (31 - e); //przesunięcie mantysy na odpowiednie miejsce
return (int32_t)m * (1 | s); //ustawienie znaku
}
return INT_MIN ^ ((1u << 31) & e); //MININT jeśli e >= 30, 0 jeśli e ujemne
}
```
jeśli e ujemne to ((1u << 31) & e) = 1 << 31 więc xor z INT_MIN (1<<31) daje 0
jeśli e >= 30 to ((1u << 31) & e) = 0 więc xor z INT_MIN daje INT_MIN
Sign in with Wallet
Connect another wallet