# having a number dividable

Discussion in 'Mathematics and Physics' started by electroRF, Jan 7, 2014.

1. ### electroRFMember

Joined:
Jun 23, 2012
Messages:
689
Likes:
9
Location:
Portugal
Hi,
Say that you got a number N, and you want it to be dividable by other number M, and you know that M is a power of 2.

For example, N = 123, M = 64.

I'm trying to write an efficient C code to find the minimal number that is larger than N and is dividable by M.

in this case -> 128

I made a few tests and the following seems to work:

( N + (M-1) ) & ~(M-1)

you see any problem with that?

anything more efficient that that?

Thank you.

2. ### NorthGuyWell-Known Member

Joined:
Sep 8, 2013
Messages:
1,218
Likes:
206
Location:
If M is known at the compile time, (M-1) and ~(M-1) can be pre-calculated. Then it's only two operations at run-time. You cannot do that in one operation, so it is the most efficient.

If M is unknown at the compile time, there are two more operations to compute (M-1) and ~(M-1). There are only a handful possible values for M, so you could create a table with pre-computed values, but it'll probably take longer to fetch them from the table than to calclulate. So, I think in this case it's the most efficient way too.

Why do you want this to be efficient?

• Like x 1
3. ### electroRFMember

Joined:
Jun 23, 2012
Messages:
689
Likes:
9
Location:
Portugal
Hi NorthGuy

Hope you got a good heat conductor nearby

M is unknown at compile time.

As for efficiency,
For example, I'd not want to perform division when I can do shift right instead, that would be wrong programming in my opinion.

I think there's additional way, but it won't work if N=0:

((N-1) / M ) *M + M

But this way uses division and multiplying which makes it less time efficient.

Joined:
Jan 12, 1997
Messages:
-
Likes:
0

5. ### PommieWell-Known MemberMost Helpful Member

Joined:
Mar 18, 2005
Messages:
10,161
Likes:
340
Location:
Brisbane Australia

The number that fits your criteria is the first number bigger than N that has the same number of trailing zeroes as M. Your equation seems to accomplish that and so I think it's the most efficient way.

Mike.

• Like x 1
6. ### electroRFMember

Joined:
Jun 23, 2012
Messages:
689
Likes:
9
Location:
Portugal
hi mike.

thats a nice point of view!!

Thanks

7. ### NorthGuyWell-Known Member

Joined:
Sep 8, 2013
Messages:
1,218
Likes:
206
Location:
In your case you can replace division and multiplication by shifts left/right, which is three operation. Also C doesn't provide an easy way to find the amount of shift.

But, this method will work with any M, although you will have to do division and multiplication. Instead of division and multiplication, you can also subtract a remainder.

Look, here you have a general (work with any Ms) solution, which is less efficient. And your first (work with specific Ms) solution, which is more efficient. This is very typical. If you want maximum efficiency you must get specific.

• Like x 1
8. ### misterTWell-Known MemberMost Helpful Member

Joined:
Apr 19, 2010
Messages:
2,697
Likes:
368
Location:
Finland
This is just the same as "Rounding up to a multiple of a known power of 2"
There are two efficient solutions
(x+7) & (-8)
and
x + (-x & 7)

EDIT: Sorry, the solution rounds up to the next multiple of 8.. I think your first solution is good, because it looks very similar to that one.

• Like x 1
9. ### electroRFMember

Joined:
Jun 23, 2012
Messages:
689
Likes:
9
Location:
Portugal
Thank you NorthGuy and T

NorthGuy,
You're right, the ((N-1) / M ) *M + M works for any M.
and I was wrong, it works also for N=0

T,
I didn't know that -X = ~(X-1).

Cool