?

Log in

No account? Create an account

Вычислительная машина должна вычислять - Ваши рубидии уже у кобальта во ртути

Dec. 6th, 2018

09:51 am - Вычислительная машина должна вычислять

Previous Entry Share Next Entry

Загадка для программистов (не для математиков, потому что числа с плавающей точкой выше их понимания):

Пусть T - некий тип чисел с плавающей точкой, и a, b, s, t, z - переменные типа Т.

Дана последовательность операторов

s := a + b
z := s - a
t := b - z


Чему равно t?

Познавательная статья о том, как делаются вычисления с плавающей точкой с двойной точностью, включая формальные оценки.

This entry was originally posted at https://spamsink.dreamwidth.org/1103357.html. Please comment there using OpenID.

Tags:

Comments:

[User Picture]
From:ilya_dogolazky
Date:December 6th, 2018 06:35 pm (UTC)
(Link)
я бы сказал А и Бэ можно подобрать так чтоб Тэ стало произвольным наперёд заданным (ну может почти произвольным)
(Reply) (Thread)
From:pigdeon
Date:December 6th, 2018 07:10 pm (UTC)
(Link)
Компьютеры работают более-менее правильно, поэтому Т по-модулю не может превосходить 1 lsb мантиссы c максимальным (без модуля) порядком чисел (a, b).
(Reply) (Parent) (Thread)
[User Picture]
From:hahi
Date:December 6th, 2018 07:03 pm (UTC)
(Link)
Судя по форме вопроса, ноль - неверный ответ :) С интересом попробую понять, почему :)
(Reply) (Thread)
[User Picture]
From:alextr98
Date:December 6th, 2018 07:23 pm (UTC)

Судя по форме вопроса, ноль - неверный ответ :)

(Link)
Может быть и ноль.
Предположим, всё в двоичной систем.
Тогда, например,
2 + 4 = 6.
6 - 2 = 4
4 - 4 = 0
(Reply) (Parent) (Thread)
[User Picture]
From:spamsink
Date:December 6th, 2018 08:58 pm (UTC)
(Link)
Короткий ответ: потому что числа с плавающей точной и вещественные числа - две большие разницы. Длинный ответ в статье. :)
(Reply) (Parent) (Thread)
[User Picture]
From:move2winnipeg
Date:December 6th, 2018 07:06 pm (UTC)
(Link)
t shuold be very small
(Reply) (Thread)
[User Picture]
From:spamsink
Date:December 6th, 2018 08:51 pm (UTC)
(Link)
Ну да.
(Reply) (Parent) (Thread)
[User Picture]
From:move2winnipeg
Date:December 6th, 2018 11:51 pm (UTC)
(Link)
Вы не представляете, какую я битву по поводу плавающей точки я вынес после каких-то там выборов в РФ. Там на одной табличке все проценты, сложенные вместе, давали вроде 100.4%, а я заметил, что это может быть погрешность в компьютере. И мне, оголтелому антисоветчику и борцу с режимом пришлось этот режим защищать. Но либерально настроенные граждане так и не смогли принять идею, что дважды два иногда может быть 3.9999... Зато радостно поведали, что Пи в военное время может достигать четырёх гыгыгы.
(Reply) (Parent) (Thread)
[User Picture]
From:spamsink
Date:December 7th, 2018 12:17 am (UTC)
(Link)
Не в компьютере, конечно (чтобы уже в 4-й значащей цифре была ошибка при сложении неотрицательных чисел, нужен ну очень паршивый компьютер), а во входных данных. Мало ли сколько было округлений вниз, а сколько - вверх.

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

