A faster way to find multiple doubles

Question

If you have the following C function used to determine if one number is a multiple of another to a valid arbirary value

#include <math.h>

#define TOLERANCE 0.0001

int IsMultipleOf(double x,double mod)
{
    return(fabs(fmod(x, mod)) < TOLERANCE);
}

It works great, but profiling shows that it is very slow, to the extent that it has become a candidate for optimization. About 75% of the time is spent on modulo, and the rest on fabs. I'm trying to figure out a way to speed things up using something like a lookup table. The parameter xchanges regularly, but modrarely changes. The number of possible values ​​of x is small enough so that the search space is not a problem, as a rule, it will be one of several hundred possible values. I can easily get rid of fabs, but I cannot find a reasonable alternative to the module. Any ideas on how to optimize the above?

Change . The code will run on a wide range of Windows desktop and mobile devices, so Intel, AMD on the desktop, and ARM or SH4 can be enabled on mobile devices. VisualStudio 2008 is a compiler.

Answer 1

Do you really need to use modulofor this?

It would be impossible to simply result = x / modand then check if the decimal part is resultclose to 0. For example:

11 / 5.4999 = 2.000003  ==> 0.000003 < TOLERANCE 

Or something like that.

Answer 2

( , fmod ) , :

• gcc
  , __builtin_fmod . .
• , SSE Intel,

, ( , ) . , .

Answer 3

, . , , .

...

• 1
• 11
• 52

...

• value = x/mod;
• exp = - BIAS;
• lsb = ;

...

/*
 * If applying the exponent would eliminate the fraction bits
 * then for double precision resolution it is a multiple.
 * Note: lsb may require some massaging.
 */
if (exp > lsb)
    return (true);

if (exp < 0)
    return (false);

- . , .

• ()
• exponent - BIAS (1023, ... , )

.

Answer 4

, C RTL fmod(): X86 FPU FPREM/FPREM1, .

, , FPREM, , RTL .

Answer 5

, , fmod, , , , ( ) . (, , ).

#include <math.h>

int IsMultipleOf(double x, double mod) {
    long n = x / mod;  // You should probably test for /0 or NAN result here
    double new_x = mod * n;
    double delta = x - new_x;
    return fabs(delta) < TOLERANCE;  // and for NAN result from fabs
}

Answer 6

, , , . , long long 60 .

Answer 7

? , , :

#include <math.h>

#define TOLERANCE 0.0001f

bool IsMultipleOf(float x, float mod)
{
    return(fabsf(fmodf(x, mod)) < TOLERANCE);
}

Answer 8

, modulo :

mod(x,m) {
  while (x > m) {
    x = x - m
  }
  return x
}

, - : :

fastmod(x,m) {
  q = 1

  while (m * q < x) {
    q = q * 2
  }

  return mod((x - (q / 2) * m), m)
}

, annother fastmod, , x < m, x.