Существуют ли числа, которые не представлены в базе 10, но могут быть представлены в базе 2?

42

C#имеет decimalтип, который используется для чисел, которые нуждаются в точном представлении в базе 10. Например, 0.1не может быть представлен в базе 2 (например, floatи double) и всегда будет приближенным при хранении в переменных этих типов.

Мне было интересно, возможен ли обратный факт. Существуют ли числа, которые не могут быть представлены в базе 10, но могут быть представлены в базе 2 (в этом случае я бы хотел использовать floatвместо них a decimalдля их обработки)?

Максимум
источник
14
+1 к вопросу, но действительно ли здесь применим тег c # ? Другие языки также имеют десятичный тип.
Патрик М
1
@Max: В качестве упражнения я предлагаю вам представить преобразование числа 2 в базу 10 вручную. Например, чтобы вычислить значение 0.11_b2, запишите его как 0.5 + 0.5 * 0.5. Есть ли какой-либо шаг, который может привести к неудаче или привести к повторению десятичной дроби? Лично я нахожу, что это упражнение отлично справляется с интуицией о числах с основанием 2. Я полагаю, можно пойти еще дальше и превратить это упражнение в доказательство по построению.
Брайан
Ах, но ты не прав. 1/1010
Ксавьер J
3
@Ramhound Учитывая ограничения памяти, двоичный файл может представлять 0.0999999....998..точное, но не полное число 0.1- аппроксимации, такие как округление до ближайшего сотого с, 0.100являются проблемой реализации, которая подразумевает не показывать вам все цифры и вместо этого округлять.
Изката
1
Что ж, можно придумать механизм кодирования FP, который позволяет точно представлять «0.1». Такое кодирование просто сдвигается вокруг наборов диапазонов номеров FP, которые могут и не могут быть представлены.
Мартин Джеймс

Ответы:

104

Вот ключ к вашему затруднению: 10является продуктом 2и 5. Вы можете представить любое число точно в десятичных десятичных числах, то есть k * 1/2 n * 1/5 m где k, nи mявляются целыми числами.

Альтернативно формулируется - если число nв 1 / n содержит фактор, который не является частью факторов базы, число не сможет быть точно представлено в фиксированном количестве цифр в двоичном / десятичном / любом другом разложении этого номер - он будет иметь повторяющуюся часть. Например, 1/15 = 0,0666666666 .... потому что 3 (15 = 3 * 5) не в 10 раз.

Таким образом, все, что может быть представлено в базе 2 точно (k * 1/2 n ), может быть точно представлено в базе 10.

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


В двоичном формате число 1/10, которое обычно равно 0,1 в десятичном виде, не может быть представлено как число, которое может быть представлено в фиксированном количестве битов в двоичном формате. Вместо этого число равно 0,00011001100110011 ... 2 (часть 0011 повторяется вечно).

Давайте посмотрим на число 1 2 /1010 2 немного более близко.

          ____                  
       0,00011                  
     + ---------                 
1010 | 1,00000                  
       0                        
       -                       
       1 0                      
         0                      
       ----                     
       1 00 --------- +          
          0 |          
       ----- |          
       1 000 |          
           0 |          
       ------ | повторяющий
       1 0000 | блок    
         1010 |          
       ------ |          
          1100 |          
          1010 |          
          ---- |          
            100 ---- +          

Это то же самое, что вы получаете, когда пытаетесь сделать длинное деление на 1/3.

1/10, когда факторинг равен 1 / (2 1 * 5 1 ). Для основания 10 (или любого кратного 10) это число заканчивается и называется обычным числом . Повторяющаяся десятичная дробь известна как повторяющаяся десятичная дробь , и те числа, которые продолжаются вечно без повторения, являются иррациональными числами.

Математика за этим углубляется в малые теоремы Ферма ... и как только вы начинаете говорить Ферма или теорема, это становится Math.SE вопрос .

Существуют ли числа, которые не представлены в базе 10, но могут быть представлены в базе 2?

Ответ - нет'.

Итак, в этот момент нам всем должно быть ясно, что каждое двоичное разложение фиксированной длины рационального числа может быть представлено как десятичное разложение фиксированной длины.


Давайте внимательнее посмотрим на десятичную в C #, которая приводит нас к десятичной с плавающей запятой в .NET и, учитывая автора, я согласен, вот как это работает.

Десятичный тип имеет те же компоненты, что и любое другое число с плавающей запятой: мантисса, показатель степени и знак. Как обычно, знак только один бит, но есть 96 бит мантиссы и 5 бит экспоненты. Однако не все комбинации показателей действительны. Работают только значения 0-28, и все они фактически отрицательны: числовое значение равно . Это означает, что максимальные и минимальные значения типа составляют +/- (2 96 -1), а наименьшее ненулевое число по абсолютной величине равно 10 -28 .sign * mantissa / 10exponent

Я сразу укажу, что из-за этой реализации есть числа в doubleтипе, которые не могут быть представлены в decimal- те, которые находятся вне диапазона. Double.Epsilonэто то, 4.94065645841247e-324что не может быть представлено в decimal, но может быть в double.

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

Есть несколько других типов, плавающих вокруг. В C # есть BigInteger, который может представлять произвольно большое целое число. Там нет никакого эквивалента в Java BigDecimal (который может представлять числа с десятичными цифрами до 2 32 цифр длинных - что является значительным диапазон) точно . Тем не менее, если вы немного поковыряетесь, вы сможете найти ручные реализации.

Есть некоторые языки, которые также имеют рациональный тип данных, который позволяет вам точно представлять рациональные значения (так что 1/3 фактически равна 1/3).


