Take the 2-minute tour ×
Programmers Stack Exchange is a question and answer site for professional programmers interested in conceptual questions about software development. It's 100% free, no registration required.

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

share|improve this question
11  
+1 to the question, but is the c# tag really applicable here? Other languages have the decimal type as well. –  Patrick M Apr 25 at 17:21
1  
@Max: As an exercise, I suggest you to imagine converting a base 2 number to base 10 by hand. E.g., to calculate the value of 0.11_b2, write it out as 0.5 + 0.5 * 0.5. Is there any step which might fail or result in a repeating decimal? Personally, I find that this exercise does a great job getting across an intuition about base 2 numbers. I suppose one could go a step further and turn this exercise into a proof by construction. –  Brian Apr 25 at 18:47
    
Ah, but you're wrong. 1/1010 –  codenoire Apr 25 at 23:45
3  
@Ramhound Given memory limitations, binary can represent 0.0999999....998.. exactly, but not the full number 0.1 - approximations like rounding to the nearest hundreth with 0.100 are an implementation concern that involves not showing you all the digits and rounding it instead. –  Izkata Apr 26 at 6:25
1  
Well, it's possible to come up with a an FP encoding mechanism that allows '0.1' to be exactly represented. Such an encoding merely shifts around the sets of FP number ranges than can and cannot be represented. –  Martin James Apr 26 at 20:23

3 Answers 3

up vote 96 down vote accepted

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/2n * 1/5m 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/2n) 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...2 (with the 0011 part repeating forever).

Lets look at the number 12/10102 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/(21 * 51). 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 / 10exponent. This means the maximum and minimum values of the type are +/- (296-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 232 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.

share|improve this answer
    
+1 for a clear and concise mathematical explanation. And to answer the more general version of the question posed in the title, an example of a number not representable in base 10 is 1/3. –  Doval Apr 25 at 15:43
    
@Doval I do suspect there's a glitch in my reasoning or explanation that a more math oriented person could point out... but I do think I'm on the right track if that is the case. –  MichaelT Apr 25 at 15:49
    
"Relatively prime" in this case just means "not a factor of", right? Is there some deeper mathematical relationship I'm missing? –  Patrick M Apr 25 at 16:55
1  
Ah, so as I understand it, n = 15 and b = 10 are not relatively prime ("share no common positive factors (divisors) except 1") because they share 5 as a factor. The key is that not all of the factors of 15 (5 and 3) are not also factors of 10. (Aside: is there a word to indicate numbers that do or don't share all common factors?) I think that is neatly wrapped up in your k, n, m equation, but to really wrap my head around it, I would need to see a 3d plot. Regardless, well deserved +1 to you. –  Patrick M Apr 25 at 17:08
1  
@PatrickM: "Aside: is there a word to indicate numbers that do or don't share all common factors?": Any integer is a factor of itself, so if all factors of m are factors of n, then it trivially follows that m is a factor of n. One term for this, as you clearly know, is factor. Another is divisor. –  ruakh Apr 26 at 20:10

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., e1, 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

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

share|improve this answer
2  
@Magus consider the irrational number e (2.71...). The natural log - ln(x) is log base e. Thus, irrational bases do exist and are useful. The particular usefulness of base pi, I'm not sure of - but that doesn't mean it isn't used somewhere. –  MichaelT Apr 25 at 15:53
6  
@Max you are straying more and more into math questions. You may find If a number is irrational in base 10, is it irrational in other bases? to be a useful read and a starting point for more number theory questions. –  MichaelT Apr 25 at 15:59
2  
1/3 isn't irrational. –  Adam Zuckerman Apr 25 at 16:00
2  
The OP asked about base 10 (ten). Making a number system base of anything will allow you to express anything as 10. Based on the Wikipedia article, using an irrational number as a base does not make it rational. Rational numbers can be expressed as integers for both the numerator and denominator, repeating numbers in a decimal, or finite termination of numbers in a decimal. –  Adam Zuckerman Apr 25 at 16:39
4  
@FrustratedWithFormsDesigner Irrationality has nothing whatsoever to do with bases. Well, that's an overstatement, but it's irrationality that has implications for the number's representation in various bases (e.g. whether it has infinite non-repeating digits), not the other way around. Read the math.se question linked to above: math.stackexchange.com/questions/625473/… –  delnan Apr 25 at 16:39

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.

share|improve this answer

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.