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?
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?
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
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):
You can isolate the fractional (post-period) part of the number like this:
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:
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 * 2Y), where X and Y are (possibly negative) integers). Since 10 is a multiple of 2, every value of typefloat
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 factfloat
can only hold a close approximation of the mathematical value, one that isn't a repeating decimal (unless you count the repeating0
that follows the non-zero digits). The stored value is likely to be exactly0.3333333432674407958984375
; only the first 7 or so digits after the decimal point are significant.I don't think that there's solution in general (at least, with
float
/double
):float
(or evendouble
);float
/double
are approximate values.E.g., here's a result of division
(double)1/(double)97
: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: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 ofint(x)
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 forB_i
.The rational approximations are then
A_n/B_n
.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 becomesThis 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:
Then our sequence of approximations is
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:
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.