"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

For what I gather you want to detect if a number is nearly divisible by other, right?

I'd do something like this:

#define NEARLY_DIVISIBLE 0.1f 

bool IsNearlyDivisible(float n1, float n2)
{
   float remainder = (fmodf(n1, n2) / n2);
   remainder = remainder < 0f   ? -remainder : remainder;
   remainder = remainder > 0.5f ? 1 - remainder   : remainder;
   return (remainder <= NEARLY_DIVISIBLE);
}

Answer 4

I think it's right:

bool nearlyDivisible(float num,float div){
float f = num % div;
if(f>div/2.0f){
f=f-div;
}
f=f>0?f:0.0f-f;
return f<0.1f;
}

Answer 5

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!

Answer 6

Why wouldn't you just divide by 32, then round and take the difference between the rounded number and the actual result?

Something like (forgive the untested/pseudo code, no time to lookup):

#define NEARLY_DIVISIBLE 0.1f
float result = val / 32.0f;
float nearest_int = nearbyintf(result);
float difference = abs(result - nearest_int);
if( difference < NEARLY_DIVISIBLE )
{
    // It's nearly divisible
}

If you still wanted to do checks from above and below, you could remove the abs, and check to see if the difference is >0 or <0.

Answer 7

This is without uing the fmodf twice.

int main(void)
{
    #define NEARLY_DIVISIBLE 0.1f
    #define DIVISOR 32.0f
    #define ARRAY_SIZE 4
    double test_var1[ARRAY_SIZE] = {63.9,64.1,65,63.8};
    int i = 54;
    double rest;
    for(i=0;i<ARRAY_SIZE;i++)
    {
        rest = fmod(test_var1[i] ,DIVISOR);
        if(rest < NEARLY_DIVISIBLE)
        {
            printf("Number %f max %f larger than  a factor of the divisor:%f\n",test_var1[i],NEARLY_DIVISIBLE,DIVISOR);
        }
        else if( -(rest-DIVISOR) < NEARLY_DIVISIBLE)
        {
            printf("Number %f max %f less than  a factor of the divisor:%f\n",test_var1[i],NEARLY_DIVISIBLE,DIVISOR);
        }
    }
    return 0;
}