如何计算(a次b)除以c仅使用32位整数类型,即使b次不适合这种类型

Question

请考虑以下内容作为参考实现:

/* calculates (a * b) / c */
uint32_t muldiv(uint32_t a, uint32_t b, uint32_t c)
{
    uint64_t x = a;
    x = x * b;
    x = x / c;
    return x;
}

我感兴趣的是一个不需要64位整数类型的实现(在C或伪代码中).

我开始草拟一个如下概述的实现:

/* calculates (a * b) / c */
uint32_t muldiv(uint32_t a, uint32_t b, uint32_t c)
{
    uint32_t d1, d2, d1d2;
    d1 = (1 << 10);
    d2 = (1 << 10);
    d1d2 = (1 << 20); /* d1 * d2 */
    return ((a / d1) * (b /d2)) / (c / d1d2);
}

但困难在于选择d1和d2的值来避免溢出((a/d1)*(b/d2)<= UINT32_MAX)并最小化整个计算的误差.

有什么想法吗？

Answer 1

我已经调整了Paul发布的用于无符号整数的算法（通过省略处理符号的部分）。该算法基本上是古埃及的a分数乘法floor(b/c) + (b%c)/c（这里斜线表示实数除法）。

uint32_t muldiv(uint32_t a, uint32_t b, uint32_t c)
{
    uint32_t q = 0;              // the quotient
    uint32_t r = 0;              // the remainder
    uint32_t qn = b / c;
    uint32_t rn = b % c;
    while(a)
    {
        if (a & 1)
        {
            q += qn;
            r += rn;
            if (r >= c)
            {
                q++;
                r -= c;
            }
        }
        a  >>= 1;
        qn <<= 1;
        rn <<= 1;
        if (rn >= c)
        {
            qn++; 
            rn -= c;
        }
    }
    return q;
}

只要适合 32 位，该算法就会产生准确的答案。您还可以选择返回余数r。