In the previous post, we found that fractional numbers are a problem when you squeeze them into a fixed number of digits.  More importantly, we found that the fractions that require a repeating sequence of digits to represent will vary depending on number base.

We typically work in base 10.  Apparently it is because we have 10 fingers. It isn’t a very clever base to have picked for our base, because it only has 2 factors, 2 and 5.  It is easy to find out if a number is divisible by 2 or 5, but not so easy for the other digits.  Perhaps this is why early measurement systems circumvented the problem by introducing things like 12 ounces to the pound, because 12 is a number nicer base for dividing things up.

Anyway, we use base 10. Its factors are 2 and 5.  Our computers use base 2.  Its factors are none (it is prime). Luckily, 2 itself is a factor of 10, so at least we can express things like one half and one quarter as non-repeating decimals in both bases.  One half is 0.5 in base 10 and 0.1 in base 2.  If our computers were tri-state machines, base 3, then there would be no non-repeating numbers that could be expressed in one that could also be expressed in the other.   I predict that if this was the case, our programming languages, and maybe even our processors, would have developed the ‘rational’ type a long time ago.

Anyway, the inability to represent a fraction as a fixed number of digits has a problem in a machine with a fixed number of digits available to represent numbers.  The Patriot missile was one of those, as are most other computers.

Going back to the number 0.1 (decimal) from the last blog post, which is a repeating sequence of digits in binary.  If a hypothetical machine has only 6 binary digits available for storing a number then 0.1 decimal will be stored as 0.000110 (which is actually 3/32 = 0.09375, not 0.1 as we wanted).  The machine is unable to store the number 0.1, even though to the user this is not a complex thing to have to store.  If the user wanted to store one third, and the field allowed only decimal sequences, then they might type 0.33333333 until the UI field was full, and they would accept that the number stored was nearly a third, not actually a third.

To improve the accuracy of 0.1 stored in 6 binary digits, you can ask why not have a power of 2 number so that we don’t need to store the leading zeros, making the number into a floating point number – in this case we could use 1.10011e-4, where the -4 means -4 powers of two.  Now we are closer, 51/512 = 0.099609375, still not 0.1 but closer. We could (like the IEEE) even accept that the “1.” part of the floating point is redundant (it will always start with that) so we could store .100110e-4, but this is still 51/512, although would have been more accurate for other examples.

Whatever we do, we cannot store 1/10 as a binary fixed point number, or floating point with a binary exponent.  There are two failings when we do.  The first is the sort that broke the Patriot missile, which is that if you do a lot of maths with the number then you end up accumulating a lot of error.

The second caused the problems in the UI which I was trying to fix.  The users were complaining that when they typed 0.1 into the UI, it was converted to 0.099999992374623 (or something like that).

Internally the s/w took that value from the UI, and converted it into a floating point number to store in the object model.  This was then fetched out by a “model/view” type thing, and converted to a decimal string.  The floating point number was not actually 0.1, and was not displayed as such.

There are several solutions to the problem.

One solution is to use a decimal fixed or floating point number. Newer programming languages than C++ have the decimal fixed point type. C# has a ‘decimal’ type, and Java has a BigInteger.  Both types have a decimal exponent, rather than a binary one.  So 0.1 can be stored as 1e-1, and 0.007 can be stored as 7e-3.  The disadvantage of this is that (unless it has passed me by), hardware doesn’t support native data types like this currently (except some variants of the IBM Power architecture).  Multiplying and dividing by 10 is a much more complex business than multiplying and dividing by 2 on a binary machine, so the hardware to support this data type isn’t typically available. The nice thing about this solution is that it solves the UI problem, but also accumulation of errors problem that caused the Patriot missile to have a fault.

However, if speed is an issue then using a decimal integer may not be acceptable.  In this case, another solution is to avoid moving the user’s input into an internal representation at all. The program can validate the user’s input, but store it as it was entered, as a string, so it can be presented back to them without any danger of corrupting it. Clearly this doesn’t solve the accumulation of errors, because at some point it needs to be converted to the approximate form to do whatever maths is required, but at least you avoid complaints from the users that their numbers are mangled by the application.

This is a topic that I have written on before, but I think it is interesting and often misunderstood. I once spent a few days thinking about a problem with one of the products I worked on, after some other engineers had spent many days on it too. There are other sources of information available, of course.
First I repeat the question recently asked on my Facebook page: when is a half (1/2) equal to 0.1111…?
The answer is at Dr Doolittle’s school for sloths and triffids. Or, in other words, in the number base 3 (sloths and trifids would presumably use base 3 for counting). This fact has an important consequence for user interface design, and for management of data in internal object models.
Representing 1/3 as a ‘decimal’ in base 3 is easy. It is 0.1. Likewise 2/3 is easy too, 0.2. However, 1/2 is represented as 0.11111… You can establish this by doing the long division. You cannot write 1/2 in a fixed number of base-3 digits, any more than you can express one third (1/3) in a fixed number of base-10 digits. And, importantly, any more than you can express one tenth (1/10) in base-2. Apparently this caused an American Patriot missile to fail, but it also caused a less dangerous error in a UI that I worked upon.

One tenth in base 2 is 0.0 0011 0011 0011 0011…

You could decompose any rational number into its prime factors, including those in the denominator. For instance 35/6 is 5×7/3×2. It is easy to tell whether a fraction will be inexpressable in some base. If every denominator factor is a factor of the base. In the previous example, if the base can be expressed as Nx2 + Mx3 the. the fraction would be represeted as a terminating sequence of digits. If not, then it would require a recurring sequence of digits.

More on this topic, about the conequence of using a limited number of digits, later

There are 6 orange sweets in a bag along with some others, with N total. The chance of getting 2 orange in a row is 1/3.  Show ‘N^2 – N – 90 = 0’

Probability of getting orange on first selection is 6/N (because there are N sweets and 6 are orange). 

Probability of getting second orange after getting the first is 5/(N-1) because there are now 5 orange sweets and N-1 total. 

So 6/N x 5/(N-1) = 1/3

6×5 / N(N-1) = 1/3

30×3 = N(N-1)

90 = N^2 – N

N^2 – N – 90 = 0

Due to a recent enforced change in employment status, I thought I might fill my time by writing some thoughts on the world of technology – or more specifically on software development.