Потому что вы пытаетесь спорить с жаргонизмом. Все люди (из моего окружения), кто произносит фразу про удвоение правильных битов имеют в виду совершенно определённую вещь, то есть возведение погрешности в квадрат (при соблюдении ряда условий, и я об этом дважды предупредил). При этом все они понимают, что может не быть ни одной правильной цифры. Просто так говорят условно, и в большинстве случаев это и правда так. Это был мой последний ответ по данной теме в этой ветке комментариев.
Я дал вам источник, с которого можно начать разбираться. Дальше я рекомендую взять формулы, которые там участвуют, и проверить, что ваш пример в точности в них укладывается, либо убедиться, что вы сделали неправильный пример. Поскольку мы отклонились от темы статьи, я предлагаю на этом закончить.
Откройте, пожалуйста, хотя бы википедию и посмотрите там раздел Proof of quadratic convergence for Newton's iterative method.
Квадратичная сходимость — это когда точность возводится в квадрат на каждой итерации. Про стабилизацию битов это не говорит. Про десятичные цифры тоже. Когда мы говорим про то, что количество битов удваивается, это не совсем правильные слова, а устоявшееся название, но все вроде понимают их смысл, кто в теме. Это как в математическом анализе, мы говорим "почти всюду", а имеем в виду "за исключением множества меры нуль". Вроде все понимают.
В вашем примере с корнем вы взяли очень далекое приближение, поэтому точность всё равно будет возрастать квадратично, но слишком долго приходится идти до первого правильного бита, то удвоение почти ничего не даст. Вопрос первого приближения очень важен, если взять не то число, алгоритм будет долго-долго тормозить сначала, что у вас и происходит.
Что-то я не понимаю. Какие такие гарантии точного знака? Не слышал. Метод Ньютона даёт, грубо говоря, удвоение знаков, но это жаргон такой, так просто принято говорить. В действительности он даёт возведение точности в квадрат по сравнению с предыдущим шагом. То есть, скажем, была точность 2 в минус 2, стала 2 в минус 4, потом 2 в минус 16.
Мне кажется, вы не понимаете суть. В моём примере чтобы получить точными ВСЕГО ДВА БИТА, неизвестно как долго ещё считать! Уже получили 41 бит после запятой, а всё ещё не знаем, какими точно будут ВСЕГО ДВА бита. А сколько ещё считать? Никто не знает! Это это незнание характерно для ВСЕХ алгоритмов всех трансцендентных функций, никаких гарантий никто никогда не давал.
Вот вы сами пишите: "соотвественно точность не достаточна".
Вопрос в том КОГДА она будет достаточной? Этого никто не знает.
Между ними разница 2 в степени -40. Оба эти числа были получены в ходе вычислений пошаговым алгоритмом (одно на 100-м шаге, другое — на 101-м), которое из них по-вашему нужно взять в качестве достаточно-точного для того, чтобы сформировать правильное округление?
Как видим, 40 битов точности недостаточно, чтобы понять, с какой стороны мы от серединки. А сколько достаточно? Не знаем! Вот в этом и состоит суть проблемы TMD.
Благодарю за пояснение, я вообщем-то с десятичными числами не знаком особо, просто привёл примеры, которые на слуху. Если бы у меня была такая задача, то как вы и говорите, считал бы в рациональных числах. В большинстве случаев там скорость не важна.
Спасибо, буду знать, это это банковское округление :) А бывает ещё nearest-ties-to-away, это когда величина посередине округляется дальше от нуля. То есть это то, что у нас в математике принято: 12.5→13; 13.5→14. Именно этот режим прописан в Стандарте для десятичных чисел с плавающей запятой, и я думал, что банковская система должна работать по этому варианту округления, раз она работает с десятичными числами.
А разве я говорил где-то, что смотрится чётная цифра ПОСЛЕ округляемой? Вы что-то не то говорите. Цифра, которая в моих примерах подчёркивается — это так называемый round-bit (назовём его b), по его значению проверяем направление округления, есть ещё sticky-bit (s), который является логическим или над всеми остальными битами, идущими после round-bit. Далее смотрится та самая цифра, которая остаётся последней после округления это least-bit (l), именно она должна стать чётной в случае, если b=1 и s=0. Таким образом, имеем три бита lrs информации по которым однозначно определяем округление. Но я намеренно не хотел как-то путать читателей этими тремя битами, а постарался объяснить на словах.
Для трансцендентных функций никогда не бывает s=0, вы правы, там всегда будет какая-то единичка дальше. Проблема лишь в том, что мы можем не знать b=0 или b=1. Алгоритм может плясать от одного к другому и обратно, пока не стабилизируется. Думаю, вы правильно меня поняли, но мне просто слово банковское непонятно, не знаком с такой терминологией.
Да, возможно, но мне кажется, что это не очень правильно, потому что стандарты предполагается делать как бы вечными, а если ситуация в математике изменится и учёные научатся считать корректно до последнего бита, то придётся переписывать стандарт.
Стандарт есть, но в нём нет жёсткого требования о корректном округлении последнего бита (об этом сказано в статье), потому что обеспечить такое округление наука пока не в силах для всех случаев.
Верно, но бывают сложные формулы, где в промежутке могут возникать большие числа (возведение процентов в 365-ю степень, например) и запятая будет плавать. Для этого существует тип данных Decimal64, прописанный в Стандарте IEEE-754.
Ну можно и с фиксированной, однако есть же Стандарт IEEE-754, который описывает типы данных Decimal64, например как раз для этого дела. Причина проста. В финансовой математике действуют законы государства, прописанные в десятичной системе счисления. Например, если написано по закону, что, скажем, налог составляет 12.4 рубля, значит должно быть ровно столько, а когда мы воспользуемся типом данных binary64, будет (ближайшее число):
А это уже прямое нарушение закона. Когда выполняется множество действий с такими вот числами (видели, наверное, эти ипотечные формулы с возведением в 365-ю степень и прочее), тогда погрешность будет нарастать, и нарушение закона будет нарастать ещё больше. Как-то так, если кратко.
Тогда я не понимаю, чего вы хотите от меня, если всё что я хотел сказать, написано в статье. Я описал открытую научную проблему над которой учёные работают активно минимум 15 последних лет. Если вам показалось, что они зря тратят время, то лучше сказать об этом им, но не мне :)
Опять мы говорим о разном. Я же приводил пример с числами 1,999999 и 2,0. Прикладному программисту не важно, что у него получилось "почти два, но не совсем". Он округлит — и дело с концом. Разработчику библиотеки ВАЖНО, чтобы результат был корректно округлён до последнего бита, ему ВАЖНО получить именно 2,0 (в данном примере).
Благодарю за комментарий! Вы говорите о совершенно другой проблеме. Вы говорите о том, насколько точным будет итоговый результат после множества операций с числами с плавающей запятой. Эти вещи просчитываются аналитически и описаны в книге [3] (там есть оценки на погрешность при сложениях, умножениях и т. д.). Я же говорю о том, что вычислять значения элементарных функций нужно точно до последнего бита и причина необходимости делать это описана в последних абзацах.
А вот для обычных прикладных программистов эта проблема (описанная в статье) не важна. Им без разницы, что там с битами, им важно, чтобы конечный ответ был бы с определённой точностью. Между 51 и 52 битами точности для их целей может не быть разницы вообще.
Ох, так и быть, отвечу, нарушу своё обещание :)
Вы цитируете человека, который приписал мне то, чего я не говорил. Вот с ним, пожалуйста, и дискутируйте.
Хотя может это я не прав, не вижу, кому отвечаете. Тогда прошу прощения, не освоился, видимо :)
Потому что вы пытаетесь спорить с жаргонизмом. Все люди (из моего окружения), кто произносит фразу про удвоение правильных битов имеют в виду совершенно определённую вещь, то есть возведение погрешности в квадрат (при соблюдении ряда условий, и я об этом дважды предупредил). При этом все они понимают, что может не быть ни одной правильной цифры. Просто так говорят условно, и в большинстве случаев это и правда так. Это был мой последний ответ по данной теме в этой ветке комментариев.
Я дал вам источник, с которого можно начать разбираться. Дальше я рекомендую взять формулы, которые там участвуют, и проверить, что ваш пример в точности в них укладывается, либо убедиться, что вы сделали неправильный пример. Поскольку мы отклонились от темы статьи, я предлагаю на этом закончить.
Благодарю за дискуссию!
Откройте, пожалуйста, хотя бы википедию и посмотрите там раздел Proof of quadratic convergence for Newton's iterative method.
Квадратичная сходимость — это когда точность возводится в квадрат на каждой итерации. Про стабилизацию битов это не говорит. Про десятичные цифры тоже. Когда мы говорим про то, что количество битов удваивается, это не совсем правильные слова, а устоявшееся название, но все вроде понимают их смысл, кто в теме. Это как в математическом анализе, мы говорим "почти всюду", а имеем в виду "за исключением множества меры нуль". Вроде все понимают.
В вашем примере с корнем вы взяли очень далекое приближение, поэтому точность всё равно будет возрастать квадратично, но слишком долго приходится идти до первого правильного бита, то удвоение почти ничего не даст. Вопрос первого приближения очень важен, если взять не то число, алгоритм будет долго-долго тормозить сначала, что у вас и происходит.
Что-то я не понимаю. Какие такие гарантии точного знака? Не слышал. Метод Ньютона даёт, грубо говоря, удвоение знаков, но это жаргон такой, так просто принято говорить. В действительности он даёт возведение точности в квадрат по сравнению с предыдущим шагом. То есть, скажем, была точность 2 в минус 2, стала 2 в минус 4, потом 2 в минус 16.
Мне кажется, вы не понимаете суть. В моём примере чтобы получить точными ВСЕГО ДВА БИТА, неизвестно как долго ещё считать! Уже получили 41 бит после запятой, а всё ещё не знаем, какими точно будут ВСЕГО ДВА бита. А сколько ещё считать? Никто не знает! Это это незнание характерно для ВСЕХ алгоритмов всех трансцендентных функций, никаких гарантий никто никогда не давал.
Вот вы сами пишите: "соотвественно точность не достаточна".
Вопрос в том КОГДА она будет достаточной? Этого никто не знает.
Если хотите, я вам сейчас объясню подробнее. Допустим, нам нужно округлить корректно всего до двух битов после запятой. Перед нами два числа:
1,01011111111111111111111111111111111111111 → 1,01
1,01100000000000000000000000000000000000001 → 1,10
Между ними разница 2 в степени -40. Оба эти числа были получены в ходе вычислений пошаговым алгоритмом (одно на 100-м шаге, другое — на 101-м), которое из них по-вашему нужно взять в качестве достаточно-точного для того, чтобы сформировать правильное округление?
Как видим, 40 битов точности недостаточно, чтобы понять, с какой стороны мы от серединки. А сколько достаточно? Не знаем! Вот в этом и состоит суть проблемы TMD.
Благодарю за пояснение, я вообщем-то с десятичными числами не знаком особо, просто привёл примеры, которые на слуху. Если бы у меня была такая задача, то как вы и говорите, считал бы в рациональных числах. В большинстве случаев там скорость не важна.
Как это нет вопросов? :) Я же столько написал о том, что мы НЕ ЗНАЕМ, с какой стороны мы от середины :)
Спасибо, буду знать, это это банковское округление :) А бывает ещё nearest-ties-to-away, это когда величина посередине округляется дальше от нуля. То есть это то, что у нас в математике принято: 12.5→13; 13.5→14. Именно этот режим прописан в Стандарте для десятичных чисел с плавающей запятой, и я думал, что банковская система должна работать по этому варианту округления, раз она работает с десятичными числами.
А разве я говорил где-то, что смотрится чётная цифра ПОСЛЕ округляемой? Вы что-то не то говорите. Цифра, которая в моих примерах подчёркивается — это так называемый round-bit (назовём его b), по его значению проверяем направление округления, есть ещё sticky-bit (s), который является логическим или над всеми остальными битами, идущими после round-bit. Далее смотрится та самая цифра, которая остаётся последней после округления это least-bit (l), именно она должна стать чётной в случае, если b=1 и s=0. Таким образом, имеем три бита lrs информации по которым однозначно определяем округление. Но я намеренно не хотел как-то путать читателей этими тремя битами, а постарался объяснить на словах.
Для трансцендентных функций никогда не бывает s=0, вы правы, там всегда будет какая-то единичка дальше. Проблема лишь в том, что мы можем не знать b=0 или b=1. Алгоритм может плясать от одного к другому и обратно, пока не стабилизируется. Думаю, вы правильно меня поняли, но мне просто слово банковское непонятно, не знаком с такой терминологией.
Благодарю за поправку :)
Да, возможно, но мне кажется, что это не очень правильно, потому что стандарты предполагается делать как бы вечными, а если ситуация в математике изменится и учёные научатся считать корректно до последнего бита, то придётся переписывать стандарт.
Стандарт есть, но в нём нет жёсткого требования о корректном округлении последнего бита (об этом сказано в статье), потому что обеспечить такое округление наука пока не в силах для всех случаев.
В таком случае благодарю за полезные комментарии!
Верно, но бывают сложные формулы, где в промежутке могут возникать большие числа (возведение процентов в 365-ю степень, например) и запятая будет плавать. Для этого существует тип данных Decimal64, прописанный в Стандарте IEEE-754.
Ну можно и с фиксированной, однако есть же Стандарт IEEE-754, который описывает типы данных Decimal64, например как раз для этого дела. Причина проста. В финансовой математике действуют законы государства, прописанные в десятичной системе счисления. Например, если написано по закону, что, скажем, налог составляет 12.4 рубля, значит должно быть ровно столько, а когда мы воспользуемся типом данных binary64, будет (ближайшее число):
12.4000000000000003552713678800500929355621337890625
А это уже прямое нарушение закона. Когда выполняется множество действий с такими вот числами (видели, наверное, эти ипотечные формулы с возведением в 365-ю степень и прочее), тогда погрешность будет нарастать, и нарушение закона будет нарастать ещё больше. Как-то так, если кратко.
Тогда я не понимаю, чего вы хотите от меня, если всё что я хотел сказать, написано в статье. Я описал открытую научную проблему над которой учёные работают активно минимум 15 последних лет. Если вам показалось, что они зря тратят время, то лучше сказать об этом им, но не мне :)
Опять мы говорим о разном. Я же приводил пример с числами 1,999999 и 2,0. Прикладному программисту не важно, что у него получилось "почти два, но не совсем". Он округлит — и дело с концом. Разработчику библиотеки ВАЖНО, чтобы результат был корректно округлён до последнего бита, ему ВАЖНО получить именно 2,0 (в данном примере).
Денежные расчёты принято делать в десятичной арифметике с плавающей запятой. Если будет интересно, объясню почему.
Благодарю за комментарий! Вы говорите о совершенно другой проблеме. Вы говорите о том, насколько точным будет итоговый результат после множества операций с числами с плавающей запятой. Эти вещи просчитываются аналитически и описаны в книге [3] (там есть оценки на погрешность при сложениях, умножениях и т. д.). Я же говорю о том, что вычислять значения элементарных функций нужно точно до последнего бита и причина необходимости делать это описана в последних абзацах.
А вот для обычных прикладных программистов эта проблема (описанная в статье) не важна. Им без разницы, что там с битами, им важно, чтобы конечный ответ был бы с определённой точностью. Между 51 и 52 битами точности для их целей может не быть разницы вообще.