Редактирование: Adaptive precision arithmetic

Перейти к: навигация, поиск

Внимание! Вы не авторизовались на сайте. Ваш IP-адрес будет публично видимым, если вы будете вносить любые правки. Если вы войдёте или создадите учётную запись, правки вместо этого будут связаны с вашим именем пользователя, а также у вас появятся другие преимущества.

Правка может быть отменена. Пожалуйста, просмотрите сравнение версий, чтобы убедиться, что это именно те изменения, которые вас интересуют, и нажмите «Записать страницу», чтобы изменения вступили в силу.
Текущая версия Ваш текст
Строка 1: Строка 1:
 
==Мотивация==
 
==Мотивация==
Все вычисления, производимые компьютером в модели с ''плавающей точкой'', имеют погрешность. При большом количестве арифметических действий она возрастает. Во многих случаях результирующая погрешность уже не устраивает, и требуется либо абсолютно точное вычисление, либо меньшая погрешность. Одним из решений данной проблемы является хранение чисел в виде рациональных дробей, в которых числитель и знаменатель представляется в виде длинного целого числа. Но работать с такими числами довольно "дорого" по времени и тяжело в реализации: необходимо писать факторизацию чисел, эффективно сокращать дроби. Для улучшения работы нужны определенные оптимизации. Одной из них и является использование ''адаптивной арифметики'' (англ. ''adaptive precision arithmetic'').
+
<wikitex>Все вычисления, производимые компьютером во $\mathrm {floating}$ $\mathrm {point}$[http://en.wikipedia.org/wiki/Floating_point] модели, имеют погрешность. При большом количестве арифметических действий она возрастает. Во многих случаях результирующая погрешность уже не устраивает, и требуется либо абсолютно точное вычисление, либо меньшая погрешность. Одним из решений данной проблемы является хранение чисел в виде рациональных дробей, в которых числитель и знаменатель представляется в виде длинного целого числа. Но работать с такими числами довольно "дорого" по времени и тяжело в реализации: необходимо писать факторизацию чисел, эффективно сокращать дроби. Для улучшения работы нужны определенные оптимизации. Одной из них и является использование ''адаптивной арифметики'' (англ. ''adaptive precision arithmetic'').
 
+
</wikitex>
 
==Базовые понятия==
 
==Базовые понятия==
 
===Представление чисел===
 
===Представление чисел===
Большинство современных процессоров поддерживают числа с плавающей точкой в форме <tex> \pm \mathrm{significand} \times 2^{\mathrm{exponent}}</tex>. Значащая часть числа (мантисса) представляет собой <tex>p</tex>-битное двоичное число в форме <tex>b.bbb \dots</tex>, где каждое <tex>b</tex>   
+
Большинство современных процессоров поддерживают числа с плавающей точкой в форме <tex> \pm significand \times 2^{exponent}</tex>. Значащая часть числа (мантисса) представляет собой <tex>p</tex>-битное двоичное число в форме <tex>b.bbb \dots</tex>, где каждое <tex>b</tex>   
 
обозначает один бит. Также имеется один бит на знак.
 
обозначает один бит. Также имеется один бит на знак.
  
Строка 10: Строка 10:
  
 
Далее в этой статье фраза "что-либо представимо в <tex>p</tex> битах" будет означать представимость в <tex>p</tex> битах мантиссы, ''не'' учитывая  знак и экспоненту.
 
Далее в этой статье фраза "что-либо представимо в <tex>p</tex> битах" будет означать представимость в <tex>p</tex> битах мантиссы, ''не'' учитывая  знак и экспоненту.
 
 
===Разложения===
 
===Разложения===
 
{{Определение
 
{{Определение
Строка 56: Строка 55:
 
}}
 
}}
  
Например, в 4-битной арифметике произведение <tex>111 \times 101 = 100011</tex> будет округлено в <tex>1.001 \times 2^5</tex>.
+
''Например'', в 4-битной арифметике произведение <tex>111 \times 101 = 100011</tex> будет округлено в <tex>1.001 \times 2^5</tex>.
  
 
При вычислении результата может возникнуть ситуация, когда значение попадает в точности между двумя соседними <tex>p</tex>-битными значениями. Тогда требуется определить правило поведения в таком случае. Рассмотрим некоторые из них.
 
При вычислении результата может возникнуть ситуация, когда значение попадает в точности между двумя соседними <tex>p</tex>-битными значениями. Тогда требуется определить правило поведения в таком случае. Рассмотрим некоторые из них.
Строка 70: Строка 69:
 
}}
 
}}
  
Например, в 4-битной арифметике число <tex>10011</tex> будет округлено до <tex>1.010 \times 2^4</tex> по первому правилу, и до <tex>1.001 \times 2^4</tex> по второму.
+
''Например'', в 4-битной арифметике число <tex>10011</tex> будет округлено до <tex>1.010 \times 2^4</tex> по первому правилу, и до <tex>1.001 \times 2^4</tex> по второму.
  
 
Стоит отметить, что стандарт IEEE 754 использует округление до ближайшего четного по умолчанию.
 
Стоит отметить, что стандарт IEEE 754 использует округление до ближайшего четного по умолчанию.
Строка 78: Строка 77:
 
Из-за округления данные операции теряют некоторые важные свойства, например, ассоциативность: <tex>(1000 \oplus 0.011) \oplus 0.011 = 1000</tex>, но <tex>1000 \oplus(0.011 \oplus 0.011) = 1001</tex>.
 
