5 ms·

It's actually pretty simple. When you have a base 10 system (like ours), it can only express fractions that use a prime factor of the base. In a way, not so si

by msie 10y ago

It's actually pretty simple. When you have a base 10 system (like ours), it can only express fractions that use a prime factor of the base. In a way, not so simple (obvious to you? not to me)

jacobolus 10y ago
It’s not obvious that 1/7 cannot be expressed in decimal, or 1/5 cannot be expressed in binary?
- bcook 10y ago
  >I thought people learned this sort of thing in grade school. Along with tact and general respect for others?
  - jacobolus 10y ago
    This is a discussion of the vagaries of floating point math, on a forum for programmers. I would expect that most folks learned something about how to carry out decimal long division in ~3th–6th grade sometime. If we can’t assume any kind of common base-line level of background experience but need to re-hash all of school mathematics in every conversation, then it’s hard to have a technical discussion. There’s absolutely nothing wrong with not having an understanding of this point, or forgetting grade school arithmetic, and I’m not trying to be condescending, but it seems weird for the top-level poster to call out the the article’s language. The idea that some fractions don’t have a terminating decimal expansion is “pretty simple” in the context of any reasonable standard for discussion among programmers. Here’s the language from the article. Is it really that confusing? > When you have a base 10 system (like ours), it can only express fractions that use a prime factor of the base. The prime factors of 10 are 2 and 5. So 1/2, 1/4, 1/5, 1/8, and 1/10 can all be expressed cleanly because the denominators all use prime factors of 10. In contrast, 1/3, 1/6, and 1/7 are all repeating decimals because their denominators use a prime factor of 3 or 7. In binary (or base 2), the only prime factor is 2. So you can only express fractions cleanly which only contain 2 as a prime factor. In binary, 1/2, 1/4, 1/8 would all be expressed cleanly as decimals. While, 1/5 or 1/10 would be repeating decimals. If the top-level poster was confused and wanted help, he/she could have said something like “Can someone explain this point to me? I don’t understand what it means for 1/7 to be a ‘repeating decimal’, or what a ‘prime factor of the base’ means.”
    - imh 10y ago
      >If we can’t assume any kind of common base-line level of background experience but need to re-hash all of school mathematics in every conversation, then it’s hard to have a technical discussion. We can have any kind of discussion we want, but whatever the participant's level of understanding, talking down to them is unacceptable. You don't need to dumb things down here, but when someone doesn't understand what you meant, you can ignore it or help out, just don't be condescending.
    - jacobolus 10y ago
      Apparently the explanation in the linked article originally came from a Hacker News comment a year and a half ago, https://news.ycombinator.com/item?id=10560130 https://news.ycombinator.com/item?id=10560130