Специально для C # и выбора числа с плавающей точкой или рационального, я буду откладывать на Jon Skeet из плавающей десятичной точки в .NET :

Большинство бизнес-приложений, вероятно, должны использовать десятичные, а не с плавающей или двойной. Мое эмпирическое правило заключается в том, что искусственные ценности, такие как валюта, обычно лучше представить с десятичной плавающей запятой: например, концепция ровно 1,25 доллара вполне разумна. Для значений из мира природы, таких как длины и веса, двоичные типы с плавающей запятой имеют больше смысла. Несмотря на то, что существует теоретический «ровно 1,25 метра», в реальности этого никогда не произойдет: вы, безусловно, никогда не сможете измерить точные длины, и вряд ли они вообще существуют на атомном уровне. Мы привыкли к определенной терпимости.

Сообщество
источник
+1 за четкое и краткое математическое объяснение. И чтобы ответить на более общую версию вопроса, поставленного в заголовке, пример числа, не представленного в базе 10, равен 1/3.
Доваль
@ Довал Я подозреваю, что в моих рассуждениях или объяснениях есть сбой, который мог бы указать более ориентированный на математику человек ... но я думаю, что я на правильном пути, если это так.
«Относительно простое» в данном случае означает «не фактор», верно? Есть ли какие-то более глубокие математические отношения, по которым я скучаю?
Патрик М
1
Ах, насколько я понимаю, n = 15и b = 10они не являются относительно простыми («не делите общих положительных факторов (делителей), кроме 1»), потому что они имеют 5 как фактор. Ключевым моментом является то, что не все факторы 15 (5 и 3) не являются также факторами 10. (Помимо: есть ли слово для обозначения чисел, которые имеют или не разделяют все общие факторы?) Я думаю, что это аккуратно завернутый в ваше k, n, mуравнение, но чтобы действительно обернуть его вокруг, мне нужно было бы увидеть 3D-график. В любом случае, заслуженно +1 к вам.
Патрик М
1
@PatrickM: «В стороне: есть ли слово для обозначения чисел, которые делят или не разделяют все общие факторы?»: Любое целое число является фактором само по себе, поэтому, если все факторы m являются факторами n , то из тривиального следует, что m является фактором n . Одним из терминов для этого, как вы ясно знаете, является фактор . Еще один делитель .
Руах
6

Как только вы выйдете за пределы допустимых значений, ответ будет положительным. Тем не менее, почти все внутри диапазона будет иметь представление. C # Десятичная ссылка Хотя это не указано в спецификации, иррациональные числа не могут быть точно представлены (например, e 1 , pi, квадратный корень из 2 и т. Д.).

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

Точность: 28-29 значащих цифр

1 Спасибо MichaelT за напоминание о другом иррациональном номере.

Адам Цукерман
источник
2
@Magus рассмотрим иррациональное число e(2.71 ...). Натуральный лог - ln (x) - логарифмическая база e. Таким образом, иррациональные основы существуют и полезны. В особой полезности базового числа я не уверен - но это не значит, что он где-то не используется.
6
@ Макс, ты все больше и больше увлекаешься математическими вопросами. Вы можете найти Если число иррационально в базе 10, иррационально ли оно в других базах? быть полезным чтением и отправной точкой для большего количества вопросов теории чисел.
2
1/3 не иррациональна.
Адам Цукерман,
2
ОП спросил о базе 10 (десять). Создание основы системы счисления чего-либо позволит вам выразить что-либо как 10. Основываясь на статье в Википедии , использование иррационального числа в качестве основы не делает его рациональным. Рациональные числа могут быть выражены как целые числа как для числителя, так и для знаменателя, повторяющихся чисел в десятичной дроби или конечного окончания чисел в десятичной дроби.
Адам Цукерман
5
@FrustratedWithFormsDesigner Иррациональность не имеет никакого отношения к базам. Ну, это преувеличение, но это иррациональность, которая имеет значение для представления числа в различных основах (например, имеет ли оно бесконечные неповторяющиеся цифры), а не наоборот. Прочитайте вопрос math.se связанный выше: math.stackexchange.com/questions/625473/...
1

Тип с плавающей запятой с двумя базовыми значениями может точно представлять множество значений, которые не могут иметь тип с базовыми десятьми одинакового размера . Любое значение, которое будет точно представлено типом base-2 некоторого размера, будет точно представлено в типе base-ten достаточного размера. Требуемый размер для типа чисто базовых десяти для представления всех значений двоичного числа с плавающей запятой будет зависеть от диапазона экспонент двоичного типа; сотни битов за floatили тысячи за double.

При этом Decimalтип является достаточно большим, чтобы его можно было использовать в качестве «универсального» типа, способного хранить значение любого другого числового примитива и обеспечивать некоторые другие дополнительные функции, кроме того (если ничего другого, использовать один бит чтобы указать, является ли сохраненное значение результатом преобразования a double, и если этот бит установлен, используйте 64 бита для хранения рассматриваемого значения). Однако Microsoft решила этого не делать. В результате, преобразование , doubleчтобы Decimalне сможет полностью при больших значениях, будет вызывать малые значения должны быть округлены до ближайшего 1E-28. Кроме того, даже в динамическом диапазонеdecimal, метод преобразования не будет "туда-обратно". Например, оценка 1.0 / 3.0 как двойного результата даст 0.3333333333333333148, но преобразование этого значения в десятичное даст 0.333333333333333m, а обратное преобразование в двойное приведет к 0.3333333333333329818.

Supercat
источник