如何计算（a次b）除以c仅使用32位整数类型，即使b次不适合这种类型 [英] how to calculate (a times b) divided by c only using 32-bit integer types even if a times b would not fit such a type

问题描述

将以下内容视为参考实现：

Consider the following as a reference implementation:

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

我对不需要的实现（在C或伪代码中）感兴趣一个64位整数类型。

I am interested in an implementation (in C or pseudocode) that does not require a 64-bit integer type.

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

I started sketching an implementation that outlines like this:

/* 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）并最小化整个计算的误差。

But the difficulty is to pick values for d1 and d2 that manage to avoid the overflow ((a / d1) * (b / d2) <= UINT32_MAX) and minimize the error of the whole calculation.

有什么想法？

推荐答案

我已经改编了由 Paul for unsigned int（通过省略正在处理的部分）迹象）。该算法基本上是古埃及乘法 a 分数 floor（b / c）+（b％c）/ c （斜杠表示实际除法）。

I have adapted the algorithm posted by Paul for unsigned ints (by omitting the parts that are dealing with signs). The algorithm is basically Ancient Egyptian multiplication of a with the fraction floor(b/c) + (b%c)/c (with the slash denoting real division here).

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 。

This algorithm will yield the exact answer as long as it fits in 32 bits. You can optionally also return the remainder r.

这篇关于如何计算（a次b）除以c仅使用32位整数类型，即使b次不适合这种类型的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！