0

I'm running on a platform with no floating-point support, and the largest integer type being 32 bits.

Given a pair of values, I need to ensure that none of them exceeds 16 bits before I continue to process them.

If either one of them does, then I need to reduce both while maintaining their ratio as accurately as possible.

Here is what I've done so far:

#define MAX_VAL 0x0000FFFF

typedef unsigned int uint32;

void func(uint32 x, uint32 y) {
    if (x > MAX_VAL && y <= MAX_VAL) {
        y = y * MAX_VAL / x;
        x = MAX_VAL;
    }

    if (x <= MAX_VAL && y > MAX_VAL) {
        x = x * MAX_VAL / y;
        y = MAX_VAL;
    }

    while (x > MAX_VAL || y > MAX_VAL) {
        x >>= 1;
        y >>= 1;
    }

    ...
}

This seems to work well in terms of accuracy.

However, I would still like to improve performance, specifically with regards to the while loop, while maintaining the level of accuracy of course.

Any ideas how to approach that?

halfer
  • 19,824
  • 17
  • 99
  • 186
goodvibration
  • 5,980
  • 4
  • 28
  • 61
  • Have you measured and profiled (on an optimized build) that this is a top-two (or possibly top-three) bottleneck in your program? Then my general tip is that you wait until this does become a top-two bottleneck. Compilers are very good at optimizations, and might do a better job than you or me (they usually do). If it turns out this *is* a top-two bottleneck, then remember to document what the function is supposed to do, and why the code is what it is, in details. Hand-optimizations tend to make very obfuscated code, which is very hard to maintain. – Some programmer dude Jul 06 '20 at 03:41
  • 1
    Even though if you want to remove the while loop, I suggest you to find the position of the highest bit set and shift those many bits in one shot, [read](https://stackoverflow.com/questions/53161/find-the-highest-order-bit-in-c). – kiran Biradar Jul 06 '20 at 03:46
  • Have you tried just `x = (x * MAX_VAL + y / 2) / y; y = MAXVAL;` for `x < y` with no loop after. Also note that both this and the posted code are subject to integer overflow. – dxiv Jul 06 '20 at 03:46
  • @dxiv: That sounds promising, but I'd need a more thorough description, since (for example) it reduces accuracy when both values are 16 bits to begin with. – goodvibration Jul 06 '20 at 03:49
  • @goodvibration That's essentially the same as yours, but it rounds the division to the nearest integer instead of truncating (`a / b` truncates, `(a + b/2) / b` rounds to nearest). – dxiv Jul 06 '20 at 03:51
  • @dxiv: How exactly is it the same when mine keeps 100% accuracy for `x` and `y` being smaller than `0x10000`, while yours doesn't? – goodvibration Jul 06 '20 at 03:53
  • @goodvibration That's the calculation when you would need to scale them. The case when both are within range should be excluded with an `if` like the posted code does. – dxiv Jul 06 '20 at 03:57
  • 1
    You could start by dividing both by their gcd, which will entail *no* loss of accuracy. – Nate Eldredge Jul 06 '20 at 04:06
  • @NateEldredge: That would beat the purpose of performance (which is my primary goal here, after achieving desired accuracy), since the performance of GCD itself could be catastrophic (worst case is the pair of largest consecutive Fibonacci 32-bit numbers). – goodvibration Jul 06 '20 at 04:11
  • @NateEldredge: In addition to that, it won't even solve the problem in all cases, since some pairs will simply not be reduced to 16 bits at the end of the operation! – goodvibration Jul 06 '20 at 04:14
  • Yes, that's why I said **start**. – Nate Eldredge Jul 06 '20 at 04:14
  • @goodvibration The priority of performance *over* accuracy may be worth including in the question. Otherwise the "mathematically correct" answer would involve the convergents of `x/y`. – dxiv Jul 06 '20 at 04:16
  • Does your platform have a ["count leading zeros" instruction](https://en.wikipedia.org/wiki/Find_first_set) that you could access with an intrinsic or inline asm, or a compiler builtin that may be well optimized? – Nate Eldredge Jul 06 '20 at 04:19
  • 1
    Can you quantify your required accuracy in a precise way? – Nate Eldredge Jul 06 '20 at 04:20
  • 1
    @dxiv: You said the original code is subject to integer overflow - where? I don't see it. Multiplication is only done on values at most `MAX_VAL`, and `MAX_VAL * MAX_VAL` fits in `uint32`. – Nate Eldredge Jul 06 '20 at 04:38
  • @NateEldredge My bad, I misread the conditionals. There is no potential for overflow, indeed. – dxiv Jul 06 '20 at 04:43

0 Answers0