5
\$\begingroup\$

I have the following simple program which calculates and returns the nearest power of 2 of a given number. Because I use increments and decrements to find the closest power, this takes a very long time when working with higher numbers. Is there any way to reduce the run time of the program when working with larger numbers?

puts "Enter the value of n:" 
n = gets.chomp.to_i 
def ispow2(n)
 n & (n - 1) == 0
end
if ispow2(n)
 puts "#{n} is the closest power of 2 to #{n}."
 exit
end
x = n
y = n
until ispow2(x)
 x += 1
 ispow2(x)
end 
until ispow2(y)
 y -= 1
 ispow2(y)
end
if (n - y) == (x - n)
 puts "#{x} and #{y} are the closest powers of 2 to #{n}."
else if (n - y) < (x - n)
 puts "#{y} is the closest power of 2 to #{n}."
else
 puts "#{x} is the closest power of 2 to #{n}."
end
200_success
146k22 gold badges190 silver badges479 bronze badges
asked Oct 11, 2015 at 4:03
\$\endgroup\$

3 Answers 3

6
\$\begingroup\$

Performance

What's the next power of 2 smaller than this number (binary presentation)?

0b00100101010010011

It's all the 1's reset except the first:

0b00100000000000000

What's the next power of 2 greater? It's smaller number shifted to left:

0b01000000000000000

The implementation of this logic will be both faster and simpler.

However, be mindful of the special cases when the target number is exactly a power of 2 or zero.

else if

This didn't work on my computer:

if (n - y) == (x - n)
 puts "#{x} and #{y} are the closest powers of 2 to #{n}."
else if (n - y) < (x - n)
 puts "#{y} is the closest power of 2 to #{n}."
else
 puts "#{x} is the closest power of 2 to #{n}."
end

I had to change the else if to elsif.

Don't repeat yourself

Instead of this:

if (n - y) == (x - n)
 puts "#{x} and #{y} are the closest powers of 2 to #{n}."
elsif (n - y) < (x - n)
 puts "#{y} is the closest power of 2 to #{n}."
else
 puts "#{x} is the closest power of 2 to #{n}."
end

It would be better to reduce the duplication in the printing:

if (n - y) == (x - n)
 puts "#{x} and #{y} are the closest powers of 2 to #{n}."
else
 if (n - y) < (x - n)
 result = y
 else
 result = x
 end
 puts "#{result} is the closest power of 2 to #{n}."
end
answered Oct 11, 2015 at 4:43
\$\endgroup\$
11
  • 1
    \$\begingroup\$ Clearing all but the most significant bit set will yield the largest power of two that is less than or equal to the input. A power of two that is strictly less than the input only exists for integers greater than 1. If you subscribe to the idea that 0 is also somehow a power of two, note that the left-shifting trick will fail in this case. \$\endgroup\$ Commented Oct 11, 2015 at 6:57
  • 1
    \$\begingroup\$ Good point, I added a note about the special cases of exact power of 2 and 0. And no, 0 is certainly not a power of 2. \$\endgroup\$ Commented Oct 11, 2015 at 7:00
  • \$\begingroup\$ OP is talking about the nearest powers of two so I think your logic is fine but you should make the explanation match it. \$\endgroup\$ Commented Oct 11, 2015 at 7:06
  • \$\begingroup\$ I thought I did. Did you see my update? \$\endgroup\$ Commented Oct 11, 2015 at 7:08
  • 1
    \$\begingroup\$ I'd rather replace "What's the next power of 2 smaller than this number (binary presentation)?" with "What's the next power of 2 less than or equal to this number (binary presentation)?". But the remark about the special case of input 0 remains. However, if you return "less than or equal" for the lower bound, it is unclear what you want for the upper bound. In the end, the OP will have to clarify the requirements. \$\endgroup\$ Commented Oct 11, 2015 at 7:11
1
\$\begingroup\$

Maybe not the quickest, but still reasonably quick and clean solution would be to use logarithms.

def nearest_power_of_2 number
 return 0 if number <= 0
 exponent = Math.log2 number
 higher_power = 2**exponent.ceil
 lower_power = 2**exponent.floor
 (higher_power - number) <= (number - lower_power) ? higher_power : lower_power
