Ошибки округления
1) Если посчитать на калькуляторе NumLock Calculator вот что -
100000000+0,1-100000000, то получим 0,09999999999854.
2) 25-го февраля 1991 г. ракетный комплекс Патриот не смог перехватить иракский Скад, и тот, попав в казармы, убил 28 и ранил более сотни борцов за Демократию.
Казалось, какая тут связь? А она в том, что число 0.1 в компьютере является бесконечной дробью.
"Причина этого была в неверном вычислении времени с момента включения компьютера, связанном с ошибкой округления при комьютерных арифметических операциях.
Внутренний таймер отсчитывает время в десятых долях секунды, (т.е. счетчик таймера это целое число) и поэтому для того, чтобы получить время в секундах, это значение умножалось на 1/10. Для этой операции использовался 24-битный регистр.
Но число 0.1 в двоичном представлении является бесконечной дробью
(1/10=1/24+1/25+1/28+1/29+1/212+1/213+...)
и поэтому по помещении в 24-битный регистр округляется. Эта маленькая ошибка округления, умноженная на большое количество десятых долей секунды, дала более серьезную ошибку -
Т.к. двоичное представление 1/10 - бесконечная дробь 0.0001100110011001100110011001100...., то в 24-х битный регистр запишется округление 0.00011001100110011001100, а хвост 0.0000000000000000000000011001100... - в двоичном виде - или около 0.000000095 в десятичном, будет отброшен. За примерно 100 часов работы системы ошибка составит 0.000000095х100х60х60х10=0.34 секунды.
Скад же летит со скоростью 1.676 м/сек, и за это время разминулся более чем на полкилометра с его ожидаемым положением."
(с) вольный перевод отсюда - http://www.ima.umn.edu/~arnold/disasters/patriot.html
Еще намного про компьютерные ошибки -
3) "On June 4, 1996 an unmanned Ariane 5 rocket launched by the European Space Agency exploded just forty seconds after its lift-off from Kourou, French Guiana.
...
Specifically a 64 bit floating point number relating to the horizontal velocity of the rocket with respect to the platform was converted to a 16 bit signed integer. The number was larger than 32,767, the largest integer storeable in a 16 bit signed integer, and thus the conversion failed."
(с) http://www.ima.umn.edu/~arnold/disasters/ariane.html
4) "Так, установка Therac-25(*) вполне корректно работала в течение нескольких лет до первого переоблучения; и последующие зафиксированные инциденты происходили спорадически в течение 2.5 лет на общем "нормальном" фоне. NASA инвестировала огромные средства и ресурсы в верификацию и сопровождение программного обеспечения для космических кораблей Shuttle. Несмотря на это, за 10-летие с 1980 г. - времени начала использования ПО - выявлено 16 ошибок "первой степени серьезности" (способных привести к "потере корабля и/или экипажа"). Восемь из этих ошибок не были обнаружены своевременно и присутствовали в коде во время полетов, хотя, к счастью, без последствий.
____
(*)В 1985-87 гг. 6 человек получили смертельную дозу облучения во время сеансов радиационной терапии с применением медицинского ускорителя Therac-25 (количество пациентов, также подвергшихся переоблучению, но выживших, точно не известно). "
(с) http://www.osp.ru/os/1998/06/179592/
А разгадка одна - безблагодатность -
1) "Сама мысль о том, что человек может испытывать удовлетворение от хорошо выполненной работы - просто потому, что эта работа творческая и профессиональная, признана абсурдной.
...
Я знаю одного очень крупного производителя ПО, который декларировал, что у него проектирование занимает 20% от времени разработки, а (условно говоря) отладка - остающиеся 80%. Те, кто ратует за обратное соотношение этих величин, не только убедительно доказали, что это реалистично, но и показали, что это улучшило бы тусклый имидж фирмы."
(с) http://www.osp.ru/os/1998/01/179366/
2) "When I began to program an electronic computer in 1953, von Neumann was
still disparaging floating-point computation, which was generally deemed impervious to
error-analysis. Occasional anomalous results were expected. Often they were attributed
wrongly to “Ill-Condition”. Putting one’s data through several numerical methods some
of whose results might agree was a prudent policy. Those days are back. Their challenges
will be illustrated by a program like some used by structural engineers for forty years. To
cope, we need debugging aids like those in §14 of my web page’s <…/Mindless.pdf>."
(c) http://www.cs.berkeley.edu/~wkahan/BASCD08K.pdf
Казалось бы, со времен 1953-го года тип данных с плавающей точкой стал аж двойной точности, что означает 19-20 десятичных разрядов. Хотя как сказать,
"В малых ЭВМ серии МИР (МИР-1, МИР-2, МИР-3) удалось полностью осуществить аппаратурную реализацию языков высокого уровня. Структурная интерпретация языков высокого уровня МИР и АНАЛИТИК позволила получить эффективную реализацию работы с вещественными числами произвольной разрядности, целыми числами неограниченной разрядности и точных операций над дробными рациональными числами и др. В машине МИР-2 операции выполнялись не только над числами, но и над произвольными алгебраическими выражениями, которые рассматривались с точностью до основных соотношений алгебры анализа (включая соотношения для трансцендентных функций). Структурная реализация аналитических преобразований обеспечила настолько существенное повышение производительности, что для целого ряда конкретных аналитических задач время их решения на ЭВМ МИР-2 оказалось сравнимым со временем решения на машинах традиционной архитектуры с номинальным быстродействием, в сотни раз превосходящим быстродействие МИР-2."
(с) http://www.iprinet.kiev.ua/gf/mir.htm
"В 1965 году в Киеве была создана одна из наиболее уникальных таких ЭВМ - МИР-1
...
Чтобы скрыть недостаток финансирования (точнее, его следствие - малый объем памяти), по умолчанию разрядность равнялась 6 (десятичным разрядам). Однако многие задачи решались при разрядности 9, 10, 12, а то и 18-20 разрядов. Отдельные задачи решались при разрядности 100."
(c) http://reactivmen.narod.ru/gl11/index36.htm
3) ...
но зато увеличилась память и быстродействие, следовательно, число операций, и, как было проиллюстрировано в абзаце №2, ошибки округления никуда не делись.
Остаются принципиальные источники ошибок, слабо зависящие от разрядности - "грязный ноль", вычитание близких чисел или сложение далеких друг ото друга чисел, подробнее тут -
http://www.softelectro.ru/ieee754.html
или знакопеременные ряды, подробнее тут -
Д. MAKKPAKEH, У. ДОРН "ЧИСЛЕННЫЕ МЕТОДЫ И ПРОГРАММИРОВАНИЕ на ФОРТРАНЕ", пар. 2.1
(Знакопеременые ряды - это измышление дьявола (с)Харди, по памяти)
или "За 20 шагов (j=20) 24-я гармоника увеличится в 2.3* 10^14 раз. Поэтому достаточно иметь в начальном условии ошибку всего лишь в 14 знаке после запятой, чтобы на 20 шаге она сделала неверными все цифры вплоть до единиц перед запятой."
(c) http://www.spbstu.ru/publications/m_v/N_002/Sushkova/par_06.html
Это краткий результат поиска какой-нибудь библиотеки, которая контролировала бы ошибки округления и их распространение. Числу сопоставляется не только его значение, но и его точность, чтоб у результата было, например, также св-во доверительного числа знаков после запятой.
Как распространяются и накапливаются ошибки, хорошо написано у Маккракена.
Интересно, что за эффект работает тут - http://pinochet.livejournal.com/54110.html#cutid1
100000000+0,1-100000000, то получим 0,09999999999854.
2) 25-го февраля 1991 г. ракетный комплекс Патриот не смог перехватить иракский Скад, и тот, попав в казармы, убил 28 и ранил более сотни борцов за Демократию.
Казалось, какая тут связь? А она в том, что число 0.1 в компьютере является бесконечной дробью.
"Причина этого была в неверном вычислении времени с момента включения компьютера, связанном с ошибкой округления при комьютерных арифметических операциях.
Внутренний таймер отсчитывает время в десятых долях секунды, (т.е. счетчик таймера это целое число) и поэтому для того, чтобы получить время в секундах, это значение умножалось на 1/10. Для этой операции использовался 24-битный регистр.
Но число 0.1 в двоичном представлении является бесконечной дробью
(1/10=1/24+1/25+1/28+1/29+1/212+1/213+...)
и поэтому по помещении в 24-битный регистр округляется. Эта маленькая ошибка округления, умноженная на большое количество десятых долей секунды, дала более серьезную ошибку -
Т.к. двоичное представление 1/10 - бесконечная дробь 0.0001100110011001100110011001100...., то в 24-х битный регистр запишется округление 0.00011001100110011001100, а хвост 0.0000000000000000000000011001100... - в двоичном виде - или около 0.000000095 в десятичном, будет отброшен. За примерно 100 часов работы системы ошибка составит 0.000000095х100х60х60х10=0.34 секунды.
Скад же летит со скоростью 1.676 м/сек, и за это время разминулся более чем на полкилометра с его ожидаемым положением."
(с) вольный перевод отсюда - http://www.ima.umn.edu/~arnold/disasters/patriot.html
Еще намного про компьютерные ошибки -
3) "On June 4, 1996 an unmanned Ariane 5 rocket launched by the European Space Agency exploded just forty seconds after its lift-off from Kourou, French Guiana.
...
Specifically a 64 bit floating point number relating to the horizontal velocity of the rocket with respect to the platform was converted to a 16 bit signed integer. The number was larger than 32,767, the largest integer storeable in a 16 bit signed integer, and thus the conversion failed."
(с) http://www.ima.umn.edu/~arnold/disasters/ariane.html
4) "Так, установка Therac-25(*) вполне корректно работала в течение нескольких лет до первого переоблучения; и последующие зафиксированные инциденты происходили спорадически в течение 2.5 лет на общем "нормальном" фоне. NASA инвестировала огромные средства и ресурсы в верификацию и сопровождение программного обеспечения для космических кораблей Shuttle. Несмотря на это, за 10-летие с 1980 г. - времени начала использования ПО - выявлено 16 ошибок "первой степени серьезности" (способных привести к "потере корабля и/или экипажа"). Восемь из этих ошибок не были обнаружены своевременно и присутствовали в коде во время полетов, хотя, к счастью, без последствий.
____
(*)В 1985-87 гг. 6 человек получили смертельную дозу облучения во время сеансов радиационной терапии с применением медицинского ускорителя Therac-25 (количество пациентов, также подвергшихся переоблучению, но выживших, точно не известно). "
(с) http://www.osp.ru/os/1998/06/179592/
А разгадка одна - безблагодатность -
1) "Сама мысль о том, что человек может испытывать удовлетворение от хорошо выполненной работы - просто потому, что эта работа творческая и профессиональная, признана абсурдной.
...
Я знаю одного очень крупного производителя ПО, который декларировал, что у него проектирование занимает 20% от времени разработки, а (условно говоря) отладка - остающиеся 80%. Те, кто ратует за обратное соотношение этих величин, не только убедительно доказали, что это реалистично, но и показали, что это улучшило бы тусклый имидж фирмы."
(с) http://www.osp.ru/os/1998/01/179366/
2) "When I began to program an electronic computer in 1953, von Neumann was
still disparaging floating-point computation, which was generally deemed impervious to
error-analysis. Occasional anomalous results were expected. Often they were attributed
wrongly to “Ill-Condition”. Putting one’s data through several numerical methods some
of whose results might agree was a prudent policy. Those days are back. Their challenges
will be illustrated by a program like some used by structural engineers for forty years. To
cope, we need debugging aids like those in §14 of my web page’s <…/Mindless.pdf>."
(c) http://www.cs.berkeley.edu/~wkahan/BASCD08K.pdf
Казалось бы, со времен 1953-го года тип данных с плавающей точкой стал аж двойной точности, что означает 19-20 десятичных разрядов. Хотя как сказать,
"В малых ЭВМ серии МИР (МИР-1, МИР-2, МИР-3) удалось полностью осуществить аппаратурную реализацию языков высокого уровня. Структурная интерпретация языков высокого уровня МИР и АНАЛИТИК позволила получить эффективную реализацию работы с вещественными числами произвольной разрядности, целыми числами неограниченной разрядности и точных операций над дробными рациональными числами и др. В машине МИР-2 операции выполнялись не только над числами, но и над произвольными алгебраическими выражениями, которые рассматривались с точностью до основных соотношений алгебры анализа (включая соотношения для трансцендентных функций). Структурная реализация аналитических преобразований обеспечила настолько существенное повышение производительности, что для целого ряда конкретных аналитических задач время их решения на ЭВМ МИР-2 оказалось сравнимым со временем решения на машинах традиционной архитектуры с номинальным быстродействием, в сотни раз превосходящим быстродействие МИР-2."
(с) http://www.iprinet.kiev.ua/gf/mir.htm
"В 1965 году в Киеве была создана одна из наиболее уникальных таких ЭВМ - МИР-1
...
Чтобы скрыть недостаток финансирования (точнее, его следствие - малый объем памяти), по умолчанию разрядность равнялась 6 (десятичным разрядам). Однако многие задачи решались при разрядности 9, 10, 12, а то и 18-20 разрядов. Отдельные задачи решались при разрядности 100."
(c) http://reactivmen.narod.ru/gl11/index36.htm
3) ...
но зато увеличилась память и быстродействие, следовательно, число операций, и, как было проиллюстрировано в абзаце №2, ошибки округления никуда не делись.
Остаются принципиальные источники ошибок, слабо зависящие от разрядности - "грязный ноль", вычитание близких чисел или сложение далеких друг ото друга чисел, подробнее тут -
http://www.softelectro.ru/ieee754.html
или знакопеременные ряды, подробнее тут -
Д. MAKKPAKEH, У. ДОРН "ЧИСЛЕННЫЕ МЕТОДЫ И ПРОГРАММИРОВАНИЕ на ФОРТРАНЕ", пар. 2.1
(Знакопеременые ряды - это измышление дьявола (с)Харди, по памяти)
или "За 20 шагов (j=20) 24-я гармоника увеличится в 2.3* 10^14 раз. Поэтому достаточно иметь в начальном условии ошибку всего лишь в 14 знаке после запятой, чтобы на 20 шаге она сделала неверными все цифры вплоть до единиц перед запятой."
(c) http://www.spbstu.ru/publications/m_v/N_002/Sushkova/par_06.html
Это краткий результат поиска какой-нибудь библиотеки, которая контролировала бы ошибки округления и их распространение. Числу сопоставляется не только его значение, но и его точность, чтоб у результата было, например, также св-во доверительного числа знаков после запятой.
Как распространяются и накапливаются ошибки, хорошо написано у Маккракена.
Интересно, что за эффект работает тут - http://pinochet.livejournal.com/54110.html#cutid1