1. Welcome to our site! Electro Tech is an online community (with over 170,000 members) who enjoy talking about and building electronic circuits, projects and gadgets. To participate you need to register. Registration is free. Click here to register now.
    Dismiss Notice

having a number dividable

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

  1. electroRF

    electroRF Member

    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. NorthGuy

    NorthGuy Well-Known Member

    Joined:
    Sep 8, 2013
    Messages:
    1,218
    Likes:
    206
    Location:
    Northern Canada
    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 Like x 1
  3. electroRF

    electroRF Member

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

    Hope you got a good heat conductor nearby :)

    Thanks a lot for your reply.

    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.
     
  4. dave

    Dave New Member

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


     
  5. Pommie

    Pommie Well-Known Member Most 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 Like x 1
  6. electroRF

    electroRF Member

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

    thats a nice point of view!!

    Thanks
     
  7. NorthGuy

    NorthGuy Well-Known Member

    Joined:
    Sep 8, 2013
    Messages:
    1,218
    Likes:
    206
    Location:
    Northern Canada
    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 Like x 1
  8. misterT

    misterT Well-Known Member Most 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 Like x 1
  9. electroRF

    electroRF Member

    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 :)
     

Share This Page