nextPowerOf2(n)

Ruby
1

Hi,

Can someone tell me if there’s a better way to do this? It takes a
number and returns the next power of 2 up (or the original if it was
already a power of 2) Specifically, are there features of Ruby that I
should be using in this case?

Cheers,
Charlie.

def nextPowerOf2(n)
raise “integer please” if !n.kind_of? Integer
high = 0
count = 0
(0…n.size * 8 - 2).each {|b| count += n[b] ; high = b if n[b] != 0}
1 << high + (count > 1 ? 1 : 0)
end

2

Can someone tell me if there’s a better way to do this? It takes a
number and returns the next power of 2 up (or the original if it was
already a power of 2) Specifically, are there features of Ruby that I
should be using in this case?

Try this:

def log2(x)
Math.log(x) / Math.log(2)
end

def nextPowerOf2(x)
2 ** (log2(x).ceil)
end

Hadley

3

Cheers,
Charlie.

def nextPowerOf2(n)
raise “integer please” if !n.kind_of? Integer
high = 0
count = 0
(0…n.size * 8 - 2).each {|b| count += n[b] ; high = b if n[b] != 0}
1 << high + (count > 1 ? 1 : 0)
end

def nextPowerOf2(n)
2 ** (Math.log(n) / Math.log(2)).ceil
end

cheers

Simon

4

On 07/08/06, Farrel L. [email protected] wrote:

Posted via http://www.ruby-forum.com/.
def nextPowerOf2(n)
if Math.sqrt(n).modulo(1).zero?
n
else
2**Math.log2(5).to_i.succ
end
end

Farrel

Gah! I don’t even need that Math.log2 function

def nextPowerOf2(n)
if Math.sqrt(n).modulo(1).zero?
n
else
2**Math.sqrt(5).to_i.succ
end
end

Farrel

5

On 07/08/06, Farrel L. [email protected] wrote:

Charlie.

Farrel

Sorry for the repeated typos, it shoud be ‘2**Math.sqrt(n).to_i.succ’

6

On 07/08/06, Ch Skilbeck [email protected] wrote:

def nextPowerOf2(n)

My attempt:

Finds the log base 2 of a number

def Math.log2(n)
Math.log(n)/Math.log(2)
end

def nextPowerOf2(n)
if Math.sqrt(n).modulo(1).zero?
n
else
2**Math.log2(5).to_i.succ
end
end

Farrel

7

Ch Skilbeck wrote:

def nextPowerOf2(n)
raise “integer please” if !n.kind_of? Integer
high = 0
count = 0
(0…n.size * 8 - 2).each {|b| count += n[b] ; high = b if n[b] != 0}
1 << high + (count > 1 ? 1 : 0)
end

Your question has already been answered by Simon, but I’d like to show
you how your code could be more Rubyesque.

First off, method name are always lower_case_with_underscore, so

def next_power_of_2(n)

