1

In decimal (base 10), 1/3 can only be approximated to 0.33333 repeating.

What number is the equivalent in binary that can only be represented as an approximation?

GEOCHET
  • 21,119
  • 15
  • 74
  • 98
Ted
  • 57
  • 1
  • 3
  • 2
    Looks like homework to me, so I added the tag. I think that the question is legit, though, so I vote against closing. – JSBձոգչ Nov 04 '09 at 15:21
  • 2
    No, I am curious to know since this has implication when dealing with for loops and how you break/stop execution. For example, if you had (for i=1/3; i == 1; i++), this loop would never break if it was executed in base 10 – Ted Nov 04 '09 at 15:22
  • I'm simply just curious. I think it's 0.1 but am not certain – Ted Nov 04 '09 at 15:23
  • 0.9999 (repeating) == 1. See: http://en.wikipedia.org/wiki/0.999... – Andrew Song Nov 04 '09 at 15:23
  • 6
    @Ted: It's every number that can't be expressed as `k/2^n` for integer `k` and whole number `n`. – Welbog Nov 04 '09 at 15:23
  • Don't compare floating point numbers for equality, it will always end up biting you in the end. Just go with the rule that any floating point math is approximate. – SoftMemes Nov 04 '09 at 15:24
  • 0.9999 does not equal 1 to a computer. – Ted Nov 04 '09 at 15:24
  • 6
    _Never_ use a specific float value comparison, use a range: i >= 0.3332 && i <= 0.3334 – Ben S Nov 04 '09 at 15:24
  • Ted, depends on how you've defined i. It won't make sense if it's an integer anyway. – John Nov 04 '09 at 15:25
  • 1
    @Ted: Just like you can't express any number in base 10 without repeating if it can't be expressed in the form `k/10^n`. `1/3` is only one of infinite such numbers. Math Overflow can help you out a lot more than Stack Overflow can. – Welbog Nov 04 '09 at 15:25
  • 1
    FYI: http://mathoverflow.net/ – Welbog Nov 04 '09 at 15:26
  • I understand closing this question because it's similar to others, but I don't agree with the reasoning that it is "not programming related." Of course it's programming related. – John D. Cook Nov 04 '09 at 15:29
  • 1
    @John D. Cook: It's math related. This isn't a question specific to integer or floating-point encodings or anything marginally computer-science related like that. It's a simple math question and belongs on a math Q&A site. Luckily, we happen to have one handy. – Welbog Nov 04 '09 at 15:32
  • So many responses but the real answer is nowhere to be found. – shoosh Nov 04 '09 at 15:32
  • 2
    I am in complete astonishment that people don't find this a programming questions. This must be a Computer Science vs Learn-it-yourself programming example. Since Computer Scientists would most definitely find this programming related. – Ted Nov 04 '09 at 15:35

10 Answers10

5

0.1 is one such example, as well as 0.2

This question is also similar to this other SO question, which already has very good answers.

Community
  • 1
  • 1
Andrew Song
  • 3,120
  • 1
  • 27
  • 22
  • So, 0.1 and 0.2 can't be represented. Does that imply that 0.3, 0.4, 0.5 also cannot be represented? – Ted Nov 04 '09 at 15:26
  • 0.5 is 0.1 in binary, so that's no problem. 0.3 would be 0.01001100110011..., 0.4 is 0.0110011001100110011... – Joren Nov 04 '09 at 15:41
  • 3
    @Ted: Like I said in a comment to your question, this is a base problem, not a floating-point problem. A number can be written in finite space in a given base if the number can be written in the form `k/b^n`, where `b` is the base in question, `k` is an integer, and `n` is a whole number. In this case, `b=2`, and 0.1, 0.2, 0.3 and 0.4 can't be written in this form. 0.5, however, can: `1/2`. So can .75: `3/4`. – Welbog Nov 04 '09 at 15:41
  • 2
    Likewise, `.3333`... can't be expressed in finite space in base 10, because `1/3` isn't in the form `k/10^n`. But in base 3, `1/3` is represented as `0.1`, because it's in the form `k/3^n`. You can extrapolate this to any real number in a natural base. – Welbog Nov 04 '09 at 15:43
  • 2
    @Welbog: A rational number `p/q` with `(p, q) = 1` can be expressed a finite representation in base `b` if and only if every prime factor of `q` divides `b`. – jason Nov 04 '09 at 16:13
  • @Jason: That's a much stronger way of saying what I said, yeah. Numbers expressed in terms of the base's prime factors can still be expressed in terms of the base itself. For example: `1/2` can be expressed as `5/10`. I'd use your way of expressing it to someone with a strong mathematical background because it's more robust and allows me to express rationals in their simplest forms, but I'm trying to explain this concept to someone who thinks this is a programming question so I have to keep it simple. – Welbog Nov 04 '09 at 16:22
