Русский
Русский
English
Статистика
Реклама

Сложение

Что такое алгоритм! Часть 31 Математика

08.05.2021 08:23:50 | Автор: admin

Самое интересное и самое сложное, самое скучное и самое полезное об алгоритме. Страна чудес и зазеркалье Алгоритма одновременно. Попробуем подобно известному сказочнику познакомить воображаемую Алису с лабиринтом "мыслей" математика со способами использования переноса, моделирования и синтеза. И опять под катом много слов и немного картинок...


Title


Задача


Почти все предыдущие статьи этой серии были очень странными. А эта статья будет самой "чудесатой". Поэтому настроенным на взрослый скепсис пожалуй стоит закончить чтение тут, но готовых развлечься с пользой в разговоре с не очень научной строгостью и на очень важные темы Вам найдется здесь немного "сложноватого" и увлекательного чтения.


В обсуждении предыдущей статьи (как же хорошо что обсуждение наконец состоялось!) стало ясно, что за большим нагромождением слов, каждый раз формирующих статью серии, очень плохо просматривается цель. А цель, с которой все эти слова собираются под заголовком "Что такое алгоритм ?!", очень проста и одновременно амбициозна.


Цель всей работы это способы создавать алгоритмы без участия человека (формализация и автоматизация этого процесса).


Для достижения обозначенной цели необходимо много составляющих. Прежде всего и самое главное необходимо найти подсказки, как работать с алгоритмом. Можно попробовать дать определение слова "Алгоритм". Вы скажете определение "Алгоритма" уже существует, и легко найти его, например, на Вики. И да, и нет. На страницах Википедии есть множество определений разных понятий. Давайте рассмотрим простой пример ну, скажем, возьмем "Молоток". Значение (читай "определение" этого слова) тоже есть на Вики:


Молоток небольшой ударный ручной инструмент, применяемый для забивания гвоздей, разбивания предметов и других работ. В основном изготавливается из стали. Молоток один из древнейших инструментов, используемых разумным человеком.

Молоток для крокета


Тут дан некоторый набор слов. Что из них определение, а что инструкция к применению? Является ли фламинго молотком для крокета. Если ли в приведенном значении слова "Молоток" сведения, помогающие в изготовлении молотка? Думаю, что подсказок в этом "определении" так же мало, как и в определении слова "Алгоритм", взятом на странице Вики.


А почему этих подсказок нет. Первым делом можно сказать, что это связано с типом приведенного "определения". Это определение неформальное. Оно для человека. А не для математика. И почти потому оно не подходит и для станка, изготавливающего молотки. В чем проблема? Конечно, тут нет проблем. Если этим пользуется человек, то всё нормально. А вот если нам все же нужно сделать станок для производства молотков, то нужно думать. И изобретать формальное определение. Например, это будет "чертеж" или программа для изготовления этого молотка на автоматическом фрезерном станке или какой-то другой вариант описания. И это будет формальное "определение" для изготовления. Формальное "определение" для использования тоже потребуются, если этим молотком будет пользоваться не человек, а машина.


К чему это всё? Возвращаемся к алгоритму. Легкий вывод: чтобы "научить" машину изменять и создавать алгоритм тоже необходимо формальное определение. Если уточнять, то это необходимо пока машина сама не сможет конвертировать наши "определения" на свой язык. Поэтому первая статья серии начинается с разбора существующих определений "алгоритма". И вся работа опирается на констатацию факта, что формального определения алгоритма еще нет. Но для поставленных задач это определение необходимо сформулировать.


Если быть совсем честными, то формальное определение Алгоритма в работе уже сформировано. Но в этом определении есть недостаток. Это определение математика. Для того чтобы им начали пользоваться (и может быть добавили в Вики), необходимо предоставить способы применения этой математики к практическим задачам. И таких способов слишком много, и только самые важные появляются в статьях этой серии. И способ, которым является сама Математика, будет рассмотрен в текущей статье. Да, мы будем с помощью Математики описывать как работает Математика. Думаю, Льюис Кэрролл порадовался бы такому приключению для Алисы. С чего же нам начать? Ах, да...


