The smallest positive factor that applies to the array makes the array integral

Question

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

For example, if the array c n=2is equal 1.66667, 2.33333, the multiplier will be 3. If we multiply each element of the array with 3, we get 5, 7both integers.

If an array 8,10, the multiplier will be 0.5. It will give us 4,5.

(1) Is there an effective function for this in any of the well-known libraries such as boost, eigenetc.

(2) If there is nothing in the libraries, what is an effective algorithm for calculating the plural?

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 the authority of 2 denominators exactly. For example, 0.1 * 10it may not be the integral value on your platform.

If you are calculating values ​​in an array of integers, you should represent them as normalized fractions with pairs of integers of sufficient size and calculate the smallest common multiple of their denominators.

, epsilon . , , :

unsigned long long ullgcd(unsigned long long a, unsigned long long b) {
     /* compute the greatest common divisor using Euclid 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;
}

Answer 2

, . , 1.66667 2.33333 : , , .

, , , double float.

. .

. http://www.boost.org/doc/libs/1_64_0/libs/rational/index.html

Answer 3

Take a look at the Rosetta Code Convert Decimal to Rational. Since I am not versed in C, I converted the C code there to Python (although I think Python can have some appropriate libraries) and added some functions that you could easily adapt to C. If the fraction conversion denominators are everything 1.0, we divide the largest common divisor is a list of numbers. Otherwise, we return the product of unique denominators.

import math
import operator

def f(arr):
  epsilon = 4
  fractions = [rat_approx(i, 16**epsilon) for i in arr]

  # The denominators in the fraction conversion are all 1.0
  if sum([denom for (num, denom) in fractions]) == len(fractions):
    return 1.0 / gcd_of_many([num for (num, denom) in fractions])
  else:
    # Otherwise, return the product of unique denominators
    return reduce(operator.mul, set([denom for (num, denom) in fractions]), 1)

def gcd(a, b):
  if a < b:
    return gcd(b, a)
  elif b == 0:
    return a;
  else:
    return gcd(b, a % b)

def gcd_of_many(arr):
  result = arr[0]
  for i in xrange(1, len(arr)):
    result = gcd(result, arr[i])
  return result

# Converted from
# https://rosettacode.org/wiki/Convert_decimal_number_to_rational#C
def rat_approx(f, md):
    #  a: continued fraction coefficients.
    h = [0, 1, 0]
    k = [1, 0, 0]
    n = 1
    neg = 0
    num = 0
    denom = 0

    if md <= 1:
      denom = 1
      num = f
      return num, denom

    if f < 0:
      neg = 1
      f = -f

    while f != math.floor(f):
      n <<= 1
      f *= 2

    d = f

    # continued fraction and check denominator each step
    for i in xrange(65):
        a = d // n if n else 0
        if i and not a:
          break

        x = d
        d = n
        n = x % n

        x = a;
        if k[1] * a + k[0] >= md:
            x = (md - k[0]) // k[1]
            if x * 2 >= a or k[1] >= md:
                i = 65
            else:
                break

        h[2] = x * h[1] + h[0]
        h[0] = h[1]
        h[1] = h[2]
        k[2] = x * k[1] + k[0]
        k[0] = k[1]
        k[1] = k[2]

    denom = k[1]
    num = -h[1] if neg else h[1]

    return (num, denom)

Conclusion:

   f([8, 10])
=> 0.5
   f([1.66667, 2.33333])
=> 3.0