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

В 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 ...

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

Ответы на вопрос(20)

В уравнении

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))

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

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

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

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

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

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

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

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

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

For example, the number 61.0 has an exact binary representation because the integral portion of any number is always exact. But the number 6.10 is not exact. All I did was move the decimal one place and suddenly I've gone from Exactopia to Inexactville. Mathematically, there should be no intrinsic difference between the two numbers -- they're just numbers.

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

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

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

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

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

Но один из этих случаев является подмножеством другого! Всякий раз, когда

q has only 2s in its prime factorisation

это очевидноalso правда что

q has only 2s and 5s in its prime factorisation

или, другими словами,whenever p/q has a terminating 2-representation, p/q has a terminating 10-representation, Обратное, однако, делаетnot держать - всякий раз, когдаq имеет 5 в своей первичной факторизации, оно будет иметь конечное 10-представление, ноnot завершающее 2-представление. Это0.1 Пример упоминается другими ответами.

Итак, у нас есть ответ на ваш вопрос -because the prime factors of 2 are a subset of the prime factors of 10, all 2-terminating numbers are 10-terminating numbers, but not vice versa. Он составляет не около 61 против 6,1, а около 10 против 2.

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

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

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

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

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

Как 1/3 в десятичном представлении (1/3 = 0,3333333 ... & lt; - с бесконечным числом "3")

Как 0,1 в двоичном виде (0,1 = 0,00011001100110011 .... & lt; - с бесконечным числом "0011")

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

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

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

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

Причиной неточности является характер числовых баз. На основании 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, поэтому вы можетеalmost представляют 0,1.

(Примечание: я добавлю '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

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

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

Решение Вопроса

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

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

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

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


Side note to deal with the problem of finite representations:

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

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


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

well its the same for floating point(with some distinctions) but the bits represent 2^-n 2^-1=1/2=0.5
2^-2=1/(2*2)=0.25
2^-3=0.125
2^-4=0.0625

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

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

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

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

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

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

Тем не менее, реальные цифрыuncountably infinite, Вы не можете "сказать", дайте мне реальное число в позиции610000000000000& Quot; и получить ответ. Причина в том, что даже между0 а также1Существует бесконечное число значений, когда вы рассматриваете значения с плавающей точкой. То же самое верно для любых двух чисел с плавающей точкой.

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

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

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

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

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

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

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

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

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

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


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

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

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

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

Ваш ответ на вопрос