finding smallest scale factor to get each number within one tenth of a whole number from a set of doubles

Question

Suppose we have a set of doubles s, something like this:

1.11, 1.60, 5.30, 4.10, 4.05, 4.90, 4.89

We now want to find the smallest, positive integer scale factor x that any element of s multiplied by x is within one tenth of a whole number.

Sorry if this isn't very clear—please ask for clarification if needed.

Please limit answers to C-style languages or algorithmic pseudo-code.

Thanks!

Answer 1

You're looking for something called simultaneous Diophantine approximation. The usual statement is that you're given real numbers a_1, ..., a_n and a positive real epsilon and you want to find integers P_1, ..., P_n and Q so that |Q*a_j - P_j| < epsilon, hopefully with Q as small as possible.

This is a very well-studied problem with known algorithms. However, you should know that it is NP-hard to find the best approximation with Q < q where q is another part of the specification. To the best of my understanding, this is not relevant to your problem because you have a fixed epsilon and want the smallest Q, not the other way around.

One algorithm for the problem is (Lenstra–Lenstra)–Lovász's lattice reduction algorithm. I wonder if I can find any good references for you. These class notes mention the problem and algorithm, but probably aren't of direct help. Wikipedia has a fairly detailed page on the algorithm, including a fairly large list of implementations.

Answer 2

To answer Vlad's modified question (if you want exact whole numbers after multiplication), the answer is known. If your numbers are rationals a1/b1, a2/b2, ..., aN/bN, with fractions reduced (ai and bi relatively prime), then the number you need to multiply by is the least common multiple of b1, ..., bN.