Следуй за белым кроликом. Тук-тук...

Кролик


Алгоритм сложения


В предыдущей статье этой серии с загадочным номером 101, мы уже на "небольшом" примере изготовления торта познакомились с тремя способами создавать алгоритмы: это случайное обнаружение алгоритма, объединение алгоритмов и эволюционная аккумуляция алгоритма. Эти способы хороши с их использованием алгоритмы успешно, но очень медленно развивались, и они развивались бы и дальше. Но так случилось, что на их основе были сформированы следующие два. Эти способы: алгоритмический перенос и трансляция алгоритма из модели. И с этой парой, как у Алисы со встречей Траляля и Труляля, всё стало развиваться значительно веселее и, что самое главное, это позволило гораздо быстрее формировать новые и сложные алгоритмы. Что же это за близнецы Перенос и Трансляция? И почему необходимо их все же различать для продолжения разговора об Алгоритме?


Ответам на эти вопросы посвящена текущая статья. И, чтобы начать наше приключение, все же будет необходимо воспользоваться результатом предыдущей статьи. Необходимо попробовать испеченный в ней волшебный тортик с надписью "Съешь меня". Попробовать не на вкус, но использовать как рабочий метод разбора формирования сложного алгоритма.


И в этой статье будет особенный алгоритм. Для наших целей нам очень подойдёт простой и одновременно уже знакомый нам "Алгоритм сложения". Мы встречались с ним в первой статье этой серии.


Давайте немного с ним развлечёмся, оценивая структуру этого "математического действия", которое для многих наших задач является элементарным. Ведь эта элементарность появилась не сразу. И для Алисы это действие еще сложн и не всегда дается.


Сложению тебя обучили? спросила Белая Королева. Сколько будет один плюс один плюс один плюс один плюс один плюс один плюс один плюс один плюс один плюс один?

Я не знаю, ответила Алиса. Я сбилась со счета.

Экзамен по арифметике


Поможем Алисе обучиться такому сложению? Давайте рассмотрим ситуацию с участием "древнего математика", которому впервые могла понадобиться эта математическая операция. У этого "математика" тоже было что считать. Это, конечно были не слова "один" во фразе королевы, но тоже очень одинаковые объекты. Ну, например, коровы в большом стаде. И пусть сначала в его стаде было три-семь коров, так что, окинув их взглядом, "математик" всегда мог легко сказать их "количество". Это "количество" изначально даже не было числом. Это был способ оценить количество стогов сена, которое нужно запасти на зиму для стада. Или оценить количество времени, которое нужно потратить на заготовку этого сена.


Попробуем на примере стада коров разобраться в последовательности событий и действий человека, ухаживающего за стадом, приведшей к появлению "Алгоритма сложения". Мы основываемся на некоторых фактах. Например, что человек, ухаживающий за стадом, (далее будем условно называть его "пастухом") знает, что для одной коровы количество времени для заготовки сена на зиму это полдня. На основе этого знания попробуем запланировать количество труда "пастуха" (читай написать алгоритм вычисления трудозатрат). Для этого не нужно знать слово "количество" и даже знание "чисел" не является необходимым.


Опять, как и предыдущей статье, рассматриваемый алгоритм опирается на базовую стратегию "Поддержание своей жизнеспособности", и в угоду сокращения количества слов в статье текущей, опустим множество этапов эволюционного развития и сразу перейдем к достаточно элементарному алгоритму пастуха. Упростим ситуацию со стадом и оставим в нём только одну корову.


Алгоритм обеспечения одной коровы сеном на зиму прост:


Работай полдня, укладывая сено рядом с этой коровой.

Да, количество времени, необходимое для одной коровы, выбрано произвольно и не соответствует нашей реальности, но для сказочной страны вполне подходит.


Как сформировался этот алгоритм? Те кто запасал корове сена меньше оставались к весне без коровы, затем без еды и погибали. Суровая сила эволюционного отбора. Не будем рассказывать это Алисе и оставим такие сведения для взрослых размышлений.


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


Для любой коровы, рядом с которой нет укрытого стога, работай полдня, укладывая сено рядом с ней, и, заканчивая, укрой стог.

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


