How do I find the value of exponent in Ruby?

Consider the equation below:

2 ** n = A

Let us assume A=64.

What is the easiest way to find the value of n?

I am currently using following two approaches

A= 64; n = 1; n+=1 while (A >> n) > 0; n-1

A= 64; n = 0; n+=1 until (A == ( 2 ** n));n

Is there a better approach?

Other way of stating the same problem:

2 = nth root A If I know the value of A, how do I determine the value of n?

14.10.2009 00:31:24
I did a simple benchmark on three approaches. As expected logarithmic approach is the fastest. user system total real bit-wise right shift 0.235000 0.000000 0.235000 ( 0.235000) sequential compare 1.484000 0.000000 1.484000 ( 1.500000) logarithmic 0.141000 0.000000 0.141000 ( 0.140000)
Harish Shetty 14.10.2009 01:34:00
I changed the logic of bit shift shift method ( i.e my first approach) and got the best performance compared to other three methods. A= 64; n = 0; n+=1 until ((A >>= 1) == 0); n; So I am going with the bit shift approach.
Harish Shetty 14.10.2009 02:01:53
5 ОТВЕТОВ
РЕШЕНИЕ

Neither of the above answers is better than your first approach:

A= 64; n = 1; n+=1 while (A >> n) > 0; n-1

Evaluating Math.log(x) takes a lot longer than doing a dozen bit-shifts, and will also give you an answer like 5.99999999999980235 to make sense of.

See this SO question for some better ideas.

4
23.05.2017 11:47:54

log2n = ln n / ln 2

hence

log_2_64 = Math.log(64) / Math.log(2)
3
14.10.2009 00:41:55

Try this:

def exp_value(n)
  Math.log(n) / Math.log(2)
end
9
14.10.2009 00:41:55
Stuff like this makes me wish that I comprehended logarithms well, know of any good/simple online references?
Robert K 14.10.2009 00:45:21
This is not complex mathematics - they teach this in high school: en.wikipedia.org/wiki/Logarithm
duffymo 14.10.2009 00:59:34
@Duffymo: fair enough but (1) complex (or not) is a relative term here and (2) not all of us paid attention during high school math classes. There's no sense in telling someone, "this is trivial," if he or she asks for references to more information.
Telemachus 14.10.2009 01:08:38

If you care about the problems mentioned by mobrule. How about this? It is the same as your own method but use built-in function to communicate the idea explictly.

    def exp_value a 
       (1..a).to_a.detect {|n| 2**n >=a}
    end

    exp_value 64
    => 6
-1
23.05.2017 12:11:21
(1..a).to_a creates an Array of size a. So your algorithm has an O(n) complexity for something that could be achieved much more efficiently...
Lykos 10.09.2012 19:17:04
It took several seconds on my computer for numbers like 10 million, which are reasonably small to appear in real world applications.
Lykos 10.09.2012 19:40:10

The proposed answer is good, but you have to count up to your logarithm and there is a slightly more efficient way, if you know that the logarithm has an upper bound, i.e. if you know that you never deal with numbers larger than 1 << bound.

def faster_log2(n)
  l = 0; bound = 64
  while bound > 0
    if 1 << bound > n
      n >>= bound; l += bound
    end
    bound >>= 1
  end
  l
end

If you don't have an upper bound, but you still want to use this algorithm, you can also calculate a bound before executing the algorithm, but if performance is not an issue, then I would stick with the shorter solution.

def bound(n)
  bound = 1;
  bound >>= 1 while 1 << bound < n
end
0
10.09.2012 19:13:09