2
$\begingroup$

I have an array of floating point values $F$. I want to input my array into an algorithm that only takes integer values. How can I efficiently determine the smallest multiplier $m$ such that all values in $m \centerdot F$ are integers within a given tolerance $tol$?

$\endgroup$
  • $\begingroup$ I don't think you can do what you want to do if your numbers span a very large range. Can you describe the algorithm that you want to apply only to integers? Maybe someone here can help you apply it to floating-point numbers. $\endgroup$ – Bill Barth Dec 10 '13 at 14:31
  • $\begingroup$ @BillBarth It is a polygon clipping algorithm optimized for image pixels. A modest few thousand lines of source code :-) The typical floating point values in my array are of the order of 10s and 100s. I normally expect the values to have a maximum of a few decimal digits, so a quick solution could for example be (as Wolfgang points out) to simply pick a large enough scale factor, e.g. 1000. Most likely, if there is no other solution coming up soon, this is the approach I will end up with. $\endgroup$ – Anders Gustafsson Dec 10 '13 at 15:50
  • 1
    $\begingroup$ With a sufficiently large scale factor, you should be able to polish off the result with something like a GCD of all of the rounded values (recursive in the sense that $gcd(a, b, c) = gcd(a, gcd(b, c))$, so the algorithm is $O(n \log n)$). $\endgroup$ – Geoff Oxberry Dec 10 '13 at 17:05
3
$\begingroup$

Sure -- just take $m=\frac{1}{tol}\frac{1}{\min_i |F_i|} 10^{16}$.

It's easy to see that if you take $m$ just large enough, you will always achieve this. For simplicity, assume that your numbers are all larger than one and have at most 3 digits after the decimal point, then if you multiply them by a thousand, you will get only integers. Of course, multiplying by anything larger than a thousand will also work. If you don't need to exactly hit integers, you can get away with a smaller factor, but in general you'll need something that's probably proportional to one over the tolerance.

That said, as a general rule, multiplying by some large number like I suggest above is of course not a particularly useful thing. Integers are just as arbitrary as any other numbers if they have physical units -- there is nothing special about one, two, three meters. My question then would be what you want these integers to represent?

$\endgroup$
  • $\begingroup$ Context: I have a floating-point array and an algorithm that only works on integers. My plan is therefore to scale the floats to become approximately integers, and then divide the resulting integer array from the algorithm with the same multiplier. I assume the 10^16 is some kind of joke? I want to find the smallest possible multiplier to avoid as much as possible integer overflows. Let's say the decimal part of the values in my array are all multiples of 0.125. Then m=8 would suffice. m=1000 would be quite an overshoot in that case... $\endgroup$ – Anders Gustafsson Dec 10 '13 at 12:07
  • $\begingroup$ I should also point out that counting the number of digits after the decimal point is an overly simplistic approach if you have a limited bit representation of your floating point values. For 32-bit floats it is not uncommon that you see values like 2.999998, 5.230001, ... $\endgroup$ – Anders Gustafsson Dec 10 '13 at 12:32
  • 3
    $\begingroup$ The $10^{16}$ wasn't a joke. What I should have said is $2^{53}$ because floating point numbers are stored with 53 (binary) digits after the decimal point. In other words, any floating point number multiplied by $2^{53}$ is an integer multiple of a (positive or negative) power of 2. If you then divide it by the smallest power of two you encounter in your set of points, you end up with all integers. If you really wanted to, you could then divide by the largest common divisor of all numbers to get the smallest multiplier. But that all is not a practical algorithm, of course. $\endgroup$ – Wolfgang Bangerth Dec 10 '13 at 14:05
  • $\begingroup$ I think you're close but not quite, @WolfgangBangerth. Any IEEE double-precision number multiplied by $2^{53}$ is an integer if you IGNORE the exponent. Dividing by the smallest power of two, respecting the exponent, will give you an integer, but it might not fit in a computer integer type. If Anders' numbers are reasonable, your strategy will work, but if it contains a range of numbers larger than 10^16, some numbers will get treated as the same which are not. Probably better for him to tell us the algorithm he wants to apply and see if we can help him convert it to one for floating-point. $\endgroup$ – Bill Barth Dec 10 '13 at 14:26
  • 1
    $\begingroup$ @BillBarth: All correct (and that's what I mean by (i) saying that you need to divide by the smallest power of two you encounter and (ii) that it's not a practical algorithm :-) You're also correct in that one would need to know what he wants to use the result for to come up with something more useful. $\endgroup$ – Wolfgang Bangerth Dec 10 '13 at 17:39
3
$\begingroup$

If we treat the input array as $d$ real numbers rather than floating-point values, then this is a problem of best simultaneous diophantine approximation. The differences between this and the one-dimensional version, well-known to be solved by continued fraction approximations (see e.g. Knuth AOCP vol. 2, Seminumerical Algorithms) were explored by J.C. Lagarias (part I (TAMS), part II(Pac.J.Math)) in 1982 papers, and the complexity of solution in a 1985 paper (SIAM J.Comp.).

His result is that while the best simultaneous sup-norm approximation problem is NP-complete, the LLL integral lattice algorithm can be used to get in polynomial-time approximations that are within a factor $\sqrt{5d} 2^{(d + 1)/2}$ of the optimal error.

Doug Hensley has a more recent (2005) paper detailing the tradeoffs when one advances from one-dimensional to the more difficult $d \ge 2$ problems.

$\endgroup$
  • $\begingroup$ Interesting reading, @hardmath, many thanks! This was new to me. For my specific programming purpose I will go with a fixed multiplier approach, though. $\endgroup$ – Anders Gustafsson Dec 10 '13 at 19:25

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.