3

A better question is to ask what numbers can be represented exactly in binary. Everything else can only be approximated or not represented at all.

See What every computer scientist should know about floating point arithmetic.

John D. Cook
  • 29,517
  • 10
  • 67
  • 94
2

Well, there are infinite numbers that can't be precisely represented in that notation, but here's one: 1/10.

Brian Schroth
  • 2,447
  • 1
  • 15
  • 26
  • It turns out that almost all rational numbers can not be expressed in a finite binary representation. – jason Nov 04 '09 at 16:30
  • Ahhh orders of infinity. Aleph null, anyone? There are an infinite number of numbers which can and cannot be represented. – S.Lott Nov 04 '09 at 17:11
  • 1
    @S.Lott: "Almost all" is a measure-theoretic concept, not a cardinal-number concept. – jason Nov 05 '09 at 15:14
2

I am assuming that you mean to ask which rational numbers can be expressed in binary using a finite representation. I am deducing this from your example of 1/3 in decimal. The fact is that every rational number can be expressed in binary if you allow infinite representations. But this question is only interesting from a computer science perspective if you only permit finite representations. I am further assuming that you are not asking about specific computer representations (say, IEEE 754) but rather merely asking about general positional representations.

A rational number p/q with (p, q) = 1 can be expressed a finite representation in base b if and only if every prime factor of q divides b. No irrational numbers have a finite representation in any base.

In particular, a rational number p/q with (p, q) = 1 can be expressed as a finite representation in binary if and only if every prime factor of q divides 2. That is, the only rational numbers p/q with (p, q) = 1 that have a finite representation in binary are those where q = 2^k for some nonnegative integer k. Moreover, all such rational numbers can be expressed in a finite representation in binary. These numbers are known as dyadic rationals.

jason
  • 236,483
  • 35
  • 423
  • 525
1

It's every number that can't be expressed as k/2^n for integer k and whole number n.

The easy way to find all these numbers is to write down some prime numbers that do not include 2. 3, 5, 7, 11, 13, 17 and 19 are good examples of prime numbers that don't include 2.

Start multiplying. 1/3, 2/3, 1/5, 2/5, 3/5, 4/5, 1/6, 5/6, 1/7, 2/7, etc.

if you do this -- and you avoid numbers of the form k/2^n -- you'll enumerate every possible fraction that cannot be exactly represented in binary.

You should probably stop enumerating when you get to numbers for which the left-most 64-bits are all identical.

S.Lott
  • 384,516
  • 81
  • 508
  • 779
1

The numbers that can be exactly represented in base 2 are the dyadic rationals. These are numbers that can be written in the form k/2^n for some integer k and whole number n. Any number that cannot be written in that form will have a non-terminating representation in base 2.

However, you seem to be asking not about what numbers are representable in base 2, but rather what numbers are representable in some fixed floating-point type, such as float or double. This is a more subtle question; any number that is not a dyadic rational cannot be represented, but not all dyadic rationals can be represented either.

Stephen Canon
  • 103,815
  • 19
  • 183
  • 269
0

In python 2.4:

>>> 1.0 / 5.0
0.20000000000000001

That indicates that base 2 has a hard time representing it exactly.

gahooa
  • 131,293
  • 12
  • 98
  • 101
0

binary(.00011001100110011...) == decimal(.1)

Zack Burt
  • 8,257
  • 10
  • 53
  • 81
-2

I'm going to take a stab at infinity

Mobs
  • 1,572
  • 12
  • 17
-2

The same set of numbers that can't be exactly represented by base 10 can't exactly be represented by base 2. There shouldn't be a difference there.

GEOCHET
  • 21,119
  • 15
  • 74
  • 98
Dean J
  • 39,360
  • 16
  • 67
  • 93
  • Please see the link in my answer. – Andrew Song Nov 04 '09 at 15:26
  • +1 because this is a correct statement, even though it might not be worded as well as it could be. Dean is saying that (inability to express finitely in base 10) => (inability to express finitely in base 2), which is correct, since every number finitely expressible in base 2 is finitely expressible in base 10. A => B if and only if !B => !A. It's easy to show that a number in the form `k/2^n` can be expressed in the form `k/10^n`, therefore it is correct to state that if it can't be expressed as `k/10^n`, it can't be expressed as `k/2^n`. – Welbog Nov 04 '09 at 16:18
  • 1
    He is **not** saying that (ability to express finitely in base 10) => (ability to express finitely in base 2). That would be categorically wrong. – Welbog Nov 04 '09 at 16:19