Из-за округления данные операции теряют некоторые важные свойства, например, ассоциативность: <tex>(1000 \oplus 0.011) \oplus 0.011 = 1000</tex>, но <tex>1000 \oplus(0.011 \oplus 0.011) = 1001</tex>.
  
При анализе округления часто используют так называемый <tex>\operatorname{ulp}</tex>.
+
При анализе округления часто используют так называемый <tex>ulp</tex>.
 
{{Определение
 
{{Определение
 
|definition=
 
|definition=
 
'''ULP''' (англ. ''units in the last place'') {{---}}  эффективная величина самого младшего (<tex>p</tex>-ого) бита.
 
'''ULP''' (англ. ''units in the last place'') {{---}}  эффективная величина самого младшего (<tex>p</tex>-ого) бита.
 
}}
 
}}
Например, <tex>\operatorname{ulp}(-1100) = 1, \operatorname{ulp}(1) = 0.001</tex> в <tex>p</tex>-битной арифметике.
+
''Например'', <tex>ulp(-1100) = 1, ulp(1) = 0.001</tex> в <tex>p</tex>-битной арифметике.
  
Так же полезной нотацией является <tex> \operatorname{err}(a \circledast b) </tex>, которая обозначает ошибку округлении результата выполнения операции <tex>\circledast</tex>. Отметим, что если <tex>\operatorname{ulp}</tex> всегда беззнаковая величина, то <tex>\operatorname{err}</tex> может иметь знак. Для базовых операций (сложение, вычитание, умножение) <tex> a \circledast b = a \ast b + \operatorname{err}(a \circledast b)</tex>, и точное округление гарантирует, что <tex> |\operatorname{err}(a \circledast b)| \leqslant \frac{1}{2}\operatorname{ulp}(a \circledast b)</tex>.
+
Так же полезной нотацией является <tex> err(a \circledast b) </tex>, которая обозначает ошибку округлении результата выполнения операции <tex>\circledast</tex>. Отметим, что если <tex>ulp</tex> всегда беззнаковая величина, то <tex>err</tex> может иметь знак. Для базовых операций (сложение, вычитание, умножение) <tex> a \circledast b = a \ast b + err(a \circledast b)</tex>, и точное округление гарантирует, что <tex> |err(a \circledast b)| \leqslant \frac{1}{2}ulp(a \circledast b)</tex>.
  
 
==Свойства==
 
==Свойства==
Строка 188: Строка 187:
 
  <tex>7</tex>  <tex>return (x, y)</tex>
 
  <tex>7</tex>  <tex>return (x, y)</tex>
  
<wikitex>Пример работы последнего алгоритма, когда $|a| < |b|$ и $|a| < |x|$. Сумма $11.11 + 1101$ будет представлена в виде разложение $10000 + 0.11$.
+
<wikitexПример работы последнего алгоритма, когда $|a| < |b|$ и $|a| < |x|$. Сумма $11.11 + 1101$ будет представлена в виде разложение $10000 + 0.11$.
 
[[Файл:Adaptive_10.jpg|слева]]
 
[[Файл:Adaptive_10.jpg|слева]]
 
<br clear="all" />
 
<br clear="all" />
Строка 298: Строка 297:
 
* [http://en.wikipedia.org/wiki/Rounding Rounding]
 
* [http://en.wikipedia.org/wiki/Rounding Rounding]
 
* [http://www.google.ru/url?sa=t&rct=j&q=Adaptive%2Bprecision%2Barithmetic&source=web&cd=4&ved=0CDgQFjAD&url=http%3A%2F%2Fwww.cs.berkeley.edu%2F~jrs%2Fpapers%2Frobustr.pdf&ei=fZigTp6xHoWa-waGxKSOBQ&usg=AFQjCNGl9T4V-Y02Wi99TjgSDLFotO5xeg&sig2=pQ5SPC_lRGCtwoBZhMhGhA  Jonathan Richard Shewchuk, "Adaptive Precision Floating-Point Arithmetic and Fast Robust Geometric Predicates"]
 
* [http://www.google.ru/url?sa=t&rct=j&q=Adaptive%2Bprecision%2Barithmetic&source=web&cd=4&ved=0CDgQFjAD&url=http%3A%2F%2Fwww.cs.berkeley.edu%2F~jrs%2Fpapers%2Frobustr.pdf&ei=fZigTp6xHoWa-waGxKSOBQ&usg=AFQjCNGl9T4V-Y02Wi99TjgSDLFotO5xeg&sig2=pQ5SPC_lRGCtwoBZhMhGhA  Jonathan Richard Shewchuk, "Adaptive Precision Floating-Point Arithmetic and Fast Robust Geometric Predicates"]
 
 
[[Категория: Вычислительная геометрия]]
 

Пожалуйста, учтите, что любой ваш вклад в проект «Викиконспекты» может быть отредактирован или удалён другими участниками. Если вы не хотите, чтобы кто-либо изменял ваши тексты, не помещайте их сюда.
Вы также подтверждаете, что являетесь автором вносимых дополнений, или скопировали их из источника, допускающего свободное распространение и изменение своего содержимого (см. Викиконспекты:Авторские права). НЕ РАЗМЕЩАЙТЕ БЕЗ РАЗРЕШЕНИЯ ОХРАНЯЕМЫЕ АВТОРСКИМ ПРАВОМ МАТЕРИАЛЫ!

Чтобы изменить эту страницу, пожалуйста, ответьте на приведённый ниже вопрос (подробнее):

Отменить | Справка по редактированию (в новом окне)