My Solution to the Rounding-Up-to-the-Nearst-Power-of-Two Problem

This is my solution to the dreaded Java-coder stumping round-up problem.  (Yeah, I subscribe to raganwald‘s feed and I like those del.icio.us links just fine, thank you.)

This algorithm runs in log(n) time, does it not?

***

Update (an hour or so later): Hmm… in this case, it appears to take 2 lisp programmers to solve this one…. Oh well. That’s what I get for not trying to “break” my code by testing the ambiguous cases….  The only change here is to make the ‘=’ into ‘<=’ and also to rename the local function per Zach’s suggestion:

(defun round-up (number) 
  (labels ((round-iter (n p) 
             (if (<= n (expt 2 p)) 
                 (expt 2 p) 
                 (round-iter n (+ p 1))))) 
    (round-iter number 0)))

***

Update (another hour or so later): Here’s Zach’s solution:

(defun round-up (value) 
  (cond ((zerop value) 
         1) 
        ((zerop (logand value (1- value))) 
         value) 
        (t 
         (expt 2 (integer-length value))))) ***

Update (another hour or so later): Here’s Chuck’s solution:

(defun next-power-of-2 (n) 
    (expt 2 (ceiling (/ (log n) (log 2)))))
Advertisements

11 Responses to “My Solution to the Rounding-Up-to-the-Nearst-Power-of-Two Problem”

  1. Zach Beane Says:

    It’s not legal CL to bind ROUND as a local function. A Lisp that strictly enforces that requirement would reject your code (unless you shadow ROUND in a new package).

    Should (round-up 4) return 4 or 8?

  2. lispy Says:

    Thanks, Zach, that was sloppy of me.

    I’ll assume that I was in error and that 4 should “round up” to 4– I did not consider that particular type of situation, so I deserve to be wrong on this one regardless of the actual “requirements”.

  3. Zach Beane Says:

    Here’s my take, hope it doesn’t get too mangled…

    (defun round-up (value)
    (cond ((zerop value)
    1)
    ((zerop (logand value (1- value)))
    value)
    (t
    (expt 2 (integer-length value)))))

  4. chuck Says:

    (defun (next-power-of-2 n)
    (expt 2 (ceiling (/ (log n) (log 2)))))

    The OP on the Java thread phrased the question badly… so the above rounds *up* to the *next* power of 2. To round to the *nearest* (be tahat up or down) replace “ceiling” with “round”.

  5. chuck Says:

    Hey, we could refactor this SICP-style 😀
    (defun (round-up-to-power-of m n)
    (expt m (ceiling (/ (log n) (log m)))))

  6. lispy Says:

    I’m disappointed that I didn’t immediately think “logarithms.”

  7. lispy Says:

    To do this SICP style, you’d need an iterator function that returns a “next guess”, a comparation function, and evaluation function. You’d call it like this:

    ((round-to-fn #’1+ #'<= #'(lambda (x) (expt 2 x)) 143))

    They’d do something more mind-blowing, but at least we have a procedure taking procedures as arguments and returning a procedure for its value.

  8. chuck Says:

    To do this SICP style, you’d need an iterator function that returns a “next guess”, a comparation function, and evaluation function. You’d call it like this:

    ((round-to-fn #’1+ #’<= #’(lambda (x) (expt 2 x)) 143))

    LOL!!

  9. lispy Says:

    I gave my answer off the cuff just to see how I compared with the rabble. I think I rate as a “moderately clever simpleton” still ignorant of some important concepts– and my initial bad habits that I brought to Lisp are still my first response. In my defense, I’d say that unless there are serious performance problems in the application, my approach would have been “good enough” to keep the development project going. So I’m still very much in the “Git ‘R Done” camp of programming practice….

  10. By the way… Zach wins ;) « Learning Lisp Says:

    […] By the way… Zach wins 😉 Following up on the next-power-of-two question: […]

  11. Andrew Says:

    I know this is an old post, but Google offered it up when I’d forgotten the optimal solution.

    The most efficient solution I’ve found to this is explained and coded out, in C, here:
    http://acius2.blogspot.com/2007/11/calculating-next-power-of-2.html

    No loops is a big win. You do need to know how many bits you’re working with, which is usually fine but with bignums you’d need to make it general.

    If the calc is only done occasionally then it doesn’t matter which method is used, I just thought this solution was very cool.

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s


%d bloggers like this: