Стандартных реализаций нет, есть чьи-то реализации давно известных приёмов. И моя задача всего лишь в их популяризации. При этом long double к данной теме не относится из-за невозможности применить его так же просто как остальные типы. Более того, сам по себе double-double или float128 не позволяет создать целый каскад сложений с повышением точности до любых значений, а описанные в статьях приёмы — позволяют.
А точность может понадобиться наибольшая в том случае, когда полученный результат затем подвергается какой-то обработке, после которой погрешность возрастает ещё больше, затем ещё — и так много миллионов раз. Когда речь идёт об устойчивости какого-то решения, ошибка даже в 2-3 последних битах (7 ULP) в исходном числе может после миллиона последующих операций перевести систему из состояния сходится к состоянию расходится.
Любой алгоритм, основанный на перемножении двух чисел и сложении любого количества чисел может быть реализован с применением указанных в статье знаний. Но в разложении Холецкого также приходится выполнять деление и извлечение корня. Обе эти операции можно заменить серией сложений и умножений. Так что по сути подсказывать нечего.
Если нужен конкретный ответ, то мои консультации платные, обращайтесь в ЛС. Но я вас уверяю, дешевле будет вам попробовать сделать самостоятельно, это нетрудно.
Исследования нашего научного цента показали полную непригодность позитов для решения реальных задач математического анализа и дифференциальных уравнений. Хотя сама идея красивая. Больше ничего сказать не могу, мне эта тема с тех пор неинтересна. На Хабре по теме позитов есть информация от других авторов.
Спасибо за предложение и за оценку статьи. Можно предложить много специфических тестов, когда полином не будет сильно возрастать, например, мне ближе преобразование Фурье на окружности единичного радиуса (как вы понимаете, для быстрого умножения длинных чисел). Но я решил сделать всё совсем случайным, а нужную специфику пусть читатель тестирует сам.
Описываемые алгоритмы можно применить везде, где есть необходимость перемножать пару чисел и складывать цепочки чисел любого размера. Но даже если где-то есть деление, оно может быть заменено серией сложений и умножений. Так что можно всё, было бы желание и необходимость.
Однако практика показывает, что если есть необходимость решить конкретную задачу, то для неё создают конкретный алгоритм, а я описал общие методы, они могут быть неэффективными в каком-то частном случае. Например, в некоторых задачах проще взять программную реализация float128 и получить более подходящий код и более точное решение.
Здесь всё дело в том, что у нас с вами нет точного определения что такое научная и бытовая сферы. В моём миропонимании бытовое — это всё что делается просто для удовлетворения минимального набора потребностей в той или иной сфере, возможно, на скорую руку, по-быстрому, на коленках, назовите как угодно.
Например, идёт научная работа, требуется решить сложную задачу, непонятно как подступиться. Пробуем с разных сторон подобраться, просто выполняя тяп-ляп расчёты для оценки трудозатрат и перспективности того или иного метода, который будем применять. То есть удовлетворяем набор минимальных потребностей: получить хоть какие-то сведения о задаче, чтобы можно было приступить уже от бытового к научному решению.
А точность может понадобиться наибольшая в том случае, когда полученный результат затем подвергается какой-то обработке, после которой погрешность возрастает ещё больше, затем ещё — и так много миллионов раз. Когда речь идёт об устойчивости какого-то решения, ошибка даже в 2-3 последних битах (7 ULP) в исходном числе может после миллиона последующих операций перевести систему из состояния сходится к состоянию расходится.
Короче говоря, для меня быт — это не только ключи доставать, это ещё и нудная тягомотина, которая предшествует реальному научному поиску. Вся эта тягомотина — это быт учёного и занимает массу времени.
Ну ещё добавлю, что на олимпиадах по программированию эти знания тоже могут быть нужны, там не всегда требуется знать всю математическую подоплёку, достаточно просто интуитивно понимать алгоритм и уметь его правильно применять. Для таких людей, кто выступает на соревнованиях, эти знания могут быть полезны даже очень.
Это в какой именно части бытовой сферы обычно применяют?
Там где нужно на тяп-ляп собрать код, который вычисляет некоторое выражение через сложение и умножение наиболее точно, то есть когда точность обычного double не устраивает: задачи математического анализа и дифференциальных уравнений при их простейшем применении к каких-то нехитрых ситуациях в быту. Ну, скажем, по-быстрому интеграл взять, не особенно заморачиваясь, но чтобы точность была высокой.
В научных расчётах, где есть высокая ответственность, описанные в статье знания именно в таком виде применить нельзя, потому что нужно понимать их математическую основу, чтобы отвечать за каждую операцию, а я эту основу не давал.
Но вообще я за то, чтобы комментарии к статье были бы только по теме статьи. Считаю, что нужно ценить время и внимание читателей, не привлекая их к себе отстранёнными от темы соображениями. Поговорить можно в ЛС, можно с друзьями, но не с десятками тысяч людей (именно столько откроют статью), которые не для этого сюда приходят. Это моё субъективное мнение :)
Благодарю за замечание, но прошу принять во внимание то обстоятельство, что у разных коллективов существует разная традиция и своя собственная внутренняя система посланий друг другу через структуру кода. Большинство моих читателей переписывают код по своим канонам, понимая это.
Благодарю за статью. Сходные мысли, но немного о другом я писал в своей статье VK, где рассмотрел 14 причин отказа от воровства. Под воровством я таже понимаю потребление контента без оплаты времени и сил, которое затратил автор на его создание, однако я не считаю, что оплата должна пойти именно автору текста или видео. Оплата в моём понимании может быть намного шире: применить полученное знание для всеобщей пользы. Если не можете применить, имеет смысл оплатить автору деньгами в качестве штрафа за бездействие. Если и это не оплатили — значит вор :)
Спорить ни с кем не буду, просто принимайте как личное мнение. Сам давно отписался от всех тех ресурсов, которые не могу оплатить денгами или привнесением пользы обществу после потребления бесплатного контента. 10% моего дохода уходит на пожертвования. Потом будет ещё больше.
Друзья, не ругайтесь, пожалуйста. Вы оба — таких хорошие! Каждый делает свою работу в своей области, а в действительности пользу несёт каждый. Зачем ругаться? :)
Я бы не согласился, что посчитать его на интервале от 0 до Pi/2 достаточно. Перед этим есть целая проблема — выполнить редукцию аргумента x до этого интервала; есть алгоритмы, которые призваны делать это с максимально возможной точностью. Просто выполнить операцию типа x ← x-2×Pi×k не получится, будут большие потери. Но мне кажется вы об этом знаете, только забыли упомянуть.
По моему мнению не вполне удачно сочетать в себе две совершенно разные темы. Первая — базовые принципы арифметики с плавающей запятой вроде закона дистрибутивности (почему он нарушается, также как закон ассоциативности). Вторая — сложные элементы из неочевидной и нетривиальной темы, касающейся вычисления функций. Целевая аудитория, которой нужно первое, не будет вникать во второе, потому что не сможет, а вторым совершенно не нужно объяснять то, что для них уже очевидно. Поэтому для первых я рекомендую сначала пройти единственный из известных мне видео-курсов (на русском языке), где всё подробно с самого начала. Прямо вообще с нуля. Будет время, может быть сделаю и текстовый курс. Ну а вторым рекомендую помогать автору в его нелёгком начинании.
Конечно, я тут спорить не готов в силу того, что в своей работе до тригонометрических функций ещё не добрался. Превосходно, если они одинаковые (хотя сами реализации и разбивка отрезка точно разная), но я вам в одном из комментариев выше привел пример, что ряд Тейлора может проигрывать minimax-полиному. Далее я всецело доверяюсь вашему мнению, потому что как уже сказано ранее, не чувствую в себе уверенность в том, чтобы спорить, когда сам ещё до сложной реализации элементарных тригонометрических функций не добрался. Повторюсь, что я только ЗА то, чтобы вы смогли завершить свой труд, потому что я в себе таких сил сейчас не вижу. А то я думал, что мне придётся это делать через год-два, а вот глядишь, может и не придётся :)
Ряд тейлора или полиномы Чебышева/минимакс-полиномом это всё равно полиномы. Принципиальной разницы быть не должно в самом коде. Если вы думаете по-другому — пишите.
Я думаю очень по-другому. Всё дело в том, что степени этих полиномов будут различными. Минимакс-полином может оказаться вдвое короче ряда Тейлора (в зависимости от выбранного отрезка). Например, для функции exp2(x) на отрезке [0,1] если нужна точность 54 бита, то хватает минимакс-полинома 10-й степени. А ряд Тейлора будет намного длиннее, 15-я степень. При этом его реализация будет намного сложнее. В результате моих экспериментов, Тейлор проиграл Минимаксу по скорости в 8 раз. Вы только вдумайтесь. Да, код можно ускорить, ну, раза в 3. А куда деть 15-ю степень? Поэтому разница всё-таки есть.
CORDIC предназначен для вычислений без использования операции умножения и на соответствующем оборудовании он обойдет вычисления по полиномам (не говоря уже о никуда не годном ряде Тейлора). Но да, на современном железе CORDIC безнадежно устарел.
CORDIC может быть и устарел, а сам метод Shift-and-Add, лежащий в его основе — нет. Сейчас вообще всё идёт по направлению комбинации всех существующих методов. В зависимости от ситуации, каждый метод может оказаться хорошим, поэтому однозначно говорить, что уже можно сбросить со счетов, а что нельзя — не следует. Даже ряд Тейлора, хоть и плохая идея, но, например, для функции exp(x) около нуля, если нужно быстро на коленках собрать хоть что-то, вполне себе рабочий вариант. А ещё лучше он подходит для стартовой точки в методе Ньютона, потому что благодаря простым коэффициентам легко переводится на арифметику с фиксированной запятой без лишней возни. Каждому методу — своя ситуация, где он хорош. Хотя в нашей общей практике, да, не применяется.
Мои консультации платные, если интересно, пишите в ЛС.
Ответ на данный вопрос есть в предложенном курсе.
Поправлю: не точное, а наиболее точное, это разные вещи. Да и то, всегда можно подобрать тест, когда даже эти трюки спасать не будут.
Нет, не приходилось. Но могу сразу сказать, что увеличение точности обычно даёт улучшение сходимости, если в задаче нет какой-то особой специфики.
Стандартных реализаций нет, есть чьи-то реализации давно известных приёмов. И моя задача всего лишь в их популяризации. При этом long double к данной теме не относится из-за невозможности применить его так же просто как остальные типы. Более того, сам по себе double-double или float128 не позволяет создать целый каскад сложений с повышением точности до любых значений, а описанные в статьях приёмы — позволяют.
Да и я почти тоже самое написал:
Пожалуйста.
Любой алгоритм, основанный на перемножении двух чисел и сложении любого количества чисел может быть реализован с применением указанных в статье знаний. Но в разложении Холецкого также приходится выполнять деление и извлечение корня. Обе эти операции можно заменить серией сложений и умножений. Так что по сути подсказывать нечего.
Если нужен конкретный ответ, то мои консультации платные, обращайтесь в ЛС. Но я вас уверяю, дешевле будет вам попробовать сделать самостоятельно, это нетрудно.
Исследования нашего научного цента показали полную непригодность позитов для решения реальных задач математического анализа и дифференциальных уравнений. Хотя сама идея красивая. Больше ничего сказать не могу, мне эта тема с тех пор неинтересна. На Хабре по теме позитов есть информация от других авторов.
Спасибо за предложение и за оценку статьи. Можно предложить много специфических тестов, когда полином не будет сильно возрастать, например, мне ближе преобразование Фурье на окружности единичного радиуса (как вы понимаете, для быстрого умножения длинных чисел). Но я решил сделать всё совсем случайным, а нужную специфику пусть читатель тестирует сам.
Описываемые алгоритмы можно применить везде, где есть необходимость перемножать пару чисел и складывать цепочки чисел любого размера. Но даже если где-то есть деление, оно может быть заменено серией сложений и умножений. Так что можно всё, было бы желание и необходимость.
Однако практика показывает, что если есть необходимость решить конкретную задачу, то для неё создают конкретный алгоритм, а я описал общие методы, они могут быть неэффективными в каком-то частном случае. Например, в некоторых задачах проще взять программную реализация float128 и получить более подходящий код и более точное решение.
Здесь всё дело в том, что у нас с вами нет точного определения что такое научная и бытовая сферы. В моём миропонимании бытовое — это всё что делается просто для удовлетворения минимального набора потребностей в той или иной сфере, возможно, на скорую руку, по-быстрому, на коленках, назовите как угодно.
Например, идёт научная работа, требуется решить сложную задачу, непонятно как подступиться. Пробуем с разных сторон подобраться, просто выполняя тяп-ляп расчёты для оценки трудозатрат и перспективности того или иного метода, который будем применять. То есть удовлетворяем набор минимальных потребностей: получить хоть какие-то сведения о задаче, чтобы можно было приступить уже от бытового к научному решению.
А точность может понадобиться наибольшая в том случае, когда полученный результат затем подвергается какой-то обработке, после которой погрешность возрастает ещё больше, затем ещё — и так много миллионов раз. Когда речь идёт об устойчивости какого-то решения, ошибка даже в 2-3 последних битах (7 ULP) в исходном числе может после миллиона последующих операций перевести систему из состояния сходится к состоянию расходится.
Короче говоря, для меня быт — это не только ключи доставать, это ещё и нудная тягомотина, которая предшествует реальному научному поиску. Вся эта тягомотина — это быт учёного и занимает массу времени.
Ну ещё добавлю, что на олимпиадах по программированию эти знания тоже могут быть нужны, там не всегда требуется знать всю математическую подоплёку, достаточно просто интуитивно понимать алгоритм и уметь его правильно применять. Для таких людей, кто выступает на соревнованиях, эти знания могут быть полезны даже очень.
Там где нужно на тяп-ляп собрать код, который вычисляет некоторое выражение через сложение и умножение наиболее точно, то есть когда точность обычного double не устраивает: задачи математического анализа и дифференциальных уравнений при их простейшем применении к каких-то нехитрых ситуациях в быту. Ну, скажем, по-быстрому интеграл взять, не особенно заморачиваясь, но чтобы точность была высокой.
В научных расчётах, где есть высокая ответственность, описанные в статье знания именно в таком виде применить нельзя, потому что нужно понимать их математическую основу, чтобы отвечать за каждую операцию, а я эту основу не давал.
Лет 20 назад один из преподавателей привёл нам пример, когда запись вроде вашей выглядит нелепо:
Это просто к слову.
Но вообще я за то, чтобы комментарии к статье были бы только по теме статьи. Считаю, что нужно ценить время и внимание читателей, не привлекая их к себе отстранёнными от темы соображениями. Поговорить можно в ЛС, можно с друзьями, но не с десятками тысяч людей (именно столько откроют статью), которые не для этого сюда приходят. Это моё субъективное мнение :)
Благодарю за замечание, но прошу принять во внимание то обстоятельство, что у разных коллективов существует разная традиция и своя собственная внутренняя система посланий друг другу через структуру кода. Большинство моих читателей переписывают код по своим канонам, понимая это.
Благодарю за статью. Сходные мысли, но немного о другом я писал в своей статье VK, где рассмотрел 14 причин отказа от воровства. Под воровством я таже понимаю потребление контента без оплаты времени и сил, которое затратил автор на его создание, однако я не считаю, что оплата должна пойти именно автору текста или видео. Оплата в моём понимании может быть намного шире: применить полученное знание для всеобщей пользы. Если не можете применить, имеет смысл оплатить автору деньгами в качестве штрафа за бездействие. Если и это не оплатили — значит вор :)
Спорить ни с кем не буду, просто принимайте как личное мнение. Сам давно отписался от всех тех ресурсов, которые не могу оплатить денгами или привнесением пользы обществу после потребления бесплатного контента. 10% моего дохода уходит на пожертвования. Потом будет ещё больше.
Друзья, не ругайтесь, пожалуйста. Вы оба — таких хорошие! Каждый делает свою работу в своей области, а в действительности пользу несёт каждый. Зачем ругаться? :)
Я бы не согласился, что посчитать его на интервале от 0 до Pi/2 достаточно. Перед этим есть целая проблема — выполнить редукцию аргумента x до этого интервала; есть алгоритмы, которые призваны делать это с максимально возможной точностью. Просто выполнить операцию типа x ← x-2×Pi×k не получится, будут большие потери. Но мне кажется вы об этом знаете, только забыли упомянуть.
По моему мнению не вполне удачно сочетать в себе две совершенно разные темы. Первая — базовые принципы арифметики с плавающей запятой вроде закона дистрибутивности (почему он нарушается, также как закон ассоциативности). Вторая — сложные элементы из неочевидной и нетривиальной темы, касающейся вычисления функций. Целевая аудитория, которой нужно первое, не будет вникать во второе, потому что не сможет, а вторым совершенно не нужно объяснять то, что для них уже очевидно. Поэтому для первых я рекомендую сначала пройти единственный из известных мне видео-курсов (на русском языке), где всё подробно с самого начала. Прямо вообще с нуля. Будет время, может быть сделаю и текстовый курс. Ну а вторым рекомендую помогать автору в его нелёгком начинании.
Благодарю за ссылку, добавил её в конце статьи.
Конечно, я тут спорить не готов в силу того, что в своей работе до тригонометрических функций ещё не добрался. Превосходно, если они одинаковые (хотя сами реализации и разбивка отрезка точно разная), но я вам в одном из комментариев выше привел пример, что ряд Тейлора может проигрывать minimax-полиному. Далее я всецело доверяюсь вашему мнению, потому что как уже сказано ранее, не чувствую в себе уверенность в том, чтобы спорить, когда сам ещё до сложной реализации элементарных тригонометрических функций не добрался. Повторюсь, что я только ЗА то, чтобы вы смогли завершить свой труд, потому что я в себе таких сил сейчас не вижу. А то я думал, что мне придётся это делать через год-два, а вот глядишь, может и не придётся :)
Я думаю очень по-другому. Всё дело в том, что степени этих полиномов будут различными. Минимакс-полином может оказаться вдвое короче ряда Тейлора (в зависимости от выбранного отрезка). Например, для функции exp2(x) на отрезке [0,1] если нужна точность 54 бита, то хватает минимакс-полинома 10-й степени. А ряд Тейлора будет намного длиннее, 15-я степень. При этом его реализация будет намного сложнее. В результате моих экспериментов, Тейлор проиграл Минимаксу по скорости в 8 раз. Вы только вдумайтесь. Да, код можно ускорить, ну, раза в 3. А куда деть 15-ю степень? Поэтому разница всё-таки есть.
CORDIC может быть и устарел, а сам метод Shift-and-Add, лежащий в его основе — нет. Сейчас вообще всё идёт по направлению комбинации всех существующих методов. В зависимости от ситуации, каждый метод может оказаться хорошим, поэтому однозначно говорить, что уже можно сбросить со счетов, а что нельзя — не следует. Даже ряд Тейлора, хоть и плохая идея, но, например, для функции exp(x) около нуля, если нужно быстро на коленках собрать хоть что-то, вполне себе рабочий вариант. А ещё лучше он подходит для стартовой точки в методе Ньютона, потому что благодаря простым коэффициентам легко переводится на арифметику с фиксированной запятой без лишней возни. Каждому методу — своя ситуация, где он хорош. Хотя в нашей общей практике, да, не применяется.