Pull to refresh
  • by relevance
  • by date
  • by rating

Рекуррентное соотношение Мюллера: проблемы с округлением чисел с плавающей точкой

Programming *
Translation
Некоторое время назад я натолкнулся на упражнение, которое выглядит не так уж и сложно:

Пусть последовательность xn определена так:

посчитайте x30.

Это не так уж и трудно закодировать, возможно реализовав xi как рекурсивную функцию. С обычными числами с плавающей запятой двойной точности, по мере увеличения i, результат красиво сходится к 100. Супер!

К сожалению, 100 даже близко не является правильным ответом. На самом деле последовательность сходится к 5.
Читать дальше →
Total votes 60: ↑59 and ↓1 +58
Views 35K
Comments 116

Альтернатива стандарту IEEE754

Website development *Programming *Java *C++ *Mathematics *
В результате размышлений над особенностями стандарта IEEE754, я пришел к выводу, что многие положения, на которых основывается данный стандарт, зиждутся на ошибочном методологическом подходе. А именно, авторы стандарта за основу рассуждений взяли заданный формат машинного слова. Затем, исходя из заданного формата, были сформулированы требования к множеству чисел, которые могут быть представимы в этом формате. Было высказано ряд бездоказательных суждений. Например, о предпочтении использования в компьютерной арифметике дробной мантиссы. Или об обязательной потере точности, при представлении чисел в ненормализованном виде, а также недопустимости неоднозначного представления действительных чисел в экспоненциальном виде.

Отсюда родились требования к обязательной нормализации чисел после каждого арифметического действия, и как следствие, большие проблемы с представлением чисел, лежащих вблизи нуля, а также невозможность получения нуля в явном виде. Это все приводит к неоправданным затратам вычислительных ресурсов на нормализацию и борьбу с ее последствиями.

Предлагаемая здесь работа является логическим продолжением предыдущих двух моих топиков на Хабре. В своих рассуждениях я оттолкнулся от естественного представления чисел и ограничений, которые накладываются на числа, вследствие конечности носителя, на который они записываются. Такой подход позволил получить ряд очень важных выводов. Основной из них заключается в том, что процесс нормализации не является обязательным на всех этапах проведения арифметических операций. Более того, именно обязательная нормализация привела к необходимости введения специального класса денормализованных чисел, что существенно увеличило программно-аппаратные затраты.

Предложенный подход позволил прийти к выводу, что, добавлением всего одного разряда в машинном слове, можно в раз расширить диапазон представимых чисел в формате с плавающей точкой, где К — количество разрядов машинной мантиссы.

В статье вы найдете целый ряд нетривиальных выводов, которые позволяют по-новому взглянуть на представление чисел с плавающей запятой в машинном коде.
Читать дальше →
Total votes 18: ↑7 and ↓11 -4
Views 4.2K
Comments 24

И все-таки, почему Posit являются достойной альтернативой IEEE 754

High performance *Programming *C++ *Algorithms *Manufacture and development of electronics *
Месяц Posit на Хабре объявлен открытым, а значит я не могу пройти мимо и проигнорировать обрушившуюся на них критику. В предыдущих сериях:

Новый подход может помочь нам избавиться от вычислений с плавающей запятой
Posit-арифметика: победа над floating point на его собственном поле. Часть 1
Posit-арифметика: победа над floating point на его собственном поле. Часть 2
Испытания Posit по-взрослому

Думаю многие из вас могут с ходу вспомнить хотя бы один случай из истории, когда революционные идеи на момент своего становления наталкивались на неприятие сообществом экспертов. Как правило, виной такому поведению выступает обширный багаж уже накопленных знаний, не позволяющий взглянуть на старую проблему в новом свете. Таким образом, новая идея проигрывает по характеристикам устоявшимся подходам, ведь оценивается она только теми метриками, которые считались важными на предыдущем этапе развития.

Именно с таким неприятием сегодня сталкивается формат Posit: критикующие зачастую просто “не туда смотрят“ и даже банально неправильно используют Posit в своих экспериментах. В данной статье я попытаюсь объяснить почему.
Читать дальше →
Total votes 93: ↑87 and ↓6 +81
Views 12K
Comments 72

Алгоритм Кэхэна: как получить точную разность произведений

Algorithms *Mathematics *
Translation
image

Недавно я вернулся к анализу погрешностей чисел с плавающей запятой, чтобы усовершенствовать некоторые детали в следующей редакции книги Physically Based Rendering. Числа с плавающей запятой — интересная область вычислений, полная сюрпризов (хороших и плохих), а также хитрых трюков, позволяющих избавиться от неприятных неожиданностей.

В процессе работы я наткнулся на этот пост на StackOverflow, из которого узнал об изящном алгоритме точного вычисления $a \times b-c \times d$.

Но прежде чем приступать к алгоритму, нужно понять, что же такого хитрого в выражении $a \times b-c \times d$? Возьмём $a=33962.035$, $b=-30438.8$, $c=41563.4$ и $d=-24871.969$. (Это реальные значения, которые получились у меня во время запуска pbrt.) При 32-битных значениях float получаем: $a \times b=-1.03376365 \times 10^9$ и $c \times d=-1.03376352 \times 10^9$. Выполняем вычитание, и получаем $-128$. Но если выполнить вычисления с двойной точностью, а в конце преобразовать их во float, то получится $-75.1656$. Что произошло?

Проблема в том, что значение каждого произведения может сильно выйти за нижнюю границу $-1 \times 10^9$, где расстояние между представимыми значениями с плавающей запятой очень велико — 64. То есть при округлении $a \times b$ и $c \times d$ по отдельности до ближайшего представимого float, они превращаются в числа, кратные 64. В свою очередь, их разность будет кратной 64, и не останется никакой надежды, что она станет к $-75.1656$ ближе, чем $-64$. В нашем случае результат оказался ещё дальше из-за того, как два произведения были округлены в $-1 \times 10^9$. Мы напрямую столкнёмся со старым добрым катастрофическим сокращением1.
Читать дальше →
Total votes 31: ↑31 and ↓0 +31
Views 7.6K
Comments 9

Свою квалификацию программиста можно повысить, если разбираться в деталях разных технологий

ITSumma corporate blog Programming *Studying in IT IT career
Translation

Фрагмент комикса с простым объяснением, что такое числа с плавающей запятой

Когда речь идёт о повышении квалификации программиста, мы часто говорим о тестировании, написании кода для повторного использования, шаблонах проектирования, удобочитаемости.

Всё это очень важно. Но я хочу поговорить о другом способе — изучить в деталях работу систем, которые вы используете! Лично для меня это основной способ повышения квалификации.

Дело в том, что многие программисты используют технологии не задумываясь, как они работают. И это нормально. Люди выполняют поставленные задачи. От них не требуют понимания всей сути, потому что детали отвлекают от главной задачи и зачастую ничем не помогают в её выполнении.
Читать дальше →
Total votes 31: ↑28 and ↓3 +25
Views 11K
Comments 9