How do I find the value of exponent in Ruby?

Question

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?

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, Oct 14 '09 at 01:34
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, Oct 14 '09 at 02:01

score 9 · Answer 1 · answered Oct 14 '09 at 00:41

9

Try this:

def exp_value(n)
  Math.log(n) / Math.log(2)
end

answered Oct 14 '09 at 00:41

JRL

76,767
18
98
146

1

Stuff like this makes me wish that I comprehended logarithms well, know of any good/simple online references? – Robert K Oct 14 '09 at 00:45
2

This is not complex mathematics - they teach this in high school: http://en.wikipedia.org/wiki/Logarithm – duffymo Oct 14 '09 at 00:59
5

@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 Oct 14 '09 at 01:08

score 5 · Accepted Answer · edited May 23 '17 at 11:47

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.

edited May 23 '17 at 11:47

Community

1
1

answered Oct 14 '09 at 01:28

mob

117,087
18
149
283

score 3 · Answer 3 · answered Oct 14 '09 at 00:41

3

log₂n = ln n / ln 2

hence

log_2_64 = Math.log(64) / Math.log(2)

answered Oct 14 '09 at 00:41

user187291

53,363
19
95
127

score 0 · Answer 4 · answered Sep 10 '12 at 19:13

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

score -1 · Answer 5 · edited May 23 '17 at 12:11

-1

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

edited May 23 '17 at 12:11

Community

1
1

answered Oct 14 '09 at 02:08

pierrotlefou

39,805
37
135
175

(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 Sep 10 '12 at 19:17
It took several seconds on my computer for numbers like 10 million, which are reasonably small to appear in real world applications. – Lykos Sep 10 '12 at 19:40

How do I find the value of exponent in Ruby?

5 Answers5