"Nearly divisible"

Question

I want to check if a floating point value is "nearly" a multiple of 32. E.g. 64.1 is "nearly" divisible by 32, and so is 63.9.

Right now I'm doing this:

#define NEARLY_DIVISIBLE 0.1f
float offset = fmodf( val, 32.0f ) ;
if( offset < NEARLY_DIVISIBLE )
{
    // its near from above
}
// if it was 63.9, then the remainder would be large, so add some then and check again
else if( fmodf( val + 2*NEARLY_DIVISIBLE, 32.0f ) < NEARLY_DIVISIBLE )
{
    // its near from below
}

Got a better way to do this?

Answer 1

well, you could cut out the second fmodf by just subtracting 32 one more time to get the mod from below.

  if( offset < NEARLY_DIVISIBLE )
   {
       // it's near from above
   }
   else if( offset-32.0f>-1*NEARLY_DIVISIBLE)
   {
       // it's near from below
   }

Answer 2

In a standard-compliant C implementation, one would use the remainder function instead of fmod:

#define NEARLY_DIVISIBLE 0.1f
float offset = remainderf(val, 32.0f);
if (fabsf(offset) < NEARLY_DIVISIBLE) {
    // Stuff
}

If one is on a non-compliant platform (MSVC++, for example), then remainder isn't available, sadly. I think that fastmultiplication's answer is quite reasonable in that case.

Answer 3

You mention that you have to test near-divisibility with 32. The following theory ought to hold true for near-divisibility testing against powers of two:

#define THRESHOLD 0.11
int nearly_divisible(float f) {
    // printf("    %f\n", (a - (float)((long) a)));
    register long l1, l2;
    l1 = (long) (f + THRESHOLD);
    l2 = (long) f;
    return !(l1 & 31) && (l2 & 31 ? 1 : f - (float) l2 <= THRESHOLD);
}

What we're doing is coercing the float, and float + THRESHOLD to long.

f       (long) f    (long) (f + THRESHOLD)
63.9    63          64
64      64          64
64.1    64          64

Now we test if (long) f is divisible with 32. Just check the lower five bits, if they are all set to zero, the number is divisible by 32. This leads to a series of false positives: 64.2 to 64.8, when converted to long, are also 64, and would pass the first test. So, we check if the difference between their truncated form and f is less than or equal to THRESHOLD.

This, too, has a problem: f - (float) l2 <= THRESHOLD would hold true for 64 and 64.1, but not for 63.9. So, we add an exception for numbers less than 64 (which, when incremented by THRESHOLD and subsequently coerced to long -- note that the test under discussion has to be inclusive with the first test -- is divisible by 32), by specifying that the lower 5 bits are not zero. This will hold true for 63 (1000000 - 1 == 1 11111).

A combination of these three tests would indicate whether the number is divisible by 32 or not. I hope this is clear, please forgive my weird English.

I just tested the extensibility to other powers of three -- the following program prints numbers between 383.5 and 388.4 that are divisible by 128.

#include <stdio.h>

#define THRESHOLD 0.11

int main(void) {
    int nearly_divisible(float);
    int i;
    float f = 383.5;
    for (i=0; i<50; i++) {
        printf("%6.1f %s\n", f, (nearly_divisible(f) ? "true" : "false"));
        f += 0.1;
    }
    return 0;
}

int nearly_divisible(float f) {
    // printf("    %f\n", (a - (float)((long) a)));
    register long l1, l2;
    l1 = (long) (f + THRESHOLD);
    l2 = (long) f;
    return !(l1 & 127) && (l2 & 127 ? 1 : f - (float) l2 <= THRESHOLD);
}

Seems to work well so far!