[lnkForumImage]
TotalShareware - Download Free Software
Confronta i prezzi di migliaia di prodotti.
Asp Forum
 Home | Login | Register | Search 


 

Forums >

comp.lang.ruby

nextPowerOf2(n

Ch Skilbeck

8/7/2006 2:30:00 PM

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


--
Posted via http://www.ruby-....
31 Answers

hadley wickham

8/7/2006 2:47:00 PM

0

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

8/7/2006 2:49:00 PM

0



> From: Ch Skilbeck
> Sent: Monday, August 07, 2006 4:30 PM
>
> 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

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

cheers

Simon

Farrel Lifson

8/7/2006 2:50:00 PM

0

On 07/08/06, Ch Skilbeck <ruby@skilbeck.com> 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
>
>
> --
> Posted via http://www.ruby-....
>
>

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

8/7/2006 2:51:00 PM

0

On 07/08/06, Farrel Lifson <farrel.lifson@gmail.com> wrote:
> On 07/08/06, Ch Skilbeck <ruby@skilbeck.com> 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
> >
> >
> > --
> > Posted via http://www.ruby-....
> >
> >
>
> 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

8/7/2006 2:54:00 PM

0

On 07/08/06, Farrel Lifson <farrel.lifson@gmail.com> wrote:
> On 07/08/06, Farrel Lifson <farrel.lifson@gmail.com> wrote:
> > On 07/08/06, Ch Skilbeck <ruby@skilbeck.com> 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
> > >
> > >
> > > --
> > > Posted via http://www.ruby-....
> > >
> > >
> >
> > 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

8/7/2006 3:02:00 PM

0

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

Just some thoughts


Cheers,
Daniel

Rick DeNatale

8/7/2006 3:25:00 PM

0

On 8/7/06, Daniel Schierbeck <daniel.schierbeck@gmail.com> wrote:
> 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[b] ; high = b if n[b] != 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[b]
> high = b unless n[b] == 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.denh...

Visit the Project Mercury Wiki Site
http://www.mercuryspace...

Robert Klemme

8/7/2006 3:37:00 PM

0

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

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 Gray

8/7/2006 3:55:00 PM

0

On Aug 7, 2006, at 10:05 AM, Daniel Schierbeck wrote:

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

James Edward Gray II

Daniel Schierbeck

8/7/2006 3:56:00 PM

0

Rick DeNatale wrote:
> On 8/7/06, Daniel Schierbeck <daniel.schierbeck@gmail.com> wrote:
>> 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[b] ; high = b if n[b] != 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[b]
>> high = b unless n[b] == 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