Почему десятичные числа не могут быть представлены точно в двоичном виде?

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

Что я не понимаю, так это то, почему с математической точки зрения числа справа от десятичной запятой более «особенные», чем те, что слева?

Например, число 61.0 имеет точное двоичное представление, потому что целая часть любого числа всегда точна. Но число 6.10 не является точным. Все, что я сделал, это переместил десятичное число на одно место, и внезапно я перешел из Экзактопии в Инэктактвиль. Математически не должно быть никакой разницы между двумя числами - это просто числа.

В отличие от этого, если я переместу десятичное число на одно место в другом направлении, чтобы получить число 610, я все еще нахожусь в Exactopia. Я могу продолжать двигаться в этом направлении (6100, 610000000, 610000000000000), и они все еще точны, точны, точны. Но как только десятичное число пересекает некоторый порог, числа перестают быть точными.

В чем дело?

Изменить: чтобы уточнить, я хочу держаться подальше от обсуждения стандартных представлений, таких как IEEE, и придерживаться того, что я считаю математически "чистый" способ. В базе 10 позиционные значения:

... 1000  100   10    1   1/10  1/100 ...

В двоичном виде они будут:

... 8    4    2    1    1/2  1/4  1/8 ...

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

Числа Десятичные могут быть представлены точно, если у вас есть достаточно мест - просто не плавающая двоичные числа точки. Если вы используете тип с плавающей запятой (например, System.Decimalв .NET), то множество значений, которые не могут быть точно представлены в двоичной форме с плавающей запятой, могут быть точно представлены.

Давайте посмотрим на это по-другому - в базе 10, с которой вы, вероятно, будете чувствовать себя комфортно, вы не можете точно выразить 1/3. Это 0.3333333 ... (периодически). Причина, по которой вы не можете представить 0.1 как двоичное число с плавающей запятой, по той же причине. Вы можете представлять 3, 9 и 27 точно, но не 1/3, 1/9 или 1/27.

Проблема в том, что 3 - это простое число, которое не является коэффициентом 10. Это не проблема, если вы хотите умножить число на 3: вы всегда можете умножить на целое число, не сталкиваясь с проблемами. Но когда вы делите на число, которое является простым и не является фактором вашей базы, вы можете столкнуться с проблемой (и это произойдет , если вы попытаетесь разделить 1 на это число).

Хотя 0,1 обычно используется в качестве простейшего примера точного десятичного числа, которое не может быть точно представлено в двоичном формате с плавающей запятой, возможно, 0,2 является более простым примером, поскольку он равен 1/5, а 5 - это простое число, которое вызывает проблемы между десятичным и двоичным числами. ,

Дополнительное примечание для решения проблемы конечных представлений:

Некоторые типы с плавающей десятичной запятой имеют фиксированный размер, как и System.Decimalдругие, такие java.math.BigDecimalкак «произвольно большие», но в какой-то момент они достигнут предела, будь то системная память или теоретический максимальный размер массива. Это совершенно отдельный пункт к основному из этого ответа, однако. Даже если бы у вас было действительно произвольно большое количество битов, с которыми вы могли бы играть, вы все равно не могли бы представить десятичный 0,1 точно в представлении с плавающей двоичной точкой. Сравните это с обратным: учитывая произвольное количество десятичных цифр, вы можете точно представить любое число, которое точно представляется в виде плавающей двоичной точки.

Например, число 61.0 имеет точное двоичное представление, потому что целая часть любого числа всегда точна. Но число 6.10 не является точным. Все, что я сделал, это переместил десятичное число на одно место, и внезапно я перешел из Экзактопии в Инэктактвиль. Математически не должно быть никакой разницы между двумя числами - это просто числа .

Давайте на минутку отойдем от деталей основ 10 и 2. Давайте спросим - в базе b, какие числа имеют конечные представления, а какие нет? Мгновенная мысль говорит нам, что у числа xесть bконечное представление, если и только если существует целое число, nтакое x b^nкак целое число.

