From: Michael Ulm <michael.ulm@...>
Date: 2006-08-08T16:43:08+09:00
Subject: Re: nextPowerOf2(n)

Jacob Fugal wrote:

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

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 Ulm
R&D Team
ISIS Information Systems Austria
tel: +43 2236 27551-219, fax: +43 2236 21081
e-mail: michael.ulm@isis-papyrus.com
Visit our Website: www.isis-papyrus.com

---------------------------------------------------------------
This e-mail is only intended for the recipient and not legally
binding. Unauthorised use, publication, reproduction or
disclosure of the content of this e-mail is not permitted.
This email has been checked for known viruses, but ISIS accepts
no responsibility for malicious or inappropriate content.
---------------------------------------------------------------