nextPowerOf2(n)

[Daniel Martin]

Others have already given you floating point solutions to this, but
I've found that at least for numbers under 2**64, this is faster (uses
only integer arithmetic). This method is also easily translateable
into extremely fast C, if that becomes necessary:

(code snipped)

I should note that the algorithm I used - which could, I suppose, be
viewed as simply clever loop unrolling after doing quick 32-bit shifts
to get into the ballpark, was cribbed from some assembly in the C
header file longlong.h, which includes the macro count_leading_zeros
that counts the number of zeros in the front of a long long variable.
Any C implementation would probably be advised to make good use of
that macro, which may, depending on your processor, be implemented as
a single assembly language instruction. (See the BSR instruction on
x86, for example)

Also, since someone was saying that all the integer math
implementations were essentially equivalent in speed, being all
O(log(n)), here's a O(log(log(n))) implementation. I shudder to think
though how big an input you'd need before this beats my earlier code:

def nextPowerOf2(n)
return n if (n-1)&n == 0
return 1 if n < 2
n <<= 1
t = [2]
t.unshift(t[0]*t[0]) while t[0] < n
t.shift
ret = 1
t.each {|s|
if (s <= n) then
ret *= s
n /= s
end
}
ret
end

 

[Suraj N. Kurapati]

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

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)

def nextPowerOf2(n)
raise "integer please" if !n.kind_of? Integer
high = 0
count = 0
(0..n.size * 8 - 2).each {|b| count += n ; high = b if n != 0}
1 << high + (count > 1 ? 1 : 0)
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-----

 

[Rick DeNatale]

Rick DeNatale wrote:

Hmm, what about:

def next_power_of_2(n)
throw 'eeek' if n < 0
return 1 if n < 2
1 << (n-1).to_s(2).size
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. <G>

--=20
Rick DeNatale

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

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

 

[Suraj N. Kurapati]

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

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

 

[Simon Kröger]

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

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

 

[Ch Skilbeck]

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 ; high = b if n != 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.

 

[Paul Sanchez]

How about the following, which plays stupid bit tricks?


def highest_power_of_2 n
(masked_n = n & ~(n & -n)) == 0 ? n : highest_power_of_2(masked_n)
end

def next_power_of_2 n
(h = highest_power_of_2(n)) == n ? n : h << 1
end


That's O(# of bits == 1).

--paul

 

[Michael Ulm]

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: (e-mail address removed)
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.
---------------------------------------------------------------

 

[benjohn]

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

 

[Jacob Fugal]

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

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 Fugal

 

[Paul Sanchez]

I rewrote my recursive method:

def highest_power_of_2 n
(masked_n = n & ~(n & -n)) == 0 ? n : highest_power_of_2(masked_n)
end

to be interative with parallel assignment:

def highest_power_of_2 n
old_n, n = n, n & ~(n & -n) until n == 0
old_n
end

def next_power_of_2 n
(h = highest_power_of_2(n)) == n ? n : h << 1
end

irb(main):023:0> next_power_of_2 7
=> 8
irb(main):024:0> next_power_of_2 8
=> 8
irb(main):025:0> next_power_of_2 9
=> 16
irb(main):026:0> next_power_of_2 783809810893409890187340987180987904091873409871039847019873409871093784098713094870918734098710987340987130984709187340987109348709187340987109387409871390470978139847098173497810938740987139847091872394870918734097819873490871039874098719
=> 833501804109981784259981473840157224643094790289488520049532226470504654727204008940179025108944286342866238824179155055736100206764920635045419506541353755761894697439251819807884785738976753091120627016985825247711343504684557661395484672

Bet you didn' know that last one. I love Ruby's ability to do big
integers!

--paul

 

[Rick DeNatale]

G>

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) #=3D> 1
puts next_power_of_2(1) #=3D> 1
puts next_power_of_2(2) #=3D> 2
puts next_power_of_2(3) #=3D> 4
puts next_power_of_2(4) #=3D> 4
puts next_power_of_2(5) #=3D> 8
puts next_power_of_2(255) #=3D> 256
puts next_power_of_2(256) #=3D> 256
puts next_power_of_2(257) #=3D> 512
puts next_power_of_2(536870911) #=3D> 536870912
puts next_power_of_2(536870912) #=3D> 536870912
puts next_power_of_2(536870913) #=3D> 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.

--=20
Rick DeNatale