Так, например, x = 11/500имеет завершающее 10-представление, потому что мы можем выбрать n = 3и затем x b^n = 22целое число. Однако x = 1/3это не так, потому что все, что nмы выберем, мы не сможем избавиться от 3.

Этот второй пример побуждает нас задуматься о факторах, и мы видим, что для любого рационального x = p/q (предположительно в самых низких терминах) мы можем ответить на вопрос, сравнивая простые факторизации bи q. Если qесть какие-либо первичные факторы, не входящие в первичную факторизацию b, мы никогда не сможем найти подходящего, nчтобы избавиться от этих факторов.

Таким образом, для базы 10 любой, p/q где qимеет простые факторы, кроме 2 или 5, не будет иметь завершающего представления.

Итак, теперь, возвращаясь к базисам 10 и 2, мы видим, что любое рациональное с конечным 10-представлением будет иметь форму p/qименно тогда, когда qимеет только 2s и 5s в своей первичной факторизации; и это же число будет иметь завершающее 2-представление именно тогда, когда qимеет только 2s в своей первичной факторизации.

Но один из этих случаев является подмножеством другого! Когда бы ни

qимеет только 2s в своей первичной факторизации

очевидно также верно, что

qимеет только 2S и 5S в своей главной факторизации

или, другими словами, всякий разp/qp/q , когда имеет завершающее 2-представление, имеет завершающее 10-представление . Обратное, однако, не имеет места - всякий раз, когда q5 имеет первичную факторизацию, оно будет иметь конечное 10-представление, но не конечное 2-представление. Это 0.1пример, упомянутый в других ответах.

Итак, у нас есть ответ на ваш вопрос - поскольку простые множители 2 являются подмножеством простых множителей 10, все 2-конечные числа являются 10-конечными числами, но не наоборот. Это не около 61 против 6,1 - это около 10 против 2.

В заключительной ноте, если воля людей использовали (скажу) основаниями 17 , но наши компьютеры , используемых базой 5, ваша интуиция никогда бы не была отведена этим - не было бы ни одного (не ноль, нецелого) чисел, прекращенных в обоих случаях!

Основная (математическая) причина в том, что когда вы имеете дело с целыми числами, они счетны бесконечно .

Это означает, что, хотя их существует бесконечное количество, мы можем «отсчитать» все элементы в последовательности, не пропуская ни одного. Это означает, что если мы хотим получить элемент в 610000000000000ой позиции в списке, мы можем выяснить это с помощью формулы.

Однако реальные цифры неисчислимо бесконечны . Вы не можете сказать «дайте мне реальный номер на позиции 610000000000000» и получить ответ. Причина в том, что даже между 0и 1существует бесконечное число значений, когда вы рассматриваете значения с плавающей запятой. То же самое верно для любых двух чисел с плавающей точкой.

Больше информации:

http://en.wikipedia.org/wiki/Countable_set

http://en.wikipedia.org/wiki/Uncountable_set

Обновление: мои извинения, я, кажется, неправильно понял вопрос. Мой ответ о том, почему мы не можем представлять все реальные значения, я не осознавал, что с плавающей запятой автоматически классифицируется как рациональная.

Повторим то, что я сказал в своем комментарии г-ну Скиту: мы можем представить 1/3, 1/9, 1/27 или любое рациональное в десятичной записи. Мы делаем это, добавляя дополнительный символ. Например, строка над цифрами, которые повторяются в десятичном разряде числа. Нам нужно представить десятичные числа в виде последовательности двоичных чисел: 1) последовательность двоичных чисел, 2) ось радиуса и 3) некоторый другой символ, обозначающий повторяющуюся часть последовательности.

Обозначение цитаты Хенера - способ сделать это. Он использует символ кавычки для представления повторяющейся части последовательности. Статья: http://www.cs.toronto.edu/~hehner/ratno.pdf и запись в Википедии: http://en.wikipedia.org/wiki/Quote_notation .

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

BCD - двоично-десятичное десятичное число - представления являются точными. Они не очень компактны, но это компромисс, который вы должны сделать для точности в этом случае.

