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
\$\endgroup\$
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
\$\endgroup\$
  • 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\$ – 5gon12eder Oct 11 '15 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\$ – Stop ongoing harm to Monica Oct 11 '15 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\$ – 5gon12eder Oct 11 '15 at 7:06
  • \$\begingroup\$ I thought I did. Did you see my update? \$\endgroup\$ – Stop ongoing harm to Monica Oct 11 '15 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\$ – 5gon12eder Oct 11 '15 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.

\$\endgroup\$
  • \$\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\$ – Borsunho Oct 11 '15 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\$ – tomsmeding Oct 11 '15 at 9:07
  • \$\begingroup\$ 2**Math.log2(number).round seems more readable than the last 4 lines \$\endgroup\$ – dgmora Oct 12 '15 at 10:24
  • 1
    \$\begingroup\$ @dgmora 2**Math.log2(2.9).round == 4 \$\endgroup\$ – Borsunho Oct 12 '15 at 11:16
  • \$\begingroup\$ You're right, I did only check for integers :/ \$\endgroup\$ – dgmora Oct 12 '15 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\$
  • \$\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\$ – Borsunho Oct 12 '15 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\$ – dgmora Oct 12 '15 at 12:17

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.