Почему десятичные числа не могут быть представлены точно в двоичном формате?
В 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 ...
Также нет произвольных ограничений на эти числа. Позиции увеличиваются до бесконечности влево и вправо.
23 ответа
Десятичные числа могут быть представлены точно, если у вас достаточно места - только не с помощью чисел с плавающей запятой. Если вы используете тип с плавающей запятой (например, 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 точно в представлении с плавающей двоичной точкой. Сравните это с обратным: учитывая произвольное количество десятичных цифр, вы можете точно представить любое число, которое точно представляется в виде плавающей двоичной точки.
Причиной неточности является характер числовых баз. В базе 10 вы не можете точно представить 1/3. Она становится 0,333... Однако в базе 3 1/3 точно представлена 0,1, а 1/2 - бесконечно повторяющаяся десятичная дробь (tresimal?). Значения, которые могут быть представлены конечным образом, зависят от числа уникальных простых факторов основания, поэтому основание 30 [2 * 3 * 5] может представлять больше дробей, чем основание 2 или основание 10. Еще больше для основания 210 [2 * 3 * 5 * 7].
Это отдельная проблема от "ошибки с плавающей запятой". Неточность заключается в том, что несколько миллиардов значений распространяются в гораздо большем диапазоне. Таким образом, если у вас есть 23 бита для значения, вы можете представить только около 8,3 миллиона различных значений. Затем 8-разрядный показатель обеспечивает 256 вариантов распределения этих значений. Эта схема позволяет получить наиболее точные десятичные дроби около 0, поэтому вы можете почти представить 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 имеет только 2 с и 5 s в своей первичной факторизации; и это же число будет иметь 2-концевое окончание именно тогда, когда q имеет только 2 s в своей первичной факторизации.
Но один из этих случаев является подмножеством другого! Всякий раз, когда
qимеет только2s в своей первичной факторизации
очевидно также верно, что
qимеет только2с и5s в своей первичной факторизации
или, другими словами, всякий раз, когда p/q имеет завершающее 2-представление, p/q имеет завершающее 10-представление. Обратное, однако, не имеет места - всякий раз, когда q имеет 5 в своей основной факторизации, у него будет завершающее 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 - двоично-десятичный десятичный код - представления являются точными. Они не очень компактны, но это компромисс, который вы должны сделать для точности в этом случае.
(Примечание: я добавлю '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 в основании 10, вам нужно сказать 0.33333(3). В двоичном коде это проблема того же типа, но она возникает только для другого набора чисел.
Я удивлен, что никто еще не сказал это: используйте продолженные дроби. Таким образом, любое двоичное число может быть конечно представлено в двоичном виде.
Некоторые примеры:
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
что является превосходным рациональным приближением.
Вы не можете точно представить 0,1 в двоичном формате по той же причине, по которой вы не можете измерить 0,1 дюйма с помощью обычной английской линейки.
Английские линейки, как и двоичные дроби, состоят из половинок. Вы можете измерить полдюйма, или четверть дюйма (что, конечно, половина половины), или восьмую, или шестнадцатую, и т. д.
Однако, если вы хотите измерить десятую часть дюйма, вам не повезло. Это меньше одной восьмой дюйма, но больше шестнадцатой. Если вы попытаетесь уточнить, то обнаружите, что это чуть больше 3/32, но чуть меньше 7/64. Я никогда не видел настоящую линейку с градацией тоньше 64-х, но если вы посчитаете, то обнаружите, что 1/10 меньше 13/128, больше 25/256 и больше 51. /512. Вы можете идти дальше и дальше, к 1024-м, 2048-м, 4096-м и 8192-м, но вы никогда не найдете точную маркировку, даже на бесконечно тонкой линейке с основанием 2, которая точно соответствует 1/10, или 0,1.
Зато найдете кое-что интересное. Давайте посмотрим на все приближения, которые я перечислил, и для каждого явно запишем, больше или меньше 0,1:
Теперь, если вы прочитаете последнюю колонку, вы получите
0001100110011. Не случайно бесконечно повторяющаяся двоичная дробь для 1/10 равна 0,0001100110011...
В уравнении
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, у вас есть 6 * 10 ^ 1 + 1 * 10 ^ 0; 10 ^ 1 и 10 ^ 0 оба являются целыми числами. 6.1 - это 6 * 10 ^ 0 + 1 * 10 ^ -1, но 10 ^ -1 - это 1/10, что определенно не является целым числом. Вот как ты попал в Inexactville.
Проблема в том, что вы на самом деле не знаете, действительно ли это число равно 61.0 . Учти это:
float a = 60;
float b = 0.1;
float c = a + b * 10;
Каково значение с? Это не совсем 61, потому что b на самом деле не.1, потому что.1 не имеет точного двоичного представления.
Параллель может быть сделана из дробей и целых чисел. Некоторые дроби, например 1/7, не могут быть представлены в десятичной форме без большого и большого количества десятичных дробей. Поскольку плавающая точка основана на двоичном коде, особые случаи меняются, но возникают проблемы с точностью точности.
Число 61.0 действительно имеет точную операцию с плавающей точкой, но это не так для всех целых чисел. Если вы написали цикл, который добавляет один к числу с плавающей запятой двойной точности и к 64-разрядному целому числу, в конечном итоге вы достигнете точки, в которой 64-разрядное целое число идеально представляет число, а с плавающей запятой - потому что не хватает значительных битов.
Намного проще достичь точки аппроксимации справа от десятичной точки. Если бы вы начали записывать все числа в двоичном формате с плавающей запятой, это имело бы больше смысла.
Еще один способ думать об этом заключается в том, что когда вы замечаете, что 61.0 отлично представлен в базе 10, а смещение десятичной точки вокруг не меняет этого, вы выполняете умножение на степени десяти (10^1, 10^-1). В плавающей запятой умножение на степени два не влияет на точность числа. Попробуйте взять 61.0 и несколько раз разделить его на три, чтобы продемонстрировать, как совершенно точное число может потерять свое точное представление.
Я не буду повторять то, что уже обобщено в других 20 ответах, поэтому я просто кратко отвечу:
Ответ в вашем содержании:
Почему два основания не могут точно представлять определенные соотношения?
По той же причине, что десятичные дроби недостаточны для представления определенных соотношений, а именно, неприводимых дробей со знаменателями, содержащими простые множители, отличные от двух или пяти, которые всегда будут иметь неопределенную строку, по крайней мере, в мантиссе десятичного разложения.
Почему десятичные числа не могут быть представлены точно в двоичном формате?
Этот вопрос на первый взгляд основан на неправильном представлении о самих ценностях. Никакой системы счисления недостаточно для представления какой-либо величины или отношения таким образом, чтобы сама вещь говорила вам, что она является одновременно величиной, и в то же время также давала интерпретацию самой по себе внутренней ценности представления. Таким образом, все количественные представления и модели в целом являются символическими и могут быть поняты только апостериори, а именно после того, как человека научили читать и интерпретировать эти числа.
Поскольку модели являются субъективными вещами, истинными постольку, поскольку они отражают реальность, нам не обязательно интерпретировать двоичную строку как сумму отрицательных и положительных степеней двойки. Вместо этого можно заметить, что мы можем создать произвольный набор символов, который использует основание два или любое другое основание для точного представления любого числа или отношения. Просто учтите, что мы можем ссылаться на всю бесконечность, используя одно слово и даже один символ, не «показывая бесконечность» как таковую.
В качестве примера я разрабатываю двоичное кодирование для смешанных чисел, чтобы иметь большую точность и аккуратность, чем с плавающей точкой IEEE 754. На момент написания этой статьи идея состояла в том, чтобы иметь знаковый бит, обратный бит, определенное количество бит для скаляра, чтобы определить, насколько «увеличить» дробную часть, а затем оставшиеся биты равномерно разделить между целая часть смешанного числа, а последнее - число с фиксированной точкой, которое, если установлен обратный бит, следует интерпретировать как единицу, деленную на это число. Это имеет преимущество , что позволяет мне для представления чисел с бесконечными десятичными расширениями, используя их обратные , которые действительно имеют согласующий десятичные разложения, или в качестве альтернативы, как фракция непосредственно, потенциально в качестве приближения, в зависимости от моих потребностей.
Высокий результат ответа выше прибил это.
Сначала вы смешивали основание 2 и основание 10 в своем вопросе, затем, когда вы помещаете число справа, которое не делится на основание, у вас возникают проблемы. Как 1/3 в десятичной дроби, потому что 3 не входит в степень 10 или 1/5 в двоичной системе, которая не входит в степень 2.
Другой комментарий, хотя НИКОГДА не использовать равный с числами с плавающей точкой, точка. Даже если это точное представление, в некоторых системах с плавающей запятой есть некоторые числа, которые могут быть точно представлены более чем одним способом (IEEE плохо об этом, это ужасная спецификация с плавающей запятой, с которой следует начинать, так что ожидайте головной боли). Ничего не отличается здесь 1/3 не равно числу на вашем калькуляторе 0,3333333, независимо от того, сколько 3-х есть справа от десятичной точки. Это или может быть достаточно близко, но не равно. поэтому вы ожидаете, что что-то вроде 2*1/3 не будет равно 2/3 в зависимости от округления. Никогда не используйте равные с плавающей точкой.
Вы знаете целые числа, верно? каждый бит представляет 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
Бинарное представление с плавающей точкой:
знак Exponent Fraction(я думаю, что невидимое 1 добавляется к дроби)
B11 B10 B9 B8 B7 B6 B5 B4 B3 B2 B1 B0
Существует бесконечное число рациональных чисел и конечное число битов для их представления. См. http://en.wikipedia.org/wiki/Floating_point.
Как мы уже обсуждали, в арифметике с плавающей запятой десятичная дробь 0.1 не может быть идеально представлена в двоичной форме.
Представления с плавающей точкой и целые числа обеспечивают сетки или решетки для представленных чисел. Когда арифметика завершена, результаты падают с сетки и должны быть возвращены на сетку путем округления. Пример 1/10 на двоичной сетке.
Если мы будем использовать двоичное кодированное десятичное представление, как предложил один джентльмен, сможем ли мы сохранить числа в таблице?
Для простого ответа: у компьютера нет бесконечной памяти для хранения дробей (после представления десятичного числа как формы научного представления). Согласно стандарту IEEE 754 для чисел с плавающей запятой двойной точности, у нас есть ограничение в 53 бита для хранения дроби. Для получения дополнительной информации: http://mathcenter.oxford.emory.edu/site/cs170/ieee754/