В рекурсивном цикле, почему это значение меняется?

Question

У моего профессора есть программа, которая берет семена и функцию и рекурсивно выводит и вводит значение оттуда.

Основная идея состоит в том, что у вас есть f (x), и вы начинаете с x_0, так что f (x_0) = x_1. Тогда у вас есть x_2 = f (x_1) и так далее, что x_n = f (x_ {n-1}).

В любом случае, иногда вы можете получить такие циклы. Например Пусть F (х) = 2х мод 1.

В программе можно ввести 0,2 и ожидать, что цикл: (0,2, 0,4, 0,3, 0,6, 0,2, ...)

Но в конце концов, его программа делает что-то странное .. вокруг 50-й итерации вы получаете 0.20001, где вы ожидаете 0,2, то из-за этого программа вырывается из цикла и достигает 1, а затем вы получаете все выходы 0 после этого.

Я предполагаю, что это имеет какое-то отношение к тому, как компьютеры приближаются к значениям, но я просто не понимаю, почему он в конечном итоге рассчитает 0.20001 вместо 0,2. Может ли кто-нибудь дать мне техническое объяснение этому?

Answer 1

Арифметика с плавающей точкой является детерминированной (*).

Вы считаете, что вы видите начальную периодическую фазу, которая затем изменяется на что-то другое («0.2, 0.4, 0.3, 0.6, 0.2»), но если вы напечатали значения с достаточной точностью (используйте формат %.16e, если вы используют C или C-подобный язык), вы увидите, что первый «0,2» не совпадает со вторым «0,2».

Если какое-либо значение действительно повторялось в течение первой фазы, то последовательность была бы периодической и все остальные значения повторялись бы бесконечно, как и следовало ожидать.

---

(*) Если вы не программируете на языке, с точно в момент компиляции и дрянной семантике с плавающей точкой. Java может быть скомпилирована точно в срок, но значение операций с плавающей запятой определяется довольно строго, и операции должны реализовать это определение до и после компиляции точно в срок, не оставляя места для странного поведения, подобного этому. Определение C# операций с плавающей запятой достаточно странно, что через некоторое время программа может изменить поведение из-за компиляции точно в момент, но это, вероятно, единственный широко используемый язык с такими ужасными свойствами.