Среда снова предоставляет нашему "пастуху" новые ситуации и проверяет его профпригодность в разработке алгоритмов выживания. Итак, у "пастуха" новое счастье коров в его стаде ещё больше. И эти коровы очень плотно живут в коровнике и сено рядом с ними укладывать не получается. Коровы размещены также плотно как слово "один" во фразе Королевы. Но сено на зиму нужно запасти, а Алисе необходимо посчитать сумму. Пора изобретать более совершенные алгоритмы. И эти алгоритмы будут основываться на комплементарных действиях и сходстве разных предметов по отношению к некоторым алгоритмам. На сцену выходит первый близнец синтез алгоритма с именем "Перенос".


Близнецы


Перенос


Для использования чисел еще рановато, но мы уже близко. Возьмем вместо них пока нечто попроще и породнее. Алисе я бы посоветовал посмотреть на пальцы. Ну а для "пастуха" пальцев будет маловато. Но всегда можно найти объект поменьше коровы, который можно поместить в руках, например, камешки. И что нужно с ними сделать? Правильно сопоставить! Палец сопоставим слову "один". А камешек сопоставим одной корове. Легко сказать "сопоставить". А каким алгоритмом это можно сделать?


У Алисы ситуация проще. На каждое услышанное слово "один" достаточно "комплементарно" загнуть один палец на своих руках. Для "пастуха" это сопоставление чуть сложнее, но принцип схож. Стадо тоже необходимо выстроить в структуру и лучше всего использовать структуру линейную, совсем как у слов "один" во фразе Королевы. Например, это можно сделать утром, когда коровы выходят из коровника с узкой дверью, пропускающей за раз только одну корову. Необходимо заранее запастись камешками. И для каждой выходящей коровы брать камешек и "загнуть его", ну, нет, конечно, это же не палец Алисы. Нужно положить его в отдельное выбранное место. Так формируется кучка камней. И когда последняя корова выйдет, в кучке будет лежать столько же камней сколько коров в стаде. А зачем нам эти загнутые пальцы и кучка камней? Правильно! С ними проще работать, чем с растворяющейся в памяти длинной фразой или большим стадом. С ними можно выполнить подсчет. С кучкой камней легко придумать алгоритм формирования запаса сена на зиму в отдельном от коровника хранилище. И можно выполнить много еще чего. Мы перенесли опору алгоритма запаса сеном на зиму с использования коров на использование камешков. И упростили жизнь "пастуху", сделав его уже немного "математиком".


До серьезного математика остался один шаг. Этот шаг появление операции сложения. И шаг прост. Например, нужно, два "пастуха", хранящих в кармане кучки камешков, которые соответствуют каждая своему стаду. При этом достаточно только возникновения ситуации, когда два стада нужно объединить. В этом случае, конечно, можно прогнать полученное объединенное стадо через коровник с узкой дверью. Но ведь гораздо проще просто высыпать две кучки камешков в одно место!


Наверно, как-то так и родился алгоритм сложения! А вместе с ним зародилась и математика. Как способ повышать эффективность алгоритмов переносом в более удобную область. И эта область только поначалу была камешками, а в последствие дополнилась числами, интегралами, исчислением предикатов и много, много, много еще чем...


Но, а как же второй близнец "Трансляция"? Да, да он тоже нам нужен, и тоже нужен Алисе.


Трансляция


Сложения не знает, сказала Черная Королева.

А Вычитание знаешь? Отними из восьми девять.

Этого я не знаю, но зато

Зато? Что так смутило Алису? Ответ прост, и подсказкой будет то, что этот момент смущал те только Алису, он сильно мучил и "древних математиков". А сложность этого момента сводится к простому утверждению: не все математические действия с "камешками" однозначно соответствуют (то есть переносятся) на стадо коров. И отрицательные числа, наверно, стали самой простой и только первой проблемой, с которой столкнулась математика. Ведь очень непонятно какой корове соответствует отрицательное число -1.


