nextPowerOf2(n)

[Ch Skilbeck]

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 ; high = b if n != 0}
1 << high + (count > 1 ? 1 : 0)
end

 

[hadley wickham]

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

 

[Kroeger, Simon (ext)]

=20

From: Ch Skilbeck
Sent: Monday, August 07, 2006 4:30 PM
=20
Hi,
=20
Can someone tell me if there's a better way to do this? It takes a=20
number and returns the next power of 2 up (or the original if it was=20
already a power of 2) Specifically, are there features of Ruby that I=20
should be using in this case?
=20
Cheers,
Charlie.
=20
def nextPowerOf2(n)
raise "integer please" if !n.kind_of? Integer
high =3D 0
count =3D 0
(0..n.size * 8 - 2).each {|b| count +=3D n ; high =3D b if n = !=3D 0}
1 << high + (count > 1 ? 1 : 0)
end

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

cheers

Simon

 

[Farrel Lifson]

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 ; high = b if n != 0}
1 << high + (count > 1 ? 1 : 0)
end

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

 

[Farrel Lifson]

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 ; high = b if n != 0}
1 << high + (count > 1 ? 1 : 0)
end

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

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

 

[Farrel Lifson]

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 ; high = b if n != 0}
1 << high + (count > 1 ? 1 : 0)
end

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

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

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

 

[Daniel Schierbeck]

def nextPowerOf2(n)
raise "integer please" if !n.kind_of? Integer
high = 0
count = 0
(0..n.size * 8 - 2).each {|b| count += n ; high = b if n != 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
high = b unless n == 0
end

Just some thoughts


Cheers,
Daniel

 

[Rick DeNatale]

def nextPowerOf2(n)
raise "integer please" if !n.kind_of? Integer
high = 0
count = 0
(0..n.size * 8 - 2).each {|b| count += n ; high = b if n != 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
high = b unless n == 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/

 

[Robert Klemme]

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 ; high = b if n != 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

 

[James Edward Gray II]

(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
high = b unless n == 0
end

James Edward Gray II

 

[Daniel Schierbeck]

def nextPowerOf2(n)
raise "integer please" if !n.kind_of? Integer
high = 0
count = 0
(0..n.size * 8 - 2).each {|b| count += n ; high = b if n != 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
high = b unless n == 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

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


Cheers,
Daniel

 

[Alex Young]

Robert Klemme wrote:

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

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

 

[hadley wickham]

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

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

Hadley

 

[Daniel Martin]

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

 

[ara.t.howard]

Robert Klemme wrote:

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

 

[Jacob Fugal]

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

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 Martin
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 Fugal

 

[Rick DeNatale]

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 ; high = b if n != 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
high = b unless n == 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

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

 

[Simon Kröger]

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:

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

 

[Rick DeNatale]

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.

lass Integer
def denatale_next_power_of_2
trial = 1
loop do
return trial if trial >= self
trial <<= 1
end
end

def klemme_next_power_of_2
x = self
c = 0

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

1 << c
end
end

class Wicham


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

def self.next_power_of_2(x)
2 ** (log2(x).ceil)
end
end


class Kroeger

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

class Lifson

def self.next_power_of_2(n)
if Math.sqrt(n).modulo(1).zero?
n
else
2**Math.sqrt(n).to_i.succ
end
end
end
===== End of next_power_of_2.rb =====

And now the test cases

load 'next_power_of_2.rb'

require 'test/unit'

class TestIntegerMethods < Test::Unit::TestCase

def setup
@check_array = [[1, 1], [2,2]]
(2..100).each do | i |
@check_array << [ 2**i - 1, 2**i] << [2**i,
2**i] << [2**i + 1, 2**(i+1)]
end
end

def test_denatale
@check_array.each do | input, output |
assert_equal(output,
input.denatale_next_power_of_2, "#{input} => #{output}")
end
end
def test_wicham
@check_array.each do | input, output |
assert_equal(output, Wicham.next_power_of_2(input))
end
end

def test_kroeger
@check_array.each do | input, output |
assert_equal(output, Kroeger.next_power_of_2(input))
end
end

def test_lifson
@check_array.each do | input, output |
assert_equal(output, Lifson.next_power_of_2(input))
end
end
end

=== end of 'test_powers.rb' ===

And now the results
rick@bill:~/rubyscripts$ ruby test_powers.rb
Loaded suite test_powers
Started
FFF
Finished in 0.38841 seconds.

1) Failure:
test_kroeger(TestIntegerMethods)
[test_powers.rb:34:in `test_kroeger'
test_powers.rb:33:in `test_kroeger']:
<536870912> expected but was
<1073741824>.

2) Failure:
test_lifson(TestIntegerMethods)
[test_powers.rb:40:in `test_lifson'
test_powers.rb:39:in `test_lifson']:
<2> expected but was
<4>.

3) Failure:
test_wicham(TestIntegerMethods)
[test_powers.rb:28:in `test_wicham'
test_powers.rb:27:in `test_wicham']:
<536870912> expected but was
<1073741824>.

4 tests, 471 assertions, 3 failures, 0 errors
rick@bill:~/rubyscripts$

So unless I screwed something up in transcribing the code, which is
entirely possible, only the integer arithmetic solutions actually
worked.

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.


--
Rick DeNatale

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

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

 

[Simon Kröger]

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