По той же причине, по которой вы не можете точно представить 1/3 в основании 10, вам нужно сказать 0,33333 (3). В двоичном виде это проблема того же типа, но она возникает только для разного набора чисел.

(Примечание: я добавлю 'b', чтобы указать здесь двоичные числа. Все остальные числа даны в десятичном виде)

Один из способов думать о вещах - это что-то вроде научной нотации. Мы привыкли видеть числа, выраженные в научных обозначениях, например, 6.022141 * 10 ^ 23. Числа с плавающей точкой хранятся внутри, используя аналогичный формат - мантиссу и экспоненту, но используя степени два вместо десяти.

Ваш 61.0 может быть переписан как 1.90625 * 2 ^ 5 или 1.11101b * 2 ^ 101b с мантиссой и показателями. Чтобы умножить это на десять и (переместить десятичную точку), мы можем сделать:

(1.90625 * 2 ^ 5) * (1.25 * 2 ^ 3) = (2.3828125 * 2 ^ 8) = (1.19140625 * 2 ^ 9)

или в мантиссе и показателях в двоичном виде:

(1.11101b * 2 ^ 101b) * (1.01b * 2 ^ 11b) = (10.0110001b * 2 ^ 1000b) = (1.00110001b * 2 ^ 1001b)

Обратите внимание, что мы сделали там, чтобы умножить числа. Мы умножили мантиссы и добавили экспоненты. Затем, поскольку мантисса закончилась больше двух, мы нормализовали результат, увеличив показатель степени. Это как когда мы корректируем показатель степени после выполнения операции над числами в десятичной научной нотации. В каждом случае значения, с которыми мы работали, имели конечное представление в двоичном формате, и поэтому значения, выводимые с помощью основных операций умножения и сложения, также давали значения с конечным представлением.

Теперь рассмотрим, как мы разделим 61 на 10. Начнем с деления мантисс, 1.90625 и 1.25. В десятичном виде это дает 1.525, хороший короткий номер. Но что это, если мы преобразуем его в двоичный файл? Мы сделаем это обычным способом - вычитая наибольшую степень двух, когда это возможно, точно так же, как преобразование целых десятичных чисел в двоичную, но мы будем использовать отрицательные степени двух:

1,525 - 1 * 2 ^ 0 -> 1
0,525 - 1 * 2 ^ -1 -> 1
0,025 - 0 * 2 ^ -2 -> 0
0,025 - 0 * 2 ^ -3 -> 0
0,025 - 0 * 2 ^ -4 -> 0
0,025 - 0 * 2 ^ -5 -> 0
0,025 - 1 * 2 ^ -6 -> 1
0,009375 - 1 * 2 ^ -7 -> 1
0,0015625 - 0 * 2 ^ -8 -> 0
0,0015625 - 0 * 2 ^ -9 -> 0
0,0015625 - 1 * 2 ^ -10 -> 1
0.0005859375 - 1 * 2 ^ -11 -> 1
+0,00009765625 ...

Ооо Теперь у нас проблемы. Оказывается, что 1.90625 / 1.25 = 1.525 - это повторяющаяся дробь, если выразить ее в двоичном виде: 1.11101b / 1.01b = 1.10000110011 ... b У наших машин только столько битов, которые содержат эту мантиссу, и поэтому они просто округляют дробь и принять нули за определенной точкой. Ошибка, которую вы видите, когда вы делите 61 на 10, является разницей между:

1.100001100110011001100110011001100110011 ... b * 2 ^ 10b
и, скажем:
1.100001100110011001100110b * 2 ^ 10b

Именно это округление мантиссы приводит к потере точности, которую мы связываем со значениями с плавающей запятой. Даже когда мантисса может быть выражена точно (например, при добавлении двух чисел), мы все равно можем получить числовые потери, если мантиссе нужно слишком много цифр, чтобы соответствовать после нормализации показателя степени.