И дальше встает вопрос. Отказываться ли от этих "странных" отрицательных чисел? Или можно использовать их, но не переносить в коровы? Со знаниями, которыми обладает современный школьник старших классов, ответ тривиален. Конечно, использовать! И, видимо, Алисе придётся все же изучить и такое "странное" вычитание. Но "древним математикам" было не так легко. И только польза от алгоритмов, использующих отрицательные числа, помогла принять это сложное решение и ответить на заданный вопрос утвердительно. Да, нужно использовать отрицательные числа!



Такие же странные вопросы, подобные вопросу об "отрицательных числах", впоследствии вставали перед математиками не один раз. Вопросы были запутанными совсем как у Гусеницы, и каждый раз новая абстракция становилась всё "страньше" и "страньше". Иррациональные числа вместо рациональных (например, для алгоритма нахождения длины окружности по диаметру). Квадратный корень из отрицательного числа ("мнимая единица"), например, для алгоритма решения кубического уравнения. "Бесконечность", например, для нахождения значения предела сходящейся суммы бесконечного ряда (еще древнегреческий философ Зенона размышлял над этой странной задачей в парадоксе "Ахиллес и черепаха"). Парадоксов перед математиками было много. Некоторые все же исключались, потому что не было возможности использовать их в полезных алгоритмах. Так было, например, с парадоксом "Множество всех множеств". Но основой всех таких размышлений и решений было одно наличие полезных алгоритмов, в которых использовались эти "странности". И тут "естественный отбор" тоже работал. И эволюционный способ формирования математических алгоритмов, медленным и в дополнение к нему быстрым накоплением привел к тому, что мы сейчас называем слово "Математика".


А где же прячется различие двух близнецов "Переноса" и "Трансляции". Вы, да и Алиса, верно уже догадались. При задании трансляции обязательно вводятся ограничения и указывается подмножество взаимно-однозначно соответствующих объектов и алгоритмов, внутри которого можно корректно произвести перенос между двумя алгоритмическими областями: прикладной областью ("стадом коров") и пространством модели ("горсткой камешков"). Вне этого подмножества перенос невозможен. Как невозможна "минус одна корова". Эти ограничения необходимы в представленной модели с "отрицательными числами". Самой простой модели, которую удалось найти. Но такие же ограничения есть и для моделей с трансляцией куда более сложной. Все же здесь остановимся. Не будем всё сваливать в одну кучу ведь перед нами нечто посложнее стада коров.


Оставим сложную часть для следующей статьи, в которой продолжим наш разговор об ученых, моделях и разных способах использования Алгоритма для изучения научного познания. На очереди вывод на чистую воду алгоритмичности "Физики". И, думаю, опять в этом нам должна помочь Алиса. Осталось только найти этому занятию время и надеяться, что мы не потратим его впустую.


хорошо бы получше провести время

Все понятно! с торжеством сказал Шляпа.

Провести время?! Ишь чего захотела! Время не проведешь! Да и не любит он этого!

Время


Выводы


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


В этой статье мы познакомились еще с двумя способами синтеза алгоритмов ("Перенос" и "Трансляция из модели"). Эти способы еще не до конца описаны, но их основа уже немного просматривается.


На примере "пастуха-математика" смогли понаблюдать за эволюцией и скрытой алгоритмичностью Математики.


Вроде бы разработали помощь Алисе в сложении для правильных ответов Королеве.


Развлеклись?


Спасибо Вам за внимание.


Отзывы


Буду очень благодарен за отзывы, пожелания и предложения, так как они помогают мне скорректировать направление развития работы в этой области.


Отдельное волнение у меня есть по стилю повествования и форматированию, используемым в статье (кавычки, абзацы, курсив). Напишите, пожалуйста, если у Вас есть замечания к ним. Можно личным сообщением.


Ссылки


Подробнее..

Сложение двух чисел с плавающей запятой без потери точности

17.10.2020 10:23:13 | Автор: admin
Здравствуйте, друзья, как вы думаете, если мы напишем такой код:

s = a+b;z = s-a;t = b-z;

