应用于数组时最小的正乘数使数组成为整数

Question

给定的阵列n非负元素,有在该返回C/C++的任何库中的函数最小正乘数,当施加到所述阵列的每个元件返回一个整数数目？

例如,如果数组为n=2is 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;
}