Мы на самом деле делаем такие вещи все время, когда округляем десятичные числа до приемлемого размера и просто даем первые несколько цифр. Поскольку мы выражаем результат в десятичном виде, это кажется естественным. Но если бы мы округлили десятичную дробь, а затем преобразовали ее в другое основание, это выглядело бы так же безобразно, как десятичные дроби, которые мы получаем из-за округления с плавающей запятой.

Это хороший вопрос.

Весь ваш вопрос основан на "как мы представляем число?"

ВСЕ числа могут быть представлены с десятичным представлением или с двоичным представлением (дополнение 2). Все они !!

НО некоторые (большинство из них) требуют бесконечного числа элементов («0» или «1» для двоичной позиции или «0», «1» - «9» для десятичного представления).

Как 1/3 в десятичном представлении (1/3 = 0.3333333 ... <- с бесконечным числом «3»)

Как 0,1 в двоичном виде (0,1 = 0,00011001100110011 .... <- с бесконечным числом «0011»)

Все в этой концепции. Поскольку ваш компьютер может рассматривать только конечный набор цифр (десятичных или двоичных), только некоторые цифры могут быть точно представлены в вашем компьютере ...

И, как сказал Джон, 3 - это простое число, которое не является коэффициентом 10, поэтому 1/3 нельзя представить с конечным числом элементов в базе 10.

Даже с арифметикой с произвольной точностью система нумерации в базе 2 не в состоянии полностью описать 6.1, хотя она может представлять 61.

Для 6.1 мы должны использовать другое представление (например, десятичное представление или IEEE 854, которое разрешает основание 2 или основание 10 для представления значений с плавающей запятой)

Если вы сделаете достаточно большое число с плавающей запятой (как это может сделать экспоненты), то вы также получите неточность перед десятичной запятой. Так что я не думаю, что ваш вопрос полностью обоснован, потому что предпосылка неверна; Дело не в том, что смещение на 10 всегда будет создавать большую точность, потому что в некоторой точке число с плавающей запятой будет вынуждено использовать экспоненты для представления большого размера и таким образом потеряет некоторую точность.

Я удивлен, что никто еще не сказал это: используйте продолженные дроби . Таким образом, любое двоичное число может быть конечно представлено в двоичном виде.

Некоторые примеры:

1/3 (0,3333 ...)

0; 3

5/9 (0,5555 ...)

0; 1, 1, 4

10/43 (0,232558139534883720930 ...)

0; 4, 3, 3

9093/18478 (0.49209871198181621387596060179673 ...)

0; 2, 31, 7, 8, 5

Отсюда существует множество известных способов сохранить последовательность целых чисел в памяти.

В дополнение к сохранению вашего числа с идеальной точностью, дробные дроби также имеют ряд других преимуществ, таких как наилучшее рациональное приближение. Если вы решите прекратить последовательность чисел в непрерывной дроби раньше, оставшиеся цифры (при повторном объединении в дробь) дадут вам наилучшую возможную дробь. Вот как находятся приближения к пи:

Пи продолжил фракцию:

3; 7, 15, 1, 292 ...

Завершая последовательность в 1, это дает фракцию:

355/113

что является превосходным рациональным приближением.

В уравнении

2^x = y ;  
x = log(y) / log(2)

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

 2^1, 2^0, 2^(log(1/2) / log(2)), 2^(log(1/4) / log(2)), 2^(log(1/8) / log(2)),2^(log(1/16) / log(2)) ........

Это может решить проблему, поэтому, если вы хотите написать что-то вроде 32.41 в двоичном формате, это будет

2^5 + 2^(log(0.4) / log(2)) + 2^(log(0.01) / log(2))

Или

2^5 + 2^(log(0.41) / log(2))

Проблема в том, что вы на самом деле не знаете, действительно ли это число равно 61.0. Учти это:

float a = 60;
float b = 0.1;
float c = a + b * 10;

Каково значение с? Это не совсем 61, потому что b на самом деле не .1, потому что .1 не имеет точного двоичного представления.

