From: Jacob Fugal <lukfugl@...>
Date: 2006-08-08T02:31:49+09:00
Subject: Re: nextPowerOf2(n)

On 8/7/06, hadley wickham <h.wickham@gmail.com> wrote:
> > 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