# need a fast algorithm for next multiple

Printable View

• 02-07-2012
m37h0d
need a fast algorithm for next multiple
i have this:

Code:

``` static unsigned int nextMultiple(unsigned int of,unsigned int from) {         if(from < of ) return of;         unsigned int fmodof = from%of ;         return fmodof ? (from - (fmodof)) +of : from; }```
it works, but i'm betting there's a faster algorithm. anyone have suggestions?
• 02-07-2012
oogabooga
I don't understand your algorithm. I mean, if you just want the next multiple of 10 from 50, why don't you just return of + from ?

Could you explain in English what it's supposed to do and give examples?
• 02-07-2012
m37h0d
it's to help me generate aligned memory addresses.

e.g. nextMultiple(16,30) //returns 32;
• 02-07-2012
oogabooga
All I can think of is to take advantage of the fact that you probably only want multiples of 2. So with that assumption:
Code:

```typedef unsigned int uint; inline uint nextMultiple(uint of, uint n) {     uint ret = n & ~(of - 1);     return ret ? ret : of; }```
It avoids your initial if, but otherwise seems to have the same number of operations.

Another idea is instead of passing in of, pass in lg(of) (log base 2 of), something like:
Code:

```inline uint nextMultiple(uint lgof, uint n) {     uint ret = n >> lgof << lgof;     return ret ? ret : n; } n = nextMultiple(4, n); // pow(2,4) is 16```
That looks like it has one less operation than the previous alg, but you'd have to test them to see which, if any, is faster.
• 02-07-2012
laserlight
Assuming that from will be greater than 0, you could write:
Code:

`return ((from - 1) / of + 1) * of;`
Of course, I'm assuming that despite the name, nextMultiple(16, 32) == 32 rather than 48.
• 02-07-2012
oogabooga
I just tested my "solutions" from post 4 and they don't even work!
• 02-08-2012
iMalc
It's even simpler than that for alignment to powers of two:
Code:

`return (from + of-1) & ~(of-1);`
Note that of-1 and ~(of-1) should be replaced with the appropriate constants during optimisation and inlining. After optimisation it should amount to just one addition and one and operation. E.g. two clock cycles. Can't get better than that.

Same assumption as laserlight.
• 02-08-2012
m37h0d
thank you, everyone.
• 02-09-2012
m37h0d
in the interest of sharing, i thought i'd post my modest additions:

Code:

``` template<unsigned int of,unsigned int ofMod2> class NextMultiple {         inline static unsigned int evaluate(unsigned int from)         {                 return ((from - 1) / of + 1) * of;         } }; template<unsigned int of> class NextMultiple<of,0> {         inline static unsigned int evaluate(unsigned int from)         {                 return (from + of-1) & ~(of-1);         } }; template<unsigned int of>inline static unsigned int nextMultiple(unsigned int from) {         return NextMultiple<of,of%2>::evaluate(from); }```
• 02-09-2012
phantomotap
O_o

A power of two is not the same thing as a multiple of two.

And the implementation from `NextMultiple' should be public.[/Edit]

Soma
• 02-09-2012
m37h0d
DOH!

you're right...i caught that last night and then forgot about it.
• 02-10-2012
m37h0d
there we go...

Code:

``` template<unsigned int number,unsigned int exponent> class Pow:         Pow<number,exponent-1> { public:         static const unsigned int value = Pow<number,exponent-1>::value*number; }; template<unsigned int number> class Pow<number,1> { public:         static const unsigned int value = number; }; template<unsigned int base,unsigned int number, bool numberGreaterThanBase=true> class Log:         private Log<base, number/base, (number > base) > {         static_assert(number>=base,"number must be greater than base"); public:         static const unsigned int value = 1+Log<base,number/base,(number>base)>::value;         static const bool isPerfectPower = Pow<value,base>::value == number; }; template<unsigned int base,bool numberGreaterThanBase> class Log<base,1,numberGreaterThanBase> { public:         static const unsigned int value=0; }; template<unsigned int base> class Log<base,0,false> { public:         static const unsigned int value=0; }; template<unsigned int of,bool isPowerOfTwo> class NextMultiple { public:         inline static unsigned int evaluate(unsigned int from)         {                 return from ? ((from - 1) / of + 1) * of : of;         } }; template<unsigned int of> class NextMultiple<of,true> { public:         inline static unsigned int evaluate(unsigned int from)         {                 return (from + of-1) & ~(of-1);         } }; template<unsigned int of>inline static unsigned int nextMultiple(unsigned int from) {         return NextMultiple<of,Log<2,of>::isPerfectPower>::evaluate(from); }```
thanks again all - good catch soma; i probably would have forgotten about that until well after investigating random segfaults.
• 02-10-2012
phantomotap
O_o

I'm sorry, I thought you understood better; iMalc's suggestion works because of the ways powers of two work. You don't need to do all that to determine of something is a power of two. You can just use a modification of the same test at compile-time that you use at run-time.

Code:

`!(of & (of - 1)) == isPowerOfTwo`
Soma
• 02-10-2012
m37h0d
i had the static log stuff laying around already. i didn't think about it, i just tested it and ran with it. that does make sense now though.