How can I detect if a float has a repeating decimal expansion in C#?

Question

I simply need to know how I can detect repeating decimal expansion in floats.

Example:

0.123456789123456789

The repeating portion of the number would be 123456789.

I want to automatize this in C#, is there any smart solution?

Answer 1

There's a nice trick for calculating rational approximations to a given float (based on some properties of Euclid's algorithm for GCDs). We can use this to determine whether or not the "best" approximation is of the form A/(2^a 5^b), if it is then the float terminates (in base 10), if not it will have some repeating component. The tricky bit will be determining which of the approximations is the right one (due to floating point precission issues).

So heres how you get approximate rational expressions.

First iterate x = 1/x - floor(1/x) keeping track of int(x)

x = 0.12341234
1/x = 8.102917
x <= 1/x - 8 = 0.102917
1/x = 9.7165
x <= 1/x - 9 = 0.71265277
1/x = 1.3956
x < 1/x - 1 = 0.3956
...

Next stick the int parts of x into the top row of this table, call them k_i. The values A_i = A_{i-2} + k_i * A_{i-1} and the same for B_i.

           ||  8      |  9  | 1   | 2   | 1   |  1  |    8 |    1 |    1
A =    1 0 ||  1      |  9  | 10  | 29  | 39  |  68 |  583 |  651 | 1234
B =    0 1 ||  8      | 73  | 81  | 235 | 316 | 551 | 4724 | 5275 | 9999

The rational approximations are then A_n/B_n.

1/8       = 0.12500000000000000     | e = 1.5e-3
9/73      = 0.12328767123287671     | e = 1.2e-4
10/81     = 0.12345679012345678     | e = 4.4e-5
29/235    = 0.12340425531914893     | e = 8.1e-6
39/316    = 0.12341772151898735     | e = 5.4e-6
68/551    = 0.12341197822141561     | e = 3.6e-7
583/4724  = 0.12341236240474174     | e = 2.2e-8
651/5275  = 0.12341232227488151     | e = 1.8e-8
1234/9999 = 0.12341234123412341     | e = 1.2e-9

So if we decide our error is low enough at the 1234/9999 stage, we note that 9999 can not be written in the form 2^a 5^b, and thus our decimal expansion is repeating.

Note that while this seems to require a lot of steps we can get faster convergence if we use x = 1/x - round(1/x) (and keep track of round round(1/x) instead). In that case the table becomes

     8  10    -4     2      9     -2
1 0  1  10   -39   -68   -651   1234
0 1  8  81  -316  -551  -5275   9999

This gives you a subset of the previous results, in fewer steps.

It is interesting to note that the fraction A_i/B_i is always such that A_i and B_i have no common factors so you dont event need to worry about canceling out factors or anything like that.

For comparison lets look at the expansion for x = 0.123. The table we get is:

      8   8   -3    -5  
 1 0  1   8  -23   123
 0 1  8  65 -187  1000

Then our sequence of approximations is

 1/8      = 0.125       e = 2.0e-3
 8/65     = 0.12307..   e = 7.6e-5
 23/187   = 0.12299..   e = 5.3e-6
 123/1000 = 0.123       e = 0

And we see that 123/1000 is exactly the fraction we want and since 1000 = 10^3 = 2^3 5^3 our fraction is terminating.

If you actually want to find out what the repeating part of the fraction is (what digits and what period) you need to do some additional tricks. This involves factoring the denominator and finding the lowest number (10^k-1) with all those factors (other than 2 and 5), then k will be your period. So for our top case we found A = 9999 = 10^4-1 (and thus 10^4-1 contains all the factors of A - we were kind of lucky here...) so the period of the repeating part is 4. You can find more details about this final part here.

A final and important aspect of not of this algorithm is that it does not require all the digits to mark a decimal expansion as repeating. Consider x = 0.34482, this has the table:

     3 -10 -156
1 0  1 -10   . 
0 1  3 -29   .

We get a very accurate approximation at the second entry and stop there, concluding that our fraction is probably 10/29 (as that gets use within 1e-5) and from the tables in the link above we can discern that its period will be 28 digits. This could never be determined using string searches on the short version of the number, which would require at least 57 digits of the number to be known.

Answer 2

you can't detect period like in your example as for representation in base 10, precision of float is 7 digits.

http://msdn.microsoft.com/en-us/library/aa691146%28v=vs.71%29.aspx

Answer 3

You can isolate the fractional (post-period) part of the number like this:

value - Math.Floor(value)

If you do this with the double value "1.25", you'll end up with the value "0.25". Thus, you'll have isolated the part "to the right of the period". Of course, you'll have it as a double between 0 and 1, and not an integer as your question seems to require.

Your question states that you need to "detect periods in floats". If all you need is to determine if a fractional part exists, the following code will approximately work:

value != Math.Floor(value)

Answer 4

Personally I would convert it to a String, snag the substring of everything after the period, then convert to the data type you need it in. For example (It's been years since I wrote any C# so forgive any syntax problems):

float checkNumber = 8.1234567;
String number = new String( checkNumber ); // If memory serves, this is completely valid
int position = number.indexOf( "." ); // This could be number.search("."), I don't recall the exact method name off the top of my head
if( position >= 0 ){ // Assuming search or index of gives a 0 based index and returns -1 if the substring is not found
    number = number.substring( position ); // Assuming this is the correct method name to retrieve a substring.
    int decimal = new Int( number ); // Again, if memory serves this is completely valid
}

Answer 5

You can't.

Floating-point has finite precision. Every value of type float is an integer multiple of an integer power of 2.0 (X * 2^Y), where X and Y are (possibly negative) integers). Since 10 is a multiple of 2, every value of type float can be represented exactly in a finite number of decimal digits.

For example, although you might expect 1.0f/3.0f to be represented as a repeating decimal (or binary) number, in fact float can only hold a close approximation of the mathematical value, one that isn't a repeating decimal (unless you count the repeating 0 that follows the non-zero digits). The stored value is likely to be exactly 0.3333333432674407958984375; only the first 7 or so digits after the decimal point are significant.

Answer 6

I don't think that there's solution in general (at least, with float/double):

• period can bee too long for float (or even double);
• float/double are approximate values.

E.g., here's a result of division (double)1/(double)97:

0.010309278350515464

Indeed, it is a repeating decimal with 96 repeating digits in period. How to detect this, if you only have 18 digits after decimal point?

Even in decimal there's not enough digits:

0.0103092783505154639175257732