CODEWITHSUNDEEP
rubymathfloating-accuracy
Kokizzu
Kokizzu

Reputation: 26888

Convert number to their log2

I need to convert number into their minimal log2 +1, but I have a problem, that in 32-bit Ruby, log2(8) = 2.9999999999999996

The input (pos) and output (level) should be:

1 -> 1
2-3 -> 2
4-7 -> 3
8-15 -> 4
16-31 -> 5
and so on..

My formula:

pos = 8 
level = ( Math.log(pos,2) + 1 ).to_i
# 3 (wrong) in 32-bit Ruby
# 4 (correct) in 64-bit Ruby

Is there more way to prevent this from happening or is there any other formula that convert pos to correct level as shown above?

Upvotes: 1

Views: 706

Answers (3)

Cary Swoveland
Cary Swoveland

Reputation: 110725

The maximum representable value with IEEE 754-2008 binary32 is (2−2**(−23)) × 2**127, so the base 2 log of a number stored in binary 32 is less than decimal 128. Since the round-off error is a small fraction of one, we can round to the nearest integer and see if 2 to that integer power equals the given number. If it does, return the integer power; else return nil, signifying that it is not a power of 2.

def log_2_if_integer(n)
  x = Math.log(n,2).round(0).to_i
  (2**x == n) ? x : nil
end

log_2_if_integer(4)   #=> 2
log_2_if_integer(512) #=> 9
log_2_if_integer(3)   #=> nil

In other words, because the log is less than 128, rounding error could not produce a value x such that 2**(x+m) == n for any (positive or negative) integer m != 0.

Upvotes: -1

Patrick Oscity
Patrick Oscity

Reputation: 54694

Here's another interesting way to compute the floored logarithm for integers:

0.upto(Float::INFINITY).find{|e| x - base**e < base }

Upvotes: 1

sawa
sawa

Reputation: 168179

pos = 8
level = 0
until pos < 2
  level += 1
  pos /= 2
end
level + 1 #=> 4

Upvotes: 2

Related Questions