Edited at 2018-12-07 12:19 am (UTC)
(Reply) (Parent) (Thread)
[User Picture]
From:move2winnipeg
Date:December 7th, 2018 01:03 am (UTC)
(Link)
Я понимаю, что .4 это огромная ощибка, которая не отличается от 146% :)
Мало ли сколько и каких там операций было. А может один раз криво округлили, а до этого всё идеально было.
Но дискуссия там вообще не о том была. В основном обсуждалось ка плохо быть (мне) трёхрублёвой кремлёвской проституткой.
(Reply) (Parent) (Thread)
[User Picture]
From:alexanderr
Date:December 6th, 2018 08:00 pm (UTC)
(Link)
ну, тут широкое поле возможностей. во-первых, все эти числа имеют конечную точность.
т.е. если я спрошу чему равно 1е100 - 1e(-100). всегда возможны ошибки округления.

во-вторых, кроме минимального размера числа есть еще и максимальный.    overflow может произойти уже
на первом шаге.

NaN
(Reply) (Thread)
[User Picture]
From:spamsink
Date:December 6th, 2018 08:53 pm (UTC)
(Link)
Вопрос задается в предположении, что исходные числа не Inf и не NaN, и что результат сложения не приводит к переполнению.
(Reply) (Parent) (Thread)
[User Picture]
From:move2winnipeg
Date:December 7th, 2018 01:07 am (UTC)
(Link)
a <- int(a)
;)
(Reply) (Parent) (Thread)
From:rezkiy
Date:December 6th, 2018 08:52 pm (UTC)
(Link)
нулю конечно :-)

https://godbolt.org/z/9o-t1M
(Reply) (Thread)
[User Picture]
From:spamsink
Date:December 6th, 2018 08:55 pm (UTC)
(Link)
С -ffast-math - это не "конечно", а "если очень хочется". :-)
(Reply) (Parent) (Thread)
From:pigdeon
Date:December 7th, 2018 02:19 am (UTC)
(Link)
Математикам эта проблема также должна быть знакома. Ведь в матане есть специальная лемма, что 0.(9) == 1.0 - т.е. любая конечная запись числа порождает потерю точности (содержит ошибку представления). Компьютеры всего лишь предоставили возможность всем желающим убедиться в этом печальном факте.
(Reply) (Thread)
[User Picture]
From:spamsink
Date:December 7th, 2018 03:19 am (UTC)
(Link)
Точнее будет сказать, что для любого нецелого числа найдется такое основание, что любая конечная запись этого числа в этом основании будет с потерей точности.


(Reply) (Parent) (Thread)
[User Picture]
From:fatoff
Date:December 7th, 2018 04:27 am (UTC)
(Link)
Не глядя в ответы: чегой-то там типа numerical_limits::epsilon.
(Reply) (Thread)
[User Picture]
From:spamsink
Date:December 7th, 2018 05:55 am (UTC)
(Link)
Может оказаться в некоторых случаях, но ответить можно и более детально.
(Reply) (Parent) (Thread)
[User Picture]
From:fatoff
Date:December 8th, 2018 04:24 am (UTC)
(Link)
Оптмизатор должен породить более определённый 0.
(Reply) (Parent) (Thread)
[User Picture]
From:spamsink
Date:December 8th, 2018 04:54 am (UTC)
(Link)
Какой ещё оптимизатор? Речь не идёт ни о каком языке программирования.
(Reply) (Parent) (Thread)
[User Picture]
From:archaicos
Date:December 7th, 2018 12:57 pm (UTC)
(Link)
Ага-ага. Но только толку-то. Вдруг оказывается, что компилятор по собственной инициативе тебе подставляет FMA, не поддерживая при этом #pragma STDC FP_CONTRACT. И вроде бы везде железо по стандарту IEEE-754/784, а результат разный, как у дедов в прошлом веке. Как будто и стандартов не было. И это даже не на православном x87, где нужно переключать точность, и все забывают или забивают. Тьфу.


Edited at 2018-12-07 12:59 pm (UTC)
(Reply) (Thread)
[User Picture]
From:spamsink
Date:December 8th, 2018 07:59 am (UTC)
(Link)
Вопрос был про абстрактные операции с плавающей точкой, а не про реализацию языка программирования.
(Reply) (Parent) (Thread)