• Наиболее точное скалярное произведение векторов типа double. Вычисление значения полинома
    +1
    Вы не пробовали точное скалярное произведение

    Поправлю: не точное, а наиболее точное, это разные вещи. Да и то, всегда можно подобрать тест, когда даже эти трюки спасать не будут.


    в методе сопряженных градиентов

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

  • Наиболее точное скалярное произведение векторов типа double. Вычисление значения полинома
    +1

    Стандартных реализаций нет, есть чьи-то реализации давно известных приёмов. И моя задача всего лишь в их популяризации. При этом long double к данной теме не относится из-за невозможности применить его так же просто как остальные типы. Более того, сам по себе double-double или float128 не позволяет создать целый каскад сложений с повышением точности до любых значений, а описанные в статьях приёмы — позволяют.

  • Наиболее точное скалярное произведение векторов типа double. Вычисление значения полинома
    0

    Да и я почти тоже самое написал:


    А точность может понадобиться наибольшая в том случае, когда полученный результат затем подвергается какой-то обработке, после которой погрешность возрастает ещё больше, затем ещё — и так много миллионов раз. Когда речь идёт об устойчивости какого-то решения, ошибка даже в 2-3 последних битах (7 ULP) в исходном числе может после миллиона последующих операций перевести систему из состояния сходится к состоянию расходится.
  • Наиболее точное скалярное произведение векторов типа double. Вычисление значения полинома
    +1

    Пожалуйста.


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


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

  • Наиболее точное скалярное произведение векторов типа double. Вычисление значения полинома
    +1

    Исследования нашего научного цента показали полную непригодность позитов для решения реальных задач математического анализа и дифференциальных уравнений. Хотя сама идея красивая. Больше ничего сказать не могу, мне эта тема с тех пор неинтересна. На Хабре по теме позитов есть информация от других авторов.

  • Наиболее точное скалярное произведение векторов типа double. Вычисление значения полинома
    +1

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


    Описываемые алгоритмы можно применить везде, где есть необходимость перемножать пару чисел и складывать цепочки чисел любого размера. Но даже если где-то есть деление, оно может быть заменено серией сложений и умножений. Так что можно всё, было бы желание и необходимость.


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

  • Наиболее точное скалярное произведение векторов типа double. Вычисление значения полинома
    0

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


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


    А точность может понадобиться наибольшая в том случае, когда полученный результат затем подвергается какой-то обработке, после которой погрешность возрастает ещё больше, затем ещё — и так много миллионов раз. Когда речь идёт об устойчивости какого-то решения, ошибка даже в 2-3 последних битах (7 ULP) в исходном числе может после миллиона последующих операций перевести систему из состояния сходится к состоянию расходится.


    Короче говоря, для меня быт — это не только ключи доставать, это ещё и нудная тягомотина, которая предшествует реальному научному поиску. Вся эта тягомотина — это быт учёного и занимает массу времени.


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

  • Наиболее точное скалярное произведение векторов типа double. Вычисление значения полинома
    0
    Это в какой именно части бытовой сферы обычно применяют?

    Там где нужно на тяп-ляп собрать код, который вычисляет некоторое выражение через сложение и умножение наиболее точно, то есть когда точность обычного double не устраивает: задачи математического анализа и дифференциальных уравнений при их простейшем применении к каких-то нехитрых ситуациях в быту. Ну, скажем, по-быстрому интеграл взять, не особенно заморачиваясь, но чтобы точность была высокой.


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

  • Наиболее точное скалярное произведение векторов типа double. Вычисление значения полинома
    +10

    Лет 20 назад один из преподавателей привёл нам пример, когда запись вроде вашей выглядит нелепо:


    Matrix[NUM_OF_ROWS-1][NUM_OF_COLUMNS-1] = Matrix[NUM_OF_ROWS-1][NUM_OF_COLUMNS-1] + 1

    Это просто к слову.


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

  • Наиболее точное скалярное произведение векторов типа double. Вычисление значения полинома
    +2

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

  • Почему донат — это будущее, если всё сделать правильно
    0

    Благодарю за статью. Сходные мысли, но немного о другом я писал в своей статье VK, где рассмотрел 14 причин отказа от воровства. Под воровством я таже понимаю потребление контента без оплаты времени и сил, которое затратил автор на его создание, однако я не считаю, что оплата должна пойти именно автору текста или видео. Оплата в моём понимании может быть намного шире: применить полученное знание для всеобщей пользы. Если не можете применить, имеет смысл оплатить автору деньгами в качестве штрафа за бездействие. Если и это не оплатили — значит вор :)


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

  • Точные и быстрые вычисления для чисел с плавающей точкой на примере функции синуса. Часть 2: libm
    +2

    Друзья, не ругайтесь, пожалуйста. Вы оба — таких хорошие! Каждый делает свою работу в своей области, а в действительности пользу несёт каждый. Зачем ругаться? :)

  • Точные и быстрые вычисления для чисел с плавающей точкой на примере функции синуса. Часть 2: libm
    0

    Я бы не согласился, что посчитать его на интервале от 0 до Pi/2 достаточно. Перед этим есть целая проблема — выполнить редукцию аргумента x до этого интервала; есть алгоритмы, которые призваны делать это с максимально возможной точностью. Просто выполнить операцию типа x ← x-2×Pi×k не получится, будут большие потери. Но мне кажется вы об этом знаете, только забыли упомянуть.

  • Точные и быстрые вычисления для чисел с плавающей точкой на примере функции синуса. Часть 2: libm
    0

    По моему мнению не вполне удачно сочетать в себе две совершенно разные темы. Первая — базовые принципы арифметики с плавающей запятой вроде закона дистрибутивности (почему он нарушается, также как закон ассоциативности). Вторая — сложные элементы из неочевидной и нетривиальной темы, касающейся вычисления функций. Целевая аудитория, которой нужно первое, не будет вникать во второе, потому что не сможет, а вторым совершенно не нужно объяснять то, что для них уже очевидно. Поэтому для первых я рекомендую сначала пройти единственный из известных мне видео-курсов (на русском языке), где всё подробно с самого начала. Прямо вообще с нуля. Будет время, может быть сделаю и текстовый курс. Ну а вторым рекомендую помогать автору в его нелёгком начинании.

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

    Благодарю за ссылку, добавил её в конце статьи.

  • Точные и быстрые вычисления для чисел с плавающей точкой на примере функции синуса. Введение и часть 1
    0

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

  • Точные и быстрые вычисления для чисел с плавающей точкой на примере функции синуса. Введение и часть 1
    +2
    Ряд тейлора или полиномы Чебышева/минимакс-полиномом это всё равно полиномы. Принципиальной разницы быть не должно в самом коде. Если вы думаете по-другому — пишите.

    Я думаю очень по-другому. Всё дело в том, что степени этих полиномов будут различными. Минимакс-полином может оказаться вдвое короче ряда Тейлора (в зависимости от выбранного отрезка). Например, для функции exp2(x) на отрезке [0,1] если нужна точность 54 бита, то хватает минимакс-полинома 10-й степени. А ряд Тейлора будет намного длиннее, 15-я степень. При этом его реализация будет намного сложнее. В результате моих экспериментов, Тейлор проиграл Минимаксу по скорости в 8 раз. Вы только вдумайтесь. Да, код можно ускорить, ну, раза в 3. А куда деть 15-ю степень? Поэтому разница всё-таки есть.

  • Точные и быстрые вычисления для чисел с плавающей точкой на примере функции синуса. Введение и часть 1
    +1
    CORDIC предназначен для вычислений без использования операции умножения и на соответствующем оборудовании он обойдет вычисления по полиномам (не говоря уже о никуда не годном ряде Тейлора). Но да, на современном железе CORDIC безнадежно устарел.

    CORDIC может быть и устарел, а сам метод Shift-and-Add, лежащий в его основе — нет. Сейчас вообще всё идёт по направлению комбинации всех существующих методов. В зависимости от ситуации, каждый метод может оказаться хорошим, поэтому однозначно говорить, что уже можно сбросить со счетов, а что нельзя — не следует. Даже ряд Тейлора, хоть и плохая идея, но, например, для функции exp(x) около нуля, если нужно быстро на коленках собрать хоть что-то, вполне себе рабочий вариант. А ещё лучше он подходит для стартовой точки в методе Ньютона, потому что благодаря простым коэффициентам легко переводится на арифметику с фиксированной запятой без лишней возни. Каждому методу — своя ситуация, где он хорош. Хотя в нашей общей практике, да, не применяется.

  • Точные и быстрые вычисления для чисел с плавающей точкой на примере функции синуса. Введение и часть 1
    0

    Вы во многом правы в этой фразе:


    Более того, расчет с точностью ±1ulp обычно нужен только разработчикам библиотек, никакие практические цели такой точности не требуют

    но не во всём. Я как раз разработчик библиотек. И мне бывает нужна точность, которая на десятки (иногда сотни) порядков выше 1ulp по причине, указанной в этой статье. Один из практических смыслов такой точности — чтобы округление результата было корректным до последнего бита, чтобы обеспечить полную повторяемость результата не зависимо ни от компилятора, ни от вычислительной машины. А в обыденной жизни да, я согласен, что это не нужно, из-за последнего бита даже ракета не упадёт… хотя, не знаю. Знаю только, что из-за разницы даже в последнем бите бывает, что некоторые программы работают слишком по-разному, но это из-за наличия в них кучи других ошибок. Ошибка в округлении последнего бита является лишь катализатором для их проявления.

  • Точные и быстрые вычисления для чисел с плавающей точкой на примере функции синуса. Введение и часть 1
    +1

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


    У меня есть желание поделиться ссылкой: существует книга Jean-Michel Muller, “Elementary Functions: Algorithms and Implementation”, 2016, в этой книге огромное количество знаний о вычислении элементарных функций. В принципе, её достаточно чтобы знать о них почти всё, что сейчас применяют в этой области, за исключением каких-то продвинутых алгоритмов, изобретённых недавно. В том числе и общую теорию. Например, там сказано, что не следует вычислять синус на отрезке от 0 до Pi/2, потому что это невыгодно, отрезок нужно уменьшать минимум до [0, Pi/256] и уже дальше особыми формулами распространять на весь период. Также есть целая глава, где сказано, что синус (и любую другую элементарную функцию на монотонном интервале) можно вычислить используя только сдвиги и сложения, а также небольшую таблицу предподсчитанных заранее констант (Shift-and-Add Algorithms).


    Ещё рекомендую для ознакомления библиотеку libquadmath где почти все элементарные функции реализованы для float128 и весь код хорошо виден. Посмотрите как там реализован синус (файл sincosq_kernel.c), там сразу одновременно вычисляется синус и косинус. Метод не очень хитрый, но не очевидный: там и редукция аргумента, и minimax-полином (если я верно понял, это именно он), и финальная корректировка с помощью таблиц. В общем, я так понял, вы хотели рассказать об этом в следующей статье? Мне просто показалось, что это очень большой труд — всё это рассказать, и однажды это хотел сделать я, но прикинул, что нужно для этого ещё пару лет потренироваться на тех статьях, что я пишу сейчас. Поэтому элементарные функции решил пока оставить. Очень сложная для популярного изложения (для меня) тема. Само только вдумчивое чтение упомянутой книги далось не с одного месяца.


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


    PS. А ещё я начал бы с экспоненты или 2 в степени x, эти функции кажутся намного проще. Но это уже как вам угодно.

  • Можно ли сложить N чисел типа double наиболее точно?
    0

    Этот алгоритм описан в книге [1], можете сами прочитать. Погрешность в этом случае будет не больше чем значение ulp умножить на сумму всех тех частичных сумм, которые вы будете получать по ходу работы алгоритма. Это довольно плохая теоретическая оценка. А что будет на практике — попробуйте сами.

  • Можно ли сложить N чисел типа double наиболее точно?
    0

    Здесь всё зависит от субъективного восприятия информации. Если я говорю о возможной погрешности в одном случае и умалчиваю о ней же в другом, то это не значит, что её там нет. Это значит что я о ней не сказал. Разумный читатель сможет подумать и сделать нужные ему выводы, в частности, вот вы же сделали — и хорошо.


    Кстати, исходный вопрос был не о сравнении float128 против двух double, а о сравнении double против двух float.

    Не совсем. Автор задаёт вопрос вот так:


    я правильно понимаю, что все приведенные алгоритмы не лучше простого перехода к арифметике с более высокой точностью?

    А уже потом приводит пример (орфография сохранена):


    Скажем, если сравнивать приведенные алгориты на float против использования double в качестве аккамулятора.

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

  • Можно ли сложить N чисел типа double наиболее точно?
    0
    А ваш ответ выглядит так, как будто float128 хуже двух double, хотя вы сами же и пишете что у float128 разрядов мантиссы больше.

    Может быть и хуже, потому если float128 не аппаратный, то будет работать медленно. Ведь важна не только точность, но приличная скорость. И второе, чем double лучше, так это тем, что из него можно сделать 3-double, а из float128 нельзя. То есть в зависимости от решаемой задачи мы можем сказать, что лучше. А автор вопроса, на который я отвечал, просит дать ответ безотносительно решаемой задачи. А это всегда будет приводить к неопределённым ответам, и, следовательно, к неопределённым замечаниям к этим неопределённым ответам. И так далее. В итоге получится, что правы все, но каждый — по-своему.

  • Можно ли сложить N чисел типа double наиболее точно?
    +1

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

  • Можно ли сложить N чисел типа double наиболее точно?
    0
    Вы так пишете как будто алгоритм Кэхена два раза не округляет!

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


    все приведенные алгоритмы не лучше простого перехода к арифметике с более высокой точностью

    Я отвечаю, что мы не знаем, что будет лучше, но, вероятно, ответы будут разными. Какой из них точнее — неизвестно.

  • Можно ли сложить N чисел типа double наиболее точно?
    0

    Вы возлагаете на меня слишком большие надежды. Я пишу научно-популярный текст, цель которого — положить начало знакомства читателей с обсуждаемой темой. Никоим образом я не хочу чтобы эти материалы именно в таком поверхностном виде ложились бы в основу чьей-то серьёзной работы. Я делаю здесь именно школу, а не науку, показываю верхушку айсберга того, что уже описано в научной литературе, но по какой-то причине плохо описано в литературе популярной. Поэтому если вас интересует судьба всей цифровой фильтрации, то лучше сразу покупать книгу [1], затем те статьи, на которые ссылаются её авторы при обсуждении интересующих вас алгоритмов. Другого пути, увы, нет. Напрасно думать, что моя статья на Хабре может дать хотя бы тысячную долю того знания, которое реально требуется для ответственных проектов. А вся цифровая фильтрация, согласитесь, — это сложная и ответственная область.

  • Можно ли сложить N чисел типа double наиболее точно?
    +1

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

  • Можно ли сложить N чисел типа double наиболее точно?
    0

    Да, можно и так сказать, но я подразумевал ещё потерю времени на сортировку или на искусственное создание заведомо отсортированного порядка на входе в алгоритм.

  • Можно ли сложить N чисел типа double наиболее точно?
    0

    Ни в коем случае точный результат с помощью double получить нельзя. Потому что разбежка у float по экспоненте может составлять более 250 битов, а double удержит только 52 из них. По поводу порядка я уже написал комментарий другому читателю.

  • Можно ли сложить N чисел типа double наиболее точно?
    +1

    Конечно, я не мог опубликовать все таблицы, которые получил у себя, и может быть что-то не видно, но отчасти поэтому я и предложил читателям самостоятельно провести необходимые исследования. Потому что верить мне — это оказать себе медвежью услугу. Но если вам так нужно моё субъективное мнение, то вот оно...


    Насколько это ухудшает/улучшает результат?

    Не знаю, всегда по-разному. Может в два раза, может в 3, а может и не получиться разницы. Проверьте сами и убедитесь, пожалуйста. На экспоненциальных тестах сортировка по возрастанию обычно именно спасает (в два раза), а по убыванию — портит (тоже в два раза). На равномерных — зависит от экспоненты. Поэтому я лично не могу подобрать однозначной рекомендации. Интуиция тут не работает. Например, когда речь идёт о равномерном распределении на интервале [1,2), то вы при использовании интуиции вряд ли учли тот факт, что уже после первого действия сумма S становится наверняка больше любого из слагаемых. После второго — совсем больше и дальше остальные тысячи элементов уже складываются с большой погрешностью. При этом в случае хаотичного порядка получается то же самое! Иными словами, при одинаковом знаке сортировка по возрастанию имеет смысл только когда числа очень разные, с разными экспонентами. Когда экспоненты одинаковые — сортировать может быть вредно. Это мой субъективный вывод.


    Как обстоят дела с сортировкой, если все значения одинакового знака? Можно ли считать что в таком случае сортировка точно не ухудшает результат?

    Скорее всего, да, но только если экспоненты очень разные.


    Если складывать отдельно положительные и отрицательные значения, но предварительно отсортировав их, ситуация лучше?

    Ответ на этот вопрос есть в одной из таблиц.


    Ну и последний, практический вопрос: я правильно понимаю, что все приведенные алгоритмы не лучше простого перехода к арифметике с более высокой точностью?

    С точки зрения точности да, но только при условии, что вы затем не возвращаетесь обратно к арифметике с более низкой точностью, так как в этом случае вы рискуете получить ошибку двойного округления. То есть результат применения алгоритма 3 и прямолинейного применения float128 может дать разбежку в 1 бит из-за того, что вы должны будете выполнить дополнительное действие float128 → double. Но это вряд ли будет происходить на бытовых задачах. Особенно если учесть, что float128 имеет 112 битов против 104 у double-double.


    Теперь что касается ваших слов не лучше. Что значит не лучше? У вас есть аппаратный float128? Если нет, то может быть есть хороший программный, который будет быстрее double-double? Я сомневаюсь, хотя экспериментов не проводил. Поэтому не знаю, что действительно будет лучше. А если модифицировать алгоритм 3 немного и складывать хвостики этим же алгоритмом, мы получим double-double-double. И вообще можем создать любой каскад по принципу того, как создаётся длинная арифметика с целыми числами. Поэтому опять я не понимаю, что значит не лучше. Я давно убедился, что в профессиональной сфере нельзя сравнивать различные технологии по правилу лучше / не лучше. Каждая технология предназначена для сугубо своей задачи. Для конкретной задачи ДА, она может быть лучше или хуже. Сама по себе она лучше или хуже быть не может в принципе. Такой вот у меня ответ получился :)


    Но повторюсь, лучше вы эти (или другие) ответы получите сами, проверив всё на своей практике. Это будет куда продуктивнее.

  • Можно ли сложить N чисел типа double наиболее точно?
    +1
    Конечно, эффективней вместо Кэхэна и т.п. было бы просто использовать длинную мантиссу, но FPU такого не умеет.

    Именно так, поэтому я и намекнул в статье, что для ускорения можно попробовать смотреть на исходные числа глубже, то есть как на битовые последовательности. Это позволит взять, например, два целых числа int64 и по полной программе использовать 127-11=116 битов под мантиссу. Это будет даже точнее чем double-double. Но говорить об этом прямо в данной статье я не решился. Потому что у меня был опыт ручной обработки double, когда я решил вместо медленных операций с плавающей запятой перейти к арифметике с фиксированной запятой на целых числах, там как раз было очень удобно, что все экспоненты в моей задаче были равны и по сути можно было избавиться от сдвигов. И вот, возомнив себя самым умным, я получил замедление программы в 8 раз. Точно также однажды решил заменить умножение и сложение на fma, и получил замедление в 4 раза. Тогда я понял, что нельзя просто так предполагать, что хорошо понимаешь как что будет работать с этой плавающей арифметикой, нужны масштабные исследования. И по этой же причине я не стал сравнивать предложенные здесь алгоритмы по скорости.

  • Можно ли сложить N чисел типа double наиболее точно?
    +2
    Я ожидал увидеть переход к произвольной «разрядности» – с гарантированной точностью результата

    Не было такой цели, но если бы она была, то я бы начал с модификации алгоритма Rump–Ogita–Oishi. Там где 2 double, точно также делается и 3 и так далее. Но задача была всё-таки как можно быстрее победить обычную наивную сумму.


    Много воды.

    Каждому своё. Мне не так просто отыскать правильный баланс между сухой научной работой и обучающим материалом. Беру что-то среднее, что примерно в 10 раз короче, чем тот максимальный размах, с которого я вообще начинаю планирование статьи. Я работал в вузе 11 лет и хорошо представляю себе в чём нуждается большинство из тех людей, которых я представляю себе в качестве читателей. Для остальных чтение подобных статей может быть только таким: берём список источников, и не читая мою статью сразу погружаемся в их содержание, не теряя на меня больше ни минуты. Всё, никаких проблем не вижу :), и даже не нужно тратить время на объяснение того, что субъективно не понравилось, потому что ясно же, что всем не угодишь.

  • Можно ли сложить N чисел типа double наиболее точно?
    +1

    Да, благодарю. Вообще ведь очевидно, что в алгоритме Rump–Ogita–Oishi эти погрешности, которые складываются отдельно, можно также складывать этим же алгоритмом, сразу получая 3 double. Вообще нетрудно собрать целый каскад. Получаем аналог длинной арифметики, в которой метод two_sum как будто играет роль переноса, как это делается при сложении длинных целых чисел. Там мы тоже ведь разбиваем сумму на две части: сумма по модулю 2**64-1 и перенос.

  • Можно ли сложить N чисел типа double наиболее точно?
    +2

    Да, верно! Благодарю :) Ошибка алгоритма 3 составила 4503599627370496ulp (52 бита). Однако если числа отсортировать, то алгоритм 3 работает правильно (как по возрастанию, так и по убыванию). Теперь нужно найти именно бытовой тест, чтобы алгоритм перестал работать. Такого я найти не смог.

  • Можно ли сложить N чисел типа double наиболее точно?
    +3

    Я многое делал, но у меня не получилось добиться ошибки. Поэтому я сразу и говорю: либо покажите, пожалуйста, как вы это сделали, либо, если нет примера, ничего говорить не нужно. Зачем тратить своё и чужое время?

  • Можно ли сложить N чисел типа double наиболее точно?
    +3

    Это не то. Нужен конкретный тест суммы чисел, а не более сложных операций. Именно конкретный тест, а не слова.

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

    Ознакомился со статьёй, на которую вы дали ссылку. Да, мне знакома ситуация, в которой оказался её автор. И вот мой учебный видео-курс КАК РАЗ для этого случая отлично подходит. Всё с самого начала, с самых базовых представлений. Да, пара формул встречается, но даже до их появления у зрителя уже появляется нужный образ в голове, понимание того, как это устроено. 8 уроков не зря же делалось: плавное погружение. Как раз для тех, кому нужно с самого начала. Посмотрите первый и второй уроки чтобы убедиться, они на YouTube. Но давайте всё-таки не путать научно-популярное изложение материала и учебный курс. Это принципиально разные виды художественного творчества.

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

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

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

    Я снова повторюсь, что не считаю вас правым в этой ситуации, хотя и не возражаю против того, чтобы у вас было своё мнение. Я описываю тему, связанную с арифметикой с плавающей запятой, и считаю что читатель должен владеть основой, если его эта тема волнует. Если это не его тема, значит ему не нужно её читать. Вот представьте, вы оказались в вузе, скажем, на математическом факультете. Преподаватель математического анализа исходит из предположения, что вы знаете что такое 2+2=4. А вы встаёте и возражаете: никто не пойдёт читать 100500 источников, чтобы вас понять. Чья это проблема: ваша или преподавательская? Очевидно, что ваша. Вы могли бы с тем же успехом попросить меня разъяснить в двух словах что такое вообще сложение чисел, как возникает перенос, иначе читатели могут не понять. Потому что моя целевая аудитория — это люди, которые УЖЕ давно поняли, что если они имеют дело с числами с плавающей запятой, то они обязаны понимать их также, как понимают целые числа. Если они этого по какой-то причине не делают, значит дальше погружаться в тему им НЕ нужно.


    Считайте, что я в начале статьи сделал #include "floating point feeling" и не должен повторять своими словами то, что описано в этой библиотеке. Ну а если такой библиотеки нет у читателя, то и пара слов об устройстве формата binary64 НИЧЕГО не даст, а только утомит тех, кто в теме.


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

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

    Это именно видео-курс. Текстовых данных полно в интернете, или в книге [1]. В моём исполнении текстовый курс будет стоить в 10 раз дороже, чем видео. Но мне кажется, что вы здесь немного ошибаетесь. Вот смотрите сами: текста в интернете полно, а учить никто не хочет, ленятся читать. Вот это видео как раз для ленивых :) Потому что я нашёл способ очень простого и понятного объяснения темы, и в тексте оно как-то не будет смотреться. Но это моё мнение.