Someone 10y ago
If you can write n=p/q with p and q relatively prime using d digits after the decimal point in base 10, 10^d times n is an integer. We also have 10^d*n = 10^d*p/q so 10^d*p must be divisible by q. Since p and q are relatively prime, 10^d must be divible by q. That's only possible if all prime factors of q are 2 or 5.
joatmon-snoo 10y ago
A maths professor, during their lecture, says "obviously, we now have equation 42" when a student interrupts, asking "how is that obvious?" The professor looks back at the blackboard, starts to speak, but then remains silent as a consternated look falls across their face. After ten minutes of silent pondering, they erase three blackboards and manically fills them with equations, derivations, and other expressions. After another half-hour of furious scribbling--eventually filling both sides of two more free-standing chalkboards--they exclaim, "AHA! It is obvious!"
contravariant 10y ago
It's phrased incredibly badly, but basically you can only write a fraction with a finite number of decimals if the denominator divides 10^k (for some k). This means the denominator can't have prime factors other than 2 and 5 (which are the two prime factors of the base). This last statement isn't exactly trivial, but is reasonably easy to prove.
VLM 10y ago
Modern, lets say, post turn of the century popular languages all support some kind of rational data type allowing native fraction arithmetic. https://en.wikipedia.org/wiki/Rational_data_type https://en.wikipedia.org/wiki/Rational_data_type Anyway... It turns out that humans like numbers that are evenly spaced like 1/10, 2/10 (1/5), 3/10, 4/10. That all seems pretty evenly spaced to us, but its actually totally arbitrary that we have 10 handy (ugh the puns) appendages. If we chill with space aliens they will think numbers are evenly spaced like 1/14, 2/14 (aka 1/7), 3/14, 4/14 (aka 2/7)... much like jamming a metric socket on an imperial nut to fix your car, the amount of error varies wildly base on size. You can get away with a 9/16 socket on a 10 mm nut most times, but a 15/16th socket will probably require a hammer to fit a 24mm nut. Or just round off all the nuts with a vise-grip pliers. Anyway the space alien's 7/14 is actually a perfect match to our 5/10 but the amount of error varies from not much, to quite a bit, in the other attempts at interplanetary standardization. Likewise if you think of the computer as a space alien (not too far from truth, I sometimes feel) it uses binary and thinks numbers like 1/8, 2/8 (1/4), 3/8, are evenly spaced. Or as some specific example expressing our 1/2 in floating point is pretty easy for most computers while expressing 1/5 or 1/3 is somewhat less successful, or somewhat far in error compared to our closest 1/10th based numbers. In the old days like half a century ago there were competing software floating point designs with varying levels of success vs speed. Everything is super boring today and standardized. 72 bit pdp-10 floating point was from a romantic adventurous era, like an Indiana Jones movie (well, one of the good ones). IEEE 754 is modern and better in all regards, yet has all the panache and style of a modern econobox commuter car. Think of the glory of PDP8 Fortran floating point spread unevenly across three words of four octal digits, 2 bits of signs, 2 bits MSB of mantissa, and 8 bits of exponent in the first 12 bit octal word, now that is something glorious to wake up to in the morning.
- hanoz 10y ago
  > appendages a.k.a. digits!
