Given a decimal number, find the smallest integer

问题:

Best to use an example to describe the problem. Lets say I have a decimal value 100.227273.

100.227273 * X = Y

I need to find the smallest positive integer X that gives integer Y.

回答1:

If the 100.227273 is just an approximation and you want to get the best rational approximation, use continued fractions.

Take 100.227273 as example.

1. Take the integer part (100) away. Now you get 100.227273 = 100 + 0.227273.
2. Invert 0.227273 to get 4.39999 (4.4?).
3. Repeat step 1 until you are satisfied with the error.

So you get

                       1
100.227273 = 100 + —————————
                         1
                   4 + —————
                           1
                       2 + —
                           2

Simplify this expression to get 2205/22.

[Editor's note: For example code, see this answer.]

回答2:

1000000/gcd(1000000,227273). Also known as lcm(1000000,227273)/227273. In this case, 1 million.

What you want to do, is turn 0.227273 into a fraction in simplest form. The number you're looking for is then the denominator of that fraction. Since 227273/1000000 is already in simplest form, you're done. But if your input was 100.075, then 75/1000 is not in simplest form. The simplest form is 3/40, so the solution for X is 40.

As an optimisation, you can simplify the calculation because you know that the starting denominator is a power of 10, so its only prime factors are 2 and 5. So all you need to look for in the numerator is divisibility by 2 and 5, which is easier than Euclid's algorithm. Of course if you already have an implementation of gcd and/or lcm, then this is more effort on your part, not less.

Bear in mind when you get the result, that floating-point numbers cannot in general represent decimal fractions precisely. So once you have the mathematically correct answer, it will not necessarily give you an integer answer when you do a floating-point multiplication. The flip side of this is that of course the question only applies if there is a finite decimal expression of the number you're interested in.

If you have the number as a quotient in the first place, then you need to find the denominator of its simplest form directly, not by converting it to decimal and truncating it. For example, to solve this problem for the number "6 and one third", the answer is 3, not any power of 10. If the input is "the square root of 2", then there is no solution for X.

Well, actually, the smallest integer X with the property you require is 0, but I assume you don't mean that ;-)

回答3:

I've got a feeling you actually mean this:
How to convert floats to human-readable fractions?

回答4:

If your positive decimal value D has n digits to the right of the decimal point, then D * 10^n is an integer and X = 10^n / gcf(10^n, D * 10^n) = lcm(10^n, D * 10^n) is the smallest positive integer X.

回答5:

I am assuming that the input decimal r is a positive rational number r with a terminating decimal representation.

Let d be the number of digits after the decimal point (assume that we have trimmed all extraneous zeros from the decmial representation of r). Then note that 10^d * r is an integer m. Let g = gcd(10^d, m). Then 10^d / g * r = m / g is an integer p. Let q = 10^d / g. I claim that q is the smallest such positive integer.