то не кажется ли вам, что в результате его выполнения получится, что t=0? С точки зрения привычной математики действительных чисел это и правда так, а вот с точки зрения арифметики с плавающей запятой в переменной t будет кое-что другое. Там будет то, что спасает нас от потери точности при сложении чисел $a$ и $b$. Кого интересует данная тема, прошу под кат.


По моей традиции текстовая статья дублируется на видео. По содержанию текст и видео идентичны.



Читателю статьи для её восприятия нужно понимать способ представления чисел с плавающей запятой в формате IEEE-754 и понимать, почему, например, 0,1+0,20,3, но если такого навыка у вас по каким-то причинам нет, но вы хотели бы его приобрести, то прошу обратить внимание на список источников конце статьи, на пункты [1] и [3-5].

Итак, у нас следующая проблема. Сумма двух чисел с плавающей запятой c=a+b может вычисляться с некоторой ошибкой. Знаменитый на весь интернет пример 0,3 0,2+0,1 хорошо это показывает. Наша задача в том, чтобы всё-таки складывать числа без этой ошибки. То есть сделать так, чтобы мы могли как-то сложить 0,2+0,1 и хоть в каком-то виде знать точный результат. В каком смысле точный, если даже исходные числа 0,1 и 0,2 не имеют точного представления в формате IEEE-754? Вот сейчас и поясню.

Начнём с того, что чисел 0,1 и 0,2 в двоичной арифметике с плавающей запятой быть не может, а наиболее близкие к ним значения для типа данных double (число удвоенной точности binary64, так его называют в Стандарте IEEE-754) следующие:

$0{,}1 0{,}1000000000000000055511151231257827021181583404541015625 ={}\\ {}=\frac{3602879701896397}{36028797018963968}$


$0{,}2 0{,}200000000000000011102230246251565404236316680908203125 ={}\\ {}=\frac{3602879701896397}{18014398509481984}$


Десятичный результат получен с помощью правильного онлайн-конвертера, а дробь посчитана с помощью библиотеки MPIR и функции mpq_set_d, которая умеет переводить double к рациональной дроби.

К сожалению, это данность, от неё никуда не уйти, если хранить числа в типе данных double (или любом другом типе фиксированного размера из Стандарта IEEE-754). Но проблема, которую мы решаем, другая. Нам нужно эти два числа, наиболее близких к 0,1 и 0,2, сложить так, чтобы получить результат без погрешности. То есть чтобы в результате сложения иметь число

0,1000000000000000055511151231257827021181583404541015625 +0,2000000000000000111022302462515654042363166809082031250 =0,3000000000000000166533453693773481063544750213623046875.

К сожалению, если просто написать код s=0.1+0.2, то мы получим кое-что другое, а именно

s == 0.3000000000000000444089209850062616169452667236328125

что отличается от правильного ответа ровно на

$t = 2{,}77555756156289135105907917022705078125 \cdot 10^{-17}$


Подумаешь, скажете вы, десять в минус семнадцатой! Мне чтобы пиксель на экран вывести такая погрешность не помеха!. И будете правы. Задача точного вычисления каких-либо выражений относится к очень узкой области Computer Science, связанной с разработкой математических библиотек для языков программирования. Когда вы вызываете какую-нибудь функцию из такой библиотеки, то можете и не подозревать, что в основе её работы лежит труд десятков и сотен человек, выполняемый на протяжении десятилетий, а работает такая функция правильно благодаря совершенно неочевидным алгоритмам Вот я и хотел бы приоткрыть для вас этот удивительный мир, для чего и пишу такие научно-популярные статьи.

Зачем может понадобиться точное сложение двух чисел? Приложений много, но вот одно из них, которое будет понятно всем. Если вы хотите сложить все числа из массива X[N] и сделаете это вот так:

S = 0.0;for (i=0; i<N; ++i)  S = S + X[i];

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

Итак, теперь давайте я опишу проблему чуть более формально. В рамках статьи представьте, что всё происходит в типе данных double, это никак не изменит сути изложения.

У нас есть два числа $a$ и $b$ типа double. Нам не важно, что эти числа $a$ и $b$ уже содержат в себе какую-то погрешность, полученную, например, в результате конвертирования десятичной строки в формат IEEE-754. Важно, что они сейчас перед нами, а их предыстория нас не интересует. Нужно сложить эти два числа c=a+b так, чтобы в результате сложения не возникло погрешности.

