应用于数组时呈现数组积分的最小正乘数

Question

给定一个包含 n 个非负元素的数组，在任何库中是否有 C/C++ 的函数 returns 最小的正乘数当应用于数组的每个元素时returns一个整数？

例如，如果n=2的数组是1.66667, 2.33333，乘数就是3。当我们将数组的每个元素乘以3时，我们得到5, 7，都是整数。

如果数组是8,10，乘数就是0.5。那会给我们 4,5.

(1) boost、eigen 等知名库中是否有有效的函数？

(2) 如果图书馆中没有可用的东西，计算倍数的有效算法是什么？

Answer 1

不是您指定的方式。问题是 decimal 值 1.66667 和 2.33333 没有这样的乘数：你假设一个近似值源于，从数学角度来看是什么, 任意舍入策略。

然后还有浮点数属性需要担心，因此您可以使用 double 或 float.

排除任何问题

这里最好的选择是使用分数 class 来表示数字。然后任何普通的乘法器都会用一些简单的数学运算。

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

Answer 2

在一般情况下，您的问题没有很好的解决方案，因为这些值以浮点格式存储，精度有限，只能存储分母的 2 次幂的分数。例如 0.1 * 10 在您的平台上可能不是一个整数值。

如果您从整数计算数组中的值，您应该将它们表示为具有适当大小的整数对的标准化分数，并计算它们的分母的最小公倍数。

如果你想要问题的近似解，你可以指定epsilon的值，手工设计一个解。我想不出适合这个需求的库函数，但是暴力解决方案很容易写：

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;
}

Answer 3

看看 Rosetta Code 的 "Convert decimal number to rational." 由于我不精通 C，我将那里的 C 代码转换为 Python（尽管我认为 Python 可能有一些相关的库）并添加了几个可以轻松适应 C 的函数。如果分数转换中的分母都是 1.0，我们除以数字列表的最大公约数。否则，我们 return 唯一分母的乘积。

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)

输出：

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

应用于数组时呈现数组积分的最小正乘数

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

c

c++

algorithm

boost

eigen