From: Rick DeNatale <rick.denatale@...>
Date: 2006-08-08T05:04:31+09:00
Subject: Re: nextPowerOf2(n)

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/