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?

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?

it's to help me generate aligned memory addresses.

e.g. nextMultiple(16,30) //returns 32;

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.

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.

I just tested my "solutions" from post 4 and they don't even work!

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.

thank you, everyone.

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);
}

---

O_o

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

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

Soma

DOH!

you're right...i caught that last night and then forgot about it.

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.

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

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.