Но ведь это невозможно!

Да, это невозможно, спасибо что дочитали, до новых встреч :)

Шучу, конечно. Это невозможно только если мы храним результат сложения в одной переменной того же типа данных. Но вспомните пример выше. У нас была переменная s, и переменная t. Причём s была округлённым результатом сложения a+b, а t была равна разности этого округлённого результата и точного значения суммы. При этом выполняется равенство s+t=a+b.

И вот хорошая новость состоит в том, друзья, что такое представление суммы a+b в виде суммы s+t можно выполнить всегда (если a+b)! Если s=a+b оказывается точно-представимым значением в типе double, то очевидно, что t=0. Если это не так, то t будет равно некоторому очень маленькому (по сравнению с s) числу, которое является точно-представимым. Итак, вот оно, фундаментальное свойство суммы чисел с плавающей запятой: ошибка округления в результате суммирования чисел типа double всегда будет точно-представимым числом типа double! А это означает, что пара чисел (s, t) всегда даёт нам возможность сохранить сумму чисел a+b как бы без погрешности. Да, мы вынуждены хранить две переменные вместо одной, но прелесть в том, что их всего две, а не больше.

Теперь опишем это свойство на математическом языке. Введём обозначение RN(x) это результат приведения произвольного вещественного числа x к типу данных double по правилу округления round-nearest-ties-to-even, то есть это округление к ближайшему, но в случае равного удаления от двух ближайших к тому, у которого последний бит мантиссы равен нулю (чётный). Именно этот режим работает почти везде по умолчанию, то есть если вы не знаете, о чём я сейчас говорю, то в вашем процессоре на 100% работает именно этот режим, так что не беспокойтесь.

Пусть a и b числа типа double. Пусть |a||b| и RN(a+b) . Тогда следующий алгоритм

s = RN (a+b);z = RN (s-a);t = RN (b-z);return (s, t);

вычисляет пару (s, t) таких чисел, для которых:
  1. s+t = a+b (в точности)
  2. s число типа double, наиболее близкое к a+b.


Основная цель моих статей объяснять сложные вещи простым языком, поэтому давайте я построю для вас образ, помогающий понять этот алгоритм. Пожалуйста, посмотрите на рисунок, а ниже даётся его описание.


Прямоугольник олицетворяет переменную с плавающей запятой фиксированного размера, поэтому прямоугольники, помеченные символами а и b имеют одинаковый размер, но $b$ смещён относительно $a$ вправо, потому что у нас есть условие: |a||b|. Третий прямоугольник Точное а+b это некоторое промежуточное значение, которое может иметь больший размер, чем размер переменных $a$ и $b$, поэтому оно будет округлено, и хвостик, вылезающий за границы нашего типа данных, будет отброшен. Таким образом, мы переходим к четвёртому прямоугольнику Округлённое a+b, это и есть наше значение s, полученное в первой строке алгоритма. Если теперь из s снова вычесть $a$, то останется только b без хвостика. Это делается во второй строке алгоритма. Теперь мы хотим получить хвостик от $b$, и это делается в третьей строке алгоритма, когда из исходной переменной $b$ мы вычитаем b без хвостика. Остаётся хвостик, это и есть переменная t, которая показывает ту самую погрешность, которая возникла в ходе округления. При этом из данных рассуждений видно, что такой хвостик всегда будет умещаться в одну переменную, потому что он не может превышать размера переменной $b$. В крайнем случае, когда смещение $b$ относительно $a$ будет настолько большим, что s=RN(a+b)=a, то в этом случае, очевидно, z=0 и t=b. Скучный рисунок на эту тему я вам предлагаю изобразить самостоятельно.

Если вы не находите картинки убедительными для себя, то в книге [1, раздел 4.3.1, теорема 4.3] есть строгое математическое доказательство, но оно не умещается в формат научно-популярной статьи. Его краткая суть в том, что в нём показано почему в строках 2 и 3 алгоритма не будет выполняться округления, то есть эти выражения вычисляются точно, а если так, значит t=b-z=b-(s-a) = (a+b)-s в точности, что нам как раз и нужно: t является разностью между реальной суммой a+b и её округлённым значением s.