Существует порог, потому что значение цифры изменилось с целого на нецелое. Для представления 61 у вас есть 6 * 10 ^ 1 + 1 * 10 ^ 0; 10 ^ 1 и 10 ^ 0 оба являются целыми числами. 6.1 - это 6 * 10 ^ 0 + 1 * 10 ^ -1, но 10 ^ -1 - это 1/10, что определенно не является целым числом. Вот как ты попал в Inexactville.

Параллель может быть сделана из дробей и целых чисел. Некоторые дроби, например 1/7, не могут быть представлены в десятичной форме без большого и большого количества десятичных дробей. Поскольку плавающая точка основана на двоичном коде, особые случаи меняются, но возникают проблемы с точностью точности.

Существует бесконечное число рациональных чисел и конечное число битов, которые их представляют. См. Http://en.wikipedia.org/wiki/Floating_point#Accuracy_problems .

Число 61.0 действительно имеет точную операцию с плавающей точкой, но это не так для всех целых чисел. Если вы написали цикл, который добавляет один к числу с плавающей запятой двойной точности и к 64-битному целому числу, в конечном итоге вы достигнете точки, в которой 64-битное целое число идеально представляет число, но с плавающей запятой этого не происходит. потому что не хватает значащих битов.

Намного проще достичь точки аппроксимации с правой стороны десятичной точки. Если бы вы начали записывать все числа в двоичном формате с плавающей запятой, это имело бы больше смысла.

Другой способ думать об этом заключается в том, что когда вы замечаете, что 61.0 отлично представлен в базе 10, а смещение десятичной точки вокруг не меняет этого, вы выполняете умножение на степени десяти (10 ^ 1, 10 ^ -1 ). В плавающей точке умножение на степени два не влияет на точность числа. Попробуйте взять 61.0 и несколько раз разделить его на три, чтобы продемонстрировать, как совершенно точное число может потерять свое точное представление.

Вы знаете целые числа, верно? каждый бит представляет 2 ^ n

2 ^ 4 = 16
2 ^ 3 = 8
2 ^ 2 = 4
2 ^ 1 = 2
2 ^ 0 = 1

хорошо то же самое для плавающей запятой (с некоторыми различиями), но биты представляют 2 ^ -n 2 ^ -1 = 1/2 = 0,5
2 ^ -2 = 1 / (2 * 2) = 0,25
2 ^ -3 = 0,125
2 ^ -4 = 0,0625

Бинарное представление с плавающей точкой:

Фракция экспоненты (я думаю, что к дроби добавляется невидимое 1)
B11 B10 B9 B8 B7 B6 B5 B4 B3 B2 B1 B0

Высокий результат ответа выше прибил это.

Сначала вы смешивали основание 2 и основание 10 в своем вопросе, затем, когда вы помещаете число справа, которое не делится на основание, у вас возникают проблемы. Как 1/3 в десятичной дроби, потому что 3 не входит в степень 10 или 1/5 в двоичной системе, которая не входит в степень 2.

Другой комментарий, хотя НИКОГДА не использовать равный с числами с плавающей точкой, точка. Даже если это точное представление, в некоторых системах с плавающей запятой есть некоторые числа, которые могут быть точно представлены более чем одним способом (IEEE плох в этом, это ужасная спецификация с плавающей запятой, с которой следует начинать, так что ожидайте головной боли). Ничего не отличается здесь 1/3 не равно числу на вашем калькуляторе 0,3333333, независимо от того, сколько 3 есть справа от десятичной точки. Это или может быть достаточно близко, но не равно. поэтому вы ожидаете, что что-то вроде 2 * 1/3 не будет равно 2/3 в зависимости от округления. Никогда не используйте равные с плавающей точкой.

Как мы уже обсуждали, в арифметике с плавающей запятой десятичная дробь 0.1 не может быть идеально представлена ​​в двоичной форме.

Представления с плавающей точкой и целые числа предоставляют сетки или решетки для представленных чисел. Как только арифметика закончена, результаты падают с сетки и должны быть возвращены на сетку путем округления. Пример 1/10 на двоичной сетке.

Если мы будем использовать двоичное кодированное десятичное представление, как предложил один джентльмен, сможем ли мы сохранить числа в сетке?