Comments 172
Пока непонятно что мы получили. Было два числа такие, что их сумма представляла некую сумму. Мы получили два других числа с той же суммой.
Знаю, что дальше магический финт ушами будет, но пока польза не видна.
См например Kahan summation algorithm
Тема интересная, но подача всё же сложная для восприятия. "Физический смысл" прямоугольников я так и не понял. Скорее всего метафора не удачная или нужны дополнительные пояснения. В идеале, тут нужна такая визуализация, чтобы и без формул было всё понятно.
Я являюсь организатором митапов PiterJS, где помогаю докладчикам улучшать свои выступления. А так же являюсь автором канала на близкую тематику — Core Dump.
Поэтому, у меня к вам деловое предложение: когда будете готовить следующее видео, напишите нам в чат с предложением поревьюить черновой вариант, — постараемся помочь сделать ваше видео более доступным.
Так же возможен вариант какой-либо коллаборации или даже объединения.
Благодарю, Дмитрий. Я приму к сведению ваше предложение.
По прямоугольникам следует сразу же пояснить, что они представляют размерность разрядной сетки. Поэтому и одинаковые. А сдвиг обозначает относительное положение десятичной запятой в этих двух числах. Тогда сразу всё становится понятно.
Помню как в ВУЗе на каком-то предмете начали нас гонять по задачам, решаемым при помощи симплекс-таблиц. Расчётки, контрольные и т.д.
На кафедре ИКТ у нас был преподаватель, у которого была своя софтина для расчёта симплекс-таблиц, и старшекурсники ходили к нему на поклон чтобы рассчитать таблицы для диплома. Понятное дело не за спасибо.
Как-то раз я увидел одну из распечаток с результатами, и был неприятно удивлён, так как увидел промежуточные и конечные результаты в стиле 0.9999999999.
В симплекс-таблицах вся методика построена на делении одних чисел на другие, причём итеративно. При решении в десятичных дробях гарантированно будет накапливаться погрешность. Даже без плавающей запятой — просто за счёт округления.
Поэтому классический вариант предполагает использование простых дробей.
В общем захотелось мне утереть нос преподу. Я тогда только-только начал перебираться из MS-DOS в Windows 95, и первое что мне попалось под руку из инструментов — VBA для Excel.
В итоге мне удалось написать макрос, расчитывающий симплекс-таблицы прямо на листе Excel. При этом, дабы не терять в точности, я обучил макрос работе с простыми дробями.
Помню как смеялась комиссия на олимпиаде, где я рассказывал о причинах, побудивших меня к написанию этого макроса. Сказал, что меня не устраивает 0.999999999 вместо единицы. Сказал без фамилий, но вся комиссия прекрасно знала о ком идёт речь, потому и развеселились.
Насколько я знаю, в самом Excel встроенный метод расчёта симплексов появился только спустя несколько лет.
Дело не только в этом (есть и другие проблемы, почитайте про алгоритм Кэхэна), но статья объясняет простые вещи сложным языком.
Хотите десятичные вычисления? Не пользуйтесь двоичными.
Да, сегодня это для соответствующих применений (по советской терминологии, "экономических") наилучший вариант.
Но это таки (пока?) заметно дороже, при равных длинах и точности.
А ещё во многих случаях там, где нам кажется, что значения десятичные, они на самом деле двоичные, но просто так пахнут :) например, датчики обычно отдают двоичные значения. Не зря в C99 ввели "%a" для printf.
Другими словами, на целых числах.
Очень часто именно так и делается. Тем не менее есть альтернативы. Есть десятичная плавучка (у IBM даже с аппаратной поддержкой). Есть Decimal из C#, у которого 28 цифр мантиссы. Есть decimal управляемой точности в Python и ещё много где.
Тут можно упереться только в максимальные значения, если оперировать триллионами рублей.
Ну тут уже больше триллионов надо :)
2^63/100 ~= 90 квадриллионов (коротких).
Более того, в IEEE 754 от 2008 года добавлены типы decimal32, decimal64, decimal128. И они даже реализованы на аппаратном уровне в некоторых (немногих) процессорах Intel.
Более того, в IEEE 754 от 2008 года добавлены типы decimal32, decimal64, decimal128.
Я об этом же :)
И они даже реализованы на аппаратном уровне в некоторых (немногих) процессорах Intel.
Вот этого не видел. Ни в "Software Developer’s Manual", ни в "Instruction Set Extensions and Future FeaturesProgramming Reference" такого не описывают. Это какая-то особая фишка, или это вообще не x86?
Прошу прощения, я ошибся. Аппаратная реализация была у IBM ("IBM Z").
У Интела есть библиотека с эмуляцией всех операций, но реализации в железе — нет.
Тут можно ещё упереться в нарушение закона. Дело в том, что если где-то прописано, что процентная ставка 0.1%, то при временном переводе её в double, мы получаем другую ставку, и нарушаем закон. Так что здесь нужно сначала доказать, что такой перевод повлияет только на скорость, но не на ответ.
Дело в том, что если где-то прописано, что процентная ставка 0.1%, то при временном переводе её в double, мы получаем другую ставку, и нарушаем закон.
у меня вопрос в связи с этим. Если мы считаем процентную ставку помесячно и округляем в меньшую сторону — на сроке год — она эффективно получается меньше (на доли копеек, но тем не менее). Как с этим бороться? В разные месяцы по-разному округлять? Хранить где-то дробные значения? Или внимательно читать условия договоров и начислений и имплементировать соответствующие алгоритмы?
Мне известно только два способа: рациональные числа и арифметика с произвольной точностью (увеличиваем точность так, чтобы эти копейки, даже возведённые в степень, не сыграли бы роли). Если бы я разрабатывал финансовое ПО, то смотрел бы в сторону библиотеки длинной арифметики MPIR и там есть соответствующие типы данных mpq (рациональные) и mpf (с плавающей запятой). Слишком сложных вычислений там быть не может, поэтому каких-то особенных тормозов не будет.
Физика с Вами не согласна )
В том плане — что мне из банка не могут выдать вклад (или его часть) дробными частями копеек.
А раз — где-то в алгоритме должно быть учтено, что "мнимая" часть денег от вклада — должна в момент снятия вклада "исчезнуть", а то банки оставались б должны всем своим клиентам )
Я говорю о том, чтобы делать указанным способом именно промежуточные вычисления, а выдавать уже с округлением. Накопившиеся именно в ходе выдачи округления распределять по закону, но я законов этих не знаю. Так что по остальной части вопроса — это не ко мне :)
мне из банка не могут выдать вклад (или его часть) дробными частями копеек
Конечно же могут. Представьте, что вы забираете процент, набежавший за год. И этот процент всегда (без потери общности) равен 1⅓ рубля.
В первый год вам дадут рубль, во второй — тоже, а в третий — два рубля.
Это так не работает…
Есть счёт накопленных процентов, на который происходит начисление в соответствии с правилами (по сути формула) у этого счёта (для РФ) точность до копейки, большей точности там просто не будет. С момент причисления средств к основному счёту(капитализации)/выплаты сумма просто просто переводится с одного счёта на другой.
для РФ
Волшебный прием: вы сужаете целевое множество утверждения «мне из банка не могут выдать вклад (или его часть) дробными частями» (все банковские институты) до знакомого (банки РФ), после чего следует волшебный пасс: «это так не работает».
Это так не работает в банках РФ потому что писали правила, а потом переносили их в код — не особо умные люди, не желающие подумать.
Это так не работает потому что это правила бух.учёта по РСБУ, детально по US GAAP расписать не могу(, но вы наверное знаете как это работает по правилам в США? Или хотя бы как это происходит в Испании в банковском секторе?
как это происходит в Испании в банковском секторе?
«Банковский сектор» — слишком уж расплывчатый гипероним. В регулируемых именно государственным банковским законодательством банках — не знаю, но предполагаю, что по-разному, в зависимости от прямизны рук соответствующих программистов. Насколько мне известно, четкого закона, регулирующего округление, — нет.
В финансовых институтах, которые банками официально не являются (нет лицензии на депозит средств клиента дольше трех дней), — все происходит преимущественно, как я описал. Конкретно у нас есть клиенты, которые переводят к нам маленькие деньги в сотне разных валют десятками тысяч раз в день, а вечером — выполняется транзакция по конвертации всего этого богатства в, напримемр, фунты. Если мы начнем использовать флоаты, там погрешность может набежать уже довольно нешуточная, поэтому мы бережно все храним в целых центах (у разных валют количество разменных монет в одной номинальной единице может различаться), и при конвертации используем ровно тот метод, который предложен в этой статье, а именно считаем накопленнную ошибку.
Особенно это важно при учете всяких IDR и, например, GBP в одной транзакции. Если без остатка операцию выполнить не удается, остаток сохраняется до следующего вечера.
Округление происходит по правилам, причём после каждого "периода" при внесении на внутренний счёт накопленных процентов, правила оговариваются (либо правилам математического округления, либо по другим (т.н. бухгалтерское округление), никаких промежуточных данных в банковском по, по сути, не сохраняется, только остатки на счетах, у которых есть объявленная точность...
Если мы считаем процентную ставку помесячно и округляем в меньшую сторону — на сроке год — она эффективно получается меньше (на доли копеек, но тем не менее). Как с этим бороться?
Где-то должны быть просто записаны правила. Если не в законе, то в договоре. Или в каких-то нормативных документах.
Таких проблем полно. Вот с которой я сталкивался когда-то: пусть НДС 20% (типовой для Украины), а цены записаны без НДС. Вот цена одной единицы товара 1 гривна 12 копеек, соответственно НДС будет 22 копейки. А вот две единицы товара — 2 гривны 24 копейки, тогда НДС уже будет 45 копеек, а не 44. Как правильно считать — по всей накладной, по каждому пункту или по каждой единице товара?
Насколько я помню, несколько лет налоговая морочила голову, пока не постановила — по накладной. Но на это потребовалось особое разъяснение.
Мы просто придумали алгоритм разбрасывания копеек, чтобы итоговая сумма процентов на дату очередного начисления была равна обычно (half up) округленной сумме за весь прошедший период. Запросили разъяснения у регулятора допустимо ли, что в отдельные периоды на копейку разница по сравнению с расчётом за один период — ответили что допустимо, если итоговая сумма на конец периода совпадает. То есть если на 6-й месяц клиент видит, что ему на копейку больше начислили чем за 5-й, но за 6 месяцев вместе ему начислили 1/2 годовой, то норм. С аннуитетом решили не рисковать не соблюдением термина "равные платежи" и доли копеек отбрасывали в пользу клиента.
Процентная ставка применяется нарастающим итогом, то есть при расчете за суммы процентов за второй месяц, рассчитывается сумма за два месяца, из нее вычитается сумма за первый месяц, получаем результат.
И наоборот, портит двоичные, когда вы их зачем-то хотите видеть как десятичные.
нет же. любое число, имеющее конечную запись в двоичном виде, будет иметь конечную же запись в десятичном виде (притом, если я ничего не путаю, знаков после запятой в десятичном виде будет столько же)
Всё формально так, но дальше дело в длине записи и в обратном переводе (потому что если перевели в десятичные, то надо и вернуть в двоичные?)
Разные системы конверсии тут имеют разные правила. Например, repr() в Python сейчас действует по принципу: показывает форму с минимальной длиной из тех, что конвертируются в данное число во внутреннем (двоичном) представлении при стандартном правиле округления. Поэтому, например, если вы ввели 0.1, оно подберёт на выходе текст "0.1", а если вы его умножили на 3, оно будет на одну йоту отличаться от того, что ближайшее к 0.3, и поэтому будет выведено как "0.30000000000000004". Всё из-за задачи предельно честного вывода. А вот какой-нибудь "{:g}".format(0.1*3) выведет 0.3, потому что у него умолчательное усечение до 6 значащих цифр.
А если бы не было бы такого усечения — то всё вы выводилось максимально длинно:
>>> '%.55g' % 0.1
'0.1000000000000000055511151231257827021181583404541015625'
>>> '%.55g' % 0.3
'0.299999999999999988897769753748434595763683319091796875'
>>> '%.55g' % (0.1*3)
'0.3000000000000000444089209850062616169452667236328125'ну и кому такие подробности нужны?
По отношению к этим конверсиям известны следующие цифры:
- Сколько максимум десятичных цифр (на всех значениях порядка) могут быть сохранены при переводе в двоичную форму и обратно. Оно в C++. Для float32 и float64 (double) соответственно 6 и 15.
- Сколько максимум десятичных цифр требуется для перевода любого числа из двоичного внутреннего представления в десятичное и обратно, чтобы получить то же число. Оно в C++. Для float32 и float64 (double) соответственно 9 и 17.
И поэтому умолчательное (почти везде) форматирование в 6 значащих цифр это как-то смешно.
Я вам больше скажу, почти все компиляторы не умеют переводить десятичное число в двоичное правильно. Кроме GCC последних версий. Все остальные, что были доступны, были успешно нами завалены. Когда число очень близко к границе округления, компилятору не хватает внутренней точности чтобы округлить правильно. Например, вот это число:
float x = 1.26765082690182057923967346278399
99999999999999999999999999999999999999999999
99999999999999999999999999999999999999999999
99999999999999999999999999999999999999999999
9999999999999999999e30f;Правильный ответ 0x71800001. Компиляторы Visual C++ и Intel C++ (любых версий) выдают на один бит больше. Таких примеров у нас сотни.
Кроме GCC последних версий.
Clang в диапазоне от 3.8 до 10.0 включительно — тоже выдал с 01 в конце. Стандартная сборка Ubuntu, если это важно.
Виндовых компиляторов у меня нет, а вот numpy.float32 выдал с 02. Голый Python — тоже, но у него нет float32, поэтому работает промежуточный double. Проверил на GCC/Clang — если явно константу задать в double и потом из неё уже делать float, то получается в конце 02. Может, у остальных проблема из-за той же промежуточной конверсии?
За пример спасибо, сложил в копилку.
Я не знаю как работают компиляторы, исходников у меня нет, но знаю о том, почему так получается. Дело в том, что есть так называемые пограничные случаи, когда десятичное число очень-очень близко к середине между двух точно-представимых. Так близко, что разница проявляется только в каком-нибудь тысячном бите после запятой. Каким бы ни был алгоритм конвертирования, если он работает с фиксированным числом битов, он будет завален каким-нибудь таким тестом. Поэтому делаются эти тесты очень просто. Берём число, лежащее точно посередине. Прибавляем к нему (или вычитаем из него), например, 2 в степени минус тысяча (десять тысяч, миллион) — и всё, тест готов. Промежуточные округления тут роли не играют, причина ошибки — недостаток битов в процессе вычисления, алгоритм не может охватить все тысячу битов, чтобы увидеть направление округления. Нужна длинная арифметика.
По поводу Clang, там я точно уже не помню, но он на long double у меня легко заваливался, сейчас уже не скажу, какие тесты были.
Я не знаю как работают компиляторы, исходников у меня нет
GCC, Clang — они есть. MPFR, MPC — тоже. Код math.h в какой-нибудь glibc — тоже. Не знаю, может, у вас какие-то навязанные снаружи ограничения с использованием только MSVC хозяйства, но сейчас это становится тупо непрактичным: наука давно уже упорно переползает на open source именно потому, что оно открыто, проверяемо и в конце концов лучше развиваемо.
Дело в том, что есть так называемые пограничные случаи, когда десятичное число очень-очень близко к середине между двух точно-представимых. Так близко, что разница проявляется только в каком-нибудь тысячном бите после запятой.
Да, и ваша предыдущая статья была об этом. Это я помню (и замечал там, что в вопросе про ULP вы абсолютизируете влияние этой самой проблемы, там, где во многих местах вероятнее предположить просто более ранние версии, или намеренную жертву точности в пользу скорости работы). Но именно код рассматриваемых компиляторов, когда компилирует программу, использует неограниченную точность (GCC явно требует для своей сборки комплект из GMP, MPFR и MPC). Поэтому вот это
если он работает с фиксированным числом битов
там, скорее всего, не выполняется (не поручусь за совсем тонкие случаи, но у них цель и метод именно такие — компиляция делается с произвольной точностью).
По поводу Clang, там я точно уже не помню, но он на long double у меня легко заваливался, сейчас уже не скажу, какие тесты были.
Ну, может, старая версия, а, может, проблема прикрученности этого самого x87 long double ржавой проволокой сбоку (и то наверняка давно исправили). И опять же вопрос в платформе. Это на Unix обычно long double честный, а на Windows/64 он алиас для просто double.
Я имел в виду нету исходников Intel С++ И MS C++.
В остальном вы правы, да я абсолютизирую, потому что критически отношусь к своему труду и от других того же требую, может и напрасно это, но такой уж я человек. Поэтому хотя конвертирование десятичного числа в плавающее хоть и разрешено с этой ошибкой в последнем бите делать, я всё-таки от своих требую строгой точности. Причины может быть личные, может быть в психике моей, но так уже вышло :)
Наука на Open Source не совсем вся переползает. Например, многие используют Maple (закрытый) для своей работы и некоторые его функции настолько сильнее чем у других (бесплатных) систем компьютерной алгебры реализованы, что тем до Maple ещё как до Луны. И я не верю, что это можно сделать (перейти на OpenSource), пока в нашем обществе деньги в принципе как явление существуют. Но это уже философский вопрос. Сам я против Open Source, но ни коим образом других людей не осуждаю за то, что деньги зарабатывают, на бесплатном софте сидя. Право каждого, не моё дело.
Да, Кланг у нас старой версии, не спорю. Но не только в этом конвертировании проблема. Абсолютно все компиляторы, которые нам доступны, содержат сотни (это не преувеличение) других ошибок, гораздо более серьёзных, но разглашать их мне пока запрещено.
Указанная в статье проблема, связанная с тем, что при сложении чисел с плавающей запятой возникает погрешность, характерна для любых целых систем счисления. В книге [1], на которую я ссылаюсь, теоремы доказываются именно для произвольной системы.
Пример на то и пример, чтобы проиллюстрировать проблему, но не описать всё её многообразие проявлений. Более того, я пояснил, что статья для тех кто в теме, кому не нужно пояснять что такое 0.1+0.2 и почему это не равно 0.3. В этом примере причина ошибки НЕ В ТОМ, что числа на грани, а в том, что в результате сложения происходит округление суммы. Разложите, пожалуйста, эти числа на двоичное представление, сложите руками на бумаге и увидите, почему происходит округление. В учебном курсе [5] даётся подробное разъяснение именно этого примера в каком-то уроке, не хотелось бы здесь делать учебную комнату, уж прошу меня простить :)
Я имею в виду, возьмите соответствующие ТОЧНЫЕ значения (которые умещаются в double без округления), указанные в статье:
0,1000000000000000055511151231257827021181583404541015625 +
0,2000000000000000111022302462515654042363166809082031250 =
0,3000000000000000166533453693773481063544750213623046875.Разложите в двоичный вид и увидите, почему будет округление. Именно ЭТО округление и есть причина описываемой в статье ситуации. Если бы его не было, то условие if (0.1+0.2==0.3) срабатывало бы всегда, даже если эти числа сами по себе точно не могут быть представлены в двоичной арифметике.
Слишком много лирических отступлений, и шуток и повторяющихся объяснений. В итоге статья обрывается на середине, так с не объяснив, к чему это все было.
Я рассчитывал по крайней мере узнать как складывать массивы чисел не теряя точность. В итоге узнал только как представить сумму одних чисел суммой других чисел. :/
Ну, как бы есть алгоритм Кэхэна (см, википедию, там объяснение простое), но он не гарантирует абсолютную точность сложения.
Интересно, будет ли в рамках второй части статьи обобщение алгоритма Кэхэна с хранением массива float (минимальной необходимой длины), а не пары?
Благодарю за отзыв. Однако я прошу принять во внимание два обстоятельства. Во-первых, статья в своём названии уже говорит, что складывать мы будем два числа, во-вторых, про сумму чисел из массива сказано, что это будет в другой статье, там я расскажу, как можно уменьшить погрешность (но не убрать её совсем). Мне трудно представить, как читатель может после этого ожидать, что я расскажу об этом именно здесь. Вы говорите о том, что я много повторяюсь, но вы сейчас показали, что всё-таки я повторяюсь мало. Нужно больше.
Забегая вперёд скажу, что посчитать сумму чисел из массива произвольной длины без потери точности можно только одним способом — с помощью арифметики с бесконечной точностью.
Нет, не так, потому что в вашем примере вы искусственно ограничили условия, о которых в произвольном случае заранее ничего неизвестно. Если есть точные данные относительно слагаемых, то да, можно придумать точные ограничения для промежуточной суммы. А ещё лучше (иногда) будет воспользоваться рациональными числами.
Не очень-то полезный трюк, согласитесь. Самый простой способ представить сумму двух 32-битных чисел в виде двух 32-битных чисел, это не делать ничего вообще.
При том, я не сомневаюсь что в представленных в статье манипулациях есть практический смысл. Но читателю этот смысл не доносится, и от этого остается неприятное послевкусие от статьи (а зачем все это нужно было вы узнаете в следующей статье!).
Повторятся нужно меньше. Читатель в праве быть не внимательным, и моя претензия была не к не выполненным обещаниям. Просто к концу чтения статьи хочется прийти хоть к какому-нибудь практическому применению (суммирование множества чисел – лишь очевидный пример). А тут случился классический клиффхэнгер.
оказались… два числа той же размерности.
Я так понимаю, что нет. Если складывать два числа разных порядков, то в результате мы получим два числа: одно близкое к наибольшему порядку, а другое – может быть сильно меньше порядков обоих чисел.
Но да, в статье не указывается, что делать дальше с полученной погрешностью.
С другой стороны, это может быть и к лучшему: иметь цикл статей, у которых можно прочитать только первую и понять "ага, такой алгоритм есть, он существует, но я им почти никогда не воспользуюсь. Но буду знать". А те, кому интересно изучить дальнейшее использование, могут читать следующие статьи, пока не узнают всё или не остановятся на том уровне детализации, которого им будет достаточно.
Кстати, на курсере похожим образом иногда публикуются лекции: отрезками по 15-30 минут, затрагивая только одну подтему темы.
Я так понимаю, что нет.Как нет, если да? Сумма битов результата равна сумме битов аргументов. Это просто представление a + b в виде некоторого c + d той же разрядности. Такую операцию трудно назвать «суммированием».
Если бы операндов было больше двух – тогда такой трюк сам по себе был бы полезным. А так я могу разве что посмотреть на сдачу чтобы узнать сколько я потерял.
Опять же повторюсь, я не сомневаюсь что у приведенной техники есть практическая польза. Но в статье она не показана. Так что ждем следующей статьи.
Опять же повторюсь, я не сомневаюсь что у приведенной техники есть практическая польза. Но в статье она не показана. Так что ждем следующей статьи.
Ну вот я не знаю, насколько от данного примера легко перейти к практической значимости, но я показывал, как Kahan summation спасает длинную сумму от больших ошибок промежуточного округления.
В FMM (уже старовато, но классика; русское издание легко находится в цифре) были примеры катастрофических потерь точности на таком округлении.
Так что польза есть. Большинству, да, не приходится сталкиваться с её применением.
Ну вот кто не ждёт, а действует, тот уже проверил, где это работать может.
А так я могу разве что посмотреть на сдачу чтобы узнать сколько я потерял.
Я бы сказал, что в этом весь смысл метода из статьи и есть, иметь возможность посмотреть, какая была погрешность, и какой процент от "маленького числа" был потерян, например.
Сумма битов результата равна сумме битов аргументов
Полагаю, только для чисел в целочисленном представлении. Для float, емнип, суммирование идёт сложнее: fpu расширяет операнды до большей разрядной сетки (скажем, с 32 бит до 40, увеличивая только мантиссу), и складывает обе мантиссы, выровненные по запятой.
И вот на моменте выравнивания и обратного обрезания до 23 бит происходит потеря точности. Впрочем, я полагаю, это и так всем понятно/известно. :)
Это просто представление a + b в виде некоторого c + d той же разрядности
В лучшем случае разрядность не меняется, да. Как в примере в начале статьи 0.1 + 0.2 == 0.3 ± 2.7e-17. Порядок погрешности в 17 раз меньше порядка операндов.
А в случае сложения сильно разных по порядку чисел, вроде (2^53 - 1) + 2 == (2^53 + 1) ± 1, порядок погрешности сравним с порядком другого операнда, и вот тут бы хотелось увеличить разрядность, чтобы результат влез в сетку.
Новое число d в этом случае увеличивает общую разрядность суммы два (или меньше?) раза. Да, при сложении двух float можно просто записать результат в double и не мучаться. Но при сложении двух double – в float128? А при сложении двух float128 – в float256? Полагаю, так оно и есть, просто мы вместо введения нового типа данных с удвоенной разрядной сеткой вводим вторую переменную, в которую складируем переполнение разрядной сетки.
Но это уже близко к вопросу о практической пользы, надо ждать следующей статьи, да.
Такую операцию трудно назвать «суммированием».
Если считать суммирование операцией, принимающей два аргумента, и возвращающей, кхм, сумму этих аргументов, то да, здесь возвращается два результата.
С другой стороны, у классического fadd тоже проблема с суммированием: он возвращает не сумму, а число, близкое к сумме. :D
У метода из статьи с этой точки зрения больше прав на звание "суммирования", ибо точность результата сильно выше. А два возвращаемых результата – суть одно число, просто записанное в несколько непривычном виде.
К слову, если я правильно помню, в каком-то x86-ассемблере деление двух целых чисел записывало в два регистра два результата: частное и остаток. Остаток получался побочно, но, поскольку он тоже часто используется, его решили не выбрасывать, а складировать в один из регистров.
Так что, полагаю, технику из статьи можно обозвать «суммированием с побочным эффектом в виде значения погрешности».
Самый простой способ представить сумму двух 32-битных чисел в виде двух 32-битных чисел, это не делать ничего вообще.
Выходит, что так. Не ошибается тот, кто ничего не делает. Вот два числа, лежат в памяти рядом, никакой погрешности! :D
Аплодирую! Вы почти правильно поняли то, что я хотел сказать по этой дискуссии. Кроме последнего абзаца. Выбрать способ представления двух 32-х битных чисел в виде суммы двух 32-х битных чисел лучше так, чтобы результат сложения удовлетворял условиям задачи, ради которой эта сумма ищется. В одной задаче лучше и правда ничего не делать, в другой может оказаться, что это и не лучше вовсе. Всё зависит от задачи, а не от желаний программиста.
Например, когда мы реализуем сложение в длинной арифметике, то в одном из чисел хранится сумма, а в другом — перенос в старший разряд.
В каком смысле точный, если даже исходные числа 0,1 и 0,2 не имеют точного представления в формате IEEE-754?
IEEE754-2008 устанавливает и десятичные форматы и методы работы с ними. Считаю важным уточнить, что в статье речь только о двоичных форматах — иначе может создаться ошибочное представление о стандарте в целом.
Благодарю за замечание, но когда в черновике я так сделал, то увидел, что получается слишком много лишних уточнений. Мне кажется, что по контексту всё должно быть понятно. Особенно если учесть, что я в некоторых местах оставил это уточнение:
Начнём с того, что чисел 0,1 и 0,2 в двоичной арифметике с плавающей запятой...
У вас в начальной формулировке проблемы ни слова про двоичный формат нет.
Так что само собой на статью напрашивается ответ "вместо binary64 возьмите decimal64 и терпите издержки, если вам нужны точные десятичные вычисления".
Ну хорошо, раз вы так настаиваете, я добавил ещё слово двоичных в двух местах. Но а вообще в десятичном формате будут те же самые проблемы потери точности при сложении. Да, вы сможете сложить одну десятую и две десятых, но можно придумать много примеров, для которых возникнет та же самая ошибка округления, что здесь обсуждается. В книге, на которую я ссылаюсь, данная проблема описана для любой целочисленной системы счисления.
Но а вообще в десятичном формате будут те же самые проблемы потери точности при сложении.
Откуда? Первопричина проблемы в том, что над числами, заданными в одной системе счисления выполняются операции в другой системе счисления с внесением ошибки за счет конверсии на входе и выходе. Если весь процесс вычисления делается в той системе счисления, в которой заданы начальные числа, то описанный класс ошибок полностью исчезает.
Оттуда, что при сложении чисел с плавающей запятой в любой системе счисления вы вынуждены смещать одно число относительно другого, когда их экспоненты разные. Результирующая сумма будет занимать больше места, чем позволяет вместить переменная. Значит часть битов будет отброшена. В книге [1] эти вещи, что я описываю в статье, обсуждаются для произвольной абстрактной системы с плавающей запятой, то есть там произвольная система счисления и произвольная, но фиксированная длина мантиссы.
Если весь процесс вычисления делается в той системе счисления, в которой заданы начальные числа, то описанный класс ошибок полностью исчезает.
Нет, конечно. Вот у вас IEEE754 decimal32 с 7 значащими десятичными цифрами. Вот вы складываете 9999999 и 4. Результат 10000003 не лезет в 7 цифр и округляется до 10000000. Опаньки!
И вот тут тот самый описанный автором Kahan summation (или его близкий родственник) помогает: вы подсчитали 10000000-9999999, получили 1, вычли его из 4 (второе слагаемое), получили 3 — вот это та самая ошибка округления, которую можно при желании накапливать и которая позволяет вторым таким компонентом фактически удвоить точность расчётов.
Кстати, вы не всё исправили.
Вот тут фактическая ошибка:
К сожалению, это данность, от неё никуда не уйти, если хранить числа в типе данных double (или любом другом типе фиксированного размера из Стандарта IEEE-754).
decimal64 — тип фиксированного размера из Стандарта IEEE-754, но у него озвученной проблемы нет.
Как только используешь SIMD вычисления, сразу результат отличается от результата не SIMD алгоритма.
Вы в 32-битной Windows или Unix пишете? Там по умолчанию плавучка на FPU, а у него может стоять режим, в котором мантисса 64 бита. Но при любом режиме порядок не усекается до конверсии в целевой формат.
Там даже вот такие варианты бывают (казалось бы, пусть 0.1+0.2 считается неточно — но должно считаться всегда одинаково? ан нет, момент конверсии влияет).
Уточните режим компиляции не-SIMD варианта, проверьте через MPFR (дорого, поэтому на мелком примере) — тут много есть о чём подумать...
Это математическая статья, описываемые явления будут во всех без исключения форматах с плавающей запятой фиксированного размера не зависимо от компилятора, и если формат допускает денормализованные числа. Смысл статьи не в том, чтобы бороться с врождённой проблемой формата и как-то складывать десятичные дроби, а в том, чтобы находить сумму двух чисел без потери точности в уже заданной математической абстракции под названием двоичная арифметика с плавающей запятой. Просто я привязал её к формату IEEE-754, так как он описывает как раз такие числа и всем известен.
Это математическая статья, описываемые явления будут во всех без исключения форматах с плавающей запятой фиксированного размера не зависимо от компилятора,
Против этого никто не возражал. Но byman@ задал вопрос "почему у него с SIMD результаты другие, чем без SIMD", вот я и подсказал, куда копать.
и если формат допускает денормализованные числа
А вот при чём тут денормализованность — я уже не понял. Когда её не было (с до-IEEE форматами и правилами вычислений) — были те же эффекты, и тот же метод мог применяться с адекватным успехом.
А, прошу прощения, я не сообразил, что вы именно ему отвечаете :) Опять запутался.
Денормализованность используется в математическом доказательстве этих алгоритмов, что я в статье описал. Да, эффекты потери точности есть и без денормализованных чисел, а вот алгоритм сложения без потери точности работает только когда таковые числа присутствуют.
Это не будет работать по нескольким причинам. Во-первых, long double уже де-факто отменили (в потоковых обработках), во-вторых, он даёт только 11 дополнительных битов мантиссы, а чтобы сохранить погрешность нужно 52 (для double), в-третьих, возникает ошибка двойного округления… короче, ещё 10 причин я просто не хочу писать, вы уж простите. Мне кажется, вы не вполне поняли проблему.
А в реальности, первые калькуляторы считали в десятичной системе, результаты проверяли на бумажке (как умели) — и они совпадали.
Сейчас все повально обленились, и даже приложения «калькулятор» для пк использует двойную точность — отчего результат не всегда совпадает с бумажкой.
Интересно, что никто не упомянул, что float всегда представляют собой рациональные числа, знаменатель которых равен степени двойки.
Статья хороша и познавательна в плане математики (и, конечно, очень жду продолжения). Но в ней не хватает простого практического совета: если хочешь точности (а также скорости и компактности), никогда не пользуйся переменными с плавающей запятой. 0.1 == 1/10. Все эти float, double и иже с ними созданы для того, чтобы облегчить жизнь программиста, когда не требуется идеальная точность вычислений.
Благодарю за отзыв. Но вот в каком непростом положении я нахожусь. Дело в том, что у каждого читателя своя математическая культура, и подстроиться под каждого невозможно. Например, в моём научном коллективе и без слов понятно, когда какой тип данных применять (рациональные числа, с плавающей запятой, с конечной или бесконечной точностью, позиты Джона Густафсона, интервальную арифметику, числа половинной точности или увосьмерённой). У нас все и так знают, что к чему и почему. У других людей может не быть этих знаний, но есть другие знания. Как я могу угадать, какие у них знания? Напишу про точность, мне ответят, что я мог бы этого не писать. Если не напишу, ответят, что надо было написать. Если напишу категорично (никогда не пользуйся), ответят, что иногда можно и даже нужно, если не напишу, то скажут, что надо было написать. Поэтому я написал только по делу. Кто в теме, тому статья полезна будет, кто не в теме, тем я порекомендовал для начала ресурсы [3-5].
Артем, повторюсь, статья отличная и жду продолжения. Я не математик и даже не программист, для меня подобные вещи — эдакая магия, очень крутая, люблю такое.
Мой комментарий был вот о чем: лично у меня (хобби-программиста) ушел примерно год на осознание простого факта, что double можно использовать только в исключительных случаях, и выработку понимания, как с этим жить. Все-таки в мире цифровых систем (в отличие от аналоговых) в принципе не существует такого явления, как дробные числа. Есть только нули и единицы. И математика вынуждена подстраиваться под эту несовершенную ситуацию, для чего придумываются всевозможные обертки двоичных чисел, позволяющие им с разной степенью точности (аппроксимации) прикидываться тем, чем они не являются.
Но с практической точки зрения (а Хабр читают практики) важно помнить, что это именно обертки, под которыми скрываются банальные и совершенно неделимые нули и единицы. И правильный (ИМХО) подход — оперировать нулями и единицами как они есть. Это я к тому, что в статье упоминается именно тип double, а не вообще дробные числа.
Ну, как-то так. Я ни в коем случае не критикую статью, повторюсь, она очень хороша и познавательна.
Ну так а я и не оправдываюсь, а благодарю вас за отзыв. Я лишь пояснил, что не посчитал нужным как-то отходить от основной темы. Да, я тоже практик, мне писать просто о теории откровенно скучно, но ведь приходится, потому что без неё не получится дальше описать практику.
Я взял тип данных double просто для единообразия описания, если вы откроете книгу [1], то увидите, что там знания даются с позиции вообще полностью абстрактной системы с произвольным основанием (не только двоичным или десятичным) и произвольной, но фиксированной точностью. Там есть вырвиглазные теоремы и я хочу их как-то обойти. Вот для этого взял и свёл всё к double, понятно, что для float то же самое будет, только битов меньше.
А что касается причин появления разных обёрток, то она намного сложнее, чем вы сейчас пишите. Но я бы не стал дискутировать об этом в комментариях, с вашего позволения :) Это очень длинная тема, и мы уйдём в философию, утомив других читателей.
Есть только нули и единицы, других чисел в принципе нет (замнём про троичные, десятичные и прочие ичные компьютеры для ясности). А есть различные интерпретации этих последовательностей. float и integer просто разные интерпретации, уместные в разных случаях. Есть и другие интерпретации, включая строки. Вон JS обходится (почти) без integer. JS — исключительный случай? Нет, самый популярный язык по некоторым метрикам.
Нужно знать области применимости, плюсы, цену плюсов, минусы и способы обхода минусов и выбирать подходящий. Нет лучшего формата, нет универсального, нет формата для исключительных случаев. Есть более подходящие для задачи, есть менее
позиты Джона Густафсона, интервальную арифметикуРасскажите про свой опыт использования позитов и интервальной арифметики. Если у вас есть примеры из практики – вообще отлично будет.
Примеры не дам, исследования нашего научного центра не подлежат разглашению. Могу только сказать одно — они не работают правильно в задачах, связанных с исчислением бесконечно малых. Мы завалили их на простых тестах, где нужно было: интегрировать, решать дифференциальное уравнение численно, применять другие численные методы, где нужно было работать с бесконечно-малыми (имеется в виду, конечно, просто с очень маленькими числами). Алгоритмы, которые хорошо сходятся для чисел формата IEEE-754 на позитах не сходились и уходили в бесконечность, либо плясали в широком диапазоне около ожидаемого ответа.
Интервальная арифметика часто выдает очень правильный, но бесполезный ответ, например, что число будет в интервале от 0 до бесконечности. Далее, возникают интересные ситуации, когда интервал [A, B] нужно поделить на интервал [A, B] (ответ, естественно, не единица), особенно когда A и B имеют разные знаки. Больше сказать ничего не могу, увы.
Мы завалили их на простых тестахВы использовали только posit или quire аккумуляторы? Мне кажется, уходить в «бесконечно-малые» и «бесконечно-большие» на posit просто нельзя – они имеют крайне низкую точность на очень больших и очень маленьких экспонентах. Универсальное правило – все значения, которые представляются в posit должны быть нормализованы (иметь экспоненциальный порядок близкий к 0). А вот промежуточные значения должны хранится в quire регистрах с весьма высокой точностью.
бесполезный ответ, например, что число будет в интервале от 0 до бесконечностиМне кажется, что это полезный ответ, в том смысле, что если бы те же вычисления делались с применением обычной арифметики аналогичной разрядности, то погрешность результата была бы «бесконечной». Или вы говорили конкретно о Густафсоновской арифметике?
Нет, quire аккумуляторы там не работают, ошибка была ведь не в том, что мы в результате каких-то накоплений потеряли точность, а именно в результате ошибок в единичных операциях с очень маленькими числами. Плотность маленьких чисел у позитов настолько низка по сравнению с плотностью денормализованных чисел в IEEE-754, что это и неудивительно. А если прямо совсем всё делать в quire, то тогда смысла нет было создавать операции сложения и вычитания для обычных позитов. Но они ведь зачем-то есть, и они работают плохо в задачах математического анализа. В этом проблема. Не знаю как для других исследователей, для нас это однозначный приговор позитам. По крайней мере, на сегодня точно. Если нужна хорошая точность, мы возьмём float128, например.
Мне кажется, уходить в «бесконечно-малые» и «бесконечно-большие» на posit просто нельзя
Да, нельзя. В этом и проблема. И инструмент quire задачу решает не лучше, чем если вместо double я возьму float128, например, или, если будет нужно, более крупный тип данных.
Мне кажется, что это полезный ответ, в том смысле, что если бы те же вычисления делались с применением обычной арифметики аналогичной разрядности, то погрешность результата была бы «бесконечной».
Нет, как раз в случае с обычной арифметикой там было бы вполне обычное число, близкое к правильному ответу.
Примеры не дамУ меня есть пример — самые обычные банальные вычисления. Я также отдельно рассмотрел поситы просто как формат хранения — и по прежнему они не показали заявленных возможностей, помимо случая данных одного порядка. Но в случае с числами одного порядка нам и плавающая точка не нужна — обычный int справляется лучше. Ну а для сжатия данных есть алгоритмы сжатия данных, в том числе и без потери точности, и изобретать для этого новые форматы чисел вовсе не обязательно.
Например, в моём научном коллективе и без слов понятно, когда какой тип данных применять (<...>, позиты Джона Густафсона, <...>)
А где реально позиты на практике используют?
если хочешь точности (а также скорости и компактности), никогда не пользуйся переменными с плавающей запятой. 0.1 == 1/10.
Правильно говорить — если нужна абсолютная точность (которая отличается от относительной).
Какой практический вывод должен следовать из статьи?
Я к примеру инженер. пишу какой-то код, также работаю с массивами и с десятичными дробными данными, циклами на сотни тысяч итераций. Думать мне об этих погрешностях или нет? Если они такие маленькие, то практического смысла от них в реальной жизни мало — погрешности при переходе от виртуального расчета в физический мир реальных объектов съедят эти несостыковки.
Может быть для долговременных систем (типа космических аппаратов летящих 30 лет со второй космической) или для процессора это играет роль?
Поэтому практической значимости не увидел, а если это академический интерес — то против ничего не имею.
В вашем случае думать об этом не надо. Я упомянул в статье, что это касается только тех, кто пишет библиотеки для языков программирования, то есть не при помощи языков программирования, а именно на стадии создании самого языка. Там в этой сфере много всяких таких алгоритмов, и они реально там нужны. По этим темам в книгах выделяют целые главы, поэтому практический смысл есть. Но если вы его не видите, значит именно вам он не нужен. Но вы можете не подозревать, что ваш любимый язык программирования работает правильно только потому, что где-то когда-то люди изобрели подобные алгоритмы, о работе которых вы никогда не узнаете, но работа которых миллионы раз выполняется когда вы нажимаете кнопку Build.
В следующей статье я собирался показать как разные способы суммирования чисел из массива могут давать погрешности, отличающиеся на несколько порядков. Эти способы, в частности, работают с применением знаний из этой статьи. Если торопитесь изучить эту сферу, то в книге [1] всё есть, я лишь немного от неё отступлю в следующей статье, а по сути расскажу то же самое.
console.log(0.01 + 0.02);
console.log(0.1 + 0.2);
получаем:
0.03
0.30000000000000004
вы можете не подозревать, что ваш любимый язык программирования работает правильно
Возникает закономерный вопрос: а как проверить, что мой язык программирования работает в указанном вами случае (или в каком-то другом)?
Я вот полагаю, возможно ошибочно, что из примера a+b=s+t в большинстве языков программирования при попытке вывода s я получу именно s, а не s+t
Тем более, если у вас вычисления на сотни тысяч операций, очень легко внезапно получить погрешность одного порядка с результатом.
Потом вопрос не в сантиметрах и метрах, в относительных размерах и числах подобия типа Рейнольдса. Какой смысл брать реальную сборку и считать сантиметры, если к примеру мы не моделируем погран слой, а смотрим общее нагружение и интергральную картину? Не вижу тут нерешаемых проблем.
А если это погран слой, который нужно аккуратно моделировать с учетом всяких выступов, то всякое моделирование все равно будет не точным, так как реальный объект и виртуальная модель далеко не одно и тоже.
Про сантиметры, метры и относительные размеры принципиально согласен, но все известные мне геометрические ядра работают с фиксированной минимальной абсолютной точностью (ну вернее как, есть ядра, которые внутри как черный ящик и не говорят про свою точность вообще ничего, поэтому за всех говорить не буду). На этапе мешера возможно это уже меньшую роль играет, утверждать не могу.
P.S. Основная мысль была в том, когда речь начинает идти о вычислениях с сотнями тысяч шагов, зависящими от результатов друг друга, определенно о погрешностях флотовых вычислений стоит задумываться и хотя бы пытаться прикинуть их порядок. Особенно, когда алгоритмы принимают дискретные решения на базе этих вычислений (как те же булеаны)
Также, если брать пример CFD, например в ансис Spaceclaim есть всякие фишки для ремонта «плохой» геометрии. Правда результат лишь гарантирует, что тело будет и поверхности не пересекаются, про точность тут уже трудно что-то сказать.
Залепухи и прочий ремонт плохой геометрии очень хорошо работает, если хорошо понятно, где его лепить. Иногда ошибки проявляются слишком далеко от места, которое их вызвало, и автоматика не справляется. Особенно много проблем получается, если рядом с плохим куском находится какая-то мелкая деталь, тогда «плохая» топология может сожрать всю мелкоту рядом. Иногда такой результат устраивает, иногда нет.
Никогда не видели, что в каких-то системах (калькуляторах кредитов и налогов, расчёт скидок в корзинах, вообще где проценты есть) числа, как говорится, не бьются? Частое явление, на самом деле. Потому что авторы кода не учли наличие погрешностей подобных и не использовали или не знали подобных алглритмов. Хорошо если просто округляли на каждой операции
В тех случаях, когда я сравнивал, получался гораздо более близкий результат, если считать месячный процент = (годовой процент) / 12.
По-моему, банкиры тут явно лукавят, чтобы показывать меньший годовой процент, чем он есть на самом деле. (Разница невелика при небольших процентах, но выливается в заметные рубли в платежах.)
Из такого месячного вычисляем реальный (сложный) годовой, из реального годового (сложный) подневный. И уже далее считаем: у меня получались очень близкие цифры к банковским и я на этом остановился.
По-хорошему нужно ещё округлять (мы не можем заплатить иррациональное число рублей) и учитывать накопившиеся проценты для конкретных дат платежа (ближайший рабочий день). Уменьшать суму аннуитентного платежа на накопившиеся проценты, результат вычитать из остатка долга. И по кругу.
Ну а вычисление аннуитентного может потребовать апроксимации его на начальном этапе, вычисления платежей, вычисления поправки по разнице последнего платежа и аннуитентного с уточнением аннуитентного и новым расчётом. (Может и несколько раз.)
P.S. Смею предположить, что либо более точная методика закреплена в каких-либо подзаконных актах, либо можно запросить точный метод расчёта у банка. Знающие люди пусть подскажут.
По-моему, банкиры тут явно лукавят, чтобы показывать меньший годовой процент
всё определено законом же
http://www.consultant.ru/document/cons_doc_LAW_155986/e52bee2d092465172cd750d5a23927f45bb3d017/
Спасибо за ссылку, добавил в закладки на будущее.
По-моему, банкиры тут явно лукавят, чтобы показывать меньший годовой процент, чем он есть на самом деле.
Согласно вашей ссылке:
ПСК = i x ЧБП x 100
Ну вот только ПСК — это не годовая ставка, как нам преподносят в рекламе, годовая ставка (в процентах) будет ((1 + i)^ЧБХ — 1) × 100. Простой пример, ЧБХ = 12, 1% в месяц, то есть i = 0.01:
- ПСК = 0.01 × 12 × 100 = 12 — нам объявляют 12% годовых, но реально же
- ((1 + 0.01) ^ 12 — 1) × 100 ≈ 12.6825%.
ПСК — это то, что в сумме мы отдадим за год (в процентах), но это не годовая процентная ставка, годовая равна ПСК при ЧБХ = 1 (или i = 0). Так что лукавят.
Впрочем, на практике ПСК, скорее, полезнее: при расчёте годового бюджета нам нужен ПСК, а не годовая ставка.
А работать с ними по принципам похожим на BCD числа (операция и далее коррекция результата)?
задается только в тексте программы.
BCD_Float A,B; // И больше ничего ненужно
По-моему, вы изобрели «double-double arithmetic»: хранение результата сложения в виде пары вещественных чисел (s, t) по факту удваивает количество бит мантиссы результата, то есть от чисел двойной точности мы переходим к числам четырёхкратной точности.
Из-за этого заголовок статьи вызывает у меня некоторое недоумение: «Сложение двух чисел с плавающей запятой без потери точности» невозможно, если и аргументы, и результат имеют одинаковое количество бит для хранения мантиссы. Лучшее, чего можно добиться в этом случае, — корректного округления результата к ближайшему представимому числу, ровно этого стандарт IEEE 754 и требует от реализаций основных арифметических операций.
А ещё мне не понятно, как именно автор собирался сделать равенство из печально известного неравенства 0.2 + 0.1 != 0.3.
Если слагаемых много, то, как я понимаю, нужна только одна переменная для накопления потерянной точности. И добавление её к итоговой сумме может дать меньшую ошибку в итоге чем лишь округление на каждом шагу.
По сравнению, наверное, будет 0.2 + 0.1 — 0.3 = 0
По-моему, вы изобрели «double-double arithmetic»:
Описывает, да.
«Сложение двух чисел с плавающей запятой без потери точности» невозможно, если и аргументы, и результат имеют одинаковое количество бит для хранения мантиссы.
Если учесть, что представления чисел уже округлены до подходящего значения на разрядной сетке float или double — то формально всё честно.
А ещё мне не понятно, как именно автор собирался сделать равенство из печально известного неравенства 0.2 + 0.1 != 0.3.
Равенство и не делается, но ошибка накапливается отдельно.
Берем две целочисленных переменных того же размера что и даблы и получаем fixed point без обозначенных проблем с огромной точностью.
Вы так можете работать только в том случае, если у вас все данные более-менее одного порядка и если результаты вычислений никогда не переполнят разрядную сетку.
И про «данные одного порядка» — у float ровно таже проблема. Вы либо храните большие числа с низкой точностью, либо маленькие с высокой.
16 битный fixed point никогда не проиграет 8 битному float по точности.
Это если вы твёрдо знаете, как именно он должен быть fixed (позиция точки), и если вам нужна именно абсолютная точность.
Да, полно контекстов, где это так и нужно (те же финансы). Но полно и таких, где это не проходит.
Вы либо храните большие числа с низкой точностью, либо маленькие с высокой.
Вы всё время циклитесь на абсолютной точности.
Когда мы меряем расстояние до какой-нибудь Тау Кита, нам плюс-минус миллион километров до лампочки. Зато в позиционировании транзистора в процессоре играют роль нанометры.
Десятичный результат получен с помощью правильного онлайн-конвертера, а дробь посчитана с помощью библиотеки MPIR и функции mpq_set_d, которая умеет переводить double к рациональной дроби.
ИМХО не хватает такой же дроби для результата (и, возможно, краткого пояснения почему получили не 0.3000000000000000166533453693773481063544750213623046875)
Это есть в нашем учебном курсе [5]. Я в начале статьи предупредил, что читатель должен быть в курсе этого примера, чтобы мне не пояснять вещи, не относящиеся к теме.
ну если бы я писал подобную статью, я бы сказал о представлении числа в виде двоичного с экпонентой, показал бы какая дробь после сложения получается, почему она не может быть точно представлена в видео одного числа ieee-754, по может быть точно представлена в виде «округлённая сумма и уточнение».
буквально несколько дополнительных предложений, зато будет понятно практически любому читателю хабра.
Благодарю за замечание, но я не могу с вами согласиться. Я писал именно эту статью не для практически любого читателя хабра, а для того, которому не нужно пояснять азы арифметики с плавающей запятой. Для тех, кому эти азы нужны, я предложил сначала ознакомиться с литературой [3-5]. Там всё это уже есть, зачем мне повторять, что 2+2=4? Мне в каждой из сотни статей, что я задумал по этой теме повторять эту простую истину и объяснять про мантиссу, экспоненту и всё прочее? Поверьте, парой предложений тут не обойтись. Скажешь А, сразу попросят сказать Б… и вот тут понеслось, создавая учебный курс по данной теме, пришлось делать аж 8 уроков, и то это лишь первая часть. И делал я их как раз для того, чтобы мне не пришлось повторять одно и то же.
А текстом нельзя? Просмотр видео — это неудобно медленный способ усвоения знаний.
Это именно видео-курс. Текстовых данных полно в интернете, или в книге [1]. В моём исполнении текстовый курс будет стоить в 10 раз дороже, чем видео. Но мне кажется, что вы здесь немного ошибаетесь. Вот смотрите сами: текста в интернете полно, а учить никто не хочет, ленятся читать. Вот это видео как раз для ленивых :) Потому что я нашёл способ очень простого и понятного объяснения темы, и в тексте оно как-то не будет смотреться. Но это моё мнение.
Для тех, кому эти азы нужны, я предложил сначала ознакомиться с литературой [3-5]
ну это не работает же. никто не пойдёт читать 100500 первоисточников чтобы понять статью.
или работает не так, как ожидается
Я снова повторюсь, что не считаю вас правым в этой ситуации, хотя и не возражаю против того, чтобы у вас было своё мнение. Я описываю тему, связанную с арифметикой с плавающей запятой, и считаю что читатель должен владеть основой, если его эта тема волнует. Если это не его тема, значит ему не нужно её читать. Вот представьте, вы оказались в вузе, скажем, на математическом факультете. Преподаватель математического анализа исходит из предположения, что вы знаете что такое 2+2=4. А вы встаёте и возражаете: никто не пойдёт читать 100500 источников, чтобы вас понять. Чья это проблема: ваша или преподавательская? Очевидно, что ваша. Вы могли бы с тем же успехом попросить меня разъяснить в двух словах что такое вообще сложение чисел, как возникает перенос, иначе читатели могут не понять. Потому что моя целевая аудитория — это люди, которые УЖЕ давно поняли, что если они имеют дело с числами с плавающей запятой, то они обязаны понимать их также, как понимают целые числа. Если они этого по какой-то причине не делают, значит дальше погружаться в тему им НЕ нужно.
Считайте, что я в начале статьи сделал #include "floating point feeling" и не должен повторять своими словами то, что описано в этой библиотеке. Ну а если такой библиотеки нет у читателя, то и пара слов об устройстве формата binary64 НИЧЕГО не даст, а только утомит тех, кто в теме.
Я думаю, что изложил свои аргументы и далее повторяться не буду, уж простите.
Ознакомился со статьёй, на которую вы дали ссылку. Да, мне знакома ситуация, в которой оказался её автор. И вот мой учебный видео-курс КАК РАЗ для этого случая отлично подходит. Всё с самого начала, с самых базовых представлений. Да, пара формул встречается, но даже до их появления у зрителя уже появляется нужный образ в голове, понимание того, как это устроено. 8 уроков не зря же делалось: плавное погружение. Как раз для тех, кому нужно с самого начала. Посмотрите первый и второй уроки чтобы убедиться, они на YouTube. Но давайте всё-таки не путать научно-популярное изложение материала и учебный курс. Это принципиально разные виды художественного творчества.
Остаток от сложения по основанию 2.
/Я тролль? Или нет?
Давно такого не было: только в одном докладе на highload fwdays упомянули мельком о проблеме и подобном способе её решения, подумал завтра погуглить на свежую голову, а пока Хабр почитать и тут же первая статья на эту тему. Спасибо! Хабр торт!
На современных процессорах x64 (Intel, AMD), кстати, есть инструкция FMA (fused multiply-add), которая ускоряет подобные алгоритмы. По скорости получается, конечно, медленнее, чем без compensated алгоритмов (с обычной точностью), но намного быстрее, чем с более длинными типами (длиннее double). Кстати, никогда не компилируйте программы с compensated алгоритмами с флагом -ffast-math – вам GCC «эквивалентными» преобразованиями всю точность убьёт =)
А то тут на хабре как-то приводили примеры разрушительного поведения компилятора, если он ловил программиста на неуверенности в том, что при сложении целых чисел не произойдёт переполнения (например, делал слишком очевидные для компилятора проверки суммы двух положительных чисел на отрицательность).
По поводу чисел с плавающей точкой IEEE 754 описывает, как должны производиться вычисления. Если компилятор реализует этот стандарт, то он не имеет права производить какие-либо оптимизации в принципе (например, перестановку операций для более оптимальной загрузки пайплайна), если не уверен, что результат не изменится. Для целых чисел, насколько мне известно, такого стандарта нет, поэтому компиляторы иногда и творят неочевидные вещи.
Как сказали уже, можно включить флаг fastmath, позволяющий делать "небезопасные" оптимизации. Ряд SIMD оптимизаций, например, попадают в эту категорию.
Нет, для сложения n чисел типа double есть другие алгоритмы (о них в другой статье будет), которые призваны не убрать полностью, но уменьшить погрешность вычислений (чтобы убрать полностью именно этим алгоритмом, то да, нужно, грубо говоря, ещё n чисел, и смысла в таком алгоритме уже нет). Если же нужно убрать её полностью для какой-то реальной задачи, то следует либо перейти к рациональным числам с произвольной точностью, либо к арифметике с плавающей запятой с произвольной точностью.
Например один импульс — 10 литров. Ну и складываю в 64 бита целого по +10.
А в СКАДе привожу к метрам кубическим преобразованием в Float и нормализацией 1/1000.
В старых системах Сименса почти все аналоговые передавались целым на СКАДу. 16 бит хватало, а иногда и 8 бит брали.
В новых используют двойные счетчики — большой и малый. Для оператора это один на экране.
Я писал про это на хабре тоже, картинок меньше было, но зато материала больше https://m.habr.com/ru/post/423469/
Сложение двух чисел с плавающей запятой без потери точности