- spc476 10y ago
  Thirty years ago the BASIC languages of the 8-bit computers used non-IEEE 754 floating point math (most typical I've found is 5-byte version---one byte for sign, one for exponent, three for mantissa).
micahbright 10y ago
It's actually pretty simple, if you've taken prime number theory. FTFY
- FabHK 10y ago
  > It's actually pretty simple, if you've taken prime number theory. Or if it's explained a bit more intuitively. A terminating decimal fraction 0.xyz (in base 10) is basically xyz / 1000 Now, 1000 = 2x5 x 2x5 x 2x5. So, if you have any fraction n / d, and the denominator d has only factors 2 and 5, then you can "fill up" the remaining 2's or 5's to get a power of 10, and write it as a terminating decimal fraction: 3 / 25 = 3 * 4 / (25 * 4) = 12/100 = 0.12 7 / 8 = 7 * 125 / (8 * 125) = 875/1000 = 0.875 etc. But, if the denominator d has any factors other than 2's and 5's, there is just no way you can multiply any further integers with it to get a power of ten. A decimal floating point would then be not only 0.875, say, but 0.0000875 or 875000. So, now you say: 875/1000 x 10^E, where the 875 is your (3-digit) mantissa and the E your exponent. But that's still always an integer divided by a power of 10. So, if what we try to represent is a fraction with a denominator that has prime factors other than 2 and 5, there's no way we can represent it as a floating point decimal fraction. Similarly, a IEEE 754 floating point is basically 10011010101 / 2^53 * 2^E (with some abuse of notation, where the first part is a binary mantissa...). But, that's fundamentally still an integer divided by a power of 2. So, if what we try to represent is a fraction with a denominator that has prime factors other than 2, there's no way we can represent it as a floating point binary fraction, and therefore not as a Float64. Edit: use x for multiplication to avoid italics...
protonfish 10y ago
I get angry every time I read about floating point being discussed by people who don't understand how numbers work, but I am going to try not to rant and be constructive. Think of if this way. You can express the fraction 1/2 in decimal (0.5) and binary because 2 is evenly divisible into both 10 and 2. You can't represent 1/3 in either but you could in trinary (0, 1, 2 - it would be 0.1) Now, why programmers feel the numbers you can't represent exactly in binary are somehow worse than the ones in decimal baffles me. I guess we are just used to them and anything else seems wrong. But they are just as legitimate.
Dylan16807 10y ago
If you word it the right way, it can be very simple/'obvious'. "Moving the decimal point divides by 10. You can ONLY make fractions of 10 via the decimal point." That plus a couple examples should do fine. No need to mention prime numbers. No need to use variables.

by msie 10y ago

It's actually pretty simple. When you have a base 10 system (like ours), it can only express fractions that use a prime factor of the base. In a way, not so simple (obvious to you? not to me)

jacobolus 10y ago

It’s not obvious that 1/7 cannot be expressed in decimal, or 1/5 cannot be expressed in binary?

bcook 10y ago
>I thought people learned this sort of thing in grade school. Along with tact and general respect for others?
- jacobolus 10y ago
  This is a discussion of the vagaries of floating point math, on a forum for programmers. I would expect that most folks learned something about how to carry out decimal long division in ~3th–6th grade sometime. If we can’t assume any kind of common base-line level of background experience but need to re-hash all of school mathematics in every conversation, then it’s hard to have a technical discussion. There’s absolutely nothing wrong with not having an understanding of this point, or forgetting grade school arithmetic, and I’m not trying to be condescending, but it seems weird for the top-level poster to call out the the article’s language. The idea that some fractions don’t have a terminating decimal expansion is “pretty simple” in the context of any reasonable standard for discussion among programmers. Here’s the language from the article. Is it really that confusing? > When you have a base 10 system (like ours), it can only express fractions that use a prime factor of the base. The prime factors of 10 are 2 and 5. So 1/2, 1/4, 1/5, 1/8, and 1/10 can all be expressed cleanly because the denominators all use prime factors of 10. In contrast, 1/3, 1/6, and 1/7 are all repeating decimals because their denominators use a prime factor of 3 or 7. In binary (or base 2), the only prime factor is 2. So you can only express fractions cleanly which only contain 2 as a prime factor. In binary, 1/2, 1/4, 1/8 would all be expressed cleanly as decimals. While, 1/5 or 1/10 would be repeating decimals. If the top-level poster was confused and wanted help, he/she could have said something like “Can someone explain this point to me? I don’t understand what it means for 1/7 to be a ‘repeating decimal’, or what a ‘prime factor of the base’ means.”
  - imh 10y ago
    >If we can’t assume any kind of common base-line level of background experience but need to re-hash all of school mathematics in every conversation, then it’s hard to have a technical discussion. We can have any kind of discussion we want, but whatever the participant's level of understanding, talking down to them is unacceptable. You don't need to dumb things down here, but when someone doesn't understand what you meant, you can ignore it or help out, just don't be condescending.
  - jacobolus 10y ago
    Apparently the explanation in the linked article originally came from a Hacker News comment a year and a half ago, https://news.ycombinator.com/item?id=10560130 https://news.ycombinator.com/item?id=10560130

Someone 10y ago

If you can write n=p/q with p and q relatively prime using d digits after the decimal point in base 10, 10^d times n is an integer. We also have 10^d*n = 10^d*p/q so 10^d*p must be divisible by q. Since p and q are relatively prime, 10^d must be divible by q. That's only possible if all prime factors of q are 2 or 5.

joatmon-snoo 10y ago

A maths professor, during their lecture, says "obviously, we now have equation 42" when a student interrupts, asking "how is that obvious?" The professor looks back at the blackboard, starts to speak, but then remains silent as a consternated look falls across their face. After ten minutes of silent pondering, they erase three blackboards and manically fills them with equations, derivations, and other expressions. After another half-hour of furious scribbling--eventually filling both sides of two more free-standing chalkboards--they exclaim, "AHA! It is obvious!"

contravariant 10y ago

It's phrased incredibly badly, but basically you can only write a fraction with a finite number of decimals if the denominator divides 10^k (for some k). This means the denominator can't have prime factors other than 2 and 5 (which are the two prime factors of the base). This last statement isn't exactly trivial, but is reasonably easy to prove.

VLM 10y ago

Modern, lets say, post turn of the century popular languages all support some kind of rational data type allowing native fraction arithmetic. https://en.wikipedia.org/wiki/Rational_data_type https://en.wikipedia.org/wiki/Rational_data_type Anyway... It turns out that humans like numbers that are evenly spaced like 1/10, 2/10 (1/5), 3/10, 4/10. That all seems pretty evenly spaced to us, but its actually totally arbitrary that we have 10 handy (ugh the puns) appendages. If we chill with space aliens they will think numbers are evenly spaced like 1/14, 2/14 (aka 1/7), 3/14, 4/14 (aka 2/7)... much like jamming a metric socket on an imperial nut to fix your car, the amount of error varies wildly base on size. You can get away with a 9/16 socket on a 10 mm nut most times, but a 15/16th socket will probably require a hammer to fit a 24mm nut. Or just round off all the nuts with a vise-grip pliers. Anyway the space alien's 7/14 is actually a perfect match to our 5/10 but the amount of error varies from not much, to quite a bit, in the other attempts at interplanetary standardization. Likewise if you think of the computer as a space alien (not too far from truth, I sometimes feel) it uses binary and thinks numbers like 1/8, 2/8 (1/4), 3/8, are evenly spaced. Or as some specific example expressing our 1/2 in floating point is pretty easy for most computers while expressing 1/5 or 1/3 is somewhat less successful, or somewhat far in error compared to our closest 1/10th based numbers. In the old days like half a century ago there were competing software floating point designs with varying levels of success vs speed. Everything is super boring today and standardized. 72 bit pdp-10 floating point was from a romantic adventurous era, like an Indiana Jones movie (well, one of the good ones). IEEE 754 is modern and better in all regards, yet has all the panache and style of a modern econobox commuter car. Think of the glory of PDP8 Fortran floating point spread unevenly across three words of four octal digits, 2 bits of signs, 2 bits MSB of mantissa, and 8 bits of exponent in the first 12 bit octal word, now that is something glorious to wake up to in the morning.

hanoz 10y ago
> appendages a.k.a. digits!
spc476 10y ago
Thirty years ago the BASIC languages of the 8-bit computers used non-IEEE 754 floating point math (most typical I've found is 5-byte version---one byte for sign, one for exponent, three for mantissa).

micahbright 10y ago

It's actually pretty simple, if you've taken prime number theory. FTFY

FabHK 10y ago
> It's actually pretty simple, if you've taken prime number theory. Or if it's explained a bit more intuitively. A terminating decimal fraction 0.xyz (in base 10) is basically xyz / 1000 Now, 1000 = 2x5 x 2x5 x 2x5. So, if you have any fraction n / d, and the denominator d has only factors 2 and 5, then you can "fill up" the remaining 2's or 5's to get a power of 10, and write it as a terminating decimal fraction: 3 / 25 = 3 * 4 / (25 * 4) = 12/100 = 0.12 7 / 8 = 7 * 125 / (8 * 125) = 875/1000 = 0.875 etc. But, if the denominator d has any factors other than 2's and 5's, there is just no way you can multiply any further integers with it to get a power of ten. A decimal floating point would then be not only 0.875, say, but 0.0000875 or 875000. So, now you say: 875/1000 x 10^E, where the 875 is your (3-digit) mantissa and the E your exponent. But that's still always an integer divided by a power of 10. So, if what we try to represent is a fraction with a denominator that has prime factors other than 2 and 5, there's no way we can represent it as a floating point decimal fraction. Similarly, a IEEE 754 floating point is basically 10011010101 / 2^53 * 2^E (with some abuse of notation, where the first part is a binary mantissa...). But, that's fundamentally still an integer divided by a power of 2. So, if what we try to represent is a fraction with a denominator that has prime factors other than 2, there's no way we can represent it as a floating point binary fraction, and therefore not as a Float64. Edit: use x for multiplication to avoid italics...

protonfish 10y ago

I get angry every time I read about floating point being discussed by people who don't understand how numbers work, but I am going to try not to rant and be constructive. Think of if this way. You can express the fraction 1/2 in decimal (0.5) and binary because 2 is evenly divisible into both 10 and 2. You can't represent 1/3 in either but you could in trinary (0, 1, 2 - it would be 0.1) Now, why programmers feel the numbers you can't represent exactly in binary are somehow worse than the ones in decimal baffles me. I guess we are just used to them and anything else seems wrong. But they are just as legitimate.

Dylan16807 10y ago

If you word it the right way, it can be very simple/'obvious'. "Moving the decimal point divides by 10. You can ONLY make fractions of 10 via the decimal point." That plus a couple examples should do fine. No need to mention prime numbers. No need to use variables.