Smallest positive multiplier that when applied to an array renders the array integral

Question

Given an array of n non-negative elements, is there a function in any library for C/C++ that returns the smallest positive multiplier that when applied to each element of the array returns an integer number?

For example, if the array with n=2 is 1.66667, 2.33333, the multiplier would be 3. For when we multiply each element of the array with 3, we get 5, 7, both integer.

If the array is 8,10, the multiplier would be 0.5. That would give us 4,5.

(1) Is there an efficient function for this in any of the well-known libraries such as boost, eigen, etc.?

(2) In case there is nothing available in libraries, what is an efficient algorithm for figuring out the multiple?

Answer 1

There is no good solution to your problem in the general case because the values are stored in a floating point format that has finite precision and can only store fractions with denominators powers 2 exactly. For example 0.1 * 10 may very well not be an integral value on your platform.

If you compute the values in the array from integral quantities, you should represent them as normalized fractions with pairs of adequately sized integers and compute the least common multiple of their denominators.

If you want an approximate solution to the problem, you can specify the value of epsilon, and design a solution by hand. I can think of no library function to fit this need, but a brute force solution is easy to write:

unsigned long long ullgcd(unsigned long long a, unsigned long long b) {
     /* compute the greatest common divisor using Euclid's elegant method */
     if (a < b)
         return ullgcd(b, a);
     else
     if (b == 0)
         return a;
     else
         return ullgcd(b, a % b);
}

double least_multiple(double *a, size_t n, double epsilon) {
    for (double mult = 1;; mult += 1) {
        size_t i;
        unsigned long long div = 0;
        for (i = 0; i < n; i++) {
            double d = fabs(a[i] * mult);
            unsigned long long v = round(d);
            if (fabs(v - d) > epsilon)
                break;
            div = ullgcd(v, div);
        }
        if (i == n)
            break;
    }
    /* mult is the smallest non zero integer that fits your goal.
       the smallest multiplier is obtained by dividing it 
       by the greatest common divisor of the resulting integer array.
    */
    return mult / div;
}