Are there numbers that are not representable in base 10 but can be represented in base 2?

C# has the decimal type which is used for numbers that needs exact representation in base 10. For instance, 0.1 cannot be represented in base 2 (e.g. float and double) and will always be an approximation when stored in variables that are of these types.

I was wondering if the reversed fact was also possible. Are there numbers that are not representable in base 10 but can be represented in base 2 (in which case I would want to use a float instead of a decimal to handle them)?

Here’s the key to your quandary: 10 is the product of 2 and 5. You can represent any number exactly in base 10 decimals that is k * 1/2ⁿ * 1/5^m where k, n and m are integers.

Alternatively phrased – if the number n in 1/n contains a factor that is not part of the factors of the base, the number will not be able to be represented exactly in a fixed number of digits in the binary/decimal/whatever expansion of that number – it will have a repeating part. For example 1/15 = 0.0666666666…. because 3 (15 = 3 * 5) is not a factor of 10.

Thus, anything that is able to be represented in base 2 exactly (k * 1/2ⁿ) can be represented in base 10 exactly.

Beyond that, there is the issue of how many digits/bits are you using to represent the number. There are some numbers that are able to be exactly represented in some base, but it takes more than some number of digits/bits to do.

In binary, the number 1/10 which is conveniently 0.1 in decimal isn’t able to be represented as a number that can be represented in a fixed number of bits in binary. Instead, the number is 0.00011001100110011…₂ (with the 0011 part repeating forever).

Lets look at the number 1₂/1010₂ a bit more closely.

          ____                  
       0.00011                  
     +---------                 
1010 | 1.00000                  
       0                        
       --                       
       1 0                      
         0                      
       ----                     
       1 00 ---------+          
          0          |          
       -----         |          
       1 000         |          
           0         |          
       ------        | repeating
       1 0000        | block    
         1010        |          
       ------        |          
          1100       |          
          1010       |          
          ----       |          
            100  ----+

This is exactly the same type of thing you get when you try to do the long division for 1/3.

1/10, when factored is 1/(2¹ * 5¹). For base 10 (or any multiple of 10), this number terminates and is known as a regular number. A decimal expansion that repeats is known as a repeating decimal, and those numbers that go on forever without repeating are irrational numbers.

The math behind this delves into Fermat’s little theorem… and once you start saying Fermat or theorem, it becomes a Math.SE question.

Are there numbers that are not representable in base 10 but can be represented in base 2?

The answer is ‘no’.

So, at this point we should all be clear that every fixed length binary expansion of a rational number can be represented as a fixed length decimal expansion.

Lets look more closely at the decimal in C# which leads us to Decimal floating point in .NET and given the author, I’ll accept that thats how it works.

The decimal type has the same components as any other floating point number: a mantissa, an exponent and a sign. As usual, the sign is just a single bit, but there are 96 bits of mantissa and 5 bits of exponent. However, not all exponent combinations are valid. Only values 0-28 work, and they are effectively all negative: the numeric value is sign * mantissa / 10^exponent. This means the maximum and minimum values of the type are +/- (2⁹⁶-1), and the smallest non-zero number in terms of absolute magnitude is 10^-28.

I’ll point out right away that because of this implementation there are numbers in the double type that cannot be represented in decimal – those that are out of the range. Double.Epsilon is 4.94065645841247e-324 which can’t be represented in a decimal, but can in a double.

However, within the range that decimal can represent, it has more bits of precision than other native types and can represent them without error.

There are some other types floating around. There is a BigInteger in C# which can represent an arbitrarily large integer. There is no equivalent to Java’s BigDecimal (which can represent numbers up with decimal digits of up to 2³² digits long – which is a sizable range) exactly. However, if you poke around a bit you can find hand rolled implementations.

There are some languages that also have a rational data type which allows you to exactly represent rationals (so that 1/3 is actually 1/3).

Specifcally for C# and the choice of float or rational, I’ll defer to Jon Skeet from the Decimal floating pint in .NET:

Most business applications should probably be using decimal rather than float or double. My rule of thumb is that manmade values such as currency are usually better represented with decimal floating point: the concept of exactly 1.25 dollars is entirely reasonable, for example. For values from the natural world, such as lengths and weights, binary floating point types make more sense. Even though there is a theoretical “exactly 1.25 metres” it’s never going to occur in reality: you’re certainly never going to be able to measure exact lengths, and they’re unlikely to even exist at the atomic level. We’re used to there being a certain tolerance involved.

Once you get outside the range of acceptable values, the answer is yes. That said, almost anything inside the range will have a representation. C# Decimal reference While not stated in the specification, irrational numbers cannot be exactly represented (e.g., e¹, pi, square root of 2, etc.).

The decimal keyword denotes a 128-bit data type. Compared to floating-point types, the decimal type has a greater precision and a smaller range, which makes it suitable for financial and monetary calculations. The approximate range and precision for the decimal type are shown in the following table.

Precision: 28-29 significant digits

¹ Thanks to MichaelT for reminding me of another irrational number.

A base-two floating-point type would be able to precisely represent many values which a base-ten type of the same size could not. Any value which would be exactly representable by a base-2 type of some size would be exactly representable in a base-ten type of sufficient size. The required size for a purely-base-ten type to represent all values of a binary floating-point number would depend upon the exponent range of the binary type; hundreds of bits for a float, or thousands for a double.

That having been said, the Decimal type is large enough that it would have been possible to make usable as a “universal” type capable of holding the value of any other numeric primitive and provide some other additional features besides (if nothing else, use one bit to indicate whether the stored value is the result of converting a double, and if that bit is set, use 64 bits to hold the value in question). Microsoft opted not to do that, however. As a result, conversion of a double to Decimal will fail completely for large values, will cause small values to be rounded to the nearest 1E-28. Further, even within the dynamic range of decimal, the conversion method will not “round-trip”. For example, evaluating 1.0/3.0 as double will yield 0.3333333333333333148, but converting that to decimal will yield 0.333333333333333m and converting that back to double would yield 0.3333333333333329818.

A decimal type on a modern computer will not store real decimal digits but use 4 binary bits for one digit, or 10 bits for 3 digits, or 32 bits for 9 digits, or 64 bits for 19 digits. Plus a base ten exponent, so 3.14 = 314 x 10^-2.

To store the number 1 – 2^-k you need k binary bits, or k decimal digits and a decimal exponent of -k. Even with 128 bit of storage a Decimal type can’t store this for k >= 39. But there is no problem in principle, just a matter of storage size.

Filed under: softwareengineering - @ 06:00

Thẻ: c++, floating-point, numbers

Thiết kế website giá rẻ

Danh mục

Are there numbers that are not representable in base 10 but can be represented in base 2?