Computing Ceil of Log2 in Rust

user_18363657 0
Viewed 285

I want to calculate the following in Rust:

Python Equivalent:

math.ceil(math.log(b+1, 2))

ceil(log_2 n+1)

I have tried:

a+1.log2() 
(a+1).log2()

but I get the error use of unstable library feature 'int_log'. I don't want to use an unstable library feature. What is the easiest way to calculate log2, without any external crates if possible?

rust
2 Answers

Rust is very particular about the difference between ints and floats. You can't just type a integer and expect it to be auto-casted automatically. Always add a . at the end for a float.

Seems like you attempted to call the function on a integer. Try this:

Try this:

(1.).log2().ceil()

or

(a as f32 + 1.).log2().ceil()

If you want the end result as a integer you can use as i32 at the end. If you want double precision floats replace f32 with f64.

Reference:

https://doc.rust-lang.org/std/primitive.f32.html#method.ceil

https://doc.rust-lang.org/std/primitive.f32.html#method.log2

user_63334440

If this is time-critical then you can use knowledge of the datatypes to make things fast.

If the input is a positive integer (let's say a u64), then log2(x) is almost the index of the last non-1 bit, which you can determine using u64::leading_zeros. In fact log2(x+1) is exactly the index of the last non-1 bit of x. This gives: (playground)

pub fn main() {
    for a in 0..10u64 {
        let v = (a as f32 + 1.).log2().ceil();
        let w = u64::BITS - a.leading_zeros();
        println!("{} {} {}", a, v, w);
    }
}

outputs

0 0 0
1 1 1
2 2 2
3 2 2
4 3 3
5 3 3
6 3 3
7 3 3
8 4 4
9 4 4

A little more care is needed to handle the sign-bit for signed numbers like i64.

If your number is a floating-point value, there are still some tricks you can play to make things fast, especially if you are willing not to handle NaN, Inf and denormalised numbers.

In particular, for f64 the bit pattern for "normal" numbers is 52 bits of "fraction", 11 bits of mantissa and 1 sign bit. Calling the 11 bits of mantissa e the value of the float is (sign)*(1+fraction/2^52)*2^(e-1023)

So log2(x) = log2(1+fraction/2^52) + (e-1023).

The e-1023 part is an integer, the rest as 0<=log2(1+fraction/2^52)<1, with zero when fraction==0. So ceil(log2(x)) = if fraction==0 {e-1023} else {e-1022}.

This gives us this:

pub fn main() {
    for a in -20..20i64 {
        let f = (a as f64)/4.0 + 1.0;
        let v = f.log2().ceil();
        let b: u64 = f.to_bits();
        let s = (b >> 63) & 1;
        let e = (b >> 52) & ((1<<11)-1);
        let frac = b & ((1<<52) -1);
        let z = if frac==0 { e as i64 - 1023 } else { e as i64 -1022 };
        println!("{:0.2} {:064b} : {:01b} {:011b} {:052b} {} {}", f, b, s, e, frac, z, v);
    }
}

which outputs (after trimming out the bit representations)

...
-0.75 ... -2 -2
-0.50 ... -1 -1
-0.25 ... 0 -0
 0.00 ... 0 0
 0.25 ... 1 1
 0.50 ... 1 1
 0.75 ... 1 1
 1.00 ... 1 1
 1.25 ... 2 2
 1.50 ... 2 2
 1.75 ... 2 2
 2.00 ... 2 2
...

Again, this only holds when 1+a is a normal number. You'll need to add conditionals to handle those if you need to. (And you should unless you're sure you don't need to).

Similar tricks can be used for u32 and f32 types.

user_2219550
Related