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

Question

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

+1 to the question, but is the [tag:c#] tag really applicable here? Other languages have the decimal type as well. — Patrick M, Apr 25 '14 at 17:21
@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 '14 at 18:47
@Ramhound: Not as a single, finite-sized number, it can't. Not without rounding error or special extra knowledge (like that your number is supposed to be interpreted as some number of tenths). — cHao, Apr 26 '14 at 01:48
@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 '14 at 06:25
@Ramhound - see http://www.exploringbinary.com/why-0-point-1-does-not-exist-in-floating-point/ — Jules, Apr 26 '14 at 10:49
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 '14 at 20:23

score 109 · Accepted Answer · edited May 23 '17 at 12:40

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.

+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 '14 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. — , Apr 25 '14 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 '14 at 16:55
@PatrickM My wording is probably a bit off (which I *just* fixed up). Your question did make me think about it more clearly and hopefully word it better. (Relatively prime numbers are like 12 and 35 - they don't share any common factors which is a different thing than what I was thinking when I wrote that previous revision). — , Apr 25 '14 at 16:59
Ah, so as I understand it, `n = 15` and `b = 10` are not [relatively prime](http://mathworld.wolfram.com/RelativelyPrime.html) ("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 '14 at 17:08
+0 What happens when we get to the [ULPs](https://en.wikipedia.org/wiki/Unit_in_the_last_place) of decimals and floats? The OP looks like he understands that mathematically, all decimal numbers can be represented in binary and visa-versa. I think the question is about how computers represent numbers and the limitations therein. — Kevin, Apr 26 '14 at 01:54
@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 '14 at 20:10

score 6 · Answer 2 · edited Jun 16 '20 at 10:01

6

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.

edited Jun 16 '20 at 10:01

Community

1

answered Apr 25 '14 at 15:35

Adam Zuckerman

3,715
1
19
27

Pi and `sqrt(2)` cannot be represented in any base can they? I mean except base Pi and base `sqrt(2)` where thay are `10` – Max Apr 25 '14 at 15:42
Not that I am aware of. I am not a mathematician, so I cannot say with absolute certainty. – Adam Zuckerman Apr 25 '14 at 15:43
I think you could theoretically make a base-pi number system, in which pi would be 1. I don't think it'd be very useful, though. – Magus Apr 25 '14 at 15:44
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. – Apr 25 '14 at 15:53
@Magus: I recall that some mathemeticians prefer to measure angles in radians instead of degrees. http://www.mathsisfun.com/geometry/radians.html I don't think it counts as a base-pi number system, but it is a system where measures are made against a quantity of pi. – FrustratedWithFormsDesigner Apr 25 '14 at 15:55
@Max: Those are not rational numbers so I don't think it's ever possible to represent them completely, because it is always possible to calculate one more decimal place. – FrustratedWithFormsDesigner Apr 25 '14 at 15:56
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?](http://math.stackexchange.com/questions/625473/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. – Apr 25 '14 at 15:59
@FrustratedWithFormsDesigner: That's only if you're thinking in base 10. If that number is the base, you don't have that problem. 1/3 is more naturally expressed in base 3 than base 10, because in base 3, there are no decimal points to calculate. Everything is relative to 3 already. In the same way, a number system with a base of an irrational number solves that problem, though the uses are generally obscure. – Magus Apr 25 '14 at 15:59
2

1/3 isn't irrational. – Adam Zuckerman Apr 25 '14 at 16:00
@AdamZuckerman: That's cool? I said 'in the same way'. My point is not about irrationality, its about counting. New number system: Pi is now 1. You can have multiples of it. Being rational or not has nothing to do with making a number system from it. – Magus Apr 25 '14 at 16:01
@Magus: I think that 1/3 is rational in base 10 because it can be expressed as a fraction. Could pi and sqrt(2) be expressed as fractions in base-pi and base-sqrt(2)? I don't think so because the decimal parts don't repeat, but I wish I remembered more of this math to prove it... :( – FrustratedWithFormsDesigner Apr 25 '14 at 16:02
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](http://en.wikipedia.org/wiki/Rational_number), 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 '14 at 16:39
5

@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: http://math.stackexchange.com/questions/625473/if-a-number-is-irrational-in-base-10-is-it-irrational-in-other-bases – Apr 25 '14 at 16:39
2

@Max I think it would be more accurate to say that irrational numbers cannot be precisely expressed using a rational base. That is part of the reason why we use non-numeric glyphs to represent them. – Apr 25 '14 at 16:49

score 1 · Answer 3 · answered Apr 25 '14 at 17:30

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.

score 0 · Answer 4 · answered Mar 27 '23 at 17:10

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.

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

4 Answers4