Давайте рассмотрим несколько примеров, удобных для восприятия человека.

Пример 1.

$\begin{array}{rcl} a &{}={}& 9007199254740991 = 2^{53}-1, \\ b &{}={}& 2, \\ s &{}={}& 9007199254740992, \\ t &{}={}& 1. \end{array}$


Пояснение. Реальное значение a+b=253+1, однако в типе данных double младший бит, равный единице, не влезет в 52 бита дробной части мантиссы, по какой причине будет выброшен при округлении, но переменная t подхватит его и сохранит в качестве погрешности, а переменная s сумеет сохранить только 253 ровно. Легко видеть, что s+t будет равно 253+1.

Пример 2.

$\begin{array}{rcl} a &{}={}& 1152921504606846976 = 2^{60}, \\ b &{}={}& 1073741823 = 2^{30}-1, \\ s &{}={}& 1152921505680588800, \\ t &{}={}& -1. \end{array}$


Пояснение выполнено в двоичном коде.

  a = 1000000000000000000000000000000000000000000000000000000000000  b =                                111111111111111111111111111111a+b = 1000000000000000000000000000000111111111111111111111111111111      -------------------------------------бит округления--^   s = 1000000000000000000000000000001000000000000000000000000000000

Если выравнивание кода не поехало, то вы видите, где у суммы a+b будет бит округления, и что само округление будет выполнено вверх. Чтобы снова получить паровоз из 30 единиц, нужно вычесть единицу из s=260+230. Поэтому t=-1. Как видим, t может быть отрицательным, когда округление выполняется вверх.

Я не говорил этого явно, но алгоритм работает даже когда b<0, то есть фактически происходит вычитание.

Пример 3.

$\begin{array}{rcl} a &{}={}& 9007199254740991 = 2^{53}-1, \\ b &{}={}& -2251799813685247{,}75 = -\frac{2^{53}-1}{4}, \\ s &{}={}& 6755399441055743, \\ t &{}={}& 0{,}25. \end{array}$


В этом примере число $b$ является сдвигом вправо на 2 бита числа $a$, поэтому если $a$ влезает в double впритык, ясно, что вычитание здесь точным получиться не может. Останется небольшой хвостик размером в два бита после запятой.

Из доказательства, приведённого в [1], следует один положительный момент данного алгоритма: в ходе его выполнения не может возникнуть переполнения во второй и третьей строках, если оно не возникло при вычислении s=RN(a+b).

Недостатком является то обстоятельство, что алгоритм работает только для |a||b| (однако если вы посмотрели доказательство, то знаете, что в действительности достаточно более слабого условия, чтобы экспонента $a$ была не меньше экспоненты $b$, но проверить это условие намного сложнее). То есть нам нужно либо делать лишнюю проверку, либо как-то иначе гарантировать правильный порядок чисел на входе алгоритма. Ветвление не всегда обрабатывается достаточно быстро, это зависит от процессора и от того, как на это ветвление посмотрел компилятор (иногда он может его убрать, иногда нет, а иногда он его убрал, но оказалось так плохо, что лучше бы не трогал). Возникает вопрос: а можно сложить числа без ошибок округления, если их порядок друг относительно друга заранее неизвестен?

