# Ćwiczenia 4, grupa śr. 17-19, 15 marca 2023
###### tags: `ASK23` `ć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 | 10 |
| ----------------------:| --- | --- | --- | --- | --- | --- | --- | --- | --- | --- |
| Mikołaj Balwicki | | | | | | | | | | |
| Kamila Goszcz | | | X |==X==| X | X | | | | |
| Mateusz Materek | | |==X==| X | X | X | | | | |
| Mikołaj Łabędzki | | | | | | | | | | |
:::
:::info
**Uwaga:** Po rozwiązaniu zadania należy zmienić kolor nagłówka na zielony.
:::
## Zadanie 1
:::danger
Autor:
:::
$$\lfloor \frac{2^{32} + 2}{3} * \frac{n}{2^{32}}\rfloor = \lfloor\frac{n}{3} + \frac{2n}{3*2^{32}} \rfloor$$
Obserwacja:
$$0 \leq \frac{2n}{3*2^{32}} < \frac{1}{3} $$ bo $n < 2^{31}$
Zatem:
$$ \lfloor\frac{n}{3} + \frac{2n}{3*2^{32}} \rfloor < \lfloor\frac{n}{3} + \frac{1}{3} \rfloor$$
Niech $n = 3k +r$, gdzie $r \in \{0,1,2\}$. Wtedy
$\lfloor\frac{n}{3} + \frac{1}{3}\rfloor = \lfloor\frac{3k+r +1}{3}\rfloor = \lfloor k + \frac{r+1}{3}\rfloor = k + \lfloor\frac{r+1}{3}\rfloor \leq k + 1$
Czyli:
$$\lfloor\frac{n}{3} + \frac{2n}{3*2^{32}} \rfloor < k + 1$$.
Z drugiej strony
$$\lfloor\frac{n}{3} + \frac{2n}{3*2^{32}} \rfloor \geq \lfloor\frac{n}{3}\rfloor$$
$$\lfloor\frac{n}{3}\rfloor = \lfloor\frac{3k+r}{3}\rfloor = \lfloor k + \frac{r}{3}\rfloor = k$$
Ostatecznie
$$k \leq \lfloor\frac{n}{3} + \frac{2n}{3*2^{32}} \rfloor < k + 1$$.
oraz $k = \lfloor \frac{n}{3} \rfloor$.
Udowodniliśmy zatem, że
$$ \lfloor \frac{n}{3} \rfloor = \lfloor \frac{2^{32} + 2}{3} * \frac{n}{2^{32}}\rfloor$$
Użyjemy powyższego wzoru do implementacji operacji div3 dla $n \geq 0$.
Niech $M = \frac{2^{32} + 2}{3}$. Liczba $M$ mieści się w zakresie `int64_t`.
Szukanym wyrażeniem jest `(M * (int64_t)n) >> 32`
Dla $n < 0$ mamy:
$$\lceil \frac{n}{3}\rceil = \lfloor \frac{2^{32} + 2}{3} * \frac{n}{2^{32}}\rfloor + 1$$
Wynik:
`((M * (int64_t)n) >> 32) - (n >> 31)`
## Zadanie 2
:::danger
Autor:
:::
## Zadanie 3
:::success
Autor: Mateusz Materek
:::
:::info
https://evanw.github.io/float-toy/
http://weitz.de/ieee/
:::
The IEEE 754 standard[9] specifies a binary16 as having the following format:
- Sign bit: 1 bit
- Exponent width: 5 bits
- Significand precision: 11 bits (10 explicitly stored)
**Zakres i dokładność**
| | |
| -------- | ------------------------------------ |
|  |  |
| | |
**(w porównaniu: single precision)**
## Zadanie 4
:::success
Autor: Kamila Goszcz
:::
- $a = 3.984375 · 10^{-1} = 0.3984375 = 0.0110011111_{2} = 1.1001111100_{2} · 2^{-2}$
- $b = 3.4375 · 10^{-1} = 0.34375 = 0.0101111111_{2} = 1.0111111100 · 2^{-2}$
- $c = 1.771 · 10^3 = 1771 = 11011101011_{2} = 1.1011101011 · 2^{10}$
- $a+b = 1.1001111100_{2} · 2^{-2} + 1.0111111100 · 2^{-2} = 11.0001111 · 2^{-2} = 1.1000111100 · 2^{-1}$
- $(a+b)+c = 1.1000111100 · 2^{-1} + 1.1011101011 · 2^{10} = 1.1000111100 · 2^{-1} + 110111010110 · 2^{-1}=110111010111.1000111100 · 2^{-1}$
$1101110101\color{blue}1\color{red}1.\color{green}{1000111100} · 2^{-1} =$
$11011101\color{blue}{100}\color{red}0 = 1.1011101110 · 2^{10}$
- $b+c = 1.0111111100 · 2^{-2} + 1.1011101011 · 2^{10} = 1.0111111100 · 2^{-2} + 1101110101100 · 2^{-2}= c$
- $a+(b+c) = c$
## Zadanie 5
:::success
Autor: Mateusz Materek
:::
* `(float)x == (float)dx`: **TAK**
int32_t -> float utrata precyzji,
int32_t -> double bez utraty precyzji
double -> float utrata precyzji.
Finalnie zaokrąglenie jest takie same.
* `dx - dy == (double)(x - y)`: **NIE**
Kontrprzykład: `dx = INT_MIN`; `dy = 1`; `x-y` to negative-overflow, dx-dy jest prawidłową wartością (`double` może przechowywać większe liczby niż `int32_t`).
* `(dx + dy) + dz == dx + (dy + dz)` **TAK**
`int32_t` mieści się w double bez utraty precyzji, 3 `double` zmieszczą się w (co najwyżej) 34 bitach, a `double` ma mantysę długości 52 bitów.
* `(dx * dy) * dz == dx * (dy * dz)` **NIE**
Kontrprzykład: dx = 5, dy = INT_MAX-256, dz = INT_MAX
* `dx / dx == dz / dz`: **NIE**
Kontrprzykład: dx lub dz = 0 (wtedy mamy `1 == NaN`)
## Zadanie 6
:::success
Autor: Kamila Goszcz
:::
:::info
Reprezentacje binarne liczb zmiennoprzecinkowych f i g typu «float» zostały załadowane odpowiednio do zmiennych «x» i «y» typu «uint32_t»
:::
- zmiana znaku liczby «f»:
```c=
x ^= 1 << 31
```
- obliczenie wartości $\lfloor log_2|f| \rfloor$ typu «int» dla f w postaci znormalizowanej:
$\lfloor log_2|f| \rfloor = \lfloor log_2(m * 2^e) \rfloor = \lfloor log_2\ m + \log_2 2^e \rfloor = \lfloor log_2\ m + e\rfloor = e$
```c=
return ((x >> 23) & 255) - 127
```
- wartość logiczna operacji «f == g»:
liczba 0 ma dwie reprezentacje, a więc musimy rozważyć ten przypadek osobno
```c=
return (x == y) | ((x | y) == (1 << 32));
```
- wartość logiczna operacji «f < g»
1) x ujemne, y dodatnie - zwracamy true, chyba że są to zera dodatnie i ujemne
2) x, y tego samego znaku -> robimy x-y: jeśli bit znaku = 1 to zwracamy 1, w.p.p. 0
```c=
return ((x >> 31) & !(y >> 31) & !((x | y) == (1 << 32))
| ((((x - y) >> 31) & ((x >> 31) == (y >> 31)))
```
``` ((x & y & (y - x)) | (~x & ~y & (x - y)) | (x & ~y)) >> 31 ```
## Zadanie 7
:::success
Autor: Kamila Goszcz
:::
```c=
uint32_t mult_by_power_of_2(uint32_t f, int32_t i) {
int32_t s = f & 0x80000000; /* znak */
int32_t e = (f >> 23 & 255); /* wykładnik przesunięty do prawej*/
uint32_t m = f & 0x007FFFFF; /* mantysa */
e += i;
if (i >= 0) {
/* Sprawdzamy czy nie mamy overflow, zwracamy +- inf */
return e >= 255 ? (s | 0x7F800000) : (s | (e << 23) | m)
}
else {
/* Sprawdzamy, czy nie wpadliśmy do liczb zdenormalizowanych */
if (e <= 0) {
m >>= 1;
/* Sprawdzamy czy nie mamy underflow, zwracamy +- 0 */
if (m == 0) return s
}
return s | (e << 23) | m;
}
}
```
## Zadanie 8
:::danger
Autor:
:::
## Zadanie 9
:::success
Autor: Kamila Goszcz
:::
```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 | 0x80000000; /* mantysa 1.xxx... dosunięta do lewej */
if (e > 30)
return INT_MIN
else if (e < 0)
return 0
else
return ((m >> (31 - e)) ^ s) + (s & 1)
}
```
## Zadanie 10
:::danger
Autor:
:::
Google Drive
Gist
Clipboard
Sign in with Wallet
