nextPowerOf2(n)

[pixant]

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,

2i] << [2i + 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/

[pixant]

On 8/7/06, Simon Kröger [email protected] wrote:

Rick DeNatale wrote:

end

?

Ahh, but the following is both quicker and more economical of source
code

def next_power_of_2(n)
end

If you don’t care about a correct answer, then nil is as good as any.

–
Rick DeNatale

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

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

[pixant]

-----BEGIN PGP SIGNED MESSAGE-----
Hash: SHA1

Ch Skilbeck wrote:

end
def nextPowerOf2(n); n.to_s(2).length; end
-----BEGIN PGP SIGNATURE-----
Version: GnuPG v1.4.2.2 (GNU/Linux)

iD8DBQFE16/fmV9O7RYnKMcRAoCQAKCyUMDF8qVWCH4Vtu+CnV2UOBJTJgCghnIp
zS+Li0sTuB6E1O0lStXPn+Q=
=4y44
-----END PGP SIGNATURE-----

[pixant]

Rick DeNatale wrote:

throw ‘eeek’ if n < 0

If you don’t care about a correct answer, then nil is as good as any.

would you dare to explain?

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

puts next_power_of_2(0) #=> 1
puts next_power_of_2(1) #=> 1
puts next_power_of_2(2) #=> 2
puts next_power_of_2(3) #=> 4
puts next_power_of_2(4) #=> 4
puts next_power_of_2(5) #=> 8
puts next_power_of_2(255) #=> 256
puts next_power_of_2(256) #=> 256
puts next_power_of_2(257) #=> 512
puts next_power_of_2(536870911) #=> 536870912
puts next_power_of_2(536870912) #=> 536870912
puts next_power_of_2(536870913) #=> 1073741824

seems to be correct for a lot more cases than nil(?)

cheers

Simon

[pixant]

-----BEGIN PGP SIGNED MESSAGE-----
Hash: SHA1

Suraj N. Kurapati wrote:

def nextPowerOf2(n); n.to_s(2).length; end

Ah, well this doesn’t actually produce your desired output.
Nevertheless, this is the way to calculate the number of bits
required to represent an integer (signed & unsigned)!
-----BEGIN PGP SIGNATURE-----
Version: GnuPG v1.4.2.2 (GNU/Linux)

iD8DBQFE17EjmV9O7RYnKMcRAt4qAKCaKv5KNaMClpQg+vEBWGKhBst/4QCeIg/X
zL6KQJ9SQmCrMCqEn0WLLGE=
=bDAS
-----END PGP SIGNATURE-----

[pixant]

Ch Skilbeck wrote:

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

Thankyou all - very helpful indeed. In my eagerness to use Ruby features
I managed to almost completely forget how to code and write something
that’s orders of magnitude slower than it needed to be. This has been
extremely useful - I’m totally digging this Ruby deal, it feels like a
comfortable holiday home with nice weather and a good beach.

[pixant]

Jacob F. wrote:

irb(main):022:1> end

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.

I really doubt, that the implementation of Math.log (or any serious
implementation of a log for that matter) is O(log(n)). Usually, logs
are computed by a polynomial approximation on the interval (0.5, 1)
for the mantissa, and a trivial computation for the exponent, which
makes it O(1).

Best regards,

Michael

–
Michael U.
R&D Team
ISIS Information Systems Austria
tel: +43 2236 27551-219, fax: +43 2236 21081
e-mail: [email protected]
Visit our Website: www.isis-papyrus.com

[pixant]

On 8/8/06, Michael U. [email protected] wrote:

makes it O(1).
I stand corrected.

My guess is that the number of terms N in the polynomial that need
to be calculated for a certain precision in the approximation of
log(x) is in fact also O(log2(x)). But you’re right that
implementations can just assume an N that will be sufficiently large
for all valid 32/64-bit values and always use that precision, in which
case it can be argued the algorithm is O(1).

Jacob F.

[pixant]

The following integer implementation runs in log(log(n)) time (in non
mathematical speak, that’s “fast” ).

[In a language like c, for a fixed length word, unroll the loop and
loose the descision logic so that it only deals with the word size
you’re interested in].

class Integer
def next_power_of_two
mask_of_all_bits_below_top_bit + 1
end

def mask_of_all_bits_below_top_bit
mask = self
shift = 1
while ((shifted_mask = mask >> shift) > 0) do
mask = mask | shifted_mask
shift = shift << 1
end
mask
end
end

[pixant]

On 8/7/06, Simon Kröger [email protected] wrote:

def next_power_of_2(n)
end

puts next_power_of_2(536870912) #=> 536870912
puts next_power_of_2(536870913) #=> 1073741824

seems to be correct for a lot more cases than nil(?)

You had to go a bit further back in the thread. All of the versions
which relied on float math functions fell apart for differing
increasing values of n as the floating point math starts to diverge
from ‘pure’ math.

I never said that it wasn’t possible to write a method which produced
accurate answers, only that those float based ones don’t and that
there was no sense in benchmarking implementations which produce bogus
results against those which do.