Можно. Для этого есть второй алгоритм, но в нём вместо 3-х операций их уже 6.

  s = RN (a+b);  b' = RN (s-a);  a' = RN (s-b');  d_b = RN (b-b');  d_a = RN (a-a');  t = RN (d_a+d_b);  return (s, t)

Как это работает? В случае когда |a||b|, алгоритм работает по сути так же как предыдущий, и строгое доказательство для этого случая, которое вы можете отыскать в [2, раздел 2.3, теорема 7], сводится к тому, чтобы показать, что лишние три операции не портят этого результата. А вот основная сложность доказательства в том, чтобы рассмотреть случай |a|<|b|, он значительно труднее и тоже выходит за рамки лёгкого научно-популярного изложения. Схематичная картинка общей ситуации при |a|<|b| даётся ниже с пояснением.


Первые два прямоугольника показывают соотношение между $a$ и $b$, на этот раз $a$ смещено относительно $b$ вправо. Следующие три прямоугольника показывают процедуру сложения и отбрасывания хвостика. Дальше начинается основная сложность. Вычисляем b=s-a, то есть мы вычитаем из округлённого значения s число $a$ и выброшенный xвостик, а это значит, что b будет чуть меньше, чем $b$, и этот недостаток отмечен красным прямоугольничком. Другое дело, когда мы вычисляем a=s-b, то есть вычитаем из суммы величину b с недостатком, а значит получим а без хвостика с избытком, и этот избыток обозначается зелёным прямоугольничком. Если мы теперь вычтем из $b$ величину b (которая с недостатком), то получим избыток db. Далее вычитаем из $a$ величину a (которая с избытком), и получаем хвостик с недостатком da. Если теперь сложить хвостик с недостатком и избыток, мы получим чистый хвостик.

У читателя может возникнуть вопрос: а в каких случаях можно с уверенностью сказать, что t=0? Иными словами, про какие пары чисел (a, b) точно известно, что их сумма будет точно-представимым (без округления) числом в том же типе данных?

Мне известны только три теоремы на этот счёт, которые также приводятся в [1] и [2].

Теорема 1 [книга 1, раздел 4.2.1, теорема 4.2]. Если сумма RN(a+b) оказалась денормализованным числом, то сумма a+b является точно-представимой.

Теорема 2 [статья 2, раздел 2.2, лемма 4] Если |a+b||a| и |a+b||b|, то число a+b является точно-представимым (аналогичное верно и для разности).

Теорема 3 [книга 1, раздел 4.2.1, лемма 4.1] Пусть a0 и a/2 b 2a, тогда разность a-b будет точно представимой.

Бдительный читатель сразу вспомнит про так называемую ошибку критического сокращения старших значащих битов, называемую в литературе Catastrophic Cancellation и спросит: Как же так, ведь давно известно, что когда мы вычитаем очень близкие друг к другу числа, там возникает такая погрешность, что ой-ой-ой! Как ты говоришь, что в этом случае разность будет точно-представимой.

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

На основе рассмотренных в этой статье алгоритмов в следующей мы будем более правильно складывать числа из массива.

Благодарю за внимание!

Список источников


[1] Jean-Michel Muller, Handbook of floating-point arithmetic, 2018.
[2] Jonathan Richard Shewchuk, Adaptive Precision Floating-Point Arithmetic and Fast Robust Geometric Predicates, Discrete & Computational Geometry 18(3), 1997, pp. 305363.
[3] На Хабре: Что нужно знать про арифметику с плавающей запятой.
[4] На Хабре: Наглядное объяснение чисел с плавающей запятой.
[5] Учебный видео-курс для самых маленьких, предельно наглядное разъяснение чисел с плавающей запятой в 8-ми уроках. Первый урок на на YouTube.
Подробнее..

Категории

Последние комментарии

  • Имя: Макс
    24.08.2022 | 11:28
    Я разраб в IT компании, работаю на арбитражную команду. Мы работаем с приламы и сайтами, при работе замечаются постоянные баны и лаги. Пацаны посоветовали сервис по анализу исходного кода,https://app Подробнее..
  • Имя: 9055410337
    20.08.2022 | 17:41
    поможем пишите в телеграм Подробнее..
  • Имя: sabbat
    17.08.2022 | 20:42
    Охренеть.. это просто шикарная статья, феноменально круто. Большое спасибо за разбор! Надеюсь как-нибудь с тобой связаться для обсуждений чего-либо) Подробнее..
  • Имя: Мария
    09.08.2022 | 14:44
    Добрый день. Если обладаете такой информацией, то подскажите, пожалуйста, где можно найти много-много материала по Yggdrasil и его уязвимостях для написания диплома? Благодарю. Подробнее..
© 2006-2024, personeltest.ru