<style> .red { color: red; } .orange { color: #f99157; } </style>  aneb _Třeba to půjde, když změním epsilon_ Vašek Volhejn @ Výběrko 2021 --- ## Sčítání popředu a pozadu ---- ### Kód - Python ```python import random random.seed(1) a = [random.random() for _ in range(1000)] print("a =", a[:5], "...") print() print("Soucet a: ", sum(a)) print("Soucet a, pozadu:", sum(reversed(a))) print("Jsou stejne?", sum(a) == sum(reversed(a))) print("Rozdil:", sum(a) - sum(reversed(a))) ``` --- ### Problém - konečný počet bitů = konečný počet možností - ale čísel je nekonečně, chyby budou --- ### Absolutní/relativní odchylka Číslo $x$, jeho počítačová reprezentace $y$ Absolutní odchylka: $|x-y|$ Relativní odchylka: $\Big| \frac{x-y}{x} \Big|$ --- ### První pokus: fixed-point Fixní počet čísel před a za desetinnou tečkou: ``` 1010.0011 + 0001.1001 = 0011.1100 ``` Absolutní odchylka do 0.03125, relativní se mění Jenže co hodně malá nebo hodně velká čísla? --- ### Floating-point Řešení: zapamatovat si jen ty nejdůležitější bity a pozici desetinné tečky <pre> x = 0000000<b><span style="color: red">1</span><span style="color: #f99157">0110.1110</span></b>11110100... y = 000000000000.00<b><span style="color: red">1</span><span style="color: #f99157">11000101</span></b>1... </pre> $x \approx 1.01101110 \cdot 2^{4}$ $y \approx 1.11000101 \cdot 2^{-3}$ Relativní odchylka do ~0.002, absolutní se mění --- ### Floating-point reprezentace Tvar $a \cdot 2^b$, kde $b$ je celé, $1 \leq a < 2$ Např: - 8 bitů pro $a$ = rozsah <code><span style="color: red">1</span>.<span style="color: #f99157">00000000</span></code> až <code><span style="color: red">1</span>.<span style="color: #f99157">11111111</span></code> - rozsah $b$ od $-8$ do $7$, takže 4 bity --- <code> x = 0000000<b><span style="color: red">1</span><span style="color: #f99157">0110.1110</span></b>11110100... </code> reprezentujeme jako <code><span style="color: #f99157">01101110</span> 1100 </code> --- ### Sčítání <code> <b><span class="red">1</span>.<span class="orange">01110101</span></b> ⋅ 2³ + <b><span class="red">1</span>.<span class="orange">10010110</span></b> ⋅ 2^-1 </code> <pre> <b><span class="red">1</span><span class="orange">011.10101</span></b> + 0.<b><span class="red">1</span><span class="orange">10010110</span></b> = <b><span class="red">1</span><span class="orange">100.01110</span></b>0110 </pre> <code>≈ <b><span class="red">1</span>.<span class="orange">01110101</span></b> ⋅ 2³</code> --- ### Násobení <code> <b><span class="red">1</span>.<span class="orange">01110101</span></b> ⋅ 2³ x <b><span class="red">1</span>.<span class="orange">10010110</span></b> ⋅ 2^-1 = </code> <code> <b><span class="red">1</span>.<span class="orange">01110101</span></b> x <b><span class="red">1</span>.<span class="orange">10010110</span></b> ⋅ 2^{3 + (-1)} = </code> <code> <b><span class="red">1</span>.<span class="orange">10010011</span></b>1110001110 ⋅ 2² </code> <code>≈ <b><span class="red">1</span>.<span class="orange">10010100</span></b> ⋅ 2²</code> --- #### Skutečné floating-point typy ([IEEE 754](https://en.wikipedia.org/wiki/IEEE_754)) $x \approx a \cdot 2^b$ | C++ typ | Bity | Bity $a$ (mantisa) | Bity $b$ (exponent) | Rozsah | | ------------- | ---- | ------------------ | ------------------- | --- | | `float` | 32 | 24 | 8 | $\pm 1.17 · 10^{-38}$ až $\pm 3.40 · 10^{38}$ | | `double` | 64 | 53 | 11 | $\pm 2.25 · 10^{-308}$ až $\pm 1.80 · 10^{308}$ | --- ### Co se může pokazit Problém: operace s čísly na různých škálách $x^2 - y^2 = (x-y) \cdot (x+y)$ V doublech nemusí platit! ---- ```python >>> x=1e9+1 # 1e9 znamena 10^9 >>> y=1e9 >>> (x-y)*(x+y) 2000000001.0 >>> x**2 - y**2 2000000000.0 ``` ---- \begin{align} x^2 &= 10^{18} + 2 \cdot 10^9 + 1 \\ &\approx 10^{18} + 2 \cdot 10^9 \\ y^2 &= 10^{18} \\ x^2 - y^2 &\approx 2 \cdot 10^9 \end{align}  --- ### Co se může pokazit 2 Jak zjistit, na jaké straně přímky je bod?  Znaménko hodnoty $(x_q - x_p)(y_r - y_p) - (y_q - y_p)(x_r - x_p)$ Pro $p = (0, 0)$: $x_qy_r - y_qx_r$ ---- $(x_q - x_p)(y_r - y_p) - (y_q - y_p)(x_r - x_p)$  ---- $(x_q - x_p)(y_r - y_p) - (y_q - y_p)(x_r - x_p)$  ---- Poučení: v celých číslech super, v doublech peklo --- ### Co s tím na soutěži? ---- #### Porovnávat s odchylkou Číslo `x` může znamenat cokoliv v intervalu `(x-eps, x+eps)`, `eps` typicky mezi `1e-9` a `1e-6` | Před | Po | | -------- | -------- | | `x==y` | `abs(x-y)<eps` | | `x<y` | `x<y-eps` | | `x<=y` | `x<y+eps` | <!-- TODO ilustrace --> ---- #### Zmenšit počet nepřesných operací Když počítám $\frac{1}{2} \cdot \frac{1}{3} \cdot \frac{1}{5}$, můžu místo `1.0/2.0/3.0/5.0` napsat `1.0/(2*3*5)` ---- #### Dávat pozor na hranice celých čísel Místo `floor(x)` radši `floor(x+eps)` Místo `sqrt(x)` radši `sqrt(max(x, 0))` ---- #### Neodmocňovat - Podmínku `i < sqrt(n)` můžeme přepsat na `i*i < n` - Geometrické vzdálenosti: pokud záleží jen na pořadí, můžeme místo $\sqrt{x^2 + y^2}$ porovnávat $x^2 + y^2$ - Podobně: řazení podle úhlu <!-- TODO ilustrace --> ---- #### Počítat pomocí zlomků - Čísla tvaru $\frac{p}{q}$ můžeme reprezentovat jako dvě celá čísla $p$ a $q$, aritmetika $\frac{p_1}{q_1} + \frac{p_2}{q_2} = \frac{p_1q_2 + p_2q_1}{q_1q_2}$ apod. - Pozor na overflow! ---- #### Vypisovat s dostatečnou přesností ```c++ #include <iomanip> ... cout << fixed << setprecision(9) << x; printf("%.20f", x); ``` ---- #### Pokud k dispozici: arbitrary-precision Java: `BigDecimal` Python: `Decimal` --- ### Další zákeřnosti ``` 1. / 0. == inf -1. / 0. == -inf inf == inf + 1e9 inf - inf == nan 0. / 0. == nan nan != 3 nan != inf nan != nan (!) ``` --- ### Toť vše https://kasiopea.matfyz.cz/archiv/2017/doma/F/ https://kasiopea.matfyz.cz/archiv/2018/doma/D/ Hlavní zdroj: Kurz [Competitive Programmer's Core Skills](https://www.coursera.org/lecture/competitive-programming-core-skills/floating-point-numbers-qdtKK) --- úvod přes fixed-point čísla logaritmická škála Není asociativní! Brání optimalizacím divnosti jako nan a nekonečno; plati inf>konecne x, inf+x=inf inf - inf = -nan ("nedefinovano"), nan != nan, sqrt(1e-9) = nan <- pozor! fast inverse square root long double arbitrary precision (Java: BigDecimal, Python: Decimal?) nejcasteji reportovany GCC bug https://www.coursera.org/lecture/competitive-programming-core-skills/floating-point-numbers-qdtKK ukazka s mensim poctem bitu v mantise a exponentu x^2 - y^2 = (x-y)*(x+y) pro y=1e9, x=y+1 prvni je horsi, ma chybu o 1 vyhnuti se doublum pomoci zlomku neodmocnovat: i*i < n misto i<sqrt(n), porovnavani delek delat double operace az na konci: 1/2/3/5 = 1/(2*3*5) porovnavat s epsilonem, x < y na x < y - eps, x <= y na x < y + eps, floor rozumne hodnoty eps: 1e-9 az 1e-6