Given a decimal, find the smallest integer factor that gives an integer result

Question

It is best to use an example to describe the problem. Suppose I have a decimal value of 100.227273.

100.227273 * X = Y

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

Answer 1

If 100.227273 is approximate and you want the best rational approximation, use continued fractions .

Take 100.227273 as an example.

• Take the whole piece (100). Now you get 100.227273 = 100 + 0.227273.
• Invert 0.227273 to get 4.39999 (4.4?).
• 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.

Answer 2

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

What you want to do is 0.227273 per share in its simplest form. The number you are looking for is the denominator of this fraction. Since 227273/1000000 is already in its simplest form, everything is ready. But if your entry was 100.075, then 75/1000 is not in its simplest form. The simplest form is 3/40, so the solution for X is 40.

As an optimization, you can simplify the calculation, because you know that the initial denominator has a power of 10, so its only main factors are 2 and 5. Thus, all you need to look for in the numerator is divisibility by 2 and 5, which is easier than the Euclidean algorithm. Of course, if you already have an implementation of gcd and / or lcm, then this is more effort on your part, no less.

Remember, when you get the result, these floating point numbers may not represent decimals exactly. Therefore, if you have a mathematically correct answer, it will not necessarily give you an integer answer when you perform floating point multiplication. The flip side to this is that, of course, the question only applies if there is a finite decimal expression of the number you are interested in.

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

Well, actually, the smallest integer X with the property you require is 0 , but I assume that you do not mean this; -)

Answer 3

I have a feeling that you really mean this:
How to convert floats into human readable fractions?

Answer 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.

Answer 5

I assume that the input decimal r is a positive rational number r with finite decimal notation.

Let d be the number of digits after the decimal point (suppose we cut off all extraneous zeros from the decimal representation of r ). Then notice 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 argue that q is the smallest such positive integer.