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

Question

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

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

如果数组为 8,10，则乘数将为 0.5。这会给我们 4,5。

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

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

Answer 1

在一般情况下，您的问题没有很好的解决方案，因为值以浮点格式存储，精度有限，只能存储分母的幂为 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;
}