end
puts "#{nearest_power_of_2 10} is the closest power of 2 to #{10}."

It will work correctly for floats, but numbers equal or less than zero need special case.

I took liberty of returning 0 in case of non-positive number, as this is limit of smallest powers of 2, but it might be more appropriate to raise a DomainError if you think so, as 0 isn't really a power of 2, and result is undefined. It also has tendency to pick higher number if they happen to be equally far, you can change this by reversing <= sign.

Too keep responsibilities atomic, I extracted printing outside of calculating method. A method should do one thing, your code is more flexible and reusable that way.

answered Oct 11, 2015 at 7:45
\$\endgroup\$
5
  • \$\begingroup\$ On the side note, I can't understand why in Ruby 2**(-Float::INFINITY) == 0, but it raises domain error on (-Float::INFINITY).ceil \$\endgroup\$ Commented Oct 11, 2015 at 7:50
  • \$\begingroup\$ That's probably due to the usage of IEEE floats; I don't really know Ruby myself, but the float infinity is not really a value that you can map to an actual number, let alone round it (it's higher than any other representable floating point number by definition). But a language can freely define 2^-infinity to be zero, and it would make sense. \$\endgroup\$ Commented Oct 11, 2015 at 9:07
  • \$\begingroup\$ 2**Math.log2(number).round seems more readable than the last 4 lines \$\endgroup\$ Commented Oct 12, 2015 at 10:24
  • 1
    \$\begingroup\$ @dgmora 2**Math.log2(2.9).round == 4 \$\endgroup\$ Commented Oct 12, 2015 at 11:16
  • \$\begingroup\$ You're right, I did only check for integers :/ \$\endgroup\$ Commented Oct 12, 2015 at 11:24
1
\$\begingroup\$

I wanted to check janos' answer, as it seemed clever but it did not have neither a solution (rather an indication) or a benchmark. Here's a simple benchmarked solution:

require 'benchmark'
n = 5_000_000
def closest_power(number)
 exponent = Math.log2 number
 higher_power = 2**exponent.ceil
 lower_power = 2**exponent.floor
 (higher_power - number) <= (number - lower_power) ? higher_power : lower_power
end
def closest_power_bitwise(n)
 next_power = 2**(n.bit_length)
 previous_power = 2**(n.bit_length - 1)
 (n - previous_power) < (next_power - n) ? previous_power : next_power
end
def closest_power_op(n) 
 return n if ispow2 n 
 x = n
 y = n
 x += 1 until ispow2 x
 y -= 1 until ispow2 y
 (n - y) < (x - n) ? y : x
end
def ispow2(n)
 n & (n - 1) == 0
end
Benchmark.bm do |x|
 x.report(' log') { (1..n).each{ |i| closest_power i } }
 #op solution was slower, so it's just commented.
 #x.report(' op') { (1..n).each{ |i| closest_power_op i } }
 x.report('bitwise') { (1..n).each{ |i| closest_power_bitwise i } }
end

In my machine, the version from Borsunho is much faster:

 user system total real
 log 2.530000 0.000000 2.530000 ( 2.535258)
bitwise 1.190000 0.000000 1.190000 ( 1.190156)

After tweaking the code with Borsunho's help, the bitwise solution is much faster. Note that this solution works only with integers.

\$\endgroup\$
2
  • \$\begingroup\$ You are losing tons of clocks for to_s. Ruby has built-in bit_length, what makes bit-implementation about twice as fast. It also is more readable than mine, though it still won't work on floats. \$\endgroup\$ Commented Oct 12, 2015 at 12:01
  • \$\begingroup\$ ...Right, didn't know bit_length :). So I will just update the answer to leave the benchmark and a solution. \$\endgroup\$ Commented Oct 12, 2015 at 12:17

Your Answer

Draft saved
Draft discarded

Sign up or log in

Sign up using Google
Sign up using Email and Password

Post as a guest

Required, but never shown

Post as a guest

Required, but never shown

By clicking "Post Your Answer", you agree to our terms of service and acknowledge you have read our privacy policy.

Start asking to get answers

Find the answer to your question by asking.

Ask question

Explore related questions

See similar questions with these tags.