22 февр. 2013 г.

О точных вычислениях

Добрый день.

Любите ли вы разные представления вещественных чисел в компьютере так, как люблю их я? Считаете ли вы Excel стабильным и более-менее надёжным приложением? (А ведь иногда в нём ведут бухгалтерию небольших организаций... Да и мы не так давно задачку решали.)

А давайте проведём быстрый эксперимент! Если у вас есть на компьютере Excel или другой табличный процессор, то попробуйте сделать следующее:
- поместите в ячейку A1 число 0.1,
- под ней (в ячейку A2) вставьте формулу «=1001*A1-100» (как на картинке справа),
- обратите внимание на то, что в ячейке A2 вычислилось как раз значение 0.1 (как и должно было быть: 1001*0.1-100=0.1),
- подумайте, что будет, если «растянуть» эту ячейку вниз (т.е. распространить действие этой формулы на следующие ячейки),
- может показаться, что мы будем всего лишь многократно применять одну и ту же операцию (умножать на 1001 и вычитать 100) к одному и тому же числу (0.1), поэтому во всех остальных ячейках должно получиться наше исходное число 0.1,
- посомневайтесь чуть-чуть,
- а теперь проведите эксперимент.

Получилось странно? Вы именно этого и ожидали? Поздравляю, у вас отличная интуиция!

Значения, которые получились у меня:
A1: 0.1 (с этого начинаем)
A2: 0.1
A3: 0.1
A4: 0.1
A5: 0.1
A6: 0.109 (всего через 5 шагов ошибка уже 9%)
A7: 8.669
A8: 8577

Всего за несколько шагов мы улетели от начального числа 0.1 в заоблачные дали.

Мораль: иногда довольно простые вычисления порождают огромную ошибку. Представьте, что кто-то подобным образом рассчитывает платежи по кредиту, но не понимает, когда и почему можно доверять компьютеру, а когда компьютер «обманет» (и, кстати, правильно сделает).

Если вас заинтересовала эта тема, то, скорее всего, вы захотите прочитать короткий раздел «ошибка в процессоре intel pentium» из книги «Наука отладки» (авторы Мэтт Тэллес, Юань Хсих):
В 1993 году корпорация Intel представила новый процессор Pentium™, который обещал стать самым лучшим процессором на рынке персональных компьютеров в то время. Через год после выпуска профессор Томас Найсели (Thomas Nicely) из Линчбергского колледжа (Lynchburg College) обнаружил ошибку и сообщил о ней в Intel. Это стало совершенным кошмаром для Intel, и в конечном итоге фирма согласилась заменять микросхему автоматически по требованию... (читать дальше всю главу)

Идея заметки была подсмотрена в блоге «Десять букв».

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

Если вам понравился этот эффект, пожалуйста, поделитесь ссылкой на заметку в Twitter, Google+, Facebook или Вконтакте. Спасибо!

Хороших выходных!

13 комментариев:

  1. К слову в LibreOffice Calc и таблицах Google Docs результат аналогичный.
    Для желающих ещё раз проверить свою интуицию:
    Изменится ли что-то, если вместо 0.1 и 1001*An-100 взять 0.125 и 1001*An-125? Почему?

    ОтветитьУдалить
    Ответы
    1. Спасибо за формулировку правильного вопроса!

      Удалить
  2. Анонимный22.02.2013, 14:03

    попробуйте еще в соседней колонке, начиная с B2 ввести =A2-A1 и продлите далее по всей колонке формулу.

    ОтветитьУдалить
  3. Это, кстати, также довольно частая ошибка начинающих программистов. Еще возможны варианты, когда (условно) 0.123 ≠ 0.123 или 0.2 + 0.2 ≠ 0.4

    Неплохое разъяснение такого поведения можно найти, например, в этой статье: http://www.delphikingdom.com/asp/viewitem.asp?catalogid=374

    ОтветитьУдалить
  4. Анонимный22.02.2013, 16:28

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

    0.1(10) = 0.(00011)(2)

    Отсюда и неточность. Выход - использовать целые числа (т.е. считать деньги в копейках) или специальные типы данных.

    ОтветитьУдалить
  5. Анонимный22.02.2013, 17:22

    Присвоить ячейкам тип "scientific" и включить соответствие внутренней точности отображаемой. Хотя эксель, конечно, пожалуется, что мы теряем точность.

    ОтветитьУдалить
  6. Анонимный23.02.2013, 00:57

    О да. Недавно как раз столкнулась со связкой эксель+бухгалтерия. Заказчики выгрузили список имущества для переоценки, 106 тысяч строк, разница между числами до 6 порядков. И, естественно, искренне не могли понять, почему от сортировки строк итоговая сумма меняется на несколько копеек. Вот просто в голову такое не может прийти, компьютер — он же точный!
    К счастью, во всяких 1С используют тип с фиксированной запятой, там такого безобразия не будет.

    ОтветитьУдалить
  7. Результаты арифметических операций с плавающей точкой в Excel могут быть неточными
    http://support.microsoft.com/kb/78113

    ОтветитьУдалить
  8. Анонимный24.02.2013, 14:17

    Погрешность есть уже в четвертой строчке - через три шага:
    1. 0,1
    2. 0,1
    3. 0,1
    4. 0,1000000085
    5. 0,1000085521

    ОтветитьУдалить
    Ответы
    1. Погрешность уже во второй строчке есть, просто её вам не показывают (можно настроить, сколько знаков отображать).
      Если б погрешности при переходе от первой ко второй строке не возникало, то не трудно понять, что её не возникло бы никогда.

      Удалить
    2. Я больше скажу — погрешность есть уже в самой первой строчке. Как известно, машина считает в двоичной системе. А в ней конечной дробью могут быть записаны только рациональные числа со знаменателем, равным степени двойки. То есть 0,1 при переводе из десятичной системы в двоичную превратится в бесконечную дробь. А значит, в памяти компьютера будет находится не точно 0,1, а какое-то 0,1+eps (греч. «эпсилон» — традиционное обозначение малого числа в математике).
      Отсюда нетрудно понять, почему погрешность быстро возрастает. Подставим 0,1+eps в нашу формулу:
      1001*(0,1+eps)-100 = 100,1 + 1001*eps - 100 = 0,1 + 1001*eps,
      то есть на каждом шаге погрешность увеличится примерно в тысячу раз (точно 1001 в раз, если бы дальнейшие вычисления были совершенно точными). Это и видно в результатах: через пять шагов ошибка около 9%, через шесть — почти в 90 раз (т.е. около 9000%), через семь — почти в 90000 раз (9 млн.проц.) и так с каждым шагом на три порядка. Это то, что в математике называется неустойчивостью. Формула воспроизводила бы 0,1 бесконечное число раз, только если бы начальное приближение было равно в точности 0,1 (а в двоичном представлении с конечным числом разрядов это невозможно) и все последующие вычисления также были бы совершенно точны. Но стоит появиться небольшой погрешности — она неограниченно возрастает и со временем всё собой заполняет.

      Удалить
    3. Анонимный23.12.2013, 20:58

      погрешность уже сразу во второй строчке 1,000000000000009

      Удалить
  9. Анонимный26.05.2015, 10:36

    Ссылка по теме: http://habrahabr.ru/post/258483/

    ОтветитьУдалить

Понравилась заметка? Подпишитесь на RSS-feed или email-рассылку.

Хотите поделиться ссылкой с другими? Добавьте в закладки:



Есть вопросы или предложения? Пишите письма на адрес mytribune АТ yandex.ru.

С уважением,
      Илья Весенний