greatest multiple algorithm

[Bronson]

Hi,

i'm looking for a fast way to find greatest multiple of a, which is
smaller than b.
Recently i've used b-b%a, but maybe it could be done faster.

Any ideas?

Przemek

 

[Walter Roberson]

i'm looking for a fast way to find greatest multiple of a, which is
smaller than b.
Recently i've used b-b%a, but maybe it could be done faster.

Algebraically put, NOT C: a * floor(b/a)

Provided a is non-zero.


Note this is not the same as C's a * (int)(b/a)

(hint: what if one of the values is negative? Or if b/a is larger
than the maximum value of a signed int ?)

 

[Eric Sosman]

Bronson wrote On 06/28/07 17:40,:

Hi,

i'm looking for a fast way to find greatest multiple of a, which is
smaller than b.
Recently i've used b-b%a, but maybe it could be done faster.

(Assumptions: a and b are integers, a positive and b non-
negative.)

The formula you're using doesn't solve the problem you've
described. For example, consider a=3, b=12: your formula
yields 12, which is not smaller than b.

To solve the problem stated, you could use (b-1)-(b-1)%a.

If a is known to be a power of two, you can replace the
mod operation with an and: (b-1)-((b-1)&(a-1)). It is tempting
to simplify this even further to (b-1)&~(a-1), but this is
completely safe only if a is an unsigned integer; applying ~
to a signed integer has non-portable consequences. A possible
alternative that works for signed integers is ((b-1)|(a-1))^(a-1),
but that seems no better than the first and-ing formula.

 

[Army1987]

Hi,

i'm looking for a fast way to find greatest multiple of a, which is
smaller than b.
Recently i've used b-b%a, but maybe it could be done faster.

Any ideas?

Przemek

Compile and run this program: (I assume by "smaller" you meant "smaller or equal")

#include <stdio.h>
#include <time.h>
int main(void)
{
volatile int result;
int a, b;
clock_t t0, t1;
double elapsed;
t0 = clock();
for (b = 0; b < 10000; b++)
for (a = 1; a <= 10000; a++)
result = b - b % a;
t1 = clock();
elapsed = (double)(t1 - t0) / CLOCKS_PER_SEC;
printf("Faster? This one takes %g seconds in average...\n",
elapsed / 1e8);
return 0;
}

 

[Thad Smith]

Compile and run this program: (I assume by "smaller" you meant "smaller or equal")

My assumption was that smaller meant less than and his code was wrong.