272
правки
Изменения
→Ответ
# В формате double представимы числа в диапазоне <tex> [2.3 \times 10^{-308}, 1.7 \times 10^{308}] </tex>.
== Особые значение значения чисел с плавающей точкой ==
=== Ноль (со знаком) ===
В нормализованной форме невозможно представить ноль. Для его представления в стандарте зарезервированы специальные значения мантиссы и экспоненты.
Из свойств чисел двойной точности следует, что для них <tex> \varepsilon_m = 2^{-54}</tex>.
}}
== Unit in the last place (Unit of least precision)==
Мера единичной точности используется для оценки точности вычислений.
{{Определение
|definition=
Пусть <tex> a </tex> - число с плавающей точкой, мантисса которого имеет длину <tex> m </tex> бит, а экспонента - <tex> e </tex> бит. Тогда <tex> ulp(a) = 2^{e - m} </tex>.
}}
Приведем пример кода на Python, который показывает, при каком значении числа <tex> x </tex> компьютер не различает числа <tex> x </tex> и <tex> x + 1 </tex>.
>>> from math import *
>>> x = 1.0
>>> while (x != x + 1):
... x *= 2
...
>>> x
9007199254740992.0
>>> log(x) / log(2)
53.0
То есть <tex> x = 2^{53} </tex>, так как мантисса числа двойной точности содержит 53 бита (в памяти хранятся 52).
В C++ для расчета расстояния между двумя числами двойной точности можно воспользоваться функцией <tex> \mathrm{boost::math::float\_distance(a, b)} </tex>.
== Погрешность предиката "левый поворот" ==
=== Определения ===
{{Утверждение
|statement=
{{Утверждение
|statement=
<tex> \forall a, b, c \in D^2, \tilde{v} = (b_x - \ominus a_x) \times otimes (c_y - \ominus a_y) - \ominus (b_y - \ominus a_y) \times otimes (c_x - \ominus a_x) </tex>
<tex> \exists \tilde{\epsilon} \in D: </tex>
# <tex> \tilde{v} > \tilde{\epsilon} \Rightarrow (b - a) \times (c - a) > 0 </tex>
}}
=== Постановка задачи Расчет <tex> \tilde{\epsilon} </tex> ===Найти Обозначим <tex> v = (b - a) \varepsilontimes (c - a, b, c) = (b_x - a_x) (c_y - a_y) - (b_y - a_y) (c_x - a_x)</tex>. Теперь распишем это выражение в дабловой арифметике. <tex>\tilde{v} = (b_x \ominus a_x) \varepsilon: |otimes (c_y \ominus a_y) \ominus (b b_y \ominus aa_y) \otimes (c c_x \ominus aa_x) = \\ = [ (b_x - a_x) (c_y - a_y) (1 + \delta_1) (1 + \delta_2) (1 + \delta_3) - \\ - (b_y - a_y) (c_x - a_x) (1 + \delta_4) (1 + \delta_5) (1 + \delta_6) ] (1 + \delta_7),</tex> <tex> |\delta_i| \leq \varepsilon_m </tex> Заметим, что <tex> v \varepsilon approx \Rightarrow a, b, c tilde{v} </tex> не лежат на одной прямой.
<tex> |v - \tilde{v} | = |(b_x - a_x) (c_y - a_y) - (b_y - a_y) (c_x - a_x) - \\ominus - (b_x - a_x) (c_y - a_y) (1 + \delta_1) (1 + \delta_2) (1 + \delta_3) (1 + \delta_7) + \\+ (b_y - a_y) (c_x - a_x) (1 + \delta_4) (1 + \delta_5) (1 + \delta_6) (1 + \delta_7)| = \otimes \= |(b_x - a_x) (c_y - a_y) (1 - (1 + \delta_1) (1 + \delta_2) (1 + \delta_3) (1 + \delta_7)) - \\ominus - (b_y - a_y) (c_x - a_x) (1 - (1 + \delta_4) (1 + \delta_5) (1 + \delta_6) (1 + \delta_7))| \leq \\\leq |(b_x - a_x) (c_y - a_y) (1 - (1 + \delta_1) (1 + \delta_2) (1 + \delta_3) (1 + \delta_7))| + \\ominus + |(b_y - a_y) (c_x - a_x) (1 - (1 + \otimes delta_4) (c_x 1 + \delta_5) (1 + \delta_6) (1 + \ominus a_xdelta_7)) | = </tex>\\<tex> = [ |(b_x - a_x) (c_y - a_y) | \cdot |((1 + \delta_1) (1 + \delta_2) (1 + \delta_3) (1 + \delta_7) - </tex>1)| + \\<tex> - + |(b_y - a_y) (c_x - a_x) | \cdot |((1 + \delta_4) (1 + \delta_5) (1 + \delta_6) ] (1 + \delta_7), - 1)| = \\= |(b_x - a_x) (c_y - a_y)| \cdot |\delta_1 + \delta_2 + \delta_3 + \delta_7 + \delta_1 \delta_2 \ldots| + \\+ |(b_y - a_y) (c_x - a_x)| \cdot |\delta_4 + \delta_5 + \delta_6 + \delta_7 + \delta_4 \delta_5 \ldots| \leq \\\leq |(b_x - a_x) (c_y - a_y)| \cdot (|\delta_1| + |\delta_2| + |\delta_3| + |\delta_7| + |\delta_1 \delta_2| \ldots) + \\+ |(b_y - a_y) (c_x - a_x)| \cdot (|\delta_4| + |\delta_5| + |\delta_6| + |\delta_idelta_7| + | \delta_4 \delta_5| \ldots) \leq \\\leq |(b_x - a_x) (c_y - a_y)| \cdot (4 \varepsilon_m + 6 \varepsilon_m^2 + 4 \varepsilon_m^3 + \varepsilon_m^4) + \\+ |(b_y - a_y) (c_x - a_x)| \cdot (4 \varepsilon_m + 6 \varepsilon_m ^2 + 4 \varepsilon_m^3 + \varepsilon_m^4) = \\= (|(b_x - a_x) (c_y - a_y)| + |(b_y - a_y) (c_x - a_x)|)(4 \varepsilon_m + 6 \varepsilon_m^2 + 4 \varepsilon_m^3 + \varepsilon_m^4)</tex>
Пусть <tex> v \approx \tilde{v} t = (|(b_x - a_x) (c_y - a_y)| + |(b_y - a_y) (c_x - a_x)|).</tex>Получаем, что
<tex> e \epsilon = (|(b_x v - a_x) \tilde{v}| \leq t \cdot (c_y - a_y)| 4 \varepsilon_m + 6 \varepsilon_m^2 + 4 \varepsilon_m^3 + |(b_y - a_y) (c_x - a_x)|\varepsilon_m^4) . </tex>
<tex> \epsilon tilde {t} = (|(b_x - a_x) (c_y - a_y) (1 + \delta_1) (1 + \delta_2) (1 + \delta_3)| + \\+ |v (b_y - a_y) (c_x - a_x) (1 + \delta_4) (1 + \delta_5) (1 + \tilde{v}delta_6)| ) (1 + \delta_7) \geq \\\leq e geq |(b_x - a_x) (c_y - a_y) (1 - \times varepsilon_m)^3)|(4 1 - \varepsilon_m ) + \\+ 6 |(b_y - a_y) (c_x - a_x) (1 - \varepsilon_m)^3)|(1 - \varepsilon_m) = \\= |(b_x - a_x) (c_y - a_y)| (1 - \varepsilon_m)^2 4 + 4 |(b_y - a_y) (c_x - a_x)| (1 - \varepsilon_m)^3 4 = \\= (|(b_x - a_x) (c_y - a_y)| + |(b_y - a_y) (c_x - a_x)|) (1 - \varepsilon_m)^4= t \cdot (1 - \varepsilon_m) ^4</tex>
<tex> e t \leq \tilde{et} \frac{1}{(1 - \varepsilon_m)^4} = \tilde{et} (1 + 4 \varepsilon_m + 10 \varepsilon_m^2 + 20 \varepsilon_m^3 + \cdots) </tex>
<tex> \epsilon = |v - \tilde{v}| \leq \tilde{\epsilon} \leq \tilde{\epsilont} (1 + 4 \varepsilon_m + 10 \varepsilon_m^2 + 20 \varepsilon_m^3 + \cdots) (4 \varepsilon_m + 6 \varepsilon_m^2 + 4 \varepsilon_m^3 + \varepsilon_m^4) </tex>
=== Ответ ===
<tex dpi="180"> \tilde{\epsilon} < 8 \varepsilon_m \tilde{t} </tex> Заметим, что это довольно грубая оценка. Вполне можно было бы написать <tex> \tilde{\epsilon} < 4.25 \varepsilon_m \tilde{t} </tex>или <tex> \tilde{\epsilon} < 4.5 \varepsilon_m \tilde{t}.</tex>
== Ссылки ==
[http://citeseer.ist.psu.edu/viewdoc/download?doi=10.1.1.102.244&rep=rep1&type=pdf Goldberg, D. 1991 ''What every computer scientist should know about floating-point arithmetic'']<br>
[http://grouper.ieee.org/groups/754 ieee.org ''IEEE 754'']<br>
[http://en.wikipedia.org/wiki/Unit_in_the_last_place en.wikipedia.org ''Unit in the last place'']
[http://neerc.ifmo.ru/mediawiki/index.php/%D0%9F%D1%80%D0%B5%D0%B4%D0%B8%D0%BA%D0%B0%D1%82_%22%D0%BB%D0%B5%D0%B2%D1%8B%D0%B9_%D0%BF%D0%BE%D0%B2%D0%BE%D1%80%D0%BE%D1%82%22 neerc.ifmo.ru/mediawiki ''Предикат "левый поворот"'']
[[Категория: Вычислительная геометрия]]