Ruby has the `unless’ keyword, so

raise “integer please” unless n.kind_of? Integer

but you don’t really have to check the argument’s class – just check if
the provided object responds to #to_int, or don’t even check at all.

raise “integer please” unless n.respond_to? :to_int
n = n.to_int

Parallel assignment is cool

high, count = 0, 0

I’d split the next part up, but that may just be me

(0…(n.size * 8 - 2)).each do |b|
count += n[b]
high = b unless n[b] == 0
end

Just some thoughts

Cheers,
Daniel

8

On 8/7/06, Daniel S. [email protected] wrote:

you how your code could be more Rubyesque.
the provided object responds to #to_int, or don’t even check at all.
(0…(n.size * 8 - 2)).each do |b|
count += n[b]
high = b unless n[b] == 0
end

Just some thoughts

Here’s another take

irb(main):016:0> class Fixnum
irb(main):017:1> def next_power_of_2
irb(main):018:2> trial = 1
irb(main):019:2> trial <<= 1 while trial < self
irb(main):020:2> return trial
irb(main):021:2> end
irb(main):022:1> end
=> nil
irb(main):023:0> (-1…10).collect { | i | [i, i.next_power_of_2] }
=> [[-1, 1], [0, 1], [1, 1], [2, 2], [3, 4], [4, 4], [5, 8], [6, 8],
[7, 8], [8, 8], [9, 16], [10, 16]]
irb(main):024:0>

This should be fairly fast since at first glance it’s o(log2(n))

And it makes it a method of Fixnum

–
Rick DeNatale

IPMS/USA Region 12 Coordinator
http://ipmsr12.denhaven2.com/

Visit the Project Mercury Wiki Site
http://www.mercuryspacecraft.com/

9

Ch Skilbeck wrote:

def nextPowerOf2(n)
raise “integer please” if !n.kind_of? Integer
high = 0
count = 0
(0…n.size * 8 - 2).each {|b| count += n[b] ; high = b if n[b] != 0}
1 << high + (count > 1 ? 1 : 0)
end

Did we have this solution already?

class Integer
def next_power
x = self
c = 0

 until x == 0
   x >>= 1
   c += 1
 end

 1 << c

end
end

Kind regards

robert
10

On Aug 7, 2006, at 10:05 AM, Daniel S. wrote:

(0…(n.size * 8 - 2)).each do |b|

Prehaps:

0.upto(n.size * 8 - 2) do |b|

or:

(n.size * 8 - 2).times do |b|

count += n[b]
high = b unless n[b] == 0

end

James Edward G. II

11

Robert K. wrote:

end

1 << c

end
end
Neat, but hits an infinite loop for negative x. Then again, that wasn’t
part of the original problem…

12

irb(main):023:0> (-1…10).collect { | i | [i, i.next_power_of_2] }
=> [[-1, 1], [0, 1], [1, 1], [2, 2], [3, 4], [4, 4], [5, 8], [6, 8],
[7, 8], [8, 8], [9, 16], [10, 16]]
irb(main):024:0>

This should be fairly fast since at first glance it’s o(log2(n))

When the alternatives are O(1), that’s not that great!

Hadley

13

Ch Skilbeck [email protected] writes:

Can someone tell me if there’s a better way to do this? It takes a
number and returns the next power of 2 up (or the original if it was
already a power of 2) Specifically, are there features of Ruby that I
should be using in this case?

Others have already given you floating point solutions to this, but
I’ve found that at least for numbers under 2**64, this is faster (uses
only integer arithmetic). This method is also easily translateable
into extremely fast C, if that becomes necessary:

def nextPowerOf2(n)
return n if (n-1)&n == 0
pow=1
while (n >= 0x100000000) do pow += 32; n >>= 32; end
if (n & 0xFFFF0000 > 0) then pow += 16; n >>= 16; end
if (n & 0xFF00 > 0) then pow += 8; n >>= 8; end
if (n & 0xF0 > 0) then pow += 4; n >>= 4; end
if (n & 0xC > 0) then pow += 2; n >>= 2; end
if (n & 0x2 > 0) then pow += 1; n >>= 1; end
1<<pow
end

It returns “0” when handed 0, when arguably it should return 1; on the
other hand, the log-based methods simply blow up when handed 0, so
this is an improvement.

Benchmark on the Math.log method, the originally posted code, and then
my code shows:

  user     system      total        real

1.281000 0.000000 1.281000 ( 1.281000)
4.547000 0.000000 4.547000 ( 4.547000)
0.922000 0.000000 0.922000 ( 0.922000)

Benchmark code was:

checkarray = Array.new(50000) {rand(1<<64)}
Benchmark.bm { |x|
x.report { checkarray.each {|f| nextPowerOf2_log(f)}}
x.report { checkarray.each {|f| nextPowerOf2_orig(f)}}
x.report { checkarray.each {|f| nextPowerOf2(f)}}
}

14

Rick DeNatale wrote:

Your question has already been answered by Simon, but I’d like to show
but you don’t really have to check the argument’s class – just check if

irb(main):017:1> def next_power_of_2

This should be fairly fast since at first glance it’s o(log2(n))

And it makes it a method of Fixnum

Very nice. Better add it to Integer instead, though – otherwise Bignums
won’t have the method.

Cheers,
Daniel

15

On Tue, 8 Aug 2006, Alex Y. wrote:

  x >>= 1
  c += 1
end

1 << c

end
end
Neat, but hits an infinite loop for negative x. Then again, that wasn’t part
of the original problem…

easy to fix:

harp:~ > cat a.rb
class Integer
def next_power_2
return @next_power_2 if defined? @next_power_2

   x = self.abs
   c = 0

   until x == 0
     x >>= 1
     c += 1
   end

   np2 = 1 << c
   @next_power_2 = self < 0 ? -np2 : np2
 end

end

p 42.next_power_2
p -42.next_power_2

harp:~ > ruby a.rb
64
-64

note that it’s ‘vectorized’ : positives move up and negatives down.

-a

16

On 8/7/06, hadley wickham [email protected] wrote:

irb(main):023:0> (-1…10).collect { | i | [i, i.next_power_of_2] }
=> [[-1, 1], [0, 1], [1, 1], [2, 2], [3, 4], [4, 4], [5, 8], [6, 8],
[7, 8], [8, 8], [9, 16], [10, 16]]
irb(main):024:0>

This should be fairly fast since at first glance it’s o(log2(n))

When the alternatives are O(1), that’s not that great!

Except that the implementation of Math.log itself is most likely
O(log2(n)) as well (unless the C source contains a gigantic lookup
table; unlikely). So using a strict O-based analysis, neither is
preferable over the other.

Whether the Math.log based solutions are faster is highly variable.
The Math.log solutions will have the speed of a C implementation on
their side (vs. an in-Ruby loop). But they need to calculate two
logs (this can be eliminated by caching the result of Math.log(2) in a
constant), and then perform a division. But as Daniel M.
demonstrates, bypassing the Math.log(2) implementation with custom
in-Ruby code allows us to specific loop unrolling and other such
optimizations.

Algorithm-wise, however, they’re equal.

Jacob F.

17

Daniel M. wrote:

into extremely fast C, if that becomes necessary:
This is not because of the integer arithmetic, try this:

def nextPowerOf2(n)
1 << (Math.log(n) * Math.log(2)).ceil
end

[…snip…]

cheers

Simon

18

On 8/7/06, Daniel S. [email protected] wrote:

I’d split the next part up, but that may just be me
irb(main):016:0> class Fixnum
irb(main):024:0>

This should be fairly fast since at first glance it’s o(log2(n))

And it makes it a method of Fixnum

Very nice. Better add it to Integer instead, though – otherwise Bignums
won’t have the method.

Fair enough, and while I’m at it why not handle Floats as well

class Integer
def next_power_of_2
trial = 1
loop do
return trial if trial >= self
trial <<= 1
end
end
end

class Float
# Defer to Fixnum if not >= 0,0 and < 1.0
def next_power_of_2

            ciel.next_power_of_2 if self >= 1 || self < 0

            last_trial = 1.0
            loop do
                    trial = last_trial / 2.0
                    raise

ArgumentError.new(“#{self}.next_power_of_2 is not representable”) if
trial.zero?
return last_trial if trial < self
last_trial = trial
end
end
end

Note that some of the printed representations of some of those values
of 2^n for negative n might look weird, but that’s floating point math
for you

=> 3.814697265625e-06
irb(main):016:0> t = 0.00003.next_power_of_2
=> 3.0517578125e-05
irb(main):017:0> while t < 1.0
irb(main):018:1> p t
irb(main):019:1> t *= 2.0
irb(main):020:1> end
3.0517578125e-05
6.103515625e-05
0.0001220703125
0.000244140625
0.00048828125
0.0009765625
0.001953125
0.00390625
0.0078125
0.015625
0.03125
0.0625
0.125
0.25
0.5
=> nil

19

Rick DeNatale wrote:

I hope that this doesn’t offend anyone, but in the spirit of test
infection…

I actually took the various suggestions and wrote test cases. Here’s
my file “next_power_of_2.r b” which defines either methods on Integer,
or a class with a next_power_of_2() class method, following the
various suggestions, I did give these methods a consistent name
following Ruby naming standards.

…

This really isn’t surprising, since floating point arithmetic only
approximates real arithmetic using real numbers.

My original intention was to benchmark the various suggestions, but
since you can get the wrong answers with arbitrarily fast code, I
don’t think that it matters much.

Hmm, what about:

def next_power_of_2(n)
throw ‘eeek’ if n < 0
return 1 if n < 2
1 << (n-1).to_s(2).size
end

?

cheers

Simon

20

Daniel M. [email protected] writes:

Others have already given you floating point solutions to this, but
I’ve found that at least for numbers under 2**64, this is faster (uses
only integer arithmetic). This method is also easily translateable
into extremely fast C, if that becomes necessary:

(code snipped)

I should note that the algorithm I used - which could, I suppose, be
viewed as simply clever loop unrolling after doing quick 32-bit shifts
to get into the ballpark, was cribbed from some assembly in the C
header file longlong.h, which includes the macro count_leading_zeros
that counts the number of zeros in the front of a long long variable.
Any C implementation would probably be advised to make good use of
that macro, which may, depending on your processor, be implemented as
a single assembly language instruction. (See the BSR instruction on
x86, for example)

Also, since someone was saying that all the integer math
implementations were essentially equivalent in speed, being all
O(log(n)), here’s a O(log(log(n))) implementation. I shudder to think
though how big an input you’d need before this beats my earlier code:

def nextPowerOf2(n)
return n if (n-1)&n == 0
return 1 if n < 2
n <<= 1
t = [2]
t.unshift(t[0]*t[0]) while t[0] < n
t.shift
ret = 1
t.each {|s|
if (s <= n) then
ret *= s
n /= s
end
}
ret
end