当a和b都小于c但a * b溢出时，如何计算a * b/c? [英] How can I compute a * b / c when both a and b are smaller than c, but a * b overflows?

问题描述

假设uint是我的定点平台上最大的整数类型，我有:

Assuming that uint is the largest integral type on my fixed-point platform, I have:

uint func(uint a, uint b, uint c);

需要返回近似值a * b / c的

c的值大于a的值和b的值.

The value of c is greater than both the value of a and the value of b.

因此我们可以肯定地知道a * b / c的值将适合uint.

So we know for sure that the value of a * b / c would fit in a uint.

但是，a * b的值本身溢出了uint的大小.

However, the value of a * b itself overflows the size of a uint.

所以计算a * b / c值的一种方法是:

So one way to compute the value of a * b / c would be:

return a / c * b;

甚至:

if (a > b)
    return a / c * b;
return b / c * a;

但是，c的值大于a的值和b的值.

However, the value of c is greater than both the value of a and the value of b.

所以上面的建议只会返回零.

So the suggestion above would simply return zero.

我需要按比例减小a * b和c，但是同样-问题是a * b溢出.

I need to reduce a * b and c proportionally, but again - the problem is that a * b overflows.

理想情况下，我将能够:

Ideally, I would be able to:

• 将a * b替换为uint(-1)
• 用uint(-1) / a / b * c替换c.

• Replace a * b with uint(-1)
• Replace c with uint(-1) / a / b * c.

但是无论我如何对表达式uint(-1) / a / b * c进行排序，我都会遇到问题:

But no matter how I order the expression uint(-1) / a / b * c, I encounter a problem:

由于uint(-1) / a / b ，
• uint(-1) / a / b * c被截断为零
• uint(-1) / a * c / b由于uint(-1) / a * c
而溢出
• uint(-1) * c / a / b由于uint(-1) * c
而溢出

• uint(-1) / a / b * c is truncated to zero because of uint(-1) / a / b
• uint(-1) / a * c / b overflows because of uint(-1) / a * c
• uint(-1) * c / a / b overflows because of uint(-1) * c

我如何应对这种情况以便找到a * b / c的近似值?

How can I tackle this scenario in order to find a good approximation of a * b / c?

当最大整数类型为uint64时，平台上没有诸如_umul128之类的东西.我最大的类型是uint，并且我不支持任何大于该类型的内容(既不在硬件级别，也不在某些预先存在的标准库中).

I do not have things such as _umul128 on my platform, when the largest integral type is uint64. My largest type is uint, and I have no support for anything larger than that (neither on the HW level, nor in some pre-existing standard library).

我最大的类型是uint.

针对众多重复的建议和评论:

In response to numerous duplicate suggestions and comments:

我没有一些较大的类型"可以用来解决这个问题.这就是为什么该问题的开头声明是:

I do not have some "larger type" at hand, which I can use for solving this problem. That is why the opening statement of the question is:

假设uint是我的定点平台上最大的整数类型

Assuming that uint is the largest integral type on my fixed-point platform

我假设在SW层(通过某些内置的标准库)或在HW层上都没有其他类型.

I am assuming that no other type exists, neither on the SW layer (via some built-in standard library) nor on the HW layer.

推荐答案

我已经建立了一种可以解决O(1)复杂性(无循环)的解决方案:

I've established a solution which work in O(1) complexity (no loops):

typedef unsigned long long uint;

typedef struct
{
    uint n;
    uint d;
}
fraction;

uint func(uint a, uint b, uint c);
fraction reducedRatio(uint n, uint d, uint max);
fraction normalizedRatio(uint a, uint b, uint scale);
fraction accurateRatio(uint a, uint b, uint scale);
fraction toFraction(uint n, uint d);
uint roundDiv(uint n, uint d);

uint func(uint a, uint b, uint c)
{
    uint hi = a > b ? a : b;
    uint lo = a < b ? a : b;
    fraction f = reducedRatio(hi, c, (uint)(-1) / lo);
    return f.n * lo / f.d;
}

fraction reducedRatio(uint n, uint d, uint max)
{
    fraction f = toFraction(n, d);
    if (n > max || d > max)
        f = normalizedRatio(n, d, max);
    if (f.n != f.d)
        return f;
    return toFraction(1, 1);
}

fraction normalizedRatio(uint a, uint b, uint scale)
{
    if (a <= b)
        return accurateRatio(a, b, scale);
    fraction f = accurateRatio(b, a, scale);
    return toFraction(f.d, f.n);
}

fraction accurateRatio(uint a, uint b, uint scale)
{
    uint maxVal = (uint)(-1) / scale;
    if (a > maxVal)
    {
        uint c = a / (maxVal + 1) + 1;
        a /= c; // we can now safely compute `a * scale`
        b /= c;
    }
    if (a != b)
    {
        uint n = a * scale;
        uint d = a + b; // can overflow
        if (d >= a) // no overflow in `a + b`
        {
            uint x = roundDiv(n, d); // we can now safely compute `scale - x`
            uint y = scale - x;
            return toFraction(x, y);
        }
        if (n < b - (b - a) / 2)
        {
            return toFraction(0, scale); // `a * scale < (a + b) / 2 < MAXUINT256 < a + b`
        }
        return toFraction(1, scale - 1); // `(a + b) / 2 < a * scale < MAXUINT256 < a + b`
    }
    return toFraction(scale / 2, scale / 2); // allow reduction to `(1, 1)` in the calling function
}

fraction toFraction(uint n, uint d)
{
    fraction f = {n, d};
    return f;
}

uint roundDiv(uint n, uint d)
{
    return n / d + n % d / (d - d / 2);
}

这是我的考试:

#include <stdio.h>

int main()
{
    uint a = (uint)(-1) / 3;            // 0x5555555555555555
    uint b = (uint)(-1) / 2;            // 0x7fffffffffffffff
    uint c = (uint)(-1) / 1;            // 0xffffffffffffffff
    printf("0x%llx", func(a, b, c));    // 0x2aaaaaaaaaaaaaaa
    return 0;
}

这篇关于当a和b都小于c但a * b溢出时，如何计算a * b/c?的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！