News for hackers. Stuff that matters.
Re:Is there any point to the 12 times table? by Terr_ on Monday January 04, 2016 @05:47PM (#10839350)
Making a self-reply here, I think I know how to show binary is "worse" when it comes to un-representable rational numbers. I'm not a math major, so this is probably some incredibly obvious textbook stuff to somebody else, but...

In base-N, you can accurately write any fraction of (1/y) provided that y can be expressed using the same prime-factors found in N.

For example, 10 has the prime factors of 2 and 5, leading to the requirement that y=(2^a × 5^b) .

This means base-10 can accurately represent (1/80), because 80 = (2^4 × 5^1). In base-2, you're limited to stuff in the form (2^a).

Finally, the, uh, infinity-of-integers that matches (2^a) is always going to be "smaller" than the infinity which can be matched by (2^a × 5^b), since the latter "contains" the former when b=0.

Re:Is there any point to the 12 times table? by btilly on Monday January 04, 2016 @07:39PM (#10840049)
Your argument is intuitively correct, but formalizing it requires a very careful choice of "smaller than". In particular all of the infinities in question are countable, so in some sense they are the "same size".

But there are two approaches that we can use.

The first is to point out that in real life it is more common to encounter small numbers than big ones. So if you choose a probability distribution for what denominators you expect in practice, and sum up the values of all of the exactly represented numbers, you can get to a fixed probability of even division. And it won't be zero.

Unfortunately your choice of the relative probability of having a 2 in the denominator versus a 3 is extremely arbitrary. So while the approach makes sense, the numbers you get really will be made up. (Though no matter how you make them up, your general statement is guaranteed correct.)

The second approach is to just look at how the count of exactly representable numbers below N scales with both N and your set of primes. This has been studied. The exact counts are a mess, but if you have a set S of prime divisors of size k, then the count is (1+o(1)) * 1/k! * [product over p in S of (log(N)/log(p)].

The upshot is that for large N, more prime factors always wins. And for specific prime factors, you just look at the ratio of logs.

For instance with this approach we can say that log(3)/log(5) = 1.46497352071793... times as many denominators are exactly representable in base 12 as in base 10. (The log(2) factors cancel out.) Therefore base 12 is better.

Of course the second approach says that base 6 is as good as base 12, and it is smaller, so why not use it? Well, the reason why we keep on winding up with base 12 in practical situations is that divisibility by 4 comes up a lot. It isn't just exactly representable that matters, efficiency matters.

Re:Is there any point to the 12 times table? by dnautics on Monday January 04, 2016 @06:09PM (#10839483)
no. You can accurately represent anything which is k*2^n, where (k,n) are integers. Simple example: 3 is not 2^n but obviously expressing 3 as a floating point is not a problem. Similarly 1.5, etc.

In this fashion, primes p seem "better" as they increase, because for a given size limits on k and n, you get more 'numbers' per unit space on the real line. Composite numbers are 'even better', but there are a lot of pains in the ass with composite numbers, stemming from Z/nZ not being a field if n not prime.

Ultimately, though, your internal representation is binary, using anything not two produces other inefficiency. That's why IEEE 754 BCD is not base-10 but base-1000 (since 2^10 = 1024 which is the closest a power of two gets to a power of 10, for bit-wise representation efficiency). We don't have bi-quinary computers.

Re:Is there any point to the 12 times table? by Terr_ on Monday January 04, 2016 @08:25PM (#10840292)
Once you know you can accurately represent (1/y) in a given base, you've established do not need an infinite number of digits to the right of the radix-point no matter how many times you multiply it by an integer.

In fact, I think it exemplifies the upper bound for the number of digits you'd need for "related fractions". For example, we know "one eighth" is expressible in decimal as 0.125. Even if you pick a really big N value, N * (1/8) should never need more than three digits to the right of the decimal point.