Thread: need a fast algorithm for next multiple

  1. #1
    3735928559
    Join Date
    Mar 2008
    Location
    RTP
    Posts
    838

    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?

  2. #2
    - - - - - - - - oogabooga's Avatar
    Join Date
    Jan 2008
    Posts
    2,808
    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?
    The cost of software maintenance increases with the square of the programmer's creativity. - Robert D. Bliss

  3. #3
    3735928559
    Join Date
    Mar 2008
    Location
    RTP
    Posts
    838
    it's to help me generate aligned memory addresses.

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

  4. #4
    - - - - - - - - oogabooga's Avatar
    Join Date
    Jan 2008
    Posts
    2,808
    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.
    The cost of software maintenance increases with the square of the programmer's creativity. - Robert D. Bliss

  5. #5
    C++ Witch laserlight's Avatar
    Join Date
    Oct 2003
    Location
    Singapore
    Posts
    28,413
    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.
    Quote Originally Posted by Bjarne Stroustrup (2000-10-14)
    I get maybe two dozen requests for help with some sort of programming or design problem every day. Most have more sense than to send me hundreds of lines of code. If they do, I ask them to find the smallest example that exhibits the problem and send me that. Mostly, they then find the error themselves. "Finding the smallest program that demonstrates the error" is a powerful debugging tool.
    Look up a C++ Reference and learn How To Ask Questions The Smart Way

  6. #6
    - - - - - - - - oogabooga's Avatar
    Join Date
    Jan 2008
    Posts
    2,808
    I just tested my "solutions" from post 4 and they don't even work!
    The cost of software maintenance increases with the square of the programmer's creativity. - Robert D. Bliss

  7. #7
    Algorithm Dissector iMalc's Avatar
    Join Date
    Dec 2005
    Location
    New Zealand
    Posts
    6,318
    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.
    Last edited by iMalc; 02-08-2012 at 12:38 PM.
    My homepage
    Advice: Take only as directed - If symptoms persist, please see your debugger

    Linus Torvalds: "But it clearly is the only right way. The fact that everybody else does it some other way only means that they are wrong"

  8. #8
    3735928559
    Join Date
    Mar 2008
    Location
    RTP
    Posts
    838
    thank you, everyone.

  9. #9
    3735928559
    Join Date
    Mar 2008
    Location
    RTP
    Posts
    838
    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);
    }

  10. #10
    Master Apprentice phantomotap's Avatar
    Join Date
    Jan 2008
    Posts
    5,108
    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

  11. #11
    3735928559
    Join Date
    Mar 2008
    Location
    RTP
    Posts
    838
    DOH!

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

  12. #12
    3735928559
    Join Date
    Mar 2008
    Location
    RTP
    Posts
    838
    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.
    Last edited by m37h0d; 02-10-2012 at 10:05 AM.

  13. #13
    Master Apprentice phantomotap's Avatar
    Join Date
    Jan 2008
    Posts
    5,108
    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

  14. #14
    3735928559
    Join Date
    Mar 2008
    Location
    RTP
    Posts
    838
    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.

Popular pages Recent additions subscribe to a feed

Similar Threads

  1. Replies: 5
    Last Post: 05-31-2011, 07:37 AM
  2. Help Needed Fast! Multiple Choice Grading Program
    By namyad in forum C++ Programming
    Replies: 2
    Last Post: 11-16-2010, 11:17 AM
  3. Implement of a Fast Time Series Evaluation Algorithm
    By BiGreat in forum C Programming
    Replies: 7
    Last Post: 12-04-2007, 02:30 AM
  4. Very fast blurring algorithm
    By cfrost in forum Tech Board
    Replies: 1
    Last Post: 09-30-2005, 12:59 AM
  5. Fast prime determining algorithm
    By Ken Fitlike in forum A Brief History of Cprogramming.com
    Replies: 0
    Last Post: